14 Apr 2000 23:52:26 -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: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.