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

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


Actually, the grammar doesn't generate the described language: The
grammar allows one more a than b's. Below is a grammar that I believe
is correct w.r.t the description:


    S -> a S b
    S -> a S
    S -> a a b


This grammar is ambiguous, so it won't generate a conflict-free LR
table. The following, however, will:


    S -> a S
    S -> a B
    B -> a B b
    B -> a b


This constitutes a proof that the language is in LR(1).


To get LL(1), we start with the grammar:


    S -> a a A b
    A -> a A b
    A -> a A
    A ->


We then do left-factoring on A:


    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.


Torben Mogensen (torbenm@diku.dk)

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