14 Apr 2000 23:51:57 -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: | feriozi@my-deja.com |

Newsgroups: | comp.compilers |

Date: | 14 Apr 2000 23:51:57 -0400 |

Organization: | Deja.com - Before you buy. |

References: | 00-04-061 |

Keywords: | parse, theory |

Avi Tal <avi.tal@altavista.net> 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 .*

*>*

*> Thanks.*

*> Avi.*

*> [Feed that grammar to yacc, it'll generate a parser, which is as good*

*> a constructive proof as any that it's LALR and LR(1). -John]*

This is a slight variation on the balanced parentheses grammar. Since

that grammar is part of most programming languages, it is well-known

to be easy to parse. The proof that the grammar is LL(1) is

FIRST(S) = { s } FOLLOW(S) = { $ }

FIRST(X) = { s null } FOLLOW(X) = { b }

1: S --> a a X b

2: X --> a X b

3: X -->

PREDICT(1) = { a } the firsts of the rhs

PREDICT(2) = { a } the firsts of the rhs

PREDICT(3) = { b } the follows of X

The only possible conflict is on X productions. But since "a" predicts

2 and "b" predicts production 3, there is no conflict and the grammar

is LL(1).

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.