0. 前言

编译原理，我大学生涯中最后一门较有难度且含金量高的专业课。这门课程涉及到许多 CS 专业知识，将程序设计语言、软硬件协同、数据结构与算法等有机地结合在一起，其原理和技术——特别是思想方法——对将来的学习和工作都很有帮助。为此，我新开这一栏目，尽量深入浅出地讲解编译原理 （虽然更像是个人笔记）。

教材以清华大学出版社的《编译原理（第 3 版）》为准。

1.1 什么是编译程序

相信大家都很熟悉，我们日常使用的 C/C++、Rust、Go 等需要编译的高级语言，需要被翻译成汇编语言（更多是作为中间产物存在），接着再被翻译成机器语言（机器码），最终才能被机器识别与执行。而执行从高级语言到低级语言（汇编语言或机器语言）翻译过程的程序，就是编译程序（Compiler），该过程被称之为编译（Compilation）。

从基本功能来看，编译程序就是一种翻译程序。而编译，就是一种用源语言表示的算法转换成另一种等价的用目标语言表示的算法。

区别：解释程序（Interpreter），如 Python、Java 等。这类高级语言的特点是边解释边执行，直接由源码翻译成机器码，不经编译过程。

注：如果是从汇编语言到机器码，用到的是汇编器（Assembler），这个过程叫汇编（Assembly）。

高级语言程序的处理过程

1.2 编译过程和编译程序的结构

1.2.1 编译过程概述

编译的各个阶段可用下图表示：

  1. 词法分析（扫描器，Scanner）：从左到右读字符流的源程序，识别、拼接单词；
  2. 语法分析（分析器，Analyzer）：在词法分析的基础上，将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式”等；
  3. 语义分析：申查源程序有无语义错误，为代码生成阶段收集类型信息；
  4. 中间代码生成：将源程序变成一种内部表示形式，这种形式叫中间语言或中间代码，是一种结构简单、含义明确的记号系统；
  5. 代码优化：可进行多次。变换或改造前一阶段产生的中间代码，使生成的目标代码更高效，即省时间和空间；
  6. 目标代码生成：把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码。

1 .2.2 编译程序的结构

上述编译过程的每个阶段都要包括表格处理程序和出错处理程序。

典型编译程序的主要逻辑模块

1.2.3 编译程序的组合

编译程序的工作逻辑可分为两个阶段：

  • 分析（Analyzer）：理解源程序，挖掘源程序的意义
  • 综合（Synthesis）：生成与源程序语义上等价的目标程序

根据编译程序各部分的功能，又可分为前端（front end） 和 后端（back end）：

  • 前端：与源程序有关的编译部分
    • 词法分析、语法分析、语义分析、中间代码生成
    • 分析部分
    • 特点：与源语言有关
  • 后端：与目标机有关的部分
    • 代码优化、代码生成
    • 综合部分
    • 特点：与目标机有关

典型编译程序的逻辑过程

一个编译过程可由一遍、两遍或多遍（passes）完成。

例如一遍可以只完成词法分析工作，一遍完成词法分析和语法分析工作，甚至一遍完成整个编译工作。

1.3 PL/0 语言编译系统

PL/0 语言是 Pascal 语言的一个子集，程序结构很简单，但“麻雀虽小，五脏俱全”，有常量、变量和过程声明，也有分支和循环结构，很适合教学用。

PL/0 语言语法的 EBNF 描述如下：

<程序> ::= <分程序>.
<分程序> ::= [<常量说明部分>][变量说明部分>][<过程说明部分>]<语句>
<常量说明部分> ::= const<常量定义>{,<常量定义>};
<常量定义> ::= <识符>=<无符号整数>
<无符号整数> ::= <数字>{<数字>}
<标识符> ::= <字母>{<字母>|<数字>}
<变量说明部分>::= var<标识符>{,<标识符>};
<过程说明部分> ::= <过程首部><分程序>;{<过程说明部分>}
<过程首部> ::= procedure<标识符>;
<语句> ::= <赋值语句>|<条件语句>|<当型循环语句>|<过程调用语句>|<读语句>|<写语句>|<复合语句>|<重复语句>|<空语句>
<赋值语句> ::= <标识符>:=<表达式>
<表达式> ::= [+|-]<项>{<加法运算符><项>}
<项> ::= <因子>{<乘法运算符><因子>}
<因子> ::= <标识符>|<无符号整数>|'('<表达式>')‘
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
<条件> ::= <表达式><关系运算符><表达式>|odd<表达式>
<关系运算符> ::= == | # | < | <= | > | >=
<条件语句> ::= if<条件>then<语句>[else<语句>]
<过程调用语句> ::= call<标识符>
<当型循环语句> ::= while<条件>do<语句>
<复合语句> ::= begin<语句>{;<语句>}end
<重复语句> ::= repeat<语句>{;<语句>}until<条件>
<读语句> ::= read'('<标识符>{,<标识符>}')‘
<写语句> ::= write'('<标识符>{,<标识符>}')‘
<字母> ::= a|b|...|X|Y|Z
<数字> ::= 0|1|2|...|8|9

注：

  • <程序> 是以句点“.”结尾的；
  • <> ，括起来的部分表示的是非终结符，可继续往下推导，详见下一章；
  • ::=，定义为；
  • |，表示“或”；
  • {}，括起来的成分可重复 0 次到任意多次
  • []，括起来的成分为任选项，即出现一次或不出现。

后面我们会用 C 语言实现一个编译器作为大作业，而 PL/0 语言实现的编译器源码是重要的参考。

参考文献

  1. 王生源，董渊，张素琴，吕映芝，蒋维杜. 编译原理. 3 版. 北京：清华大学出版社,2015.
  2. Shiyi001. (2017, January 17). PL/0简单编译系统（零）. 简书. https://www.jianshu.com/p/a6c93ca376d4