Re: Is this an LL(1) Grammar ?

martin_mf@hotmail.com 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


*****************************************************************************
Chris Clark Internet : compres@world.std.com
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 : http://world.std.com/~compres
--

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