by Gene <gene.ressler@[EMAIL PROTECTED]
>
Feb 28, 2008 at 05:54 PM
On Feb 28, 12:05 am, imissfloppydi...@[EMAIL PROTECTED]
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.
