11 Apr 2000 14:29:54 -0400

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

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.