Re: Verification that a CFL is LL(1) / SLR (Torben AEgidius Mogensen)
3 Apr 2000 11:32:15 -0400

          From comp.compilers

Related articles
Verification that a CFL is LL(1) / SLR (Avi Tal) (2000-04-01)
Re: Verification that a CFL is LL(1) / SLR (2000-04-03)
Re: Verification that a CFL is LL(1) / SLR (Charles E. Bortle, Jr.) (2000-04-05)
| List of all articles for this month |

From: (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 <> 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 (

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.