Re: Noob parser question

Gene <gene.ressler@gmail.com>
Thu, 28 Feb 2008 17:54:43 -0800 (PST)

          From comp.compilers
Related articles
Noob parser question imissfloppydisks@gmail.com (2008-02-27)
Re: Noob parser question DrDiettrich1@aol.com (Hans-Peter Diettrich) (2008-02-28)
Re: Noob parser question max@gustavus.edu (Max Hailperin) (2008-02-28)
Re: Noob parser question gene.ressler@gmail.com (Gene) (2008-02-28)
Re: Noob parser question imissfloppydisks@gmail.com (2008-02-28)
| List of all articles for this month |
From: Gene <gene.ressler@gmail.com>
Newsgroups: comp.compilers
Date: Thu, 28 Feb 2008 17:54:43 -0800 (PST)
Organization: Compilers Central
References: 08-02-094
Keywords: parse
Posted-Date: 29 Feb 2008 01:21:38 EST

On Feb 28, 12:05 am, imissfloppydi...@gmail.com wrote:
> This is a CFG listed in the Aho (dragon) compiler text:
>
> expr -> expr + term | expr - term | term
> term -> term * factor | term / factor | factor
> factor -> digit | (expr)
> digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
>
> It is intended to parse simple arithmetic expressions taking into
> account the precedence of operators. What I don't understand is why
> you parse the operators with lower precedence first. I have worked
> through several examples by hand and it works but I don't understand
> why it works. Perhaps I should be content with that but I am a
> perfectionist.


Here's rough intuition.


Think about the parse tree you want to finish with when parsing, say a
* b + c * d. The expr should have a + node at the top of the tree,
with equal or higher precedence operations (in this case *) or else
terminals as the operands. To get the + at the top, it must be in the
production for expr itself. The higher precedence operators are
"lower" in the grammar.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.