Re: converting precedence to productions

Brian Bliss <>
6 Oct 1996 00:56:18 -0400

          From comp.compilers

Related articles
converting precedence to productions (1996-10-03)
Re: converting precedence to productions (Brian Bliss) (1996-10-06)
Re: converting precedence to productions (Neil Faiman) (1996-10-08)
Re: converting precedence to productions (1996-10-10)
| List of all articles for this month |

From: Brian Bliss <>
Newsgroups: comp.compilers
Date: 6 Oct 1996 00:56:18 -0400
Organization: Microware Systems
References: 96-10-014
Keywords: parse

Mark Saaltink wrote:
> I am trying to convert an operator precedence grammar to an
> unambiguous grammar without precedence rules. This is usually easy
> (e.g. expressions with normal precedence rules), but my grammar has a
> low-precedence postfix operator.
> 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.

    S ::= S1 | S post

    S1 ::= S2 | S1 post | S1 or S2

    S2 ::= S3 | S2 post | S2 and S3

    S3 ::= n | ( S )

you could also try drawing out the lalr parser tables and break the
appropriate shift arcs according to the precedence rules. there exists
an algorithm for converting any DPDA to a lr(0) grammar, albeit ugly.
the result, however, is a much smaller parser than the first approach.


Post a followup to this message

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