Re: LALR1 and LL1

Sylvain Schmitz <schmitz@i3s.unice.fr>
26 Apr 2005 20:40:26 -0400

          From comp.compilers
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)
| List of all articles for this month |
From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 26 Apr 2005 20:40:26 -0400
Organization: Compilers Central
References: 05-04-023 05-04-041
Keywords: LL(1), LALR, parse
Posted-Date: 26 Apr 2005 20:40:26 EDT

> [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.


This inclusion is proper; correct me if I'm wrong, but I think the
following example shows it:
      The language {c^n (a^n|b^n), n >= 0} has an LR(0) grammar
                S -> A | B
                A -> cAa | ca
                B -> cBb | cb,
but no LL(k) grammar. One would need to see the first "a" or "b" in
order to decide between the recognition of "c^n a^n" or the
recognition of "c^n b^n", but these symbols can be arbitrarily far
away from the beginning of the input. And we cannot factor out the
"c^n" because we need to count the number of "a" or "b" after to check
it is equal to n.


--
      Sylvain

Post a followup to this message

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