8 Oct 1996 00:13:35 -0400

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

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.