Re: LR(n) parsers

Raul Deluth Miller-Rockwell <rockwell@socrates.umd.edu>
Sat, 19 Oct 91 12:28:30 edt

          From comp.compilers

Related articles
[3 earlier articles]
Re: LR(n) parsers sra@ecs.soton.ac.uk (1991-10-14)
Re: LR(n) parsers anw@maths.nott.ac.uk (1991-10-14)
Re: LR(n) parsers bburshte@pyrps5.eng.pyramid.com (1991-10-14)
Re: LR(n) parsers mareb@levels.unisa.edu.au (1991-10-15)
Re: LR(n) parsers nickh@harlqn.co.uk (Nick Haines) (1991-10-16)
Re: LR(n) parsers mtxinu!angular!jas@uunet.uu.net (1991-10-18)
Re: LR(n) parsers rockwell@socrates.umd.edu (Raul Deluth Miller-Rockwell) (1991-10-19)
Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-19)
Re: LR(n) parsers drw@riesz.mit.edu (1991-10-22)
Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-24)
Re: LR(n) parsers sankar@Neon.Stanford.EDU (Sriram Sankar) (1991-10-24)
Re: LR(n) parsers ge@sci.kun.nl (1991-10-25)
Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-25)
[1 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: Raul Deluth Miller-Rockwell <rockwell@socrates.umd.edu>
Keywords: parse
Organization: Compilers Central
References: 91-10-036 91-10-076
Date: Sat, 19 Oct 91 12:28:30 edt

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


Post a followup to this message

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