Re: Backtracking yacc

The moderator wrote:
>[...Besides, isn't there a theorem that says that
>any LR(k) grammar can be rewritten as LR(1)? -John]


bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage) writes:
> The way I understand it is that any LR(k) _language_ can be rewritten as
> LR(1) and, in fact, if you introduce a nonterminal representing the end of
> input (which can be shifted), can also be written as LR(0). The trouble is
> that the grammar may not represent the true structure of the language.


What is meant here by "the true structure of the language"? John's dictum
that you can "rewrite" an LR(k) grammar as LL(1) is also a bit vague.
There is a theorem that says that there exists for any LR(k) grammar an
LR(1) gramar that is a right-to-right cover of the original. Furthermore,
for any LR(1) grammar, there is an SLR(1) grammar which is a
right-to-right cover for it.


If grammar A right to right covers grammar B, a right parser for each will
produce the same sequence of parse traces as a right parser for the other.


Doesn't this mean that, in making the transformation the "true structure
of the language" is preserved?


|> Compare, for example, parsing mathematical expressions with an LL parser.
|> The language is LL, sure, but the correct precedences and the possibility
|> of left recursion cannot be resolved without using some other method.


Here you are on firmer ground. Providing left covers for right grammars is
much harder, and not always possible.




Why not use all this to write grammars any old LR(k)-how, and then
transform them? Basically, because it's not worth the bother, at least
most of the time. LALR(1) is powerful enough for most purposes. (In fact I
am more taken with LL(1), for reasons I won't go into here.)
--
# Andrew Dunstan
# Department of Computer Science
# University of Adelaide
# South Australia
# net: andrewd@cs.adelaide.edu.au
--

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