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

    torbenm@diku.dk (Torben AEgidius Mogensen) 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 .
>
> S -> a a A b
> A -> a A B
> A ->
> B -> b
> B ->
>
> which yields this LL(1) table:
>
> | a | b | $
> ---+--------------+---------------+--------
> S | S -> a a A b | |
> A | A -> a A B | A -> |
> B | | B -> b / B -> | B ->
>
> The conflict for B/b can be resolved by removing B -> . This is, in
> fact, very similar to how the dangling-else problem is solved. It
> isn't difficult to see that the modified tablke accepts the correct
> language. Given that we have an LL(1) table for the language, the
> language is LL(1). I can't offhand find a grammar that generates a
> conflict-free LL(1) table directly, though.


This is not a valid LL(1) parse table for the grammar, even without
the null production under b. The problem is that $ never predicts the
fifth production. Interestingly however, the table does accept the
language a^m+1 b^m because strings of that language never require that
B -> null.


The given grammar is strong LL(2) because 'b$' does predict the fifth
production.

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