Related articles 

Parsing with infinite lookahead Matt_Timmermans@msl.isis.org (Matt Timmermans/MSL) (19940222) 
Re: Parsing with infinite lookahead jos@and.nl (19940224) 
Parsing with infinite lookahead bevan@cs.man.ac.uk (Stephen J Bevan) (19940224) 
Re: Parsing with infinite lookahead dwohlfor@cs.uoregon.edu (19940224) 
Re: Parsing with infinite lookahead parrt@s1.arc.umn.edu (Terence Parr) (19940225) 
Re: Parsing with infinite lookahead corbett@lupa.Eng.Sun.COM (19940226) 
Re: Parsing with infinite lookahead nandu@cs.clemson.edu (19940227) 
Re: Parsing with infinite lookahead hbaker@netcom.com (19940228) 
[3 later articles] 
Newsgroups:  comp.compilers 
From:  jos@and.nl (Jos Horsmeier) 
XOrganization:  AND Software bv Westersingel 108 3015 LD Rotterdam The Netherlands 
Keywords:  parse, theory 
Organization:  AND Software B.V., Rotterdam 
XFax:  +31 (10) 436 7110 Thu, 24 Feb 94 11:08:24 +0100 
References:  9402174 
Date:  Thu, 24 Feb 1994 10:08:21 GMT 
XPhone:  +31 (10) 436 7100 
Matt Timmermans/MSL <Matt_Timmermans@msl.isis.org> writes:
Does anyone know of a deterministic method for parsing any unambiguous
contextfree grammar  including those that require infinite lookahead?

For example:

S: A a  B b
A: c  A c
B: c  B c
Try to find the book `Theory of context free languages' by Arbib, Kfouri
and Moll. If memory serves me right, this book was published by Springer
Verlag. I'm sorry I don't have this book on my desk now, so I can't give
you an ISBN number now. One of the chapters gives an excellent
explanation on parsing any unambiguous grammar in O(n^2) time.
BTW, your example grammar needs some rewriting if you want to parse it
with a LL(1) parser (left recursion elimination) or a LALR(1) parser
(reduce/reduce conflict).
If not, does anyone know of a deterministic method for determining whether or
not a contextfree grammar is ambiguous?
This is an undecidable problem. As sketch of a proof runs as follows:
Let PCP = { v_i, w_i  i = [1..n] } be a Post correspondence problem.
Construct a grammar G as follows:
S : v_i S i for i in [1..n]
 w_i S i
;
S : v_i i for i in [1..n]
 w_i i
;
G is ambiguous iff the embedded PCP has a solution.
Also, does anyone know for certain whether or not the language of any
contextfree grammar can be recognized by a 1DPDA. If so, how is the
corresponding PDA constructed?
My desk is a mess right now, I can't find anything ... but here's
another reference:
The design and analysis of algorithms
Aho, Hopcroft and Ulmann.
A thorough discussion on DPDAs and NPDAs can be found in chapter 9.
kind regards,
Jos aka jos@and.nl

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