Re: Trouble understanding LL(k) vs. LALR(k) etc.

Christian Maeder <maeder@tzi.de>
15 Mar 2004 09:29:52 -0500

          From comp.compilers

Related articles
Trouble understanding LL(k) vs. LALR(k) etc. zork_666@nospammail.net (Johnathan) (2004-03-11)
Re: Trouble understanding LL(k) vs. LALR(k) etc. maeder@tzi.de (Christian Maeder) (2004-03-15)
Re: Trouble understanding LL(k) vs. LALR(k) etc. cfc@shell01.TheWorld.com (Chris F Clark) (2004-03-15)
Re: Trouble understanding LL(k) vs. LALR(k) etc. cdc@maxnet.co.nz (Carl Cerecke) (2004-03-19)
Re: Trouble understanding LL(k) vs. LALR(k) etc. derkgwen@HotPOP.com (Derk Gwen) (2004-03-26)
Re: Trouble understanding LL(k) vs. LALR(k) etc. cfc@shell01.TheWorld.com (Chris F Clark) (2004-03-26)
Re: Trouble understanding LL(k) vs. LALR(k) etc. f40mczf02@sneakemail.com (Karsten Nyblad) (2004-04-03)
Re: Trouble understanding LL(k) vs. LALR(k) etc. clint@0lsen.net (Clint Olsen) (2004-04-14)
[6 later articles]
| List of all articles for this month |

From: Christian Maeder <maeder@tzi.de>
Newsgroups: comp.compilers
Date: 15 Mar 2004 09:29:52 -0500
Organization: Universitaet Bremen, Germany
References: 04-03-042
Keywords: parse
Posted-Date: 15 Mar 2004 09:29:52 EST

Johnathan wrote:
> I have a vague idea of left factorisation and the principles of
> recursive descent parsing, and first and follow sets. Is that all I


good


> need to know to determine if a language grammar is LL-able? What is
> the difference between left and right recursion?


see below


> First I'd like to concentrate on LL(k), since it has been said that
> this class of language grammar can be parsed with hand-written
> recursive descent parsers.


that's correct


> Statements = <Statement> | <Statements> <Statement>


That's left recursion (for "Statements"), so the grammar is not LL and
not suited for recursive descent. Simple reverse to right recursion:
.... "<Statement> <Statements>"


(Right recursion is less efficient than left recursion for LR parsers,
though.)


> What I am having problems with in the grammar above is the recursive
> parts. For instance, is this valid?
>
> DeclStmt = VAR <VarList> AS <TypeName> | <ConstDecl>
> ConstDecl = CONST IDENTIFIER AS <TypeName> ASSIGNOP <Expr>
>
> VarList = IDENTIFIER | IDENTIFIER , IDENTIFIER


VarList allows only "var" or "var1, var2".:


> How can I check to see if it produces things like:
>
> Dim myVar, var2, var3 As String


change the rule to:


VarList = IDENTIFIER | IDENTIFIER , <VarList>


Both rules for Statement and VarList will now require left factorisation.


> I am thinking that my grammar will allow things like this:
>
> Dim Var1, Var2 Var3, Var4 As Whatever
>
> ... because of the VarList rule. Note the missing comma between Var2
> and Var3. I thought this would be better:


no, see above


> DeclStmt ::= DIM <Varname> { ',' <Varname> } As TYPENAME
>
> ... assuming that the part in { } is the part that's recursive.


for "VarName = IDENTIFIER", the part "<Varname> { ',' <Varname> }" is
equal to the corrected "<VarList>".


> Is my grammar LL(k)? Why or why not? I am not really sure where to go
> from here!


I think, I've answered your questions


Christian



Post a followup to this message

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