Re: Operator-precedence v.s. LL(1) (Barton Christopher Massey)
Mon, 30 Aug 1993 19:50:52 GMT

          From comp.compilers

Related articles
Opeartor-precedence v.s. LL(1) (1993-08-28)
Re: Operator-precedence v.s. LL(1) (1993-08-29)
Re: Operator-precedence v.s. LL(1) (1993-08-30)
Re: Operator-precedence v.s. LL(1) (1993-09-07)
Re: Operator-precedence v.s. LL(1) (1993-09-07)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (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 (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

Bart Massey

Post a followup to this message

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