（四十）深度解析领域特定语言（DSL）第七章——语法制导翻译——参数验证DSL语法分析器实现：语法树

        上一篇文章展示了SDD的设计和实现，接下来要讲解的是语法树（即抽象语法树）——语法分析器的输出。具体来说，执行语法分析之后，只要没有错误，我们就会输出一个语法树对象供下一环节使用。

        为简化代码的管理工作，笔者将语法树相关的代码放置到名为“ast”的包中。另外，由于语法树的构建过程是伴随着语法分析进行的，所以本环节的主要任务是以语法分析为主，构建语法树其实是一种扩展行为。代码7-12展示了语法树构建器类ASTBuilder的基本信息：

代码7-12class ASTBuilder {private TokenBuffer tokenBuffer;private Token lookahead;ASTBuilder(TokenBuffer tokenBuffer) {this.tokenBuffer = tokenBuffer;lookahead = tokenBuffer.nextToken();}
}

        前面内容中，曾经引用过TokenBuffer这一类型，不过从未展示过它的定义。现在，让我们将前面所欠的“债”还上。TokenBuffer所代表的是token缓冲区，也就是词法分析器的输出结果。该类的使用，将会改变语法分析器的运作方式（可参看图 5.6）。简单来说，语法分析器每分析完一个token之后，就会从TokenBuffer对象中获取下一个，而不是通过调用词法分析器来获取。

        TokenBuffer类的定义如代码7-13所示：

代码7-13class TokenBuffer {private List<Token> tokens;private int currentPosition;private int tokenIndex;TokenBuffer(List<Token> tokens) {this.tokens = tokens;this.currentPosition = tokenIndex = -1;}
}

        TokenBuffer类中包含了一个token对象列表，用于存储词法分析器的输出，后续所有的操作，比如获取新token、查看当前token等，都会围绕着该对象展开。

        使用TokenBuffer的另一个好处是可以更方便地支持回溯。尽管前面所有的案例都假定不需要进行回溯操作，但递归下降语法分析算法其实是可以支持的。想要做到这一点，可以考虑在如下两个关键点上进行改造：

1. 执行流程进入到非终结符对应的方法之后立即保存词法单元的索引信息，如果语法分析出现异常的话，则将词法单元的索引恢复为保存点所记录的位置。
2. 通过TokenBuffer类辅助回溯相关的操作，比如重置索引、还原保存点等。

        当然，也存在着其他的可行方案，不过笔者觉得TokenBuffer的使用能够达到简化实现的目的。就回溯这一主题相关的内容，笔者不再使用单独的案例进行说明，代码7-14给出了一般的实现模式：

代码7-14void parserMethod() {int saved = tokenBuffer.getCurrentPosition(); //代码1boolean parseSuccess = false;...if (!parseSuccess) {tokenBuffer.resetCurrentPosition(saved); //代码2}
}

        代码7-14中，方法的入口处保存了当前token的索引，即代码1处；紧接着执行具体的语法分析逻辑，执行过程中会将分析的结果保存在变量parseSuccess之中；最后，对分析结果进行判断，如果失败的话则调用TokenBuffer的resetCurrentPosition()方法来重置token索引，即代码2处。当然，就具体如何实现回滚逻辑，与语法分析器的实现模式有关，比如您还可以使用try...catch的形式来代替变量parseSuccess。以笔者个人的经验来看，现实中其实很少需要使用到回溯，大多数情况下只需要使用一个向前看字符的预测分析法就可以了。此外，DSL的作者毕竟是我们自己，这就意味着DSL的设计有很强的可控性，可以在文法设计阶段主动地规避可能的回溯。且不考虑性能问题，消除回溯最直接的好处是简化语法分析器的实现，更有利于DSL的维护和扩展。

        继继讨论TokenBuffer的实现。代码7-15展示了语法分析过程中能够使用到的方法以及用于支持回溯的方法：

代码7-15Token nextToken() {++currentPosition;return this.getToken(currentPosition);
}Token current() {return this.getToken(currentPosition);
}void popToken() {this.tokenIndex++;
}void resetCurrentPosition(int save) {this.currentPosition = tokenIndex = save;
}void reset() {this.currentPosition = tokenIndex = -1;
}Token getToken(int index) {if (index >= tokens.size()) {return new Token(TokenType.EOF);}return tokens.get(index);
}

        代码比较简单，笔者不做过多的说明，让我们继续语法树构建器类ASTBuilder的学习。代码7-16展示了该类的对外接口方法build()的实现逻辑：

代码7-16AST build() {AST tree = new AST();Node start = start(false);tree.root.child = start;return tree;
}

        build()方法用于构建语法树，返回值为语法树对象。对于语法树结构的处理，笔者设计了一个不包含任何信息的根节点并让实际的语法树作为根节点的孩子。这样做的目的仅仅是为了给语法树设置一个明确的起点，以简化后续的遍历操作。代码7-17展示了语法树类AST的基本结构：

代码7-17class AST {Node root;AST() {this.root = new Node(NodeType.ROOT);}
}

        类AST中也包含了用于对节点进行遍历的方法，待需要时笔者再进行展示。枚举类型NodeType定义了语法树节点的类型，如代码7-18所示：

代码7-18enum NodeType {ROOT, //根节点COMPARE, //比较运算LOGICAl; //逻辑运算
}

        笔者为当前案例中的每一个程序构造如比较运算，都设计了专门的语法树结点类型，最终形成了一个类族，如图 7.11所示。

图 7.11 语法树节点类图

        当前DSL案例比较简单，所以只有两个典型的程序构造：比较运算和逻辑运算，对应的节点类分别为CompareNode和LogicalNode。又由于这两类运算都是二元的，所以笔者又为它们设计了一个共同的抽象父类BinaryNode，直接继承于Node类。上述四个类的代码如代码7-19所示：

代码7-19class Node {NodeType type;Node child;
}abstract class BinaryNode extends Node {Node left;Node right;
}class LogicalNode extends BinaryNode {Token logicalOperator;LogicalNode(Token logicalOperator, Node left, Node right) {super(NodeType.LOGICAl, left, right);this.logicalOperator = logicalOperator;}
}class CompareNode extends BinaryNode {Token operator;Token left;Token right;CompareNode(Token operator, Token left, Token right) {super(NodeType.COMPARE, null,null);this.operator = operator;this.left = left;this.right = right;}
}

        值得注意的是，CompareNode类型的对象只能作为叶子节点出现，虽然其继承于BinaryNode，但它的左右孩子节点都是空值（null）。可以想象，笔者所设计的语法树其实是一棵二叉树。这是由语言特性所决定的，并不是所有的语法树都是二叉树，这一点我们曾在前文中强调过，还请读者注意。

        对于本案例而言，语法树的作用非常关键。因此，笔者挑选了几个最具代表性的DSL脚本并为其绘制了对应的语法树，如图 7.12、图 7.13、图 7.14和图 7.15所示，请读者着重关注一下DSL脚本结构和语法树结构是如何相互映射的。另外，语法树创建逻辑也比较复杂，读者可参考这些图来进行代码的学习。

图 7.12 DSL “#e > 0 and #e < 20 or #e > 30”所对应的语法树

图 7.13 DSL“ #e > 0 and (#e > 20 or #e < 30)”所对应的语法树

图 7.14 DSL“ (#e >= 0 and #e <= 8) or (#e >= 50 and #e <= 100)”所对应的语法树

图 7.15 DSL“ #e > 0.5”所对应的语法树

        下面开始学习语法分析代码的实现逻辑，这些代码都位于ASTBuilder类中，请读者对照SDD 7-4对代码进行理解。

        代码7-20中的start()函数是语法分析逻辑的入口方法，该方法对应于文法符号START。笔者比较习惯于让方法的名称与文法符号的名称一一对应，此处仍然遵循了这一约定。

代码7-20//START -> GROUP REST
Node start(boolean isNest) {Node inh = group();Node syn = rest(inh, isNest);return syn;
}

        代码中出现了一个奇怪的参数：isNest，用于标识是否是对start()方法的递归调用。如果该值是true的话，则会略过对结束类型Token（TokenType.EOF）的处理。需要注意的是，当DSL表达式中包含了括号的时候，就会出现对START符号的递归处理，即文法GROUP所对应的产生式，这也是导致该DSL复杂的主要原因之一。以脚本“#e > 0 and (#e > 20 or #e < 30)”为例，其所对应的语法分析流程将呈图 7.16所示的结构，其中的实线箭头指向了一个针对递归处理。

图 7.16 语法分析过程中，针对START符号的递归调用

        代码7-20中，对group()方法进行调用后，其返回值会作为rest()方法的参数。相当于将GROUP节点的综合属性传递给REST节点的继承属性，对应于SDD 7-4中的语义规则r1；而rest()方法的返回值又被作为了start()方法的返回值，相当于将REST节点的综合属性赋予START节点的综合属性，对应于SDD 7-4中的语义规则r2。语法分析器的实现基本上就是按照这一思路展开的，读者在进行代码学习的时候也要注意与SDD相互结合。

        让我们继续代码的学习。代码7-21展示了ASTBuilder类中其余的用于语法分析和语法树构建的代码：

代码7-21//REST -> LOGICAL GROUP REST1
Node rest(Node inh, boolean isNest) {if (this.lookahead.type == TokenType.LOGICAL) {Token logical = logical();Node group = group();Node newInh = new LogicalNode(logical, inh, group);Node syn = rest(newInh, isNest);return syn;}if (!isNest && this.lookahead.type != TokenType.EOF) {interrupt("eof");}return inh;
}//GROUP -> '(' START ')' | COMPARE
Node group() {Node result = null;if (this.lookahead.type == TokenType.OPEN_PARENTHESIS) {this.matchAndMove(TokenType.OPEN_PARENTHESIS);result = start(true);this.matchAndMove(TokenType.CLOSE_PARENTHESIS);} else {result = compare();}return result;
}//COMPARE -> '#e' RELATION 'number' | 'number' RELATION '#e'
CompareNode compare() {Token operator = null, left = null, right = null;if (this.lookahead.type == TokenType.ELEMENT) {matchAndMove(TokenType.ELEMENT);operator = relation();right = this.lookahead;matchAndMove(TokenType.NUMBER);} else if (this.lookahead.type == TokenType.NUMBER) {left = this.lookahead;matchAndMove(TokenType.NUMBER);operator = relation();matchAndMove(TokenType.ELEMENT);} else {interrupt("#e or number");}return new CompareNode(operator, left, right);
}//RELATION -> '>=' | '>' | '<= '| '<' | '='
Token relation() {Token result = this.lookahead;matchAndMove(TokenType.OPERATOR);return result;
}
//LOGICAL -> 'and' | 'or'
Token logical() {Token result = this.lookahead;matchAndMove(TokenType.LOGICAL);return result;
}void matchAndMove(TokenType target) {if (this.lookahead.type == target) {String info = String.format("current token:%s", lookahead.lexeme);//System.out.println(info);lookahead = this.tokenBuffer.nextToken();return;}this.interrupt(target.getName());
}void interrupt(String expected) {String lexeme = this.lookahead.lexeme;String error = String.format("syntax error, lexeme:%s, expected:%s", lexeme, expected);throw new ParserException(error);
}

        由于代码篇幅较长，笔者仅对部分方法作解释说明。在rest()方法的执行过程中，需要判断当前Token是否为结束类型（TokenType.EOF），以此决定是否终止对rest()方法的递归调用，同时需处理ε的情况。如前文所述，由于可能存在对start()方法的递归调用，若直接通过判断当前Token是否为EOF类型来终止递归，会导致语法分析逻辑错误。此时，参数isNest的作用便尤为关键——仅当非start()方法递归调用时，才考虑终结rest()方法的递归调用。若读者对此感到困惑，实属正常，笔者在撰写此部分内容时亦经历了深入的思考。建议通过实现代码并逐行调试的方式，辅助理解该逻辑。

        关于group()方法的实现，其结构虽相对简单，但因包含对start()方法的调用，极大增加了调试难度。建议读者在该方法中添加用于提升调试效率的代码，例如将方法名称、参数信息输出至控制台。至于ASTBuilder类中的其他方法，逻辑较为简明，笔者不再逐一赘述。接下来，将进入语义模型构建环节的代码学习。

上一章  下一章