怎么用C语言写语法分析3，基于有限自动机的表达式分析

之前写过12篇使用有限自动机（DFA）分析语法的文章，今天讲一下语义分析。

C语言如何写语法分析3、基于有限自动机的表达式分析

如何用C语言编写语法分析

用 C 实现一个真正的词法分析器

语义分析也是编译器前端的一个模块。

一般来说，它比解析更简单。

程序源代码的各种复杂逻辑经过语法分析后成为抽象语法树（AST）。

生成这种语法树很困难，因为源代码中有太多耦合的概念。

语法树生成后，遍历树一次即可完成语义分析。

不同的语句和运算符构成语法树的不同节点。不同的节点有不同的处理功能。检查类型一致性、计算中间结果、简化常量表达式并在处理函数中添加类型转换。

之后就可以生成三地址码了。从生成三地址代码开始，已经是编译器的后端了。

如上图，是语法树的节点数据结构。

因为是多叉树，所以父节点有一个指针parent，子节点组成一个指针数组，用nodes和nb_nodes表示。

第 31 行的 scf_operator_t* op 代表节点的操作符。无论是语句还是运算符，都始终被视为运算符。

将所有运算符分组到一个大数组中是支持的所有语义。

（人能看懂的源文本终于变成了机器可以处理的数据结构）

在第 1 列中，使用整数表示运算符的类型。

第 2 列是操作员的名称字符串。

第三列是操作优先级。

括号表示的表达式具有最高优先级，语句具有最低优先级。先乘除，再加减。

第四列是操作数（子节点）的数量。二元运算符个数为 2，一元运算符个数为 1，语句的子节点个数不定（设置为 -1）.

第 5 列是关联的。大多数是左结合的，一元运算符和赋值运算符是右结合的。

整个语义分析是分多步处理的，每一步都设置一个处理函数句柄。如下所示：

type 是运算符的类型。

func 是指向处理函数的指针。

第 8 行的最后一个参数 void* data 是处理函数所需的私有数据。

每一步的handler函数handle也组成一个大数组，如下：

最后一列是每种节点的处理函数。

语义分析比句法分析简单，因为语义分析是填空题，句法分析是问答题。

如果你想多支持一个运营商，就在这里填空（笑）。与语法不同，通过添加额外的符号可能会产生歧义。

下面以表达式的语义分析为例：

表达式只有一个子节点，而这个子节点的result字段是一个变量（scf_variable_t类型的指针），用来存放计算的中间结果（其实在生成机器码的情况下，它主要记录中间结果的类型）。

它调用 _scf_expr_calculate_internal() 函数，该函数递归地处理表达式。

当递归结束时，叶子节点可能是变量或标签（goto 语句）。

编程语言中的表达式是扩展表达式，比四次算术运算要复杂一点。

如果它不是叶节点，那么它必须是一个运算符（运算符或语句）。

第417-426行，如果有子节点，则递归处理。

如果是左关联的，子节点的处理顺序是从 0 ~ nb_nodes – 1。

如果是右结合，子节点的处理顺序是从 nb_nodes – 1 ~ 0。

处理完子节点后，再处理父节点。在语法树上，父节点的操作优先级必须低于子节点的操作优先级。

在处理父节点时，首先找到其当前步骤所需的处理函数句柄，然后调用它。

事实上，语法树的处理类似于一个简单的计算器。

在简单计算器的代码上，稍加修改即可完成语义分析。

难写的是语法分析，从源代码生成这个语法树。

我们来看加法的语义分析：

加法是二元运算符，解析代码可以和减法通用。

首先，获取它的两个操作数变量：v0 和 v1。

然后，如果两个变量中的至少一个是指向结构或类的指针，则将其作为运算符重载处理。

如果没有定义重载函数，则将其视为普通指针的加减法。

如果不是类的对象指针，只能是整数或浮点数。

指针也是无符号整数。

如果第一个变量是指针，那么第二个变量要么是同类型的指针，要么是整数。否则错误类型不一致。

类型检查都是在这个阶段处理的。

如果可能c语言实现词法分析器，自动升级（例如，将 32 位整数扩展为 64 位）。

指针操作的结果还是一个指针，结果类型和第一个变量一样。包括是否为 const 指针。

如果第二个变量是指针，那么第一个变量必须是整数，类似上面。

如果两个变量的类型相同，那么无论它们是什么类型，都是合法的操作。

如果类型不同，自动类型升级，寻找可以升级的类型。如果没有找到，就会报错，提示程序员自己处理。找到后，会自动添加类型转换节点。

最后生成一个result变量来记录操作结果的类型。

if语句的语义分析：

if 语句的条件表达式必须计算为整数（0 表示假，非 0 表示真）。

如果计算的是浮点数，一般说明程序有bug，直接报错即可。

然后分析if的body部分，body部分可能嵌套各类语句c语言实现词法分析器，递归分析。

事实上，语义分析是极其枯燥的代码，很多运算符的代码都是类似的。