Re: Noob parser question

imissfloppydisks@gmail.com writes:


> 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.


I think the following might help you think about it. Let's start by
defining the word "bare" to mean "not enclosed in parentheses." Now,
by looking at the grammar, you ought to be able to convince yourself
of the following facts:


(1) A factor does not include any bare operators.


(2) A term does not include any bare + or - operators.


Most of my students when they think about the grammar and these facts
find them relatively convincing, though to actually prove fact (2)
would require the principle of mathematical induction. That's because
in a production like


term -> term * factor


you can't tell that the term on the left of the arrow doesn't include
a bare + or - without somehow knowing (inductively assuming) that the
term on the right of the arrow doesn't include a bare + or -. I think
what happens is that students are essentially implying the induction
principle at an intuitive level.


Anyhow, once you've got those two facts, then the precedence and
associativity follows. For example, returning to


term -> term * factor


we can see that neither the left nor the right operand of the * can
contain a bare + or -, which tells us that * binds more tightly than +
or - does. And, because the right operand cannot contain even a bare
* or /, we know that these operations are left-associative.

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