写在前面

大家在复习的时候一定要注意自己看的笔记和往年题究竟是软工的还是计科的呀（哭哭），这俩个专业的考试范围有很大的区别……以及gxc老师真的完全不透露任何和考试相关的重点相信，如果可以的话，gxc老师的学生可以问一下其它班的同学。

编译原理的难度不算小，平常上课还是要认真听课的，不然期末复习的时候会比较痛苦。（讲道理，编译原理的实验也不算简单……

编译原理笔记（简答题）

引论

编译器 VS 解释器

• 编译器将源程序编译成机器语言，执行机器语言程序速度更快。

• 解释器逐个语句地解释并执行源程序，因此效率低，但错误诊断效果更好。

编译器框图

编译器可以分为分析部分和综合部分：

分析部分 (前端/Front end)

• 把源程序分解成单词元素，以及相应的语法结构

• 使用这个结构创建源程序的中间表示

• 同时收集和源程序相关的信息，存放到符号表

综合部分 (后端/Back end)

• 根据中间表示和符号表信息构造目标程序

1. 词法分析：词法分析器读入源程序的字符流，将其组织成有意义的词素(Lexeme)序列，产生词法单元作为输出

2. 语法分析：分析语法结构，并使用各个词法单元的第一个分量来创建中间表示形式，如语法树(Syntax Tree)；树中的每个内部结点表示一个运算，而该结点的子结点表示该结点的分量

3. 语义分析：使用语法树和符号表来检查源程序是否和语言定义一致；执行类型检查、自动类型转换等

4. 中间代码生成：生成等价的低级或类机器语言的中间表示；该中间表示应易于生成，且容易译为目标机器上的语言；一般使用三地址代码作为中间表示形式

5. 中间代码优化：对中间代码进行改进，以生成“更好”的目标代码；更快、更短、能耗更低

6. 代码生成：将中间代码映射到目标语言指令；需要合理分配寄存器以存放变量的值。

符号表管理：记录源程序中使用的变量的名字，收集各种属性

出错管理

• 语法错误：不符合语法或词法规则的错误，通常在词法分析和语法分析时检测出来。

• 语义错误：不符合语义规则的错误，通常在语义分析时检测出来。

语法描述

文法：描述语言语法结构的形式规则，即语法规则。 根据语法规则可推导出句子（语言）。

上下文无关文法：对每个语法结构的处理与其所在上下文无关。可用来处理大多数程序语言。

推导

推导：根据一组产生式，按照一定的方式用它们去推导或产生句子（语言）；

归约

• 一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号。

• 一次归约是一个推导步骤的反向操作。

• 自底向上语法分析的目标是反向构造一个推导过程。

根据句柄进行归约

句子

语言的形式化定义

由文法G 的开始符号S推导出的所有句子构成的集合称为文法G 生成的语言，记为L(G ) 。

文法二义性

可通过不同的推导过程得到同一个句子。

如果一个文法可以为某个句子生成多棵语法分析树，这个文法就是二义的；二义性文法对同一句子有多个最左推导或多个最右推导。

为什么要消除⼆义性：通常要求程序设计语言的文法是无二义性的，否则会导致⼀个程序有多个“正确”的解释。即使文法允许⼆义性，但仍需要在文法之外加以说明，来剔除不要的语法分析树，保证最后的语法解析树只有⼀棵。

解决方法：（二义性问题是不可判定的。）改写文法使其变为无二义性文法；确定相应的编译方法，引入规则或优先级来消除文法的二义性。

二义性文法都不是LR的

形式语言分类

词法分析

状态转换图

词法分析器的重要组件之一

一个状态转换图可用于识别（或接受)一定的字符串。

有穷自动机 FA

• 是对一类处理系统建立的数学模型

• 这类系统具有一系列离散的输入输出信息和有穷数目的内部状态

• 系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。

• 每当系统处理了当前的输入后，系统的内部状态也将发生改变

有穷自动机分为两类：NFA和DFA

不确定的有穷自动机(Nondeterministicfinite automata, NFA)：边上的标号没有限制，一个符号可出现在离开同一个状态的多条边上，ε可以做标号；

确定的有穷自动机(Deterministicfinite automata, DFA)：对于每个状态以及每个符号，有且只有一条边(或最多只有一条边)

DFA是NFA的一个特例。

正则表达式

可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)

语法分析

语法分析的作用

• 从词法分析器获得一个由词法单元组成的串，并验证这个串可以由源语言的文法生成。

• 对于语法错误的程序，报告错误信息，并恢复继续处理

• 对于语法正确的程序，生成语法分析树 (简称语法树)

最左推导

• 在最左推导中，总是选择每个句型的最左非终结符进行替换

• 在最右推导中，总是选择每个句型的最右非终结符进行替换

在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导

自顶向下的语法分析技术（最左推导）不能处理左递归的情况，因此需要消除左递归。但是自底向上的技术可以处理左递归。

句型、句子、语言

文法改造技术

• 消除二义性

• 消除左递归

• 提取左公因子

归约

• 一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号。

• 一次归约是一个推导步骤的反向操作。

• 自底向上语法分析的目标是反向构造一个推导过程。

根据句柄进行归约

句柄

和某个产生式体匹配的子串，代表相应最右推导中的一个反向步骤。

作用：利用句柄进行移入-归约语法分析

短语

短语是句型中相对于某个非终结符号的⼀部分，反映了语法树中非终结符号所代表的子树的结构。

对⼀个抽象语法树来说，子树的边缘是相对于该子树根节点的短语。直接短语是所有⼆层⼦树的边缘。

简述递归下降语法分析技术的基本思想

递归下降分析是一种基于产生式规则的递归函数调用实现的语法分析方法。

语法制导的翻译

语法制导翻译：使用上下文无关文法来引导对语言的翻译，是一种面向文法的翻译技术。

语法制导翻译的基本思想

抽象语法树

抽象语法树中，每个结点代表⼀个语法结构，⽐如对应某个运算符； 结点的每个⼦结点代表其⼦结构，⽐如对应运算分量，这些子结构按照特定的方式组成了较大的结构。 抽象语法树是将源代码转换为目标代码的中间表示形式，可以帮助我们更好地理解源代码的结构和语义。在语法制导翻译中，我们可以通过遍历抽象语法树来执行语义动作，⽣成目标代码。

语法制导定义(SDD)

语法制导翻译方案(SDT)

综合属性(synthesized attribute)

• 在分析树结点N上的非终结符A的综合属性只能通过N的子结点或N本身的属性值来定义

• 终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则

继承属性(inherited attribute)

• 在分析树结点 N上的非终结符A的继承属性只能通过N的父结点、N的兄弟结点或N本身的属性值来定义

• 终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值

注释分析树

依赖图是一个描述了分析树中结点属性间依赖关系的有向图

S-SDD

L-SDD

属性文法

• 在属性文法的语义规则中，仅仅通过其它属性值和常量来定义一个属性值

• 属性文法是没有副作用的SDD

S-属性定义和L-属性定义

S-属性定义(S-SDD)

• 仅仅使用综合属性的SDD

• 可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值

L-属性定义(L-SDD)

一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性： 假设存在一个产生式A→X1X2…Xn，其右部符号Xi (1≤i≤n)的继承属性仅依赖于下列属性：

• A的继承属性

• 产生式中Xi左边的符号X1,X2,…,Xi-1的属性

• Xi本身的属性，但Xi的全部属性不能在依赖图中形成环路

每个S-属性定义都是L-属性定义

中间代码生成

后缀表达式 逆波兰表示法

• 把运算对象写在前面，把操作符写在后面（后缀）

• 这种表示法无需使用括号，如(a+b)c可写成ab+c

有向无环图DAG

语法树也是一种中间表示形式；

DAG是一种更简洁的中间表示；

• 语法树中，公共子表达式每出现一次，就有一棵对应子树

• 有向无环图(Directed Acyclic Graph,DAG) 能够指出表达式中的公共子表达式，更简洁地表示表达式

三地址代码——四元式

一个四元式(quadruple)有四个字段，分别是op, arg1, arg2, result

• 单目运算符不使用arg2

• param运算不使用arg2和result

• 条件转移/非条件转移将目标标号放在result字段

三地址代码——三元式

• 一个三元式(triple)有三个字段，分别是op, arg1, arg2。

• 表达式的DAG表示和三元式是等价的。

回填技术

为布尔表达式和控制流语句生成目标代码

• 生成跳转指令时不指定跳转目标，而是使用列表记录这些不完整指令的标号

• 当知道正确的跳转目标时再填写目标

• 列表中的每个指令都指向同一个目标

机器无关的优化

中间代码的流图表示法

流图可以作为优化的基础

• 它指出了基本块之间的控制流

• 可以根据流图了解到一个值是否会被使用等信息

如何划分基本块？

全局优化

检查信息如何在一个程序的多个基本块之间流动 全局公共子表达式、复制传播、死代码消除、代码移动、归纳变量和强度消减

局部优化

仅对各个基本块本身进行局部优化 局部公共子表达式、消除死代码、代数恒等式、数组引用、指针赋值和过程调用

代码生成

代码生成器的三个任务

• 指令选择：选择适当的指令实现IR语句

• 寄存器分配和指派：把哪个值放在哪个寄存器中

• 指令排序：按照什么顺序安排指令执行

补充

最后再结合往年题看一下，概念题就差不多了