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

feriozi@my-deja.com
14 Apr 2000 23:52:26 -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:52:26 -0400
Organization: Deja.com - Before you buy.
References: 00-04-061 00-04-072
Keywords: parse, theory

    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.


Post a followup to this message

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