|converting precedence to productions email@example.com (1996-10-03)|
|Re: converting precedence to productions firstname.lastname@example.org (Brian Bliss) (1996-10-06)|
|Re: converting precedence to productions email@example.com (Neil Faiman) (1996-10-08)|
|Re: converting precedence to productions firstname.lastname@example.org (1996-10-10)|
|From:||email@example.com (Annika Aasa)|
|Date:||10 Oct 1996 11:01:34 -0400|
|Organization:||Chalmers University of Technology|
Mark Saaltink <firstname.lastname@example.org> 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 <email@example.com> 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 <firstname.lastname@example.org> 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: email@example.com S-412 96 Göteborg
Fax: +46 31 165655 Sweden
Return to the
Search the comp.compilers archives again.