本来说这一篇文章要把构造确定性状态机和look ahead讲完的，当我真正要写的时候发现东西太多，只好分成两篇了。上一篇文章说道一个基本的状态机是如何构造出来的，但是根据第一篇文章的说法，这一次设计的文法是为了直接构造出语法树服务的，所以必然在执行状态机的时候就要获得构造语法树的一切信息。如果自己开发过类似的东西就会知道，类似LALR这种东西，你可以很容易的把整个字符串分析完判断他是不是属于这个LALR状态机描述的这个集合，但是你却不能拿到语法分析所走的路径，也就是说你很难直接拿到那颗分析树。没有分析树肯定是做不出语法树的。因此我们得把一些信息插入到状态机里面，才能最终把分析树（并不一定真的要表达成树，像上一篇文章的“分析路径”（其实就是分析树的一种可能的表达形式）所确定的语法树构造出来。
就像《构造正则表达式引擎》一般给状态机添加信息的方法，就是把一些附加的数据加到状态与状态之间的跳转箭头里面去。为了形象的表达这个事情，我就拿第一篇文章的四则运算式子来举例。在这里我为了大家方便，重复一下这个文法的内容（除去了语树书声明）：
token NAME = "[a-zA-Z_]/w*";
token NUMBER = "/d+(./d+)";
token ADD = "/+";
token SUB = "-";
token MUL = "/*";
token DIV = "//";
token LEFT = "/(";
token RIGHT = "/)";
token COMMA = ",";
rule NumberExpression Number
= NUMBER : value;
rule FunctionExpression Call
= NAME : functionName "(" [ Exp : arguments { "," Exp : arguments } ] ")";
rule Expression Factor
= !Number | !Call;
rule Expression Term
= !Factor;
= Term : firstOperand "*" Factor : secondOperand as BinaryExpression with { binaryOperator = "Mul" };
= Term : firstOperand "/" Factor : secondOperand as BinaryExpression with { binaryOperator = "Div" };
rule Expression Exp
= !Term;
= Exp : firstOperand "+" Term : secondOperand as BinaryExpression with { binaryOperator = "Add" };
= Exp : firstOperand "-" Term : secondOperand as BinaryExpression with { binaryOperator = "Sub" };
那么我们把这个文发转成状态机之后，要给跳转加上什么呢？从直觉上来说，跳转的时候我们会有六种要干的事情：
1、Create：这个文法创建的语法树节点是某个类型的（区别于在这一刻给这个问法创建一个返回什么类型的语法树节点）
2、Set：给创建的语法树节点的某个成员变量设置一个指定的值
3、Assign：给创建的语法树节点的某个成员变量设置这一次跳转的符号产生的语法树节点（譬如说Exp = Exp: firstOperand “+” Term: secondOperand，走Term的时候，一个语法树节点就会被assign给那个叫做secondOperand的成员变量）
4、Using：使用这一次跳转的符号产生的语法树节点来做这次文法的返回值（譬如说Factor = !Number | !Caller这一条）
5、Shift：略
6、Reduce：略
在这里我们并没有标记整个文法从哪一个非终结符开始，因为在实际过程中，其实分析师可以从任何一个文法开始的。譬如说写IDE的时候，我们可能在某些情况下仅仅只需要分析一个表达式。所以考虑到每一个非终结符都有可能被用到，因此我们的“Token流开始”和“Token流结束”就会在每一个非终结符的状态机中都出现。因此在第一步创建Epsilon PDA（下推自动机）的时候，就可以先直接生成。在这里我们拿Exp做例子：
本栏目更多精彩内容：http://www.bianceng.cn/Programming/cplus/
双虚线代表的是Token流和Token流结束，这并不是我们现在关心的事情。在剩下的转换中，实现是具有输入的转换，而虚线则是没有输入的转换（一般称为epsilon边）。
在这里我们要明确一个概念——分析路径。分析路径代表的是token在“流”过状态机的时候，状态是如何跳转的。因此对于实际的分析过程，分析路径其实就是分析树的一种表达形式。而在状态机里面，分析路径则代表一条从开始到结尾的可能的路径。譬如说在这里，分析路径可以有三条：
$e –> e1 –> e2 –> e$
$e –> e3 –> e8 –> e7 –> e6 –> e5 –> e4 –> e$
$e –> e9 –> e14 –> e13 –> e12 –> e11 –> e10 –> e$
因此我们可以清楚，一条路径上是不能出现多个create的，否则你就不知道应该创建的是什么了。当然create和using都不能同时出现，using也不能有多个。而且由于create和set都是在描述这个非终结符（在这里是Exp）所创建的语法树节点的类型和属性，跟执行他们的时机无关，所以其实在同一条分析路径里面，create和set放在哪里都没关系。就譬如说在上面的第二条分析路径里面，create是在e6->e5里面标记出来的。就算他移动到了e3->e8，做的事情也一样。反正只要一条路径上标记了create，那么他在这条路径被确定之后，就一定会create所指定的具体类型的语法树节点。这是相当重要的，因为在后面的分析中，我们很可能需要移动create和set的具体位置。
跟上一篇文章说的一样，接下来的一步就是去除epsilon边了。结果如下：
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索路径
， 节点
， 状态
， 语法
， 分析
， 语法分析
， 树结构跳转
， 语法篇
， 一个
真正能用
语法树构造、编译原理构造语法树、lex yacc 构造语法树、构造函数语法缺少形参、可配置交换显卡没有了，以便于您获取更多的相关知识。