Re: Backtracking yacc

> Gary Merrill <sasghm@unx.sas.com> writes:
>[context hacks can all be in the lexer]


ipser@solomon.technet.sg (Ed Ipser) writes:
| With all due respect, this is not correct. Throwing the problem to the
| lexical analyzer presupposes that the conlfict involves a lexeme; this, of
| course, is not the general case.


sasghm@unx.sas.com (Gary Merrill) writes:
>Can't any conflict ultimately be seen as involving a lexeme?


This is true in the same sense that any LR(k) grammar can be rewritten as
LR(1) (or LL(1)). The key word in your statement is: "ultimately", and
therein lies the rub.


Consider the following grammar fragment:


    ...
    a IS b c ? ;
    c IS d e ;
    e IS f g ;
    g IS h i ;
    ...
    x IS y z identifier ;
    ...


Now you want the a production to be conditional. Pushing the decision from
the a production down to the x production would introduce a host of
problems (all of which are solvable through various kludges). For example,
the decision in a can depend on attributes of b and c or side effects of
the intervening productions. To move the decision would require moving all
of these computations into that decision filter.


Worse, you will have to pervert your grammar. All of the intervening
nonterminal/productions must be split into two classes (and imagine when
two or more such lexical tests collide). Messy!


There is a second problem. When the decision is made from the parser, it
has the advantage of the lookahead from the lexer but when the decision is
made from the lexer no such lookahead is available. Again, you can kludge
a lookahead (indeed, you could parse and restore the entire file) but,
again, a mess.


You are correct in the theory but I think that in practice, there is an
enormous difference between making these decisions in the lexer and in the
parser. Maybe the difference is "only" practical but it is a difference of
significance, in practice.


>(I have, by the way, looked at the literature on LADE and it appears to be
>an impressive product. I hope you guys find enough of a market for it to
>keep you going.)


LADE seems to be far more popular in Europe than in the U.S. I wish someone
would tell me why.
--

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