更新时间：2022-08-25 18:52
语法数，也称语法树（Syntax tree），是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。也称抽象语法树，之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。比如，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；而类似于 if-condition-then 这样的条件跳转语句，可以使用带有两个分支的节点来表示。
语法数（语法树）作为一种重要的程序中间表示形式，其基本形成过程可以大致分为三个步骤，即首先对源程序代码进行词法分析，对词法分析生成的单词流进行语法分析，最后进行语义分析形成源代码的语法树。语法树作为一种良好的中间表示，语法树包含了完整的源程序信息。利用语法树可以实现多种源程序处理工具，比如智能编辑器、源程序浏览器等。此外，语法树的解析器也可以作为程序静态分析工具的前端，为其提供一种便于分析的输入。语法树的构建首先要创建相应源代码的节点，每个节点表示一个类别的代码。节点的类型分为复合节点和基节点，代码中的非终结符对应着复合节点，而终结符对应着基节点。其次要根据所要解析语言的语法结构设计出合适的树形结构来表示不同种类的程序语句，设计的好坏直接影响后面对程序的分析效率。
词法分析
作为程序编译过程的第一个阶段，将程序源代码作为字符流依次输入，对读入的字符序列进行扫描分析，最终转换成单词序列输出，其中“单词”是组成程序的最小单位。此过程并不考虑单词之间的关系。词法分析为抽象语法树的生成提供了符号节点。
语法分析
此过程是程序编译过程的第二个阶段，主要是对程序进行逻辑分析。其主要任务是在第一个阶段产生的单词序列的基础上，根据所分析语言的语法规则，分析出程序的基本语法结构，如方法、变量、表达式等各种组成程序的成分。
语义分析
此过程是编译过程的第三个阶段，主要是对程序进行逻辑分析，主要分析目标是结构上没有错误的源程序，主要分析方法是对这类源程序进行上下文有关的性质核査，以及类型的核査，主要是为了确定源程序在语义上是否准确。比如它的一个工作就是审查源程序中的每个算法的运算对象是否符合程序语言的规范。如果不符合，则应该报错。
语法树结构比较简单，其对应的词法规则和语法规则易于构造，使用flex和bison工具生成的解析器能够有效地对抽象语法树进行解析。解析器由三部分组成，分别是flex生成的词法分析器、bison生成的语法分析器和手工编写的驱动程序。词法分析器识别抽象语法树文件的记号流，提供给语法分析器；语法分析器利用嵌入其中的语义动作识别语法树节点，完成解析任务；驱动程序负责为词法分析器和语法分析器提供一个调用接口，并提供解析所需的数据结构和函数的实现。
为使解析后的抽象语法树便于遍历，使用哈希表作为抽象语法树的存储结构，每个哈希表节点对应一个抽象语法树节点，树节点编号作为哈希表的关键字，采用直接定址法构造哈希函数。哈希表节点存储树节点的节点编号、节点标识符和指向节点标记列表的指针。节点标记列表采用链表存储，每个哈希表节点包含一个指向该链表的指针。解析过程主要使用链表、哈希表等数据结构，因此Linux下实现该解析器，可以使用glib库提供的链表、哈希表及其操作函数作为解析器所需的数据结构和函数。