Geek Answers Handbook

Parsing grammar expression and left-associativity

I am trying to create my own parser for an expression with variables and simplify them to a quadratic form of expression.

This is my parsing 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 use a recursive parser. Say I would like to analyze this:

"2 - 1 + 1 = 0"

and the result is 0, the parser creates the wrong tree:

  - / \ 2 + / \ 1 1

How can I make this grammar left associative? I am new to this, please can you advise me a source where I can find additional information? Can I achieve this with a recursive descent parser?

+7
parsing grammar recursive-descent associativity left-recursion
source share
1 answer

Take a look at Theodore Norwell's recursive descent parsing

There he gives three ways to solve the problem.
1. The algorithm of the shunting yard.
2. A classic solution by factoring grammar.
3. Climbing priorities

Your problem is that your grammar requires several changes, for example,

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

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

Also by default you build the tree as

  - / \ 2 + / \ 1 1

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

when you have to build a tree for left associative operators with the same priority as

  + / \ - 1 / \ 2 1

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

Since there are three ways to do this in a document, I will not disclose them here. Also, you mentioned that you are new to this, so you should get a good compiler book to understand the details that you will encounter when reading an article. Most of these methods are implemented in common programming languages ​​and are available free of charge on the Internet, but keep in mind that many people do what you do and publish the wrong results.

The best way to check if you have this right, with the same test, using a multiple sequence of subtraction operations:

7-3-2 = 2

if you get

7-3-2 = 6 or something else

then this is wrong.

+8
source share

More articles:


All Articles