30 Apr 2005 11:00:25 -0400

Related articles |
---|

LALR1 and LL1 neelesh.bodas@gmail.com (Neelesh Bodas) (2005-04-11) |

Re: LALR1 and LL1 schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-04-16) |

Re: LALR1 and LL1 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-04-26) |

Re: LALR1 and LL1 schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-04-26) |

Re: LALR1 and LL1 haberg@math.su.se (2005-04-28) |

Re: LALR1 and LL1 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-04-30) |

Re: LALR1 and LL1 schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-05-02) |

Re: LALR1 and LL1 haberg@math.su.se (Hans Aberg) (2005-05-02) |

From: | Karsten Nyblad <148f3wg02@sneakemail.com> |

Newsgroups: | comp.compilers |

Date: | 30 Apr 2005 11:00:25 -0400 |

Organization: | Compilers Central |

References: | 05-04-023 05-04-041 05-04-059 05-04-088 |

Keywords: | parse, theory |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.