Re: LR(k)-Parser wanted

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.


regards
b++
_______________________________________________________________________
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 comp.compilers page.
Search the comp.compilers archives again.