3 Apr 2000 11:32:15 -0400

Related articles |
---|

Verification that a CFL is LL(1) / SLR avi.tal@altavista.net (Avi Tal) (2000-04-01) |

Re: Verification that a CFL is LL(1) / SLR torbenm@diku.dk (2000-04-03) |

Re: Verification that a CFL is LL(1) / SLR cbrtjr@ix.netcom.com (Charles E. Bortle, Jr.) (2000-04-05) |

From: | torbenm@diku.dk (Torben AEgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | 3 Apr 2000 11:32:15 -0400 |

Organization: | Department of Computer Science, U of Copenhagen |

References: | 00-04-023 |

Keywords: | parse, LL(1) |

Avi Tal <avi.tal@altavista.net> writes:

*>I would like to know if there are methods to verify the following:*

*>1. Given an unambiguous CFL, how do we verify that it has an LL(1) grammar*

*>? / an SLR grammar?*

Write a grammar for your language. Use the standard LL(1) and SLR

parse-table constructions. If you succeed with no conflicts, this is a

proof that your grammar, and hence your language, is LL(1) / SLR.

Note that this is not a decision procedure: Some grammars for LL(1) or

SLR languages may not themselves be LL(1) or SLR. AFAIK, there is no

sure way to decide if a grammar has an equivalent LL(1) or SLR

grammar, and hence if the language is LL(1) or SLR.

*>2. Are there algorithms to convert an unambiguous CFG to LL(1) ? / SLR ?*

*>Thanks.*

No. Some unambiguous languages are not LL(1) nor SLR (or, indeed,

LR(k) for any k).

Torben Mogensen (torbenm@diku.dk)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.