Re: Verification that a CFL is LL(1) / SLR

torbenm@diku.dk (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@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)
| List of all articles for this month |
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.