Expression parser grammar and left-associativity

Question

I have been trying create my parser for expression with variables and simplify them to quadratic expression form.

This is my parser grammar:

Exercise : Expr '=' Expr
Expr : Term [+-] Expr | Term
Term : Factor [*/] Term | Factor
Factor: Atom [^] Factor | Atom
Atom: Number | Identified | [- sqrt] Atom | '(' Expr ')'

For parsing I'm using recursive descent parser. Let's say I'd like to parse this:

" 2 - 1 + 1 = 0"

and the result is 0, parser creates wrong tree:

  -
 / \
2   +
   / \
  1   1

How can I make this grammar left-associative? I'm newbie at this, please can you advice me source where I can find more information? Can I achieve this with recursive descent parser?

Selwyn

Answer 1

Take a look at Parsing Expressions by Recursive Descent by Theodore Norvell

There he gives three ways to solve the problem.
1. The shunting yard algorithm.
2. Classic solution by factoring the grammar.
3. Precedence climbing

Your problem stems from the fact that your grammar needs several changes, one example being

Exrp: Term { [+-] Expr} | Term

notice the addition of the { } around [+-] Expr indicating that they should be parsed together and that there can 0 or more of them.

Also by default you are building the tree as

  -
 / \
2   +
   / \
  1   1

i.e. -(2,+(1,1))

when you should be building the tree for left associative operators of the same precedence as

     +
    / \
   -   1
  / \
 2   1

i.e. +(-(2,1),1)

Since there are three ways to do this in the paper I won't expand on them here. Also you mention that you are new to this so you should get a good compiler book to understand the details of you will encounter reading the paper. Most of these methods are implemented in common programming languages and available free on the internet, but be aware that many people do what you do and post wrong results.

The best way to check if you have it right is with a test like this using a multiple sequence of subtraction operations:

7-3-2 = 2

if you get

7-3-2 = 6 or something else

then it is wrong.

Szymanowski

Can you share with me any good example? I have done implementation this in Haskell. According this tutorial fpcomplete.com/school/starting-with-haskell/basics-of-haskell/…, author mentioned the grammar is wrong, but I thought I fixed it by precedence. I need to implement left associativity for plus, minus, mult, divide and right associativity for power, minus and sqrt. I need some example in any programming language. – Selwyn

@Apalala Nice catch. – Szymanowski