Re: Is this an LL(1) Grammar ?

Chris F Clark <>
3 Apr 1998 16:59:44 -0500

          From comp.compilers

Related articles
Is this an LL(1) Grammar ? (Martin) (1998-03-22)
Re: Is this an LL(1) Grammar ? (Alan Southall) (1998-03-24)
Re: Is this an LL(1) Grammar ? (Joachim Durchholz) (1998-03-24)
Re: Is this an LL(1) Grammar ? (1998-03-30)
Re: Is this an LL(1) Grammar ? (Chris F Clark) (1998-04-03)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: 3 Apr 1998 16:59:44 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 98-03-207 98-03-222 98-03-249
Keywords: LL(1) asked:
> My CFG grammar can accept:
> a = b = 1;
> and
> a = b;
> Is it LL(1)? Yes? How I can make it LL(1)?

To which Brianm asked:
What if it was implemented as:
> start = assignment
> assignment = ID '=' assign

And, the answer to Brian's question is yes, that is (roughly, mod a
typo or two) the LL(2) grammar for the general case of "a = b = ...".
(Brian's RD code showed that it was LL(2) by looking at 2 tokens to
see if the 2nd was an =.) It is LL(1) if the rest of the expression
that is an assignment target cannot begin with an ID. Otherwise, you
have to left-factor a little. That, of course, answers Martin's 3rd
question also.

To Martin's first question we don't know, as we don't have a grammar,
just a couple of sentences the grammar accepts, and that doesn't help
answer the question. There are plenty of non-LL grammars which accept
those two sentences. There are even numerous regular expressions,
which is an even less powerful language family.
      grammar: VAR ("=" VAR)* ("=" CONST) // for instance is a reg-expr grammar
for your examples

However, if your grammar has no left-recursion, it is probably LL(1).
That is even more likely if the beginning of each rule is unique,
although there are many LL grammars which have rules that begin with
the same terminals or non-terminals when those rules are never active
at the same time.

Of course, the simplest way to check is to run it through a trusted LL
parser generator. If I understood correctly, Dr Johnstone was even
writing one (RDP) which would help you translate your grammar into the LL
form if it wasn't already LL.

Finally, if this is for a class assignment, you'll need to learn the
first (and perhaps follow*) rules to be certain, since that is what
your instructor is trying to get across. At that level there is no
shortcut, every LL parser generator has those rules somewhere in it
(at least implicitly). (*My memory of LL is not fresh enough to
recall whether follows apply to LL or not.)

Hope this helps,

Chris Clark Internet :
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
Web Site in Progress: Web Site :

Post a followup to this message

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