引论

在一个程序可以运行之前，它首先需要被翻译成一种能够被计算机执行的形式。完成这项翻译工作的软件系统称为编译器。

解释器并不通过翻译生成目标程序，解释器直接利用用户提供的输入执行源程序中指定的操作。

一个编译系统包括：

• 源程序经过预处理器生成经过预处理的源程序；
• 再经过编译器生成目标汇编程序；
• 再经过汇编器生成可重定位机器代码；
• 经过链接器/加载器（同时加入库文件、可重定位对象文件）生成机器代码。

编译器的两个主要部分：分析与综合/前端与后端。

编译器内部需要经过：词法分析、语法分析、语义分析、中间代码生成、机器无关代码优化、代码生成、机器相关代码优化后输出目标机器语言。

• 词法分析：将输入代码中的字符流，组织称有意义的词素序列，每个词素用词法单元输出。
• 语法分析：用递归的方式构建语法树，树中每个节点表示一个运算。
• 语义分析：检查源程序是否和语言定义的语义一致，同时也收集类型信息，存在放在语法树或者符号表里。
• 中间代码生成：编译器在经过上面三个步骤以后，可以生成一个明确的低级的或类机器语言的中间过程。该中间表示应该易于生成、且能够被轻松地翻译为目标机器上的语言。
• 代码优化：代码优化器会在中间代码的基础上在时间和空间上优化代码。
• 代码生成：最终翻译成机器能够运行的代码。
• 符号表的管理
  • 记录在原代码中使用的标识符和属性信息；
  • 提供每一个标识符的类型、参数等。

词法分析

词法分析器是编译器的第一部分，是将输入代码中的字符流，组织称有意义的词素序列，每个词素用词法单元（tokens）输出。

词法单元：

• 分为关键字、标识符、算术符号、多字符符号（>=,<>）
• 识别划分词法单元用规则（pattern）
• 词素有意义的单词
• 因为一个 token 可能有不同的表达意思，所以需要他的属性来表示他所表示的内容，所以需要用词素。
• 可以通过定义一个无意义的 token 来过滤空白的信息。

词法分析工作步骤：

1. 扫描输入（源代码）
2. 去掉无意义的字符（换行、空格等）
3. 找到 tokens
4. 创建符号表
5. 将 tokens 加入符号表
6. 返回错误
7. 将词法单元（tokens）输出给语法分析器

如何判断合法的 tokens

• 用正则表达式来判断 tokens 是否合法
  • 正则表达式是一个构造符号序列的规则集合
    • 空串用 \(\varepsilon \) 表示
    • 正则表达式的定义：\(\varepsilon  | a | r+r|rr|r^{*}|(r)\)
• 检验一个表达式是否合法的使用 DFA（确定型自动机）

语法分析

上下文无关法

上下文无关法由终结符号、非终结符号、一个开始符号和一组产生式组成。

• 终结符号一般有：
  • 排在前面的小写字母
  • 运算符号
  • 标点符号
  • 数字
  • 黑体字符串，例如 id 或 if
• 非终结符号一般有：
  • 排在前面的大写字母
  • S 一般表示开始符号
  • 小写、斜体的名字，比如 expr stmt

推导

• 最左推导：总是选择每个句型的最左非终结符号，记做 \(\Rightarrow _{lm}\)
• 最右推导：总是选择每个句型的最右非终结符号，记做 \(\Rightarrow _{rm}\)
• 语法分析树是推导的图形表示，它过滤掉了推导过程中对非终结符号应用产生式的顺序。
  • 语法分析树的叶子结点的标号既可以是非终结符号，也可以是终结符号，从左到右排列这些符号就可以得到一个句型，成为这棵树的结果或边缘

CFG 应该没有二义性、左递归、公共左因子。