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

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

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