Re: converting precedence to productions

Mark Saaltink <mark@ora.on.ca> 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 <brianb@microware.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 <faiman@zko.dec.com> 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:


URL: http://www.cs.chalmers.se/~annika/


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

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