Re: LR(k)-Parser wanted

Terence John Parr (parrt@parr-research.com) wrote:
: Josef Grosch at CoCoLab writes:
: > Also, I started to work on an LR(k) version of 'lark'. It should be called
: > partial LR(k), because again LALR(1) is used by default and LR(k) only where
: > necessary. It tries LR(2), LR(3), etc. up to a given limit. Before trying
: > LR(k) an approximation of LR(k) is tried which is much more efficient to
: > compute.


: This wouldn't happen to be the linear approximate lookahead described
: in my thesis and used in ANTLR would it? Just curious to see if
: anybody had deciphered my thesis yet ;)


Oh yes, I have deciphered the thesis of Terence, at least to some
degree. What I have implemented follows the idea of the linear
approximate lookahead, although the details are different: I
implemented it for LALR(k). I used my existing data structures which
worked as well as a GLA. I am using my own caching mechanism, because
I did not understand the one of Terence. And I combined the
computation with the digraph algorithm published by F. DeRemer and T.
Pennello: Efficient Computation of LALR(1) Look-Ahead Sets, TOPLAS 4,
4 (Oct. 1982), 615-649.


I consider the idea of the linear approximate lookahead to be a
brilliant invention. Especially, I do appreciate the underlying
principle of what Terence has done. At least I and probably others
have been caught by the existing definition of LR(k) grammars, many
attempts to implement LR(k) failed. Now, Terence just disregarded the
existing definition and he defined something new in between of LR(1)
and LR(k). This can be computed efficiently and it is a valuable
progress.


Josef Grosch


grosch@cocolab.sub.com


--

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