Re: Grammar -> Parser question

Torben Mogensen <>
9 Jun 1998 11:59:44 -0400

          From comp.compilers

Related articles
Grammar -> Parser question (1998-06-04)
Re: Grammar -> Parser question (Torbjorn Drevin) (1998-06-09)
Re: Grammar -> Parser question (Torben Mogensen) (1998-06-09)
Re: Grammar -> Parser question (1998-06-09)
Re: Grammar -> Parser question (Quinn Tyler Jackson) (1998-06-09)
Re: Grammar -> Parser question (Quinn Tyler Jackson) (1998-06-18)
| List of all articles for this month |

From: Torben Mogensen <>
Newsgroups: comp.compilers
Date: 9 Jun 1998 11:59:44 -0400
Organization: Compilers Central
References: 98-06-018 98-06-029
Keywords: parse, LL(1)

Chris writes:

>Suppose I have the following Grammar:

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

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


Post a followup to this message

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