递归下降生成Tiny语法树

自顶向下的语法分析：
递归下降法是自顶向下分析方法的通用形式。递归下降可能需要回溯。
而预测分析属于递归下降的一个特例，不需要回溯。预测分析程序试图利用一个或多个先行记号来预测出输入串中的下一个构造。LL（1）是一类最常用的预测分析程序，python的parser就是用LL（1）写的，LL（1）是自底向上算法的前奏。

自己创建一门语言，首先是要写出它的文法，然后是把文法转换成parse程序。个人感觉第一步写出文法的步骤比较重要（当然也可以从书上抄一些），转换程序是有固定的规则的，比较简单。

表达式（expression）和语句（statment）是两个概念：基本程序步骤由语句组成，而大多数语句都由表达式构成。
考虑如下Tiny的文法：

语法树可以采用树的孩子兄弟表示法，
一、递归下降法
用递归下降法写parser程序的过程，就是把图中的文法用程序翻译出来。每个文法都对应一个处理该文法的子例程。

比如 factor -> ( exp ) | number 这个文法规则，可以用如下伪代码来表示：
def factor():switch(token):case ( : match( ( );exp;match( ) );case number:match(number);else error;end switch; 
end

比较麻烦的是对左递归的处理，递归下降和LL（1）使用不同的方法来处理左递归的问题。

递归下降使用拓展巴克斯范式（EBNF）把左递归写成其他形式，
类似exp->exp addop term | term这样的表达式是左递归的，并不好直接用递归下降程序来翻译
所以通过改写成 exp->term { addop term } 可以方便表示（大括号( { } )内包含的为可重复0至无数次的项。）

exp -> exp + num|num   #这里就是递归，我们在定义“exp”这个概念，而它的定义里面又用到了自己本身！
exp -> term { addop term }
#都是匹配形如  num (+ num) (+ num) ...  的串 。在数学上，这两个表达式是等价的。

对应的exp匹配程序如下：

def exp():term();  while token = '+' or token = '-':match(token);term();end while
end

程序运行到term()的时候，还无法判断token是否匹配，但是随着term()进一步递归、下降，直到factor表达式调用match的时候，才知道token和整个文法匹不匹配。
递归下降的实质是经历了一个对语法树的前序遍历，因为语法树的叶子节点必定是非终结符，也就一定能用match函数进行比对，比对上了就进行下一步，如果没比对上，就退回并选择另一个产生式。

二、
LL（1）是将直接左递归改写成非直接左递归形式，通过first集和follow集的计算求出预测分析表，这样就可以根据读入的token选择对应的产生式。
在LL（1）中，显示维护一个栈结构，就不用产生显示递归，而是用循环（尾递归）来编写程序。

三、实际Tiny语法分析
语法分析部分。
树的结点种类NodeKind分为StmtK和ExpK两类，两类又有各自的子类。
在语法树中标明种类有利于代码生成，当遍历语法树检测到特定类型时就可以进行特定的处理。
treeNode结构为指向孩子和兄弟的节点。
语句通过同属域而不是子域来排序，即由父亲到他的孩子的唯一物理连接是到最左孩子的。孩子则在一个标准连接表中自左向右连接到一起，这种连接称作同属连接（网上查了查，没有这个概念。。）,用于区别父子连接。

typedef enum {StmtK,ExpK} NodeKind;
typedef enum {IfK,RepeatK,AssignK,ReadK,WriteK} StmtKind;
typedef enum {OpK,ConstK,IdK} ExpKind;/* ExpType is used for type checking */
typedef enum {Void,Integer,Boolean} ExpType;#define MAXCHILDREN 3typedef struct treeNode{ struct treeNode * child[MAXCHILDREN];struct treeNode * sibling;int lineno; /* source line number for listing */NodeKind nodekind;union { StmtKind stmt; ExpKind exp;} kind;  #两个变量指定表达式种类union { TokenType op;int val;char * name; } attr; #值ExpType type; /* for type checking of exps */} TreeNode;

token是一个静态全局变量
这个是主循环。在循环中匹配分号，再匹配新行（statement）

TreeNode * stmt_sequence(void)
{ TreeNode * t = statement();TreeNode * p = t;while ((token!=ENDFILE) && (token!=END) &&(token!=ELSE) && (token!=UNTIL)){ TreeNode * q;match(SEMI);q = statement();if (q!=NULL) {if (t==NULL) t = p = q;else /* now p cannot be NULL either */{ p->sibling = q;p = q;}}}return t;
}

然后在statement函数中根据首token的类别通过switch case将解析交给

match函数：用来判断当前token是否与当前表达式的下一个值匹配

static void match(TokenType expected)
{ if (token == expected) token = getToken();else {syntaxError("unexpected token -> ");printToken(token,tokenString);fprintf(listing,"      ");}
}

比如：对if语句来说，if_stmt : IF exp THEN stmt_seq END
在句法的严格限制下，if，then，end三个关键字是必须匹配的，match进行“匹配”确认，错误就报错，成功则运行词法分析读取下一个token
总共有五种语句，就不一个个详细分析了。

TreeNode * if_stmt(void)
{ TreeNode * t = newStmtNode(IfK);match(IF);if (t!=NULL) t->child[0] = exp();match(THEN);if (t!=NULL) t->child[1] = stmt_sequence();if (token==ELSE) {match(ELSE);if (t!=NULL) t->child[2] = stmt_sequence();}match(END);return t;
}

其中newStmtNode方法，负责给语法树的结点分配内存，赋值。
注意如下exp语句的解析过程，由于

TreeNode * exp(void)
{ TreeNode * t = simple_exp(); 
## exp->simple_exp comparison_op simple_exp | simple_exp
#由于exp必定会产生一个simple_exp，所以，第一步就是产生一个simple_exp
#注意：这里可以看出一个左递归的文法会使递归下降语法分析器进入一个无限循环。if ((token==LT)||(token==EQ)) { 
#之前的simple_exp会执行一个match函数。token往前会进一步，如果前进的token不满足xxx的匹配，这里就
#通不过if判断，通过了的话，就执行这里，返回的是左边的匹配TreeNode * p = newExpNode(OpK); #判断出是左边的文法，所以需要创建新结点，并且覆盖掉tif (p!=NULL) {p->child[0] = t;p->attr.op = token;t = p;}match(token);if (t!=NULL)t->child[1] = simple_exp();}#不执行的，返回右边的匹配return t;
}

最后再将语法分析树传给中间代码生成器
比如if 2>0 这个表达式，是一个exp->simple_exp comparison_op simple_exp
simple_exp再一步步递归下降到2和0

总结：递归下降的分析在判断要应用并列的产生式中的哪个的时候，还是会有尝试-出错，发现不是就换成另一个的过程。而不是一次性到位。

如果产生式没有并列，那么推导就会很简单，但是因为存在并列的情况，所以就变复杂了。

在执行循环时完成创建根节点来保持带有重复的E B N F的左结合

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！