Re: Parsing with infinite lookahead

jos@and.nl (Jos Horsmeier)
Thu, 24 Feb 1994 10:08:21 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)
[3 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: jos@and.nl (Jos Horsmeier)
X-Organization: AND Software bv Westersingel 108 3015 LD Rotterdam The Netherlands
Keywords: parse, theory
Organization: AND Software B.V., Rotterdam
X-Fax: +31 (10) 436 7110 Thu, 24 Feb 94 11:08:24 +0100
References: 94-02-174
Date: Thu, 24 Feb 1994 10:08:21 GMT
X-Phone: +31 (10) 436 7100

Matt Timmermans/MSL <Matt_Timmermans@msl.isis.org> writes:
|Does anyone know of a deterministic method for parsing any unambiguous
|context-free 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 context-free 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
|context-free 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
--


Post a followup to this message

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