Re: Parsing techniques

John Lilley wrote:
> Although LL(k) is weaker than LALR(k), PCCTS augments
> it with predicates and backtracking.
> Does anyone else have experience regarding LALR(k>1)?
> I'd like to know for sure...


Strong LL(k) and LALR(k) parsers have the same advantage over LL(k)
and LR(k): no state explosion. However, the cost of lookahead is
exponential to even store one lookahead set for k>1. LALR(k) and
Strong LL(k) therefore are really the same in terms of cost of
lookahead.


Wow...haven't thought about parsing theory in a while. Back to the
trenches...


There has been some questions regarding relative strength of full
LL(k) and LR(k). In the presence of semantic actions, the strength of
LR(k) is exactly that of LL(k) (the key to this proof, from the '70s,
is to put an action on the left edge of every rule and then do the
rule cracking to get an action on a right edge; fun reading for a
Saturday night <wink>). Anyway, given that LL(k) and LR(k) are
effectively the same for k>1, adding semantic predicates and arbitrary
lookahead to either is a huge improvement in recognition strength: way
into the context-sensitive language class.


Note that getting a parser generator to do static k>1 lookahead is
somewhat...uh...tough. BUT, at parse-time analysis is easy. I am
thinking of doing linear approximate lookahead statically and
deferring full LL(k) to run-time (sad part is that you get parser
nondeterminism errors at parse-time :( ).


> Theoretically, a recursive-descent parser written in C++ could use C++
> exceptions for error-recovery, but PCCTS doesn't support that.


Yep, ANTLR has parser exception handling (way cool), but it uses
longjmp (gulp) for its arbitrary lookahead and error handling because
in the old days C++ compilers didn't do exceptions reliably :( :( The
ANTLR 2.00 I'm building in Java uses Java exceptions. :)


Parrt on,
Terence
--

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