Re: Parsing with infinite lookahead

bromage@mundil.cs.mu.OZ.AU (Andrew James BROMAGE)
Wed, 2 Mar 1994 05:11:06 GMT

          From comp.compilers
Related articles
[3 earlier articles]
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)
Re: Parsing with infinite lookahead bromage@mundil.cs.mu.OZ.AU (1994-03-02)
Re: Parsing with infinite lookahead mareb@cis0.levels.unisa.edu.au (1994-03-24)
| List of all articles for this month |
Newsgroups: comp.compilers
From: bromage@mundil.cs.mu.OZ.AU (Andrew James BROMAGE)
Keywords: parse, theory
Organization: Computer Science, University of Melbourne, Australia
References: 94-02-174
Date: Wed, 2 Mar 1994 05:11:06 GMT

Matt Timmermans/MSL <Matt_Timmermans@msl.isis.org> writes:

>If not, does anyone know of a deterministic method for determining whether or
>not a context-free grammar is ambiguous?

It can't. See Sudkamp, "Languages and Machines" for a proof that an algorithm
which detects ambiguity in a CFG can be used to solve the post-correspondence
problem, and hence the halting problem.

Cheers,
Andrew Bromage
--

Post a followup to this message

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