本文已收录到：中科大编译原理学习笔记 专题
语法制导翻译
前面的语法分析器部分仅仅是回答了是否识别，Yes or No。
除了语法分析之外，还需要做其他工作。——这就是语法制导翻译所做的事情。
LR分析算法中的语法制导翻译，举个例子
右部最规约的时候进行计算，得到的值放在规约后的符号上。其实就是二叉树的后序遍历，先左再右最后是根部。先得到第一个E，然后是右边第二个E，最后得知中间的运算法是“+”。先遍历两个子表达式，值出来后再遍历根节点，最后放在规约后的符号上。
Yacc中的实例
以一个简单的算法表达式求值计算器为例。
视频：https://www.bilibili.com/video/BV17W41187gL?p=67
语法制导翻译的基本思想：给每条产生式规则附加一段代码，这个代码将在产生式分析完毕，即将规约的时候执行。
具体的实现细则
以LR分析算法为例，与之前单纯LR算法不同的是：
- 在规约的时候引入了一部分附加代码；
- 栈上新加一个元素“value”用于存储右部的值。
Ps：原来的symbol和state是LR分析中本身就有的标记。symbol存放当前的终结符，state存放LR(0)分析表当前的状态。忘记了symbol和state是什么，移步复习 –> LR分析算法栈内部是如何执行的
下面我们来看个例子，看下Yacc内部是如何完成这样的工作的：
视频：https://www.bilibili.com/video/BV17W41187gL?p=69
补充一点知识：左结合与移进规约冲突
下面这框框叫做“项目集规范族”，我们来看下面项目集规范族的状态4部分。 –> 如何构建项目集规范族
状态4显然是存在移进规约冲突的，因为状态4的第一条规则，点记号后面是空的——这时候应该规约，但是第二条规则点记号后面是“+”——这又是可以移进的。 这是LR(0)算法本身缺陷导致的，如何改进请移步。–> 回顾移进规约冲突问题
问：那么应该选择移进还是规约呢？
答：这需要看具体的语言语法规则，如果当前语言的规则是左结合，例如 num = a + b + c 这种语句，应该先计算 num = a + b，随后计算 sum = sum + c ——这就叫左结合。如果确实是左结合的语法规则，这里的点记号在识别到了 E + E后，就应该规约，而不是继续去读后面的“+”号。
抽象语法树
先看下我们的编译原理前端部分学到了哪里。
现代编译器语法分析的输出往往是抽象语法树。
分析树和抽象语法树的不同
分析树包含了一些不必要的信息，分析树的 左右括号、E等信息的叶子位置我们可以拿来直接存储具体的数值，去掉这些东西也没有什么影响。我们也不需要用括号来区分优先级，通过树的深度就可以知道推导的优先级。——越靠下面的树枝优先级越高。回顾 –> 分析树的二义性问题
具体语法和抽象语法
具体语法是语法分析器所采用的的语法，关注语法的约束和改写、关注消除左递归等等。
抽象语法是一种接口，是语法分析器的最终生成产物，一旦生成抽象语法树就会抛弃源代码，下一步就交给语义分析了。
抽象语法树的数据结构（讨论存储与代码实现问题）
这里所说的实现语言就是我们用来写编译器的语言，例如C或者Java等。我们需要用这些语言来实现抽象语法树的数据结构，比如用java就会用到类来构造抽象语法树。
早期的编译器直接在语法制导翻译附加的那段代码中直接生成目标代码，不产生任何数据结构。
使用抽象语法树还可以使编译器的开发更加模块化，耦合度降低。
抽象语法树的设计（C语言版）
需要注意的是下面PPT中的代码依然是伪代码，直接将其拷贝到软件中是不能够被编译的。这一部分非常建议参考下高一凡写的数据结构算法实现，大家可以在我的博客中搜下高一凡就可以找到，她将《数据结构》这本书中的所有伪代码都用cpp具体实现了。给大家一篇关于栈的具体代码实现 –> 数据结构算法实现：顺序栈——栈的顺序表示和实现
例如下面这张图就对应的具体数据结构实现中的 cx-x.h 头文件
下面这个“构造函数”对应的 box-x.cpp 函数文件。
而下面的部分对应的就是主函数 mainx-x.cpp 文件。
树的遍历函数：
在LR分析中生成抽象语法树
还记得上面的语法制导翻译部分的内容吗？其实语法制导翻译就是在语法分析的时候附加上一段代码。既然都是附加一段代码，那么直接附加一段生成抽象语法树的代码不就可以直接一步到位了吗？
看看视频，加深印象：https://www.bilibili.com/video/BV17W41187gL?p=74 第6分钟开始
抽象语法树的重要性：
下面举个报错位置的小例子来说明抽象语法树设计实现的重要性。
