|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:||Neil Faiman <email@example.com>|
|Date:||8 Oct 1996 00:13:35 -0400|
|Organization:||Digital Equipment Corporation|
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
> 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 ')'
GEM project, Digital Equipment Corporation
Return to the
Search the comp.compilers archives again.