我有以下解析器代码，该解析器接受链表作为来自父类的参数。输入表达式后，它抛出堆栈溢出错误。
我从 Swing GUI 类中的 jTextField 传递输入表达式，然后将 boolean 结果返回到同一类中的 jLabel。什么可能导致堆栈溢出错误？请帮忙，谢谢!!
输入示例:
1+2+3
(1+2)/(3+4)
import java.util.LinkedList;
class Token {
public static final int PLUS_MINUS = 0;
public static final int MULTIPLY_DIVIDE = 1;
public static final int EXPONENT = 2;
public static final int NUMBER = 3;
public static final int IDENTIFIER = 4;
public static final int OPEN = 5;
public static final int CLOSE = 6;
//public static final int NEGATIVE = 7;
public final int token; // FIELDS TO HOLD DATA PER TOKEN
public final String sequence;
public Token (int token, String sequence) {
super();
this.token = token;
this.sequence = sequence;
}
}
public class Parser {
private Token next; // POINTER FOR NEXT TOKEN
private LinkedList<Token> tokens; // LIST OF TOKENS PRODUCED BY TOKENIZER
private int counter = 0;
public Parser(LinkedList tokens)
{
this.tokens = (LinkedList<Token>) tokens.clone(); // GET LINKEDLIST
this.tokens.getFirst(); // ASSIGNS FIRST ELEMENT OF LINKEDLIST
}
//////// START OF PARSING METHODS ////////
/*
GRAMMAR:
E -> E+T | E-T | T | -E
T -> T*X | T/X | X
X -> X^F | F
F -> (E) | NUMBERS | IDENTIFIERS
F -> (E) | N | I
N -> D | ND
I -> IDENTIFIERS
*/
public boolean Parse ()
{
return E(); // INVOKE START SYMBOL
}
private boolean term (int token) // GETS NEXT TOKEN
{
boolean flag = false;
if(next.token == token)
flag = true;
counter++; // INCREMENT COUNTER
if(counter < tokens.size()) // POINT TO NEXT TOKEN
next = tokens.get(counter);
return flag;
}
///////// START OF LIST OF PRODUCTIONS /////////
//////// E -> E+T | E-T | T | -E ////////
private boolean E()
{
return E1() || E2() || E3();
}
private boolean E1 ()
{
// E -> E+T | E-T
int flag = counter;
boolean result = true;
if(!(E() && term(Token.PLUS_MINUS) && T() ))
{
counter = flag; // BACKTRACK
if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
next = tokens.get(counter);
result = false;
}
return result;
}
private boolean E2 ()
{
// E -> T
int flag = counter;
boolean result = true;
if(!T())
{
counter = flag; // BACKTRACK
if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
next = tokens.get(counter);
result = false;
}
return result;
}
private boolean E3 ()
{
// E -> -E
int flag = counter;
boolean result = true;
if(!(term(Token.PLUS_MINUS) && E() ))
{
counter = flag; // BACKTRACK
if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
next = tokens.get(counter);
result = false;
}
return result;
}
//////// T -> T*X | T/X | X ////////
private boolean T()
{
return T1() || T2();
}
private boolean T1 ()
{
// T -> T*X | T/X
int flag = counter;
boolean result = true;
if(!(T() && term(Token.MULTIPLY_DIVIDE) && X() ))
{
counter = flag; // BACKTRACK
if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
next = tokens.get(counter);
result = false;
}
return result;
}
private boolean T2 ()
{
// T -> X
int flag = counter;
boolean result = true;
if(!X())
{
counter = flag; // BACKTRACK
if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
next = tokens.get(counter);
result = false;
}
return result;
}
//////// X -> X^F | F ////////
private boolean X()
{
return X1() || X2();
}
private boolean X1()
{
// X-> X^F
int flag = counter;
boolean result = true;
if(!(X() && term(Token.EXPONENT) && F()))
{
counter = flag; // BACKTRACK
if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
next = tokens.get(counter);
result = false;
}
return result;
}
private boolean X2()
{
// X-> F
int flag = counter;
boolean result = true;
if(!F())
{
counter = flag; // BACKTRACK
if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
next = tokens.get(counter);
result = false;
}
return result;
}
//////// F -> (E) | NUMBERS | IDENTIFIERS ////////
private boolean F()
{
return F1() || F2() || F3();
}
private boolean F1()
{
// F -> (E)
int flag = counter;
boolean result = true;
if(!(term(Token.OPEN) && E() && term(Token.CLOSE)))
{
counter = flag; // BACKTRACK
if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
next = tokens.get(counter);
result = false;
}
return result;
}
private boolean F2()
{
// F -> NUMBERS
int flag = counter;
boolean result = true;
if(!term(Token.NUMBER))
{
counter = flag; // BACKTRACK
if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
next = tokens.get(counter);
result = false;
}
return result;
}
private boolean F3()
{
// F -> IDENTIFIERS
int flag = counter;
boolean result = true;
if(!term(Token.IDENTIFIER))
{
counter = flag; // BACKTRACK
if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
next = tokens.get(counter);
result = false;
}
return result;
}
}
最佳答案
您的问题是递归下降解析无法处理左递归语法。你的第一个产生式是“E -> E + T”，我们称之为左递归，因为导出的第一个东西就是你正在定义的东西。递归下降的工作方式是首先匹配“E”，然后匹配“+”，然后匹配“T”。问题是你的“E”方法首先调用“E1”方法，然后立即再次调用“E”，它又调用“E1”并遇到无限递归循环。如果你想使用递归下降，你需要保留你的语法。我复制了一个链接，其中包含有关左分解的更多信息:http://en.wikipedia.org/wiki/Left_recursion 。总之，您正在溢出堆栈，因为您有一个无限递归循环。
关于java - 递归下降解析器堆栈溢出，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30430045/