Re: LL(2) always factorable to LL(1)?

Terence Parr <>
1 Feb 1998 21:41:13 -0500

          From comp.compilers

Related articles
LL(2) always factorable to LL(1)? (Andrew M. Duncan) (1998-01-17)
Re: LL(2) always factorable to LL(1)? (Chris Clark USG) (1998-01-20)
Re: LL(2) always factorable to LL(1)? (1998-01-21)
Re: LL(2) always factorable to LL(1)? (1998-01-23)
Re: LL(2) always factorable to LL(1)? (Chris F Clark) (1998-01-23)
Re: LL(2) always factorable to LL(1)? (Terence Parr) (1998-01-23)
Re: LL(2) always factorable to LL(1)? (Scott Stanchfield) (1998-01-24)
Re: LL(2) always factorable to LL(1)? (Terence Parr) (1998-02-01)
| List of all articles for this month |

From: Terence Parr <>
Newsgroups: comp.compilers,
Date: 1 Feb 1998 21:41:13 -0500
Organization: MageLang Insitute
References: 98-01-071 98-01-080 98-01-086 98-01-100
Keywords: parse, LL(1)

Scott Stanchfield hath spake:

    Has anyone proven that the set of languages that can be represented by
    a predicated LL(k) grammar is a proper subset of those that can be
    represented in LR(k)?

Actually predicated-LL(k) is a superset of LR(k).
There are two augmentations of LL(k) to produce predicated LL(k)
grammars as I define them (from well-known techniques):

o arbitrary lookahead (backtracking): syntactic predicate.
o altering the parse according to semantic information: semantic predicate.

Both of these have been used for ages by folks building hand-built and
some automatic language tools.

Arbitrary lookahead for LR is stronger than LR(k) for any finite k if
you want a finite grammar. ;) LR(k+1) is stronger than LR(k) IF you
cannot rewrite the grammar, hence, lookahead can only help. OTOH, If
I remember correctly, the size of the LR(1) equivalent of an LR(k)
grammar has a k term in the size function, leading one to conclude
that the LR(1) grammar would be infinitely large for infinite k. Or,
perhaps more simply, LR(k)==LL(k) for grammars with actions in the
worst case and we know large lookhahead helps LL.

Showing semantics help is more obvious as it adds a whole new
dimension (that of context-sensitivity) to your parser. CFL are a
subset of the context- sensitive languages. People have overcome this
limitation by transforming context-sensitive constructs to
context-free grammars by having the lexer return context-sensitive
token streams, leaving the parser CF. Unfortunately, this trick gets
screwed up with k>1 lookahead, which we know leads to stronger parsers
(particularly with arbitrary lookahead). It is best to leave
semantics in the parser where they belong. I.e., it is best to use

type : {isType(LT(1))}? ID ;

rather than

type : TYPENAME ; //lexer calls isType() to distinguish ID,TYPENAME

Anyway, predicated-LL(k) parsers are much stronger than pure
LR(k) parsers.


Post a followup to this message

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