Re: LALR1 and LL1

Hans Aberg wrote:
> Karsten Nyblad <148f3wg02@sneakemail.com> wrote:
>
>
>>>[Are LL1 languages, as opposed to grammars, LALR languages? -John]
>>
>>1: Any LL(K) language is LR(K).
>
>
> Sylvain Schmitz <schmitz@i3s.unice.fr> wrote:
>
>
>>>[Are LL1 languages, as opposed to grammars, LALR languages? -John]
>>
>>Yes, they are:
>> Any LL(k) language has an LL(k) grammar, which is also LR(k). And
>>one can transform this LR(k) grammar into an equivalent SLR(1) grammar.
>>So LL languages are also LALR.
>
>
> Do you have any reference? -- Akim Demaille sent me an example where LL(1)
> isn't LR(1). :-) I reposted it here, but I have forgotten when. This seems
> to ne of the most often quoted mistakes.
>
> --
> Hans Aberg


I could not find an reference right away. So:


Let s1, s2, s3, s4, s5, and s6 be strings of terminals.
Let V, W, and Z be strings of terminals and non terminals.
Let A and B be non terminals.
Two strings are concatenated by placing besides each other, i.e., s1 s2
is the concatenation of s1 and s2 and V s1 is the concatenation of V and s1.


Assume that G is a grammar that is LL(K) but not LR(K) because of a
reduce/reduce conflict between two rules A -> W Z and B -> Z. Let s1 s2
s3 be the shortest string such that there is a string of terminals and
nonterminals V and three strings of terminals s4, s5, and s6 where:
    1: s1, s2, and s3 can be derived from V, W, and Z, respectively, and
    2: V W Z s4 s5 and V W Z s4 s6 and V A s4 s5 and V W B s4 s6 can be
derived right most from G's start symbol, and
    3: s4 is of length K.
Then the top most state on the parser stack after parsing s1 s2 s3 of s1
s2 s3 s4 s5 will be the state with the conflict, and the symbols pushed
on the stack will be V W Z.


Let AL be an LL(K) automaton. This automaton has to decide whether or
not A should be pushed on the stack no later than when s1 has been
recognized, but in both case the automaton may continue recognizing s2
s3 s4. that that string is longer than K. Thus G cannot be LL(K).


You can make a similar argument if the conflict is a stack/reduce conflict.


How did I use that the conflict was in the LR(K) automaton and not
in the LALR(K) automaton? In the example above I used that V W Z s4 s5
and V W Z s4 s6 that can be derived from the start symbol. Thus we know
that V W Z s4 represents a prefix of some strings in L(G). An LR(K)
parser will stop and report an error the moment the symbols pushed on
the stack + the K symbols in the windows cannot be derived to a prefix
of the language. That is not always the case when the parser is an
SLR(K) or LALR(K) parser. There the symbols pushed on the stack can
always be derived to a prefix of the language, but SLR(K) and LALR(K)
automatons may perform reduce and stack operations with erroneous
symbols in the window. (Stack operations only if K > 1.) Thus if the
automaton in the argument above had been an LALR(K) or SLR(K) automaton,
then it may not be possible to find a set of values for V and s4 such
that V W Z on the stack will be reduced to V A when s4 is in the window
even if there is no s5 such that V A s4 s5 can be derived from the start
symbol.


Thus the argument above depends on that LR(K) parsers do not perform any
stack or reduce operations if the string of grammar symbols pushed on
the stack, if that string concatenated with the string in the window is
not a prefix of a string derived from the start symbol.


Karsten Nyblad
148f3wg02 at sneakemail dot com

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