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

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

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