Re: converting precedence to productions

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

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