Re: Parsing with infinite lookahead

>From Matt Timmermans/MSL ...


I find it hard to imagine a deterministic parser based on the grammar


S: aSa | a


yet this is an unambiguous grammar and the language described is a regular
language.


Ullman and friend (Hopcoft?, A-W 1979?), in a well known text (on my other
desk) discuss decidability problems for context free grammars, etc.


The same book contains results showing the existence of inherently
ambiguous languages which consequently can't be recognised by a 1DPDA (if
you mean a Deterministic PDA).


I do know of a method for parsing all LR(1) and some non-LR(k) grammars
with a parser very similar to the LR Parser. Like LR Parsing, it is O(N)
and the parse tables are very similar to LR (or LALR(1)) parse tables. It
is a simple generalisation of the LR Parsing technique. As yet I don't
know the full power of this parser. It can use `infinite' look-ahead to
resolve LR conflicts and is quite practical. It is described in several
places (and more widely accessible soon, I hope):


%A Bob Buckley
%T Relaxing a right-most first restriction
%J Australian Comp. Sci. Comms.
%V 9
%N 1
%D 1987
%P 304-312


%A Bob Buckley
%T Three techniques for parsing a context sensitive language
%D 1993
%I School of Computer and Information Science, University of South Australia
%R CIS-93-004


regards
b++
_______________________________________________________________________
Bob Buckley Phone: +61 8 302 3465
School of Computer and Information Science Fax: +61 8 302 3381
University of South Australia, The Levels,
Pooraka, SA 5095, Australia email: Bob.Buckley@UniSA.edu.au
--

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