Re: LL(2) always factorable to 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.


Regards,
Terence
--

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