Re: LR(k)-Parser wanted

Bob Buckley <>
Thu, 11 May 1995 22:46:28 GMT

          From comp.compilers

Related articles
LR(k)-Parser wanted (1995-04-21)
Re: LR(k)-Parser wanted (1995-04-29)
Re: LR(k)-Parser wanted (1995-04-25)
Re: LR(k)-Parser wanted (Terence John Parr) (1995-04-30)
Re: LR(k)-Parser wanted (Bob Buckley) (1995-05-11)
Re: LR(k)-Parser wanted (1995-06-05)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Bob Buckley <>
Keywords: parse
Organization: Compilers Central
References: 95-04-133
Date: Thu, 11 May 1995 22:46:28 GMT

There is a tech. report (FTP-able) in my `recent publications' accessible
from my home page which describes a generalisation of LR parsing which
accepts some non-LR(k) grammars deterministically with O(n) efficiency
and includes all LR(1) grammars - extension to LR(k) is discussed.

I have an implementation in Gofer - but it is a long way from being
production software (I'm fixing bottom-up error-recovery first).

The tech. report references another interesting LR(k) implementation
by Ancona et. al.

These techniques both carry non-terminals in the look-ahead/context
of items. Our technique uses a generalisation of the LR parser with
two-stacks, to be able to achieve better than LR(k) parsing. The parsing
process parses non-terminals to resolve conflicts in terminal look-ahead
and effectively pushes the non-terminals back into the input (the second
stack) so that no `work' is repeated. This is like DRP methods published
some time ago - but we worked out how to limit the construction so that
grammar-class membership is decidable.

Bob Buckley
School of Computer and Information Science, Phone: +61 8 302 3465
University of South Australia, The Levels, Fax: +61 8 302 3381
Pooraka SA 5095 Australia

Post a followup to this message

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