Mon, 30 Aug 1993 19:50:52 GMT

Related articles |
---|

Opeartor-precedence v.s. LL(1) ejxue@ntu.ac.sg (1993-08-28) |

Re: Operator-precedence v.s. LL(1) tfj@apusapus.demon.co.uk (1993-08-29) |

Re: Operator-precedence v.s. LL(1) bart@majestix.cs.uoregon.edu (1993-08-30) |

Re: Operator-precedence v.s. LL(1) spencer@cwis.unomaha.edu (1993-09-07) |

Re: Operator-precedence v.s. LL(1) dww@cli.com (1993-09-07) |

Newsgroups: | comp.compilers |

From: | bart@majestix.cs.uoregon.edu (Barton Christopher Massey) |

Keywords: | parse, LL(1) |

Organization: | University of Oregon Computer and Information Sciences Dept. |

References: | 93-08-111 |

Date: | Mon, 30 Aug 1993 19:50:52 GMT |

ejxue@ntu.ac.sg (Xue JingLing) writes:

*> (1) operator-precedence can parse*

*> both left-recursive and/or ambiguous grammars while LL(1)*

*> cannot, (2) LL(1) can parse grammars that have two adjacent*

*> nonterminals at production right sides while the*

*> operator-precedence cannot.*

*> (1) What is the precise relationship between the two?*

*> (2) Is there a language that can be parsed by one but not the*

*> other?*

*> [The answer to (2) is clearly yes, since you've given examples. -John]*

Unless I misunderstand something badly, it's like this:

There are languages which may be described by LL(1) grammars

but not operator-precedence grammars (per your example above).

However, for any language described by an operator-precedence

grammar one may easily construct an LL(1) grammar describing

the same language. (For what amounts to a proof of this, see

the Red Dragon book.)

I suspect this is why operator-precedence grammars get such

short shrift in textbooks.

P.S. -- What's the right word for the relationship between a

grammar and its language? "parse"? "generate"? "derive"? I

use "describe", but it would be nice if the world could agree on

a terminology. I have found that the confusion between classes

of grammars and classes of languages is endemic among novices

such as myself, and a stricter terminology might help the

problem...

Bart Massey

bart@cs.uoregon.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.