Re: Parsing techniques

Terence Parr <>
9 Dec 1996 00:10:20 -0500

          From comp.compilers

Related articles
[6 earlier articles]
Re: Parsing techniques (1996-12-01)
Re: Parsing techniques (1996-12-01)
Re: Parsing techniques (1996-12-03)
Re: Parsing techniques (Ron House) (1996-12-07)
Re: Parsing techniques (1996-12-09)
Re: Parsing techniques (Terence Parr) (1996-12-09)
Re: Parsing techniques (Terence Parr) (1996-12-09)
Re: Parsing techniques (1996-12-15)
| List of all articles for this month |

From: Terence Parr <>
Newsgroups: comp.compilers
Date: 9 Dec 1996 00:10:20 -0500
Organization: MageLang Institute
References: 96-11-157 96-12-024
Keywords: parse, LR(1), LL(1)

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

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

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,

Post a followup to this message

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