6、深入探索Bison解析器与抽象语法树

深入探索Bison解析器与抽象语法树

1. Bison解析器概述

Bison解析器规范与Flex规范有着相似的三部分结构。第一部分是定义部分，主要处理解析器的控制信息，并设置解析器运行的执行环境。第二部分包含解析器的规则，第三部分则是直接复制到生成的C程序中的C代码。

Bison通过将各部分插入标准骨架文件来创建C程序。规则会被编译成代表状态机的数组，用于匹配输入的标记。动作中的$N和@N值会被转换为C代码，然后放入yyparse()函数的switch语句中，在每次规约时执行相应动作。骨架文件的某些部分有多个版本，Bison会根据使用的选项进行选择。

2. 抽象语法树（AST）

在编译器中，抽象语法树（AST）是一种强大的数据结构。与解析树不同，AST会省略那些用于管理分组但对程序无实际意义的规则节点。例如在计算器示例中，exp: term和term: factor规则仅用于告知解析器运算符的相对优先级。

一旦解析器创建了AST，就可以编写递归例程来遍历树。下面是一个简单的AST节点结构示例：

/* nodes in the abstract syntax tree */ struct ast { int nodetype; struct ast *l; struct ast *r; }; struct numval { int nodetype;