Re: LR(n) parsers

Jim Shankland:
      As long as we're getting pedantic about "automata" (alert the
      media! there may be a hidden agenda!), let me point out that an
      ambiguous grammar is ambiguous regardless of the parsing technique
      used: there will be two distinct parses for at least one string in
      the language, regardless of amount of lookahead. So if it's
      ambiguous, it's always "ambiguous for any amount of lookahead".


As long as we're getting pedantic about ambiguous grammars, let me point
out that most computer languages are really context sensitive (e.g.
Pascal's fixed number of arguments to a function). So it's not
inconceivable that the language semantics may be used to resolve
ambiguities of the grammar.


For example, if you have a production that can yield an object of class
"function" or an object of class "inert data", you either have to be
prepared for either eventuality (essentially, putting some "parser code"
into the target language) or you may be able to resolve it right then and
there...


Assuming that there is enough information available for the language
semantics to resolve the object class at compile time, you might even be
able to use this sort of resolution technique with yacc. (Put a layer
between lex and yacc, so that the yacc code can spit out multiple
"psuedo-terminals" -- with their gramatical class resolved -- into the
input stack.)


Finally, if you've gone to this trouble, you can also use yacc to parse
LR(n) grammars -- just include in each production the look-ahead. Then
when yacc hits a "pattern with explicit lookahead" you spit the lookahead
stuff back into the input stack. [But I think that if you have to go to
this kind of trouble it's probably easier to just use a hand-built
parser.]
--
Raul Deluth Miller-Rockwell
<rockwell@socrates.umd.edu>
--

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