26 Apr 2005 20:40:26 -0400

Related articles |
---|

LALR1 and LL1 neelesh.bodas@gmail.com (Neelesh Bodas) (2005-04-11) |

Re: LALR1 and LL1 schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-04-16) |

Re: LALR1 and LL1 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-04-26) |

Re: LALR1 and LL1 schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-04-26) |

Re: LALR1 and LL1 haberg@math.su.se (2005-04-28) |

Re: LALR1 and LL1 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-04-30) |

Re: LALR1 and LL1 schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-05-02) |

Re: LALR1 and LL1 haberg@math.su.se (Hans Aberg) (2005-05-02) |

From: | Sylvain Schmitz <schmitz@i3s.unice.fr> |

Newsgroups: | comp.compilers |

Date: | 26 Apr 2005 20:40:26 -0400 |

Organization: | Compilers Central |

References: | 05-04-023 05-04-041 |

Keywords: | LL(1), LALR, parse |

*> [Are LL1 languages, as opposed to grammars, LALR languages? -John]*

Yes, they are:

Any LL(k) language has an LL(k) grammar, which is also LR(k). And

one can transform this LR(k) grammar into an equivalent SLR(1) grammar.

So LL languages are also LALR.

This inclusion is proper; correct me if I'm wrong, but I think the

following example shows it:

The language {c^n (a^n|b^n), n >= 0} has an LR(0) grammar

S -> A | B

A -> cAa | ca

B -> cBb | cb,

but no LL(k) grammar. One would need to see the first "a" or "b" in

order to decide between the recognition of "c^n a^n" or the

recognition of "c^n b^n", but these symbols can be arbitrarily far

away from the beginning of the input. And we cannot factor out the

"c^n" because we need to count the number of "a" or "b" after to check

it is equal to n.

--

Sylvain

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.