Re: Parsing with infinite lookahead

mareb@cis0.levels.unisa.edu.au (Bob Buckley)
Thu, 24 Mar 1994 23:23:40 GMT

          From comp.compilers

Related articles
[4 earlier articles]
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: mareb@cis0.levels.unisa.edu.au (Bob Buckley)
Keywords: parse, theory
Organization: Compilers Central
References: 94-02-174
Date: Thu, 24 Mar 1994 23:23:40 GMT

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


Post a followup to this message

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