Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!world!iecc!compilers-sender
From: aycock@cpsc.ucalgary.ca (John Aycock)
Newsgroups: comp.compilers
Subject: Re: Recursive Descent Parsers and YACC
Keywords: parse, LL(0)
Message-ID: <9011270405.AA14638@cs-sun-fsa.cpsc.ucalgary.ca>
Date: 27 Nov 90 04:05:22 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: aycock@cpsc.ucalgary.ca (John Aycock)
Organization: Compilers Central
Lines: 33
Approved: compilers@iecc.cambridge.ma.us

| Reply-To: moss@cs.umass.edu (Eliot Moss)
|
| Folks, what is this LL(0) stuff? You need at least one token lookahead to
| choose the correct production in LL or recursive descent parsing, so LL(k)
| makes sense only for k > 0.

Not so.  Consider the following grammar:

S -> A B C
A -> a
B -> b
C -> c

No lookahead is required, yet a parser can predict that the first token will
be an 'a', the second a 'b', and so on.  As an example of where a grammar like
this could be applied, I recently wrote an EBNF->BNF converter for a compiler
class that took input files of the form:

<file> -> <terminal-section> <nonterminal-section> <start> <rules> .
<terminal-section> -> TERMINALS <terminal-list> END .
<nonterminal-section> -> NONTERMINALS <nonterminal-list> END .
   &c...

Admittedly, a rather rigid and restrictive format, but it suited the purpose
nicely.
:ja
--
John D. Aycock		aycock@cpsc.ucalgary.ca
(403) 285-8727
[Justin Graver <graver@ufl.edu> send a similar message. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.