dcsimg
BUGREPORT Antlr 2.7.1 infinite loop in ASTFactory
1 posts in topic
Flat View  Flat View
TOPIC ACTIONS:
 

Posted By:   Kenney_Westerhof
Posted On:   Friday, April 26, 2002 02:44 AM

Hi there, I've found a bug similar to outstanding bug 73 concerning tree construction resulting in an endless loop in antlr.ASTArray.add(AST[]) in the final while() loop, at least that's where it 'hangs'. Consider the following grammar file 'bug.g': { import java.io.*; class Bug { public static void main(String args[]) throws Exception { BugLexer lexer=new BugLexer(new DataInputStream(System.in)); BugParser parser=new BugParser(lexer); parser.declaration(); } } } class BugParser extends Parser; options { buildAST=true; } tokens { V   More>>


Hi there,



I've found a bug similar to outstanding bug 73 concerning
tree construction resulting in an endless loop
in antlr.ASTArray.add(AST[]) in the final while() loop,
at least that's where it 'hangs'.



Consider the following grammar file 'bug.g':



			
{
import java.io.*;

class Bug {
public static void main(String args[]) throws Exception {
BugLexer lexer=new BugLexer(new DataInputStream(System.in));
BugParser parser=new BugParser(lexer);
parser.declaration();
}
}
}

class BugParser extends Parser;
options {
buildAST=true;
}
tokens {
VAR_DECL;
}


declaration : variable_decl EOF;


// endless loop version:
variable_decl: t:type d:declarator SEMICOLON! {##=#([VAR_DECL], #t, #d);};

// correct production rule
//variable_decl: t:type d:declarator SEMICOLON! {##=#([VAR_DECL], ##);};


declarator: id:IDENTIFIER;
type: "char" | "int";


class BugLexer extends Lexer;
WS: (' ' | ' ' | '
' {newline();}| '
')
{$setType(Token.SKIP);} ;

SEMICOLON: ';';

protected DIGIT : '0'..'9' ;
protected LETTER: 'a'..'z' | 'A'..'Z';

IDENTIFIER
options { testLiterals=true;}
: (LETTER | '_') (DIGIT | LETTER | '_')*;




run antlr and compile all Bug*.java files, and run Bug,
entering for instance

			
char c;




It will run endlessly in the code I designated above
(antlr/ASTFactory.java line 165).




This is because the code generated looks like this:
(in BugParser.java)



			
public final void variable_decl() throws RecognitionException, TokenStreamException {

....
try
{
type();
t_AST = (AST)returnAST;
astFactory.addASTChild(currentAST, returnAST);
declarator(); // problem! see below..
d_AST = (AST)returnAST;
astFactory.addASTChild(currentAST, returnAST);
match(SEMICOLON);
variable_decl_AST = (AST)currentAST.root;

/* code generated with the 'correct' rule: */
variable_decl_AST=(AST)astFactory.make(
(new ASTArray(2))
.add((AST)astFactory.create(VAR_DECL))
.add(variable_decl_AST));
*/

// code generated with 'endless loop' version:
variable_decl_AST=(AST)astFactory.make(
(new ASTArray(3))
.add((AST)astFactory.create(VAR_DECL))
.add(t_AST)
.add(d_AST));
// and the call to 'make' goes into endless loop:
// first time: (see example input)
// tail=='char', tail.getNextSibling() == 'c'
// 2nd time and rest:
// tail=='c', tail.getNextSibling() == 'c';

// the rest is common code, generated using either rule
currentAST.root = variable_decl_AST;
currentAST.child =
variable_decl_AST!=null
&& variable_decl_AST.getFirstChild()!=null
? variable_decl_AST.getFirstChild()
: variable_decl_AST;
currentAST.advanceChildToEnd();
variable_decl_AST = (AST)currentAST.root;




However, the above code is not wrong. The problem resides
in the 'make()' method of ASTFactory:

			
...
for (int i = 1; i < nodes.length; i++) {
if (nodes[i] == null) continue; // ignore null nodes
if (root == null) {
// Set the root and set it up for a flat list
root = tail = nodes[i];
}
else if (tail == null) {
root.setFirstChild(nodes[i]);
tail = root.getFirstChild();
}
else {
/* A */
tail.setNextSibling(nodes[i]);
tail = tail.getNextSibling();
}
// Chase tail to last sibling
while (tail.getNextSibling() != null) {
/* B */
tail = tail.getNextSibling();
}
}



Entering the loop with i=1, everything goes well until
the while loop. The current node ( nodes[i] ) is 'char'.
This value is assigned to tail .
We enter the point marked 'B'.
tail.getNextSibling however returns 'c'. So now tail contains 'c', the last node in the array,
nodes[2].



We enter the next round, with i=2; Here, at the point marked 'A', tail.setNextSibling is called.
In this case, tail is already nodes[2] and is assigned a sibling which is also nodes[2].
This runs us into the while loop which never ends
since nodes[2] ('c') is it's own sibling.




I hope I made the problem clear.
Possible solutions are:

- fix the while loop to check if the nextSibling is tail
itself;

- better: fix setNextSibling to check for 'this' as a parameter..


There's probably a whole lot more to that but you (the author) can probably oversee the consequences of modifying that code..



Greetings,

  Kenney Westerhof

   <<Less

Re: BUGREPORT Antlr 2.7.1 infinite loop in ASTFactory

Posted By:   Kenney_Westerhof  
Posted On:   Friday, April 26, 2002 03:00 AM

Nevermind this post.. took me quite some time to figure it
out, which failed, and ofcourse, just after posting I
realize it was my mistake ;)


I forgot to use the ! to suppress automatic AST tree construction..


hope you didn't spend time reading my message ;)


Greetings,
Kenney Westerhof

About | Sitemap | Contact