6、Bison解析器与抽象语法树计算器的实现与优化
Bison解析器与抽象语法树计算器的实现与优化
1. Bison解析器概述
Bison解析器具有与Flex规范相同的三部分结构，这一结构最早源于yacc。具体如下：
-定义部分：处理解析器的控制信息，通常会设置解析器运行的执行环境。
-规则部分：包含解析器的规则。
-C代码部分：会原封不动地复制到生成的C程序中。
Bison通过将各部分插入标准骨架文件来创建C程序。规则会被编译成表示状态机的数组，用于匹配输入令牌。动作中的$N和@N值会被转换为C代码，然后放入yyparse()函数的switch语句中，在每次规约时执行相应动作。部分骨架代码有多个版本，Bison会根据使用的选项进行选择，例如若解析器使用位置特性，就会包含处理位置数据的代码。
2. 抽象语法树（AST）
抽象语法树（AST）是编译器中非常强大的数据结构。与解析树不同，解析树会为解析输入字符串所使用的每个规则都创建一个节点，而在大多数实际语法中，有些规则仅用于管理分组，对程序并无实际意义。例如在计算器示例中，exp: term和term: factor规则仅用于告知解析器运算符的相对优先级。AST本质上是省略了无意义规则节点的解析树。一旦解析器创建了AST，编写递归例程来“遍历”树就变得很简单。