Re: converting precedence to productions (Annika Aasa)
10 Oct 1996 11:01:34 -0400

          From comp.compilers

Related articles
converting precedence to productions (1996-10-03)
Re: converting precedence to productions (Brian Bliss) (1996-10-06)
Re: converting precedence to productions (Neil Faiman) (1996-10-08)
Re: converting precedence to productions (1996-10-10)
| List of all articles for this month |

From: (Annika Aasa)
Newsgroups: comp.compilers
Date: 10 Oct 1996 11:01:34 -0400
Organization: Chalmers University of Technology
References: 96-10-014 96-10-023
Keywords: parse

Mark Saaltink <> asked for:

> The grammar looks something like this:
> S ::= n | S and S | S or S | S post | ( S )
> with left associativity, and precedence decreasing to the left.

Brian Bliss <> replied:

> S ::= S1 | S post
> S1 ::= S2 | S1 post | S1 or S2
> S2 ::= S3 | S2 post | S2 and S3
> S3 ::= n | ( S )

Unfortunately, this grammar is ambiguous. The sentence "n or n post"
could be parsed either as "(n or n) post" or "n or (n post)", where
the former is what is desired.

Neil Faiman <> also replied:

> S ::= S-or | S 'post'
> S-or ::= S-and | S-or 'or' S-and | S-post 'or' S-and
> S-and ::= S-prim | S-and 'and' S-prim | S-post 'and' S-prim
> S-prim ::= 'n' | '(' S ')'

The nonterminal S-post is not defined, but I guess that it should be:

S-post ::= S 'post'

With this addition, you will also get an ambiguous grammar. Consider
the sentence "n or n post and n". It can be parsed as:

"((n or n) post) and n"

which is desired, but it can also be parsed as:

"n or ((n post) and n)"

which is wrong according to the precedence rules.

Here is a new grammar which (I hope ;-) is unambiguous and correctly
reflects the precedences:

S ::= E21
E21 ::= E20 or E10 | E11
E20 ::= E20 or E10 | E10
E11 ::= E10 and E00 | E01
E10 ::= E10 and E00 | E00
E01 ::= n | ( S ) | S post
E00 ::= n | ( S )

This grammar was derived using an algorithm described in my thesis:
"User Defined Syntax". The algorithm will transform a grammar with
prefix, postfix and infix operators of different precedences, to an
unambiguous grammar reflecting the precedences. A proof of the
algorithm can also be found in the thesis.

The algorithm was published in PLILP'91, with the title: "Precedences
in Specifications and Implementations of Programming Languages". An
extended version appeared in Theoretical Computer Science, vol. 142, 1995.

You can get these, and some related papers, off my homepage:


      -- Annika Aasa
Annika Aasa Chalmers University of Technology
Phone: +46 31 7721051 Department of Computer Sciences
Email: S-412 96 Göteborg
Fax: +46 31 165655 Sweden

Post a followup to this message

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