Re: simple syntax analysis

"Joachim Durchholz" <>
27 May 2002 21:08:44 -0400

          From comp.compilers

Related articles
simple syntax analysis (Julia Donawald) (2002-05-27)
Re: simple syntax analysis (Joachim Durchholz) (2002-05-27)
Re: simple syntax analysis (Andreas Gieriet) (2002-05-31)
Re: simple syntax analysis (Walter Misar) (2002-06-07)
| List of all articles for this month |

From: "Joachim Durchholz" <>
Newsgroups: comp.compilers
Date: 27 May 2002 21:08:44 -0400
Organization: Compilers Central
References: 02-05-140
Keywords: parse
Posted-Date: 27 May 2002 21:08:43 EDT

Julia Donawald wrote:
> Hi,
> I have written the following pseudo-code to built up a parse tree of the
> following sequence: [A] [OR] [B] [AND] [C]. I read in some books about that
> theme and create the following grammar:
> expr := factor | factor OR expr | factor AND expr
> factor:= letter | (expr)

This grammar is ambiguous. Since you have a clear preference which of
the various possible parse trees is the one you want, the grammar
doesn't reflect your intentions: you need priorities.

Since you're hand-crafting the parser, the easy way out (just adding
operator precedence specifications to the grammar) won't work. So a
grammar rewrite is in order:

      expr ::= expr1 | expr OR expr1
      expr1 ::= expr2 | expr1 AND expr2
      expr2 ::= letter | ( expr )

Note that you can control associativity by reversing the operands around
OR and AND, e.g. to get a right-associative OR, write "expr1 OR expr".
To get a nonassociative operator, write "expr1 OR expr1" (not very
useful for OR and AND, but could be helpful for "<" since that prevents
constructions like "a < b < c", which make sense but are difficult to
persuade into doing the right thing during parsing).


Post a followup to this message

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