Re: Is the language: { (a^n b^m) | n>m>0 } LL(k) ? LR(k) ?

feriozi@my-deja.com
14 Apr 2000 23:51:57 -0400

          From comp.compilers

Related articles
Is the language: { (a^n b^m) | n>m>0 } LL(k) ? LR(k) ? avi.tal@altavista.net (Avi Tal) (2000-04-05)
Re: Is the language: { (a^n b^m) | n>m>0 } LL(k) ? LR(k) ? torbenm@diku.dk (2000-04-11)
Re: Is the language: { (a^n b^m) | n>m>0 } LL(k) ? LR(k) ? feriozi@my-deja.com (2000-04-14)
Re: Is the language: { (a^n b^m) | n>m>0 } LL(k) ? LR(k) ? feriozi@my-deja.com (2000-04-14)
Re: Is the language: { (a^n b^m) | n>m>0 } LL(k) ? LR(k) ? AlexanderS@tidex.co.il (Alexander Sherman) (2000-04-29)
| List of all articles for this month |

From: feriozi@my-deja.com
Newsgroups: comp.compilers
Date: 14 Apr 2000 23:51:57 -0400
Organization: Deja.com - Before you buy.
References: 00-04-061
Keywords: parse, theory

    Avi Tal <avi.tal@altavista.net> wrote:
> Is the language: { (a^n b^m) | n>m>0 } LL(k) ? LR(k) ?
> An example of a CFG for this grammar is : S -> aaXb , X -> aXb | epsilon .
>
> Thanks.
> Avi.
> [Feed that grammar to yacc, it'll generate a parser, which is as good
> a constructive proof as any that it's LALR and LR(1). -John]


This is a slight variation on the balanced parentheses grammar. Since
that grammar is part of most programming languages, it is well-known
to be easy to parse. The proof that the grammar is LL(1) is


FIRST(S) = { s } FOLLOW(S) = { $ }
FIRST(X) = { s null } FOLLOW(X) = { b }


      1: S --> a a X b
      2: X --> a X b
      3: X -->


PREDICT(1) = { a } the firsts of the rhs
PREDICT(2) = { a } the firsts of the rhs
PREDICT(3) = { b } the follows of X


The only possible conflict is on X productions. But since "a" predicts
2 and "b" predicts production 3, there is no conflict and the grammar
is LL(1).


Post a followup to this message

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