我正在使用带有JFlex的CUP来验证表达式语法。我的基本功能在工作：我可以判断表达式是否有效。
下一步是实现简单的算术运算，例如"加 1"。例如，如果我的表达式是"1 + a"，则结果应该是"2 + a"。我需要访问解析树才能做到这一点，因为简单地识别一个数字术语是行不通的：将 1 添加到"（1 + a） * b"的结果应该是"（1 + a） * b + 1"，而不是"（2 + a） * b"。
有没有人有一个生成解析树的 CUP 示例？我想我将能够从那里拿走它。
作为额外的奖励，有没有办法使用 JFlex 获取表达式中所有令牌的列表？似乎是一个典型的用例，但我不知道该怎么做。
编辑：发现了堆栈溢出的有希望的线索：从解析器创建抽象树问题
关于CUP和AST的讨论：
http://pages.cs.wisc.edu/~fischer/cs536.s08/lectures/Lecture16.4up.pdf
具体来说，这一段：
解析器返回的符号与语法的开始相关联 符号并包含整个源程序的 AST。
这无济于事。如果符号类没有任何指向其子项的导航指针，如何遍历给定的符号实例的树？换句话说，它的外观或行为不像树节点：
package java_cup.runtime;
/**
* Defines the Symbol class, which is used to represent all terminals
* and nonterminals while parsing. The lexer should pass CUP Symbols
* and CUP returns a Symbol.
*
* @version last updated: 7/3/96
* @author Frank Flannery
*/
/* ****************************************************************
Class Symbol
what the parser expects to receive from the lexer.
the token is identified as follows:
sym: the symbol type
parse_state: the parse state.
value: is the lexical value of type Object
left : is the left position in the original input file
right: is the right position in the original input file
******************************************************************/
public class Symbol {
/*******************************
Constructor for l,r values
*******************************/
public Symbol(int id, int l, int r, Object o) {
this(id);
left = l;
right = r;
value = o;
}
/*******************************
Constructor for no l,r values
********************************/
public Symbol(int id, Object o) {
this(id, -1, -1, o);
}
/*****************************
Constructor for no value
***************************/
public Symbol(int id, int l, int r) {
this(id, l, r, null);
}
/***********************************
Constructor for no value or l,r
***********************************/
public Symbol(int sym_num) {
this(sym_num, -1);
left = -1;
right = -1;
value = null;
}
/***********************************
Constructor to give a start state
***********************************/
Symbol(int sym_num, int state)
{
sym = sym_num;
parse_state = state;
}
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
/** The symbol number of the terminal or non terminal being represented */
public int sym;
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
/** The parse state to be recorded on the parse stack with this symbol.
* This field is for the convenience of the parser and shouldn't be
* modified except by the parser.
*/
public int parse_state;
/** This allows us to catch some errors caused by scanners recycling
* symbols. For the use of the parser only. [CSA, 23-Jul-1999] */
boolean used_by_parser = false;
/*******************************
The data passed to parser
*******************************/
public int left, right;
public Object value;
/*****************************
Printing this token out. (Override for pretty-print).
****************************/
public String toString() { return "#"+sym; }
}
好的，我知道了。但不幸的是，我无法按原样在此处发布所有代码。无论如何，我都会尝试概述解决方案，如果不清楚，请提出问题。
JFlex 使用自己的Symbol类。看这里：JFlex.jar/java_cup.runtime/Symbol.class
您将看到添加的几个构造函数：
public Symbol(int id, Symbol left, Symbol right, Object o){
this(id,left.left,right.right,o);
}
public Symbol(int id, Symbol left, Symbol right){
this(id,left.left,right.right);
}
这里的键是 Object o ，即 Symbol 的值。
定义自己的类来表示 AST 树节点，定义另一个类来表示词法分析器令牌。当然，你可以使用相同的类，但我发现使用不同的类来区分两者更清楚。JFlex 和 CUP 都会生成 java 代码，并且很容易混淆您的令牌和节点。
然后，在 parser.flex 的词法规则部分中，您希望为每个令牌执行如下操作：
{float_lit} { return symbol(sym.NUMBER, createToken(yytext(), yycolumn)); }
对所有令牌执行此操作。你的createToken可能是这样的：
%{
private LexerToken createToken(String val, int start) {
LexerToken tk = new LexerToken(val, start);
addToken(tk);
return tk;
}
}%
现在让我们继续讨论parser.cup。将所有终端声明为 LexerToken 类型，将所有非终端声明为 Node 类型。您想阅读CUP手册，但为了快速复习，终端将是词法分析器识别的任何内容（例如数字，变量，运算符），而非终端将是语法的一部分（例如表达式，因子，术语......
最后，这一切都在语法定义中汇集在一起。请考虑以下示例：
factor ::= factor:f TIMES:times term:t
{: RESULT = new Node(times.val, f, t, times.start); :}
|
factor:f DIVIDE:div term:t
{: RESULT = new Node(div.val, f, t, div.start); :}
|
term:t
{: RESULT = t; :}
;
语法factor:f意味着您将因子的值别名化为 f ，您可以在下一节中引用它 {: ... :} 。请记住，我们的终端具有类型 LexerToken 的值，而我们的非终端具有 Node s 的值。
表达式中的术语可能具有以下定义：
term ::= LPAREN expr:e RPAREN
{: RESULT = new Node(e.val, e.start); :}
|
NUMBER:n
{: RESULT = new Node(n.val, n.start); :}
;
成功生成解析器代码后，您将在解析器中看到节点之间建立父子关系的部分.java：
case 16: // term ::= UFUN LPAREN expr RPAREN
{
Node RESULT =null;
int ufleft = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)).left;
int ufright = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)).right;
LexerToken uf = (LexerToken)((java_cup.runtime.Symbol) CUP$parser$stack.elementAt(CUP$parser$top-3)).value;
int eleft = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-1)).left;
int eright = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-1)).right;
Node e = (Node)((java_cup.runtime.Symbol) CUP$parser$stack.elementAt(CUP$parser$top-1)).value;
RESULT = new Node(uf.val, e, null, uf.start);
CUP$parser$result = parser.getSymbolFactory().newSymbol("term",0, ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)), ((java_cup.runtime.Symbol)CUP$parser$stack.peek()), RESULT);
}
return CUP$parser$result;
很抱歉我无法发布完整的代码示例，但希望这将为某人节省几个小时的反复试验。没有完整的代码也很好，因为它不会使所有这些CS家庭作业变得无用。
作为生命的证明，这是我的样本AST的漂亮印刷品。
输入表达式：
T21 + 1A / log(max(F1004036, min(a1, a2))) * MIN(1B, 434) -LOG(xyz) - -3.5+10 -.1 + .3 * (1)
生成的 AST：
|--[+]
|--[-]
| |--[+]
| | |--[-]
| | | |--[-]
| | | | |--[+]
| | | | | |--[T21]
| | | | | |--[*]
| | | | | |--[/]
| | | | | | |--[1A]
| | | | | | |--[LOG]
| | | | | | |--[MAX]
| | | | | | |--[F1004036]
| | | | | | |--[MIN]
| | | | | | |--[A1]
| | | | | | |--[A2]
| | | | | |--[MIN]
| | | | | |--[1B]
| | | | | |--[434]
| | | | |--[LOG]
| | | | |--[XYZ]
| | | |--[-]
| | | |--[3.5]
| | |--[10]
| |--[.1]
|--[*]
|--[.3]
|--[1]