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

torbenm@diku.dk (Torben AEgidius Mogensen)
11 Apr 2000 14:29:54 -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: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: comp.compilers
Date: 11 Apr 2000 14:29:54 -0400
Organization: Department of Computer Science, U of Copenhagen
References: 00-04-061
Keywords: parse, theory

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


Post a followup to this message

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