|LR(k)-Parser wanted firstname.lastname@example.org (1995-04-21)|
|Re: LR(k)-Parser wanted email@example.com (1995-04-29)|
|Re: LR(k)-Parser wanted firstname.lastname@example.org (1995-04-25)|
|Re: LR(k)-Parser wanted email@example.com (Terence John Parr) (1995-04-30)|
|Re: LR(k)-Parser wanted firstname.lastname@example.org (Bob Buckley) (1995-05-11)|
|Re: LR(k)-Parser wanted email@example.com (1995-06-05)|
|From:||Bob Buckley <firstname.lastname@example.org>|
|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 http://cis0.levels.unisa.edu.au/www/staff/buckley.r.e./home.html
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 Bob.Buckley@cis.UniSA.edu.au
Return to the
Search the comp.compilers archives again.