完整cmm解释器构造实践(三)：语法分析语法树节点
我的语法分析器不仅会判断cmm代码的语法是否正确, 同时会存储分析过程中得到的信息, 完成语法树的构建. 为什么要有语法树呢, 其实还是为了计算机方便做进一步的处理才用的, 语法树里面存储了从代码里面提取的信息, 我们生成语法树之后再通过遍历语法树来得到中间代码. 当然直接遍历语法树并解释执行也是可以的, 我们老师非得让我们有中间代码, 所以我的语法分析只为了生成中间代码而服务的, 虽然我的代码生成器本质上是解释器改造而成的. 那么既然语法树是存储代码信息的, 代码语法树中最小的单元树的节点就很关键了. 怎么定义树的节点, 每个人有不同的看法, 书上也没有仔细讲这部分内容, 我全凭自己的理解来定义的. 下面是我的TreeNode.java中的片段, 这里是TreeNode可能的类型以及成员变量, 注意TreeNode的类型不同, 成员变量存储的信息的意义也不相同, 所以一定要仔细看, 当然你也可以只看一个大概, 然后自己去定义, 因为TreeNode信息在生成代码的阶段还需要使用, 如果不了解其中每个变量在各种情况下的意义, 是没法生成中间代码的. 我这里就不具体解释了, 因为实在太过复杂了. 注释里有一些我当时注明的信息.
/*** 语句块使用链表存储,使用NULL类型的TreeNode作为头部,注意不要使用NULL的节点存储信息,仅仅使用next指向下一个TreeNode*/NULL = 0;/*** if语句* left存放exp表达式* middle存放if条件正确时的TreeNode* right存放else的TreeNode，如果有的话*/IF_STMT = 1;/*** left存储EXP* middle存储循环体*/WHILE_STMT = 2;/*** left存储一个VAR*/READ_STMT = 3;/*** left存储一个EXP*/WRITE_STMT = 4;/*** 声明语句* left中存放VAR节点* 如果有赋值EXP,则存放中middle中*/DECLARE_STMT = 5;/*** 赋值语句* left存放var节点* middle存放exp节点*/ASSIGN_STMT = 6;/*** 复合表达式* 复合表达式则形如left middle right* 此时datatype为可能为 LOGIC_EXP ADDTIVE_EXP TERM_EXP* value==null*/EXP = 7;/*** 变量* datatype存放变量类型Token.INT 和 REAL* value存放变量名* left:* 在声明语句中变量的left值代表变量长度exp,在其他的调用中变量的left代表变量索引值exp,若为null,则说明是单个的变量,不是数组* 不存储值*/VAR = 8;/*** 运算符* 在datatype中存储操作符类型*/OP = 9;/*** 因子* 有符号datatype存储TOKEN.PLUS/MINUS,默认为Token.PLUS* 只会在left中存放一个TreeNode* 如果那个TreeNode是var,代表一个变量/数组元素* 如果这个TreeNode是exp,则是一个表达式因子* 如果是LITREAL,该LITREAL的value中存放字面值的字符形式* EXP为因子时,mDataType存储符号PLUS/MINUS*/FACTOR = 10;/*** 字面值* value中存放字面值,无符号* datatype存放类型,在TOKEN中*/LITREAL = 11;private int type;private TreeNode mLeft;private TreeNode mMiddle;private TreeNode mRight;/*** {@link TreeNode#getType()}为{@link TreeNode#VAR}时存储变量类型,具体定义在{@link Token}中INT / REAL?????* {@link TreeNode#getType()}为{@link TreeNode#OP}时存储操作符类型,具体定义在{@link Token}中 LT GT ……* {@link TreeNode#getType()}为{@link TreeNode#EXP}时表示复合表达式* {@link TreeNode#getType()}为{@link TreeNode#FACTOR}表示因子,mDataType处存储表达式的前置符号,具体定义在{@link Token}* 中PLUS/MINUS, 默认为PLUS* {@link TreeNode#getType()}为{@link TreeNode#LITREAL}表示字面值,存储类型*/private int mDataType;/*** {@link TreeNode#getType()}为{@link TreeNode#FACTOR}时存储表达式的字符串形式的值* {@link TreeNode#getType()}为{@link TreeNode#VAR}时存储变量名*/private String value;/*** 如果是代码块中的代码,则mNext指向其后面的一条语句* 普通的顶级代码都是存在linkedlist中,不需要使用这个参数*/private TreeNode mNext;
注意有些成员变量, 比如mDataType可能存储的值其实是在Token.java中定义的常量.
cmm文法
program -> stmt-sequence stmt-sequence -> statement ; stmt-sequence | statement | ε statement -> if-stmt | while-stmt | assign-stmt | read-stmt | write-stmt | declare-stmt stmt-block -> statement | { stmt-sequence } if-stmt -> if ( exp ) then stmt-block | if ( exp ) then stmt-block else stmt-block while-stmt -> while ( exp ) stmt-block assign-stmt -> variable = exp ; read-stmt -> read variable ; write-stmt -> write exp ; declare-stmt -> (int | real) ( (identifier [= exp ]) | (identifier [ exp ]) ) ; variable -> identifier [ [ exp ] ] exp -> addtive-exp logical-op addtive-exp | addtive-exp addtive-exp -> term add-op additive-exp | term term -> factor mul-op term | factor factor -> ( exp ) | number | variable | Add-op exp logical-op -> > | < | >= | <= | <> | == add-op -> + | – mul-op -> * | /
上面是我的语法分析器所使用的cmm文法, 是由很多产生式构成的, 符号->称为推导, 加粗的是终结符, 没有加粗的是非终结符或文法描述用的符号.
上面的文法其实是一个LL(1)文法, 所谓的LL(1)文法, 就是非二义性, 且不含左递归. 说白了就是按照这个文法来检查语句是否合法, 不会出现一句代码出现两个意思, 同时程序在分析的过程中不会陷入无限递归当中. 再说明白一点就是, 我们大家很喜欢这个文法, 因为写程序很方便.
LL(1)文法使用的是自顶向下的分析方法, 第一个L代表从左向右扫描输入串, 第二个L代表使用最左推导. 数字1代表只需要提前向右看一个符号就可以知道如何推导.
递归下降子程序法却只能这样。只有对爱的人，我们才会斤斤计较，锱铢必较。
