From: Mark Probert <probertm@...>
Date: 2005-01-29T04:12:57+09:00
Subject: Re: When little languages grow...

Hi .. 

 On Friday 28 January 2005 02:37, Hugh Sasse Staff Elec Eng wrote:
> On Fri, 28 Jan 2005, Clifford Heath wrote:
> > Hugh Sasse Staff Elec Eng wrote:
> >> According to "Crafting a Compiler" ISBN 0-8053-3201-4 it seems that
> >> recursive descent implies LL(1)...
> >
> > No. LL(1) just means that the recursive descent parser may only consider
> > the current unprocessed token. If the lexer allows perusal of two
> > unprocessed tokens, your recursive descent parser is LL(2).
>
> Isn't that just re-framing the problem so that all token pairs are
> regarded as single entities?  
>
I am not sure if I fully understand but here goes.  In parsing, there is the 
sense of terminals and non-terminals.  For LL(1), the lookahead is one token, 
which needs to map to a terminal.  For LL(2) we look ahead two tokens and 
before checking the rules.  To quote from Prof Moessenboeck: "[LL(1) means 
that] at any point in the grammar the parser must be able to decide on the 
bases of a single lookahead symbol which of several possible alternatives 
have to be selected."

For example, the following rule is not LL(1):

  State = ident "=" Expr
        | ident [ "(" ExprList ")" ] .

Because we can't determine from a single lookahead which of the ident rules to 
trigger.  With LL(2) we could as it would be determined by the "=" or the 
"(".  

I hope that this helps.

Regards,

-- 
-mark.  (probertm at acm dot org)