Re: Philosophical question regarding statement terminators

Chris F Clark <cfc@world.std.com> wrote:


: My apologies for the error. If the 1st token of every rule is unique,
: it is easy to show that the grammar is LL(1).


Much as I hate to tinker with Chris's usually reliable posts, this
isn't so. For a grammar to be LL(1) it must be both left factored and
follow determined. Left factoring means that the first tokens of every
alternate production for each nonterminal are unique (Chris's 'first
token for every rule' condition is overly strong). Follow determinism
for the simple case of one symbol lookahead simply means that for a
rule that can match the empty string (epsilon or lambda depending on
whose papers you read), not only must the first sets of the alternate
productions be unique but they must also not share any tokens with the
follow set of the nonterminal. (Incidentally, textbooks often state a
third condition: that rules not be left recursive. That is
overspecification: left factored grammars can not be left recursive.)


                                                    Adrian
--
Dr Adrian Johnstone, Senior Lecturer in Computing, Computer Science Dep,
Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email a.johnstone@rhbnc.ac.uk Tel:+44(0)1784 443425 Fax:+44(0)1784 439786

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