Re: converting precedence to productions

Neil Faiman <faiman@zko.dec.com>
8 Oct 1996 00:13:35 -0400

          From comp.compilers

Related articles
converting precedence to productions mark@ora.on.ca (1996-10-03)
Re: converting precedence to productions brianb@microware.com (Brian Bliss) (1996-10-06)
Re: converting precedence to productions faiman@zko.dec.com (Neil Faiman) (1996-10-08)
Re: converting precedence to productions annika@cs.chalmers.se (1996-10-10)
| List of all articles for this month |

From: Neil Faiman <faiman@zko.dec.com>
Newsgroups: comp.compilers
Date: 8 Oct 1996 00:13:35 -0400
Organization: Digital Equipment Corporation
References: 96-10-014
Keywords: parse, question

Mark Saaltink has a language with a postfix operator with *lower* precedence
than any binary operator, and is having trouble writing a grammar for it. In
particular:


> 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.
>
> Clearly, "A and B or C" must be parsed as "(A and B) or C".
>
> It is less clear how "A or B post and C" should be parsed; it might
> reasonably be "((A or B) post) and C" or "A or ((B post) and C)".
> Assuming the former is intended, how can this grammar be transformed to
> an unambiguous grammar without precedence rules?


The problem isn't too surprising. Since the 'post' operator binds everything
to its left, "A post or B" is not the same as "B or A post" -- i.e., the
or and and operators are not syntactically commutative, even if they are
semantically commutative. So, postfix expressions can occur on the left side
of binary operators, but not on the right side:


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 ')'


-Neil Faiman
GEM project, Digital Equipment Corporation
--


Post a followup to this message

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