Re: Operator-precedence v.s. LL(1)

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

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