Re: Grammar -> Parser question

Chris writes:


>Suppose I have the following Grammar:


>condition -> expr PLUS expr |
> LPAREN condition RPAREN
>
>expr -> ID |
> LPAREN expr RPAREN


>I want to hand-code a top down recursive descent parser for this grammar
>using ideas from the Dragon Book (nonterminals become functions, terminals
>become calls to match()). I can't use lex or yacc.


>However, the LPAREN symbol is causing a problem: When I see it, I don't
>know if I'm dealing with a nested condition or a nested expression.


This example AFAICS can't be hadled by finite nfolding and left
factoring alone, which is otherwise often the case with similar
examples. In cases such as the above, a typical solution is to make a
nonterminal that recognizes (a superset of) the union of expr and
condition and then filter out the bad ones by using attributes.


The combined nonterminal has the productions


conexp -> ID
| conexp PLUS expr
                  | LPAREN conexp RPAREN


Ee eliminate the left recursion in the usual way:


conexp -> ID conexp'
                  | LPAREN conexp RPAREN conexp'


conexp' -> PLUS expr conexp'
                  | \epsilon




We then use a synthesized attribute which tells us if the result is a
condition or an expr. Using notation similar to the Dragon Book, we
can write the attributed grammar as


conexp -> ID conexp' { conexp.isexpr := conexp'.isempty }


conexp -> LPAREN conexp1 RPAREN conexp'
{ if conexp1.isexpr
then conexp.isexpr := conexp'.isempty
else if conexp'.isempty
then conexp.isexpr := false
else error }


conexp' -> PLUS expr conexp'1
{ conexp'.isempty := false }


conexp' -> \epsilon { conexp'.isempty := true }




Torben Mogensen (torbenm@diku.dk)




--

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