CODEWITHSUNDEEP
parsinggrammarambiguityll-grammarleft-recursion
Milad Naseri
Milad Naseri

Reputation: 4118

Problems with LL(1) grammar

I have a 26 rule grammar for a sub-grammar of Mini Java. This grammar is supposed to be non-object-oriented. Anyway, I've been trying to left-factor it and remove left-recursion. However I test it with JFLAP, though, it tells me it is not LL(1). I have followed every step of the algorithm in the Aho-Sethi book.

Could you please give me some tips?

Goal ::= MainClass $
MainClass ::= class <IDENTIFIER> { MethodDeclarations public static void main ( ) {
    VarDeclarations Statements } }
    VarDeclarations ::= VarDeclaration VarDeclarations | e
VarDeclaration ::= Type <IDENTIFIER> ;
MethodDeclarations ::= MethodDeclaration MethodDeclarations | e
MethodDeclaration ::= public static Type <IDENTIFIER> ( Parameters ) {
    VarDeclarations Statements return GenExpression ; }
Parameters ::= Type <IDENTIFIER> Parameter | e
Parameter ::= , Type <IDENTIFIER> Parameter | e
Type ::= boolean | int
Statements ::= Statement Statements | e
Statement ::= { Statements }
        |   if ( GenExpression ) Statement else Statement
        |   while ( GenExpression ) Statement
        |   System.out.println ( GenExpression ) ;
        |   <IDENTIFIER> = GenExpression ;
GenExpression ::= Expression | RelExpression
Expression ::= Term ExpressionRest
ExpressionRest ::= e | + Term ExpressionRest | - Term ExpressionRest
Term ::= Factor TermRest
TermRest ::= e | * Factor TermRest
Factor ::= ( Expression )
        |   true
        |   false
        |   <INTEGER-LITERAL>
        |   <IDENTIFIER> ArgumentList
ArgumentList ::= e | ( Arguments )
RelExpression ::= RelTerm RelExpressionRest
RelExpressionRest ::= e | && RelTerm RelExpressionEnd
RelExpressionEnd ::= e | RelExpressionRest
RelTerm ::= Term RelTermRest
RelTermRest ::= == Expression | < Expression | ExpressionRest RelTermEnding
RelTermEnding ::= == Expression | < Expression
Arguments ::= Expression Argument | RelExpression Argument | e
Argument ::= , GenExpression Argument | e

Each <IDENTIFIER> is a valid Java identifier, and <INTEGER-LITERAL> is a simple integer. Each e production stands for an epsilon production, and the $ in the first rule is the end-of-file marker.

Upvotes: 1

Views: 1411

Answers (2)

stmax
stmax

Reputation: 6605

I think I spotted two problems (there might be more):

Problem #1

In MainClass you have

MethodDeclarations public static void main

And a MethodDeclaration is

public static Type | e

That's not LL(1) since when the parser sees "public" it cannot tell if it's a MethodDeclaration or the "public static void main" method.

Problem #2

Arguments ::= Expression Argument | RelExpression Argument | e

Both Expression:

Expression ::= Term ExpressionRest

... and RelExpression:

RelExpression ::= RelTerm RelExpressionRest
RelTerm ::= Term RelTermRest

... start with "Term" so that's not LL(1) either.

I'd just go for LL(k) or LL(*) because they allow you to write much more maintainable grammars.

Upvotes: 2

ams
ams

Reputation: 25599

Is there anything to prevent IDENTIFIER being the same as one of your reserved words? if not then your grammar would be ambiguous. I don't see anything else though.

If all else fails, I'd remove all but the last line of the grammar, and test that. If that passes I'd add each line one at a time until I found the problem line.

Upvotes: 0

Related Questions