6. 语义分析

6.1. 语法制导翻译

语法制导翻译分为两类，一类是S型语法制导翻译，另一类是L型语法制导翻译。这里我们主要介绍S型语法制导翻译，因为他更简单，更加适用于语法树。

6.2. S型语法制导翻译

当我们构建出语法书以后，其每个节点与自己的子节点的关系就是产生式的关系，对语法树进行DFS就是遍历整个语法树，很多信息可以在遍历的过程中自底向上进行逐步翻译。

5.10. LR语法分析

经过了前面的LL语法分析，现在我们进入到了LR语法分析，LR语法分析也是一套算法，这里主要介绍两个，一个是SLR算法，领个是LR1算法。

LR语法分析本质上为从左到右自底向上算法，从左到右一个一个读入字符，然后按照产生式进行规约，直到规约出文法开始的符号。

5.10.1. LR算法

LR语法分析最重要的就是移入和规约。下面举一个例子来理解移入和规约。

1
2
3
4
5

加法：（
  终结符: number, +, *
  非终结符: PRODUCTION
  产生式: PRODUCTION -> number | PRODUCTION + PRODUCTION | PRODUCTION * PRODUCTION | (PRODUCTION)
  开始： PRODUCTION

5. 语法分析

5.1. 文法

文法的种类有很多，正则文法，上下文无关文法，上下文有关文法。

5.1.1. 正则文法

这一块内容就是我们平时所用到的正则表达式的文法，他的词是各个字符。

5.1.2. 上下文无关文法

上下文无关文法涉及到4个定义

• 终结符： 文法的基本单元，词
• 非终结符： 文法的中间变量，一些词按顺序排列构成的符号
• 产生式： 连接非终结符和终结符的等式，产生式表明了一些终结符和非终结符如何排列可以得到新的非终结符
• 开始： 文法开始的非终结符，他表明了什么样的非终结符满足当前文法

例子

1
2
3
4
5

加法：
  终结符: number, +
  非终结符: SUM
  产生式： SUM -> number + number | SUM + number
  开始： SUM

上诉文法可以接受 1+2， 我们只需要把1和2视为number，即可，此时的词法单元就是1，2，+

由于高级程序设计语言基本可以被视为上下文无关文法，文法的语法分析有很多算法，后面会依次对他们进行介绍。

5. 词法分析

词法分析，如其名，只分析词语，即token，词是一个文法的最小单元。至于什么是文法，后面会介绍，这里不需要过多忧虑。

5.1. 举个例子

比如我们有一个代码,这个代码和c/c++很相似（但是这个是pava代码，读者目前可以理解为c代码），这是一个计算斐波那契数列的代码，他的词法分析结果是什么呢？

1
2
3
4
5
6
7
8

int fib(int x){
    if(x<2) return 1;
    return fib(x-1) + fib(x-2);
}
int main(){
    int a = fib(5);
    return a;
}

下文的代码就是词法分析结果, 词法分析器从源文件依次读取，然后分割出最小的词法单元，

1. 引言

想做编译器很久了，大学期间留下了不少遗憾，没有实现自己的编译器，没有实现自己的JVM，没有实现自己的数据库，当然这其中有很多原因，比如学院的要求太松，比如自己也不够主动，经过两个多月的学习，笔者的Pava1.0以及Pava编译器已经发布，这篇Blog主要介绍理论，将引导读者一步一步构建一个自己的编译器。

2. 学习重点

开发编译器我能学到什么？编译器本身吗？其实不对，我们设计编译器的时候，会遇到很多问题，解决这些问题的方法才是最终重要的东西。

3. 编译器的流程

从头开发一个编译器是非常困难的，这涉及到很多知识点，这一部分主要介绍现代编译器的架构。

龙书上把编译器分为前端和后端两个部分，源代码首先经过前端转化为中间代码，中间代码经过后端转化为汇编文件。此后的工作就不是编译器的管理范围了，接下来由汇编器和链接器将汇编文件转化为可执行文件。

1
2

graph LR
  源代码 --编译器前端--> 中间代码 --编译器后端--> 汇编文件 --汇编器和链接器--> 可执行文件

为什么编译器要分为两个部分？为什么要分出前端和后端？实际上这样的架构做好以后，只要我们为$m$种源代码编写一个前端，为$n$种架构的机器编写后端，则我们可以组成$n*m$种编译器。当一个新类型的源代码或者新架构的机器出现时，我们可以以更快的速度对编译器进行更新，从而支持这些源代码或机器。另一方面，如果想要对源程序进行优化，编译器前端负责优化吗？还是编译器后端负责优化？这其实是优化器的工作，优化器的输入是中间代码，输出也是中间代码。