Parsing with infinite lookahead

Stephen J Bevan <bevan@cs.man.ac.uk>
Thu, 24 Feb 1994 11:08:15 GMT

          From comp.compilers
Related articles
Parsing with infinite lookahead Matt_Timmermans@msl.isis.org (Matt Timmermans/MSL) (1994-02-22)
Re: Parsing with infinite lookahead jos@and.nl (1994-02-24)
Parsing with infinite lookahead bevan@cs.man.ac.uk (Stephen J Bevan) (1994-02-24)
Re: Parsing with infinite lookahead dwohlfor@cs.uoregon.edu (1994-02-24)
Re: Parsing with infinite lookahead parrt@s1.arc.umn.edu (Terence Parr) (1994-02-25)
Re: Parsing with infinite lookahead corbett@lupa.Eng.Sun.COM (1994-02-26)
Re: Parsing with infinite lookahead nandu@cs.clemson.edu (1994-02-27)
Re: Parsing with infinite lookahead hbaker@netcom.com (1994-02-28)
Re: Parsing with infinite lookahead hbaker@netcom.com (1994-03-01)
[2 later articles]
| List of all articles for this month |
Newsgroups: comp.compilers
From: Stephen J Bevan <bevan@cs.man.ac.uk>
Keywords: parse, theory, bibliography
Organization: Compilers Central
References: 94-02-174
Date: Thu, 24 Feb 1994 11:08:15 GMT

Matt Timmermans/MSL <Matt_Timmermans@msl.isis.org> asks:
  If not, does anyone know of a deterministic method for determining whether or
    not a context-free grammar is ambiguous?


>From [DeRemer:cc:1974,pp46] :-


  Another condition that can easily be checked is the existence of an
  ambiguity due to some nonterminal being both left and right
  recursive. However, it is to be noted that this is a special case.
  In general, the question of ambiguity in context-free grammars is
  undecidable [Floyd:cacm:1962].




@inbook
{ DeRemer:cc:1974a
, author= "Franklin L. DeRemer"
, title= "Review of Formalisms and Notation"
, crossref= "cc:1974"
, pages= "37--56"
, checked= 19940222
}






@book
{ cc:1974
, author= "F. L. Bauer (editor)"
, title= "Compiler Construction -- An Advanced Course"
, series= lncs
, volume= 21
}






@article
{ Floyd:cacm:1962
, author= "R. W. Floyd"
, title= "On ambiguity in phrase-structure languages"
, journal= cacm
, volume= 5
, year= 1962
}
--

Post a followup to this message

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