大家都能看懂的编译原理

Aline744

编译是十分重要的计算机技术，大型软件的开发中，编译器能节省大量的精力，且能给程序员提供优化、链接等功能。较老的编译器有GCC、LLVM等，如今随着深度学习兴起，CUDA、Tensorflow等新型算法，也使用了许多编译原理技术。下面介绍编译器的主要流程。
1）词法分析：就是标记代码中词的成分，编译中常常使用正则表达式来判断词的性质，例如[1-9]代表一位1到9的数字，而['0']['x''X'][0-9a-fA-F]+表示十六进制数。
2）语法分析：这是编译器的核心功能，就是通过分析语法来分析程序结构。语法分析一般使用语法树来进行，请看下面三个句子：
int   i;
int   i[5];
int   i = 5;
三个句子都以int关键字开头，因此int是起始符；都以;结尾，因此;是终结符；三个句子在不同状态之间转换，形成了如下结构：

int ->  i  INIT  ;
INIT  -> 空集  
             或   ‘[’ ‘5’ ‘]’  
             或  ‘=’ ‘5’

再举一个复杂的例子：

节点一：变量  ->  ‘=’ 表达式  ‘;’  {赋值}
节点二：表达式 ->  常量   {赋值}
                变量   {读取变量值}
                或  表达式 ‘+’ 表达式   {加法}

在这个例子中，我们用到了“递归”的计算机算法。所谓的递归即函数自己调用自己，在节点二中，就用到了递归。举个例子，对于i = i + 1; 这一语句，i是变量，i + 1是表达式，符合“变量  ->  ‘=’ 表达式  ‘;’”这一形式， i + 1这个表达式，又可拆解为i ，‘+’， 1，其中i是变量，1是常量，符合表达式 ->  常量  与  表达式 ->  变量的形式。这样我们就完成了对于表达式的拆解。
在每次拆解时，我们都可以获得代码语句的信息，从而构建中间代码。例如分析i = i + 1;时，语法树首先读到变量  ->  ‘=’ 表达式，于是跳转到表达式分析（节点二第一次执行），节点二又自己调用自己（节点二第二、三次执行），通过节点二得到“i为变量”，“1为常数”两个结论，然后节点二第二、三次执行   又退回到   节点二第一次执行，得到两个数相加的结论，节点二就彻底退出，随后执行 ‘;’  {赋值}，而 {赋值}这一操作可以生成中间代码，即对变量i赋值。我们可以看到，语法树分析时，先调用的结点后退出（与堆栈类似），因此i = i + 1;这一语句，首先发现其对应节点一，然后利用节点二递归展开表达式，但是最后的结果是节点二先执行，节点一后执行。这就是语法树给我们带来的巨大方便。如果你把这一段的红字连起来看，就是如下中间代码：

i为变量
1为常数
两个数相加
对变量i赋值

是不是已经很接近汇编代码了？
再举一个例子：
  ‘*’优先级高于‘+’
节点一：变量  ->  ‘=’ 表达式  ‘;’  {赋值}
节点二：表达式 ->  常量   {赋值}
                变量   {读取变量值}
                或  表达式 ‘*’ 表达式
                或  表达式 ‘+’ 表达式   {加法}
利用该语法树分析 i = 1 + 2 * 3;，由于指定‘*’优先级高，因此代码被拆解为1 + （2*3），而不是（1+2）*3 。递归调用顺序如下：

节点一
（ 1 + 2 * 3拆分为1、+、2*3三部分）
节点二（+）
节点二（常量1）
（2*3拆分为2、*、3三部分）
节点二（*）
节点二（常量2）
节点二（常量3）

先调用的后退出，因此中间代码如下：
3
2
*
1
+
给i赋值

熟悉计算机的会发现，我们实际上实现了“逆波兰表达式”的生成。由此可见，语法树这一结构对编程的意义。建立语法树，是编译原理的核心内容，十分复杂，这里不展开描述。
3）中间代码优化与汇编生成
这一部分同样很复杂，现代编译器的优化很复杂，主要是包括空间时间优化等等，常用的手段有删除无效代码、删除无用变量、优化内存使用等，在llvm中，每一次优化被叫做一次pass，pass翻译过来就是通过，即发生变化但是本质不变。完成优化的代码就可以转换为汇编代码了，最后使用简单的字符替换，就可以生成机器码运行。

Aline744

参考资料

https://pandolia.net/tinyc/ch11_buttom_up_parse_a.html

ssffzz1

高估大家了。
大家因为嘴巴离脑子比较近，大概几厘米吧，所以嘴都很快。甚至有些话直接就从嘴喷出来了。而手离脑子有几十厘米，所以手都比较慢。

对于我们这帮们外行，这个太深。对于搞计算机的人（我是说搞计算机的，不是那帮假货），又太浅了。

dabfxz

实在不懂，因为是玩矿石收音机的，好像不搭界。

locky_z

这仅仅是编译原理中的第一次的语法分析，而实现一个语言还有大半距离
对于解释型，还有变量分配，关键字解释执行
如果对于编译型，还有二次语法分析，分析出是否重复定义、是否使用未定义变量等等。