Re: Parsing with infinite lookahead

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

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