|Verification that a CFL is LL(1) / SLR firstname.lastname@example.org (Avi Tal) (2000-04-01)|
|Re: Verification that a CFL is LL(1) / SLR email@example.com (2000-04-03)|
|Re: Verification that a CFL is LL(1) / SLR firstname.lastname@example.org (Charles E. Bortle, Jr.) (2000-04-05)|
|From:||email@example.com (Torben AEgidius Mogensen)|
|Date:||3 Apr 2000 11:32:15 -0400|
|Organization:||Department of Computer Science, U of Copenhagen|
Avi Tal <firstname.lastname@example.org> 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 ?
No. Some unambiguous languages are not LL(1) nor SLR (or, indeed,
LR(k) for any k).
Torben Mogensen (email@example.com)
Return to the
Search the comp.compilers archives again.