10 Oct 1996 11:01:34 -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: | annika@cs.chalmers.se (Annika Aasa) |

Newsgroups: | comp.compilers |

Date: | 10 Oct 1996 11:01:34 -0400 |

Organization: | Chalmers University of Technology |

References: | 96-10-014 96-10-023 |

Keywords: | parse |

Mark Saaltink <mark@ora.on.ca> asked for:

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

Brian Bliss <brianb@microware.com> replied:

*> S ::= S1 | S post*

*>*

*> S1 ::= S2 | S1 post | S1 or S2*

*>*

*> S2 ::= S3 | S2 post | S2 and S3*

*>*

*> S3 ::= n | ( S )*

Unfortunately, this grammar is ambiguous. The sentence "n or n post"

could be parsed either as "(n or n) post" or "n or (n post)", where

the former is what is desired.

Neil Faiman <faiman@zko.dec.com> also replied:

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

The nonterminal S-post is not defined, but I guess that it should be:

S-post ::= S 'post'

With this addition, you will also get an ambiguous grammar. Consider

the sentence "n or n post and n". It can be parsed as:

"((n or n) post) and n"

which is desired, but it can also be parsed as:

"n or ((n post) and n)"

which is wrong according to the precedence rules.

Here is a new grammar which (I hope ;-) is unambiguous and correctly

reflects the precedences:

S ::= E21

E21 ::= E20 or E10 | E11

E20 ::= E20 or E10 | E10

E11 ::= E10 and E00 | E01

E10 ::= E10 and E00 | E00

E01 ::= n | ( S ) | S post

E00 ::= n | ( S )

This grammar was derived using an algorithm described in my thesis:

"User Defined Syntax". The algorithm will transform a grammar with

prefix, postfix and infix operators of different precedences, to an

unambiguous grammar reflecting the precedences. A proof of the

algorithm can also be found in the thesis.

The algorithm was published in PLILP'91, with the title: "Precedences

in Specifications and Implementations of Programming Languages". An

extended version appeared in Theoretical Computer Science, vol. 142, 1995.

You can get these, and some related papers, off my homepage:

URL: http://www.cs.chalmers.se/~annika/

-- Annika Aasa

--

Annika Aasa Chalmers University of Technology

Phone: +46 31 7721051 Department of Computer Sciences

Email: annika@cs.chalmers.se S-412 96 Göteborg

Fax: +46 31 165655 Sweden

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.