【编译原理】期末复习（引论、词法分析、语法分析、语法制导翻译、中间代码生成、代码生成）_词法分析、语法分析、语义分析和代码生成

参考资料

编译原理-陈意云-第三版
哈工大编译原理 MOOC

前言

• 本文主要介绍词法分析、语法分析、语法制导翻译，这三个章节的内容
• 对于本文中出现的错误，欢迎在评论区指出，我会及时修改
• 语法分析和语法制导翻译，部分内容（如 LR 分析器），使用 Java 代码实现，并将执行结果进行截图，感兴趣的可以访问 gitee 链接

大纲

1. 引论

编译的各个阶段

$词法分析\to 语法分析\to 语义分析\to 中间代码生成\to 代码优化\to 目标代码生成$

编译器和解释器的区别

• 编译器是把源程序的每一条语句都编译成机器语言，并生成一个可执行（二进制）文件，可以在计算机上直接运行
• 解释器将代码逐行或逐句的解释成机器语言并执行，不会生成可执行文件
• 编译器对源程序的词法分析、语法分析、语义分析只要进行一次，而解释器对每个语句都要进行一次，所以编译器生成的可执行文件，比解释器更快

2. 词法分析

概念

正规式

定义

• 正规式又叫正则表达式
• 每个正规式 r 表示一个语言 L(r)
• 空串（ε）是正规式，表示 {ε}

示例

• 考虑字母表 Σ = { a , b } \Sigma = \{ a, b \} Σ={a,b}
• $a|b$ 表示 { a , b } \{a, b\} {a,b}，即 $|$ 表示或
• $(a,b)|(a,b)$ 表示 { a a , a b , b a , b b } \{aa, ab, ba, bb\} {aa,ab,ba,bb}，$()$ 相当于限制了了 $|$ 的范围
• $a^{\ast }$ 表示由任意个 $a$ 构成的所有串的集合
  • 任意个，包括 0 个，即空串
  • 为什么是所有串的集合？
    因为正规式表示一个语言，语言是字母表上的串集

正规定义

• 可以对正规式进行命名：$名称\to 正规式$
• 例如 $digit=0|1|2|3|4|5|6|7|8|9$
  表示 0 ~ 9 之间的某个符号

FA

• Finite Automaton，有限自动机，简称 FA

• 有限自动机由以下几个要素组成：

  • 状态集合：包含有限个状态的集合，每个状态表示自动机在某个特定时间点的内部状态。
  • 输入字母表：包含自动机接受的输入符号的集合。
  • 转移函数：描述了自动机在给定输入符号下从一个状态转移到另一个状态的规则。
  • 初始状态：表示自动机的初始状态，即开始状态。
  • 终止状态集合：表示自动机可接受的最终状态集合，也称为接受态或终止态。

• 示例
  直接看概念过于抽象，这里提供一个简单的示例
  假设有一个自动机：能够判断输入的2位数字，是否每一位都大于5，那么这个自动机应该长这样

  

  • 其中，每个小圆圈就是状态，而 start 是开始状态，是、不是 是结束状态
  • 每个自动机都有唯一的开始状态，有一个或多个结束状态

NFA

• Non-deterministic Finite Automaton，不确定的有限自动机，简称 NFA

• 若一个 FA 中，存在某个状态，输入符号后，转移后的状态有多个，那么这个 FA就是 NFA

• 示例
  正规式 $(a|b)ab$ 的NFA
  
  状态转换表

  状态	a	b
  0	0, 1	0
  1		2
  2

  • 状态 0 输入 a 可以转移到状态 0 或状态 1，因此是 NFA
  • NFA 中的某条路径，就是句子（属于该语言的串），例如aab
    

DFA

• Deterministic Finite Automaton，确定性有限自动机，简称 DFA
• 若一个 FA 中，存在某个状态，输入符号后，转移后的状态只有一个，那么这个 FA就是 DFA

NFA 与 DFA 的对比

• NFA 就像是在走迷宫，而DFA就像在过独木桥
  当NFA发现路走不通时，必须回头换条路再走，而DFA只需要一直往前就行
• 显然 DFA 的效率更高，因此需要将 NFA 转化成 DFA

NFA 转 DFA

epsilon-closure

• epsilon-closure(T)
  • 状态集合 T 的 epsilon 闭包
  • 对于状态集合T，经过有限次的epsilon（ε），可以到达的状态集合
  • 有限次，包括 0 次
• 示例
  
  • 只考虑：每个状态集合仅有一个状态的情况

    状态	epsilon闭包
    1	1,2,4
    3	1,2,3,4,6,7
    5	1,2,4,5,6,7
    6	1,2,4,6,7

  • 若要考虑状态集合有 $n$ 个状态，只需要分别求 epsilon 闭包 $c_1,c_2,...,c_n$，对 $c_1,c_2,...,c_n$ 求并集即可。

move

• move(T, a)
  状态集合 T 输入符号 a 之后，转移后的状态集合，并对集合内的元素求 epsilon 闭包
• 示例
  

  状态	输入符号	move
  2	a	m o v e ( { 2 } ) = e p s i l o n − c l o s u r e ( { 3 } ) = { 1 , 2 , 3 , 4 , 6 , 7 } move(\{2\})=epsilon - closure(\{3\}) = \{1, 2, 3, 4, 6, 7\} move({2})=epsilon−closure({3})={1,2,3,4,6,7}

子集构造法

算法

确认NFA 的输入符号;
求开始状态的 epsilon 闭包 A;
将 A 存入最终结果 res;
while (res 中有尚未标记的状态 T) {
	标记状态 T;
	for (每一个输入符号 a) {
		U = epsilon-clousre(move(T,a));
		if(U未标记过) {
			将 U 加入 res;
		}
		状态转换表 T 行 a 列 = U;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

示例

• 考虑 NFA
  
• 确认NFA的输入符号
  Σ = { a , b } \Sigma = \{a, b\} Σ={a,b}
• 求开始状态的 epslion 闭包
  ϵ − c l o s u r e ( 0 ) = { 0 , 1 , 2 , 4 , 7 } = A \epsilon-closure(0)=\{ 0,1,2,4,7 \} = A ϵ−closure(0)={0,1,2,4,7}=A
• 对 A 计算 move(A, a)，其中只有状态 2、7 可以接收 a
  A → a = { 3 , 8 } A\to a = \{ 3,8 \} A→a={3,8}
  ϵ − c l o s u r e ( m o v e ( A , a ) ) = { 3 , 8 } + { 1 , 2 , 4 , 6 , 7 } = { 1 , 2 , 3 , 4 , 6 , 7 , 8 } = B \epsilon-closure(move(A,a)) = \{ 3,8 \} + \{1,2,4,6,7\} = \{1,2,3,4,6,7,8\} = B ϵ−closure(move(A,a))={3,8}+{1,2,4,6,7}={1,2,3,4,6,7,8}=B
• 计算 move(A, b)
  A → b = { 5 } A \to b =\{ 5 \} A→b={5}
  ϵ − c l o s u r e ( m o v e ( A , b ) ) = { 5 } + { 1 , 2 , 4 , 6 , 7 } = { 1 , 2 , 4 , 5 , 6 , 7 } = C \epsilon-closure(move(A,b))=\{ 5 \} + \{ 1,2,4,6,7 \} = \{ 1,2,4,5,6,7 \} = C ϵ−closure(move(A,b))={5}+{1,2,4,6,7}={1,2,4,5,6,7}=C
• A 已经是标记过的状态集合了，开始计算状态 B
• 计算move(B,a)
  $B\to a=A\to a$
  $move(B,a)=move(A,a)$
• 计算move(B,b)
  B → b = { 5 , 9 } B \to b = \{5, 9\} B→b={5,9}
  ϵ − c l o s u r e ( m o v e ( B , b ) ) = { 5 , 9 } + { 1 , 2 , 4 , 6 , 7 } = { 1 , 2 , 4 , 5 , 6 , 7 , 9 } = D \epsilon-closure(move(B,b))=\{ 5,9 \} +\{ 1,2,4,6,7 \} = \{ 1,2,4,5,6,7,9 \} = D ϵ−closure(move(B,b))={5,9}+{1,2,4,6,7}={1,2,4,5,6,7,9}=D
• B 已经是标记过的状态集合了，开始计算状态 C
• 计算 move(C, a)
  $move(C,a)=move(A,a)$
• 计算move(C,b)
  $move(C,b)=move(A,b)$
• C 已经是标记过的状态集合了，开始计算状态 D
• 计算 move(D,a)
  $move(D,a)=move(A,a)$
• 计算 move(D,b)
  ϵ − c l o s u r e ( m o v e ( D , b ) ) = { 5 , 10 } + { 1 , 2 , 4 , 6 , 7 } = { 1 , 2 , 4 , 5 , 6 , 7 , 10 } = E \epsilon-closure(move(D,b)) = \{ 5,10 \} + \{ 1,2,4,6,7 \} =\{1,2,4,5,6,7,10\}=E ϵ−closure(move(D,b))={5,10}+{1,2,4,6,7}={1,2,4,5,6,7,10}=E
• move(E, a) 和 move(E, b) 不会再产生新的集合
• 最终结果
  
  
  注意到，A 是开始状态，而 E 是结束状态
  这是因为 A 中包含开始状态0，而 E 中包含结束状态10
  开始状态有一个，结束状态有一个或多个

DFA 的化简

思想

• 化简 DFA 的主要思想是：DFA 中，是否有两个代价是等价的
• 例如 DFA 中的一部分，若去掉 A，直接指向 C，DFA 的处理结果不变，也就是 A 多余了，可以化简
  

算法

接收状态子集Ⅰ
非接收状态子集Ⅱ
// 将 Ⅰ、Ⅱ 的并集称为 U
for (在 U 中的集合 G) {
	对于 G 中任意两个状态 s, t
	当输入 a 时，s,t 转移后的状态为 S1, S2 
	if(S1 和 S2 在 U 中不同的子集) {
		将 s, t 划分成两个子集
	} else {
		将 s, t 划分到同一个子集
	}
	划分后的 U' 作为新的 U
}
1
2
3
4
5
6
7
8
9
10
11
12
13

示例

• 考虑 DFA
  
  
  

• 确认输入符号集合 Σ = { a , b } \Sigma = \{a, b\} Σ={a,b}

• 将状态划分为：接收状态子集、非接收状态子集
  接收状态子集就是包含接收状态的集合，非接受状态子集是其余的集合
  接收状态子集Ⅰ = { D } 接收状态子集 Ⅰ= \{ D \} 接收状态子集Ⅰ={D}
  非接受状态子集Ⅱ = { A , B , C } 非接受状态子集Ⅱ = \{ A,B,C \} 非接受状态子集Ⅱ={A,B,C}

• 化简，意味着某些集合是等价的
  而 { D } \{D\} {D}显然不可再分，那么考虑化简 { A , B , C } \{ A,B,C \} {A,B,C}

  • m o v e ( A , a ) = m o v e ( B , a ) = m o v e ( C , a ) = B ∈ { A , B , C } move(A,a)=move(B,a)=move(C,a)=B \in \{A,B,C\} move(A,a)=move(B,a)=move(C,a)=B∈{A,B,C}
  • m o v e ( A , b ) = m o v e ( C , b ) = C ∈ { A , B , C } move(A,b) = move(C,b) = C \in \{A,B,C\} move(A,b)=move(C,b)=C∈{A,B,C}
  • m o v e ( B , b ) = D ∉ { A , B , C } move(B,b) = D \notin \{A,B,C\} move(B,b)=D∈/{A,B,C}

  由于 AC 和 B 对于不同的符号，转移到的状态子集不同（Ⅰ、Ⅱ），因此将 { A , B , C } \{A,B,C\} {A,B,C} 划分为 2 个子集： { A , C } \{A,C\} {A,C}、 { B } \{B\} {B}

• 目前只有 { A , C } \{A,C\} {A,C}可以再划分，考虑 { A , C } \{A,C\} {A,C}
  m o v e ( A , a ) = m o v e ( C , a ) = B ∈ { B } move(A,a) = move(C,a) = B \in \{B\} move(A,a)=move(C,a)=B∈{B}
  m o v e ( A , b ) = m o v e ( C , b ) = C ∈ { A , C } move(A,b)=move(C,b)=C \in \{A,C\} move(A,b)=move(C,b)=C∈{A,C}
  A 和 C 对于不同的符号，转移到的子集相同，因此不能再划分（AC 是等价的）
  用 $A$代表 { A , C } \{ A,C \} {A,C}

• 最终的状态转换表
  
  化简后的 DFA
  

正规式构造 NFA

规则

• 识别 $r=ϵ$ 的 NFA
  

• 识别 $r=a$ 的 NFA
  

• 识别 $r=a|b$ 的 NFA
  

• 识别 $r=ab$ 的 NFA
  

• 识别 $r={?}^{\ast }$ 的 NFA
  

示例

• 构造正规式 $r=(a|b{)}^{\ast }ab$ 的 NFA

• 首先构造$r=a|b$
  

• 再构造 $(a|b{)}^{\ast }$
  

• 注意到，$(a|b{)}^{\ast }$ 前面不会再有其他符号，因此可以加上开始
  

• $(a|b{)}^{\ast }$ 后面是 $ab$，并且 $ab$ 后面不会再有其他符号
  

3. 语法分析

概念

• 产生式
  $A\to ab$

  • $A$ 可以推出 $ab$
  • 这类似数学中的方程， 但是方向是单向的，即 $A=ab$，$ab\ne A$
  • 形如 $A\to B$ 的式子，称为产生式

• 文法
  文法由一个或多个推导构成

  • 例如

    E -> A
    A -> ab
    A -> ε
    1
    2
    3

• 非终结符
  考虑推导 $A\to ab$，符号 $A$ 可以推导出其他字符，那么 $A$ 被称为非终结符
  在文法中，出现在产生式左侧的，都是非终结符

  • 非终结符一般用大写字母表示
  • S 一般表示开始符号
  • 非终结符有时也用小写单词表示，例如 $expr\to (expr)$，其中 $expr$ 是expression 的缩写

• 终结符
  在文法中，没有在产生式左侧出现过的符号，都是终结符
  顾名思义，终结：到这个符号结束了，不能再继续推导了

  • 考虑文法

    E -> A
    A -> ab
    1
    2

    其中$E$，$A$ 都是非终结符，$a$ 和 $b$ 是终结符
  • 终结符一般用小写字母表示
  • 数字、标点符号、运算符号（$+-\times ÷$）等，一般都是终结符

• 上下文无关文法
  用 G 表示 上下文无关文法
  那么 $G=(V_T{V}_N,S,P)$，其中：

  • $V_T$ 表示终结符（Terminal）

  • $V_N$表示非终结符（Non Terminal）

  • $S$ 表示开始符号（Start）

  • $P$表示产生式（Production）

    上下文无关文法，还可以通过我的另一篇博客了解（点击跳转）

• 句型：从文法的开始符号出发，能够推导出的一切字符串（有限长度）

  • 句子是没有非终结符号的句型

推导

概念

• 文法由一个或多个产生式构成
• 由于产生式可以推导出符号，那么一个文法就对应一个语言（字母表上的串集）
• 推导就是根据文法中的产生式，将非终结符进行替换的过程
• 每次推导，只能使用一个产生式，不能跳步
• 示例
  • 考虑文法

    E -> (E)
    E -> -E
    E -> E + E
    E -> id
    1
    2
    3
    4

  • 可以根据文法推导出 $-(id+id)$
    1. 从 E 出发，根据$E\to -E$，得到 $E\to -E$
    2. 根据 $E\to (E)$，得到 $E\to -(E)$
    3. 根据 $E\to E+E$，得到 $E\to -(E+E)$
    4. 根据 $E\to id$，得到 $E\to -(id+E)$
    5. 根据 $E\to id$，得到 $E\to -(id+id)$

分析树

• 分析树是将推导过程，以树的形式，可视化展现
• 在上一节的示例中，由文法推导出$-(id+id)$的分析树如图

    E -> (E)
    E -> -E
    E -> E + E
    E -> id
  1
  2
  3
  4

  
  注意到，分析树的叶子节点，就是推导出的串

最左推导与最右推导

• 在上一节中，我们可能发现推导过程不唯一，例如分析树处于$E\to E+E$
  此时，两个 $E$都可以使用产生式$E\to id$，并且不会导致推导失败
• 最左推导：每次推导，都替换产生式右侧中，最左侧的非终结符
  $E\to E_1+E_2$（$E_1,E_2$相同，只是用编号区分），选择替换 $E_1$
• 最右推导：每次推导，都替换产生式右侧中，最右侧的非终结符
  $E\to E_1+E_2$（$E_1,E_2$相同，只是用编号区分），选择替换 $E_2$

二义性

• 二义性指的是分析树不唯一（在最左推导或最右推导的情况下）
• 考虑文法

    E -> (E)
    E -> E + E
    E -> E * E
    E -> id
  1
  2
  3
  4

  推导串 $id\ast id+id$
  • 推导1（最左推导）

    E -> E * E
    E -> id * E
    E -> id * E + E
    E -> id * id + E
    E -> id * id + id
    1
    2
    3
    4
    5

  • 推导2（最左推导）

    E -> E + E
    E -> E * E + E
    E -> id * E + E
    E -> id * id + E
    E -> id * id + id
    1
    2
    3
    4
    5

  

消除左递归

左递归

• 直接左递归
  $A\to Aa$
  注意到，产生式右侧的第一个符号，与产生式左侧相同
  那么可以进行无限的推导 $A\to Aa\to Aaa\to ...$

• 间接左递归
  $A\to Ba$
  $B\to Ab$
  如果将第一个产生式中的 $B$ 再进行推导，那么就会得到直接左递归 $A\to Aba$

• 在最左推导中，左递归会导致无限循环，因为每次替换的都是最左侧的非终结符

  我的另一篇博客中有更具体的描述（点击跳转）

消除直接左递归

• 考虑产生式 $A\to Aa|b$（A可以推出$Aa$或$b$）
  

• 如果 A 的推导想要结束，必然是经过了非左递归的推导，即 $A\to b$
  那么我们将 A 的推导重写为 $A\to b{A}^{\prime }$，A'是新引入的符号

• 接下来分析 A' 到底是什么

  • 其实 A' 就是递归部分，$A\to Aa$，每次左递归，都会携带一个 $a$
    所以$A^{\prime }\to a{A}^{\prime }$
  • 结合$A\to b{A}^{\prime }$，有可能 $A$ 以 $A\to b$ 就结束推导，因此 A' 还可以推导出 ε
    所以$A^{\prime }\to a{A}^{\prime }|\epsilon$

• 总结
  对于产生式$A\to A{\alpha }_1|A{\alpha }_2|...|A{\alpha }_m|{\beta }_1|{\beta }_2|...|{\beta }_n$

  1. 消除左递归时，首先将非左递归部分与新符号进行连接
     $A\to {\beta }_1{A}^{\prime }|{\beta }_2{A}^{\prime }|...|{\beta }_n{A}^{\prime }$
  2. 对于新符号，推导出的为左递归部分中的终结符；最后加上一个空串
     $A^{\prime }\to {\alpha }_1{A}^{\prime }|{\alpha }_2{A}^{\prime }|...|{\alpha }_m{A}^{\prime }|ϵ$

消除间接左递归

• 考虑间接左递归

  A -> Ba | b
  B -> Ab
  1
  2

• 将 $A$ 带入第二个产生式，可以得到直接左递归
  $B\to Bab|bb$
• 再将直接左递归消去
  $B\to bb{B}^{\prime }$
  $B^{\prime }\to ab{B}^{\prime }|ϵ$

First 与 Follow 集合

First

介绍

• First(A)
  由 A 可以推导出的所有串中，第一个终结符的集合
• 非终结符才有 First 集合
• 空串属于 First 集合

算法

• 假设产生式 $A\to B$
  • 那么 $First(A)=First(B)$
  • 若有 $B\to C$，那么 $First(A)=First(B)=First(C)$
  • 若有 $B\to c$，那么将 c 加入 $First(A)$

示例

• 考虑文法

  E -> TE'
  E' -> +TE' | epsilon
  T -> FT'
  T' -> *FT' | epsilon
  F -> (E) | id
  1
  2
  3
  4
  5

• 求解 First(E)

  1. 找出 E 为左侧的产生式

     E -> TE'
     1

  2. 产生式右侧的第一个符号是非终结符 $T$，因此 $First(E)=First(T)$，现在求解First(T)
  3. 找出 T 为左侧的产生式

     T -> FT'
     1

  4. 产生式右侧的第一个符号是非终结符 $F$，因此 $First(T)=First(F)$，现在求解First(F)
  5. 找出 F 为左侧的产生式

     F -> (E) | id
     1

  6. 其中 $F\to (E)$ 的第一个符号是非终结符，因此将(加入$First(F)$；$F\to id$ 的第一个符号是非终结符，因此将id加入 $First(F)$

  因此 $First(E)=First(T)=First(F)=\{(,id\}$

• 注意到，求解 First 集合是一个递归的过程

• 该文法各终结符的 First 集合

  非终结符	First集合
  E	(,id
  E’	+,epsilon
  T	(,id
  T’	+,epsilon
  F	(,id

Follow

介绍

• Follow 集合相较于 First 集合更复杂，集合的元素是可以跟在非终结符后的终结符
• Follow(A)
  可以跟在 A 后的终结符
• Follow 集合不包括空串
• Follow 集合的计算，会用到 First 集合

为什么要有 Follow 集合

• 考虑文法

  S -> aBC
  B -> bB
  B -> epsilon
  C -> a
  C -> d
  1
  2
  3
  4
  5

• 分析串abd

  中间句子	产生式
  S	S -> aBC
  aBC	B -> bB
  abBC	B -> epsilon
  abC	C -> d
  abd	ACCEPT

• 其中，第 3 步使用了 B 的 epsilon 产生式（$B\to epsilon$）

  • 能否使用，主要看 B 的后面跟着哪些符号（Follow集合），B 的后面是 C，而 C 可以转化为 a 或 d
  • 因为 ab 已经匹配成功了，B 当前要匹配的符号是 d，属于 B 后面紧跟的字符，因此 B 可 以转化为 epsilon
  • 假设当前要匹配的符号是 e，此时不能（没必要）使用 B 的 epsilon 产生式，因为即使转化了 B，后续也无法匹配成功，应该在 B 这一步就拒绝这个句子

算法

• Follow集合中，不允许出现 epsilon

• 每一次 Follow 集元素的增加，若跟产生式左侧有关，都是左侧添加到产生式右侧

1. Follow(S) 添加 $

2. 对于每一条产生式，对于产生式右侧

   • 对于产生式右侧的非终结符 B，若其右侧存在非终结符 C，将First(C) 添加到 Follow(B)

     A -> BC

   • 若 C 可以推出 epsilon，将Follow(A) 添加到 Follow(B)

     A - > BC

     C - > epsilon

   • 将 Follow(A) 添加到 Follow(C)
A -> C

   • 若最右侧存在终结符α，且终结符左侧存在非终结符B，将α添加到Follow(B)

     A -> Bα

3. 回到步骤2.

   若过程中有Follow集发生变化，则继续执行步骤2

   否则结束

示例

• 考虑文法

  E -> TE'
  E' -> +TE' | epsilon
  T -> FT'
  T' -> *FT' | epsilon
  F -> (E) | id
  1
  2
  3
  4
  5

• 最终结果

  符号	First	Follow
  E	( , id	$，)
  E’	+, epsilon	$，)
  T	( , id	+，$，)
  T’	*, epsilon	+，$，)
  F	( , id	*，+，$，)

• 分析第一个产生式E -> TE'

• E 本身是一个句型，Follow集中添加 $

• T 的Follow集添加 E’ 的 First集：+，epsilon

• 由于 E’ 可以推出 epsilon，所以 E 的Follow集添加到 T 的Follow集

• E’ 是产生式的最后一个字符，因此可以跟在 E 后的符号，也可以跟在 E’ 后，将 E 的Follow集添加到 E’ 的Follow集

• 对于第二个产生式E' -> +TE' | epsilon，TE’ 的位置与第一个产生式相同，跳过

• 分析第三个产生式T -> FT'

• T 本身是一个句型，Follow集中添加 $

• F 的Follow集添加 T’ 的 First集：*

• 由于 T’ 可以推出 epsilon，所以 T 的Follow集添加到 F 的Follow集

• T’ 是产生式的最后一个字符，因此可以跟在 T 后的符号，也可以跟在 T’ 后，将 T 的Follow集添加到 T’ 的Follow集

• 分析第四个产生式：T' -> *FT' | epsilon，FT’ 的位置与第三个参数是相同，跳过

• 分析第五个产生式：F -> (E) | id

• F 本身是一个句型，Follow集中添加 $

• 推出的式子中，非终结符 E 的右侧为 )，添加到到 E 的Follow集中

处理Follow集的依赖关系

• 第一个产生式E -> TE'

• E’ 依赖 E，因此将 E 的Follow集添加到 E’ 的Follow集

• E‘ 可以推出 epsilon，T 依赖 E，将 E 的Follow集添加到T的Follow集

• 对于第二个产生式E' -> +TE' | epsilon，TE’ 的位置与第一个产生式相同，跳过

• 分析第三个产生式T -> FT'

• T’ 依赖 T，将 T 的 Follow集添加到 T’ 的Follow集

• T’ 可以推出 epsilon，F 依赖 T，将 T 的Follow集添加到 F 的Follow集

• 分析第四个产生式：T' -> *FT' | epsilon，FT’ 的位置与第三个参数是相同，跳过

• 分析第五个产生式：F -> (E) | id，没有依赖关系

结束

自上而下分析

LL(1)文法

定义

• LL(1)
  • 第一个 L 表示：分析时从左到右扫描串
  • 第二个 L 表示：最左推导
  • 1 表示：每次只向右看一个符号

构建预测分析表

介绍

• LL(1) 对输入串进行分析，是根据预测分析表进行的

• select 集合

  • select(A) ：A 可以接收什么样的输入符号
  • 对于每一个产生式A -> BC，select 集合为：
    • 若 B 是终结符，那么 select(A -> BC) = B
    • 若 B 是非终结符，那么 select(A -> BC) = First(B)
    • 若 BC 为 epsilon，那么 select(A -> BC) = Follow(A)

• 预测分析表的组成

  • 表头
    由非终结符和输入符号构成
  • 行列
    每一行的每一列对应非终结符（行）接收到不同符号（列）的反应

• 一个预测分析表，看起来是这样
  

算法

• 在每个终结符对应的行，select 集合对应的列，填上对应的产生式

示例

• 考虑文法

  E -> TE'
  E' -> +TE' | epsilon
  T -> FT'
  T' -> *FT' | epsilon
  F -> (E) | id
  1
  2
  3
  4
  5

• 计算 First 与 Follow 集合

  符号	First	Follow
  E	( , id	$，)
  E’	+, epsilon	$，)
  T	( , id	+，$，)
  T’	*, epsilon	+，$，)
  F	( , id	*，+，$，)

• 对于文法中的每一个产生式，若有选择，进行分解

  例如：E' -> +TE' | epsilon

  E' -> +TE'
  E' -> epsilon
  1
  2

• 本例中的分析表

  分解后的文法

  E -> TE'
  E' -> +TE' 
  E' -> epsilon
  T -> FT'
  T' -> *FT' 
  T' -> epsilon
  F -> (E) 
  F -> id
  1
  2
  3
  4
  5
  6
  7
  8

  非终结符 \ 输入符号	id	+	*	(	)	$
  E	E -> TE’			E -> TE’
  E’		E’ -> +TE’			E’ -> epsilon	E’ -> epsilon
  T	T -> FT’			T -> FT’
  T’		T’ -> epsilon	T’ -> *FT’		T’ -> epsilon	T’ -> epsilon
  F	F -> id			F -> (E)

  • 从非终结符 E推导的产生式有：

    E -> TE'
    1

    其中，输入符号为 First(T) = { id, ( }

    那么 E 这一行，对应输入符号的列id, ( 就填上该产生式

    非终结符 \ 输入符号	id	+	*	(	)	$
    E	E -> TE’			E -> TE’

  • 从非终结符E'推导的产生式有：

    E' -> +TE' 
    E' -> epsilon
    1
    2

    1. E' -> +TE' ，输入符号为 +

       那么 E' 这一行，对应输入符号的列+ 就填上该产生式

       非终结符 \ 输入符号	id	+	*	(	)	$
       E’		E’ -> +TE’

    2. E' -> epsilon，输入符号为Follow(E') = { ), $ }

       那么 E' 这一行，对应输入符号的列), $ 就填上该产生式

       非终结符 \ 输入符号	id	+	*	(	)	$
       E’					E’ -> epsilon	E’ -> epsilon

  • 其余非终结符的推导同理

非递归的预测分析

• 有分析表

  非终结符 \ 输入符号	id	+	*	(	)	$
  E	E -> TE’			E -> TE’
  E’		E’ -> +TE’			E’ -> epsilon	E’ -> epsilon
  T	T -> FT’			T -> FT’
  T’		T’ -> epsilon	T’ -> *FT’		T’ -> epsilon	T’ -> epsilon
  F	F -> id			F -> (E)

• 预测分析器接收输入句子：id * id + id

  1. 先将 $ 与 开始符号E压入栈，将句子连接$作为输入

     栈	输入	输出
     $E	id * id + id $

  2. 弹出栈顶元素 E，输入队列的队头id，在分析表中对应的产生式为：E -> TE'，输出为TE'

     栈	输入	输出
     $	id * id + id $	E -> TE’

     将 TE' 逆序入栈

     栈	输入	输出
     $E’T	id * id + id $

  3. 弹出栈顶元素 T，输入队列的队头id，在分析表中对应的产生式为：T -> FT'，输出为FT'

     栈	输入	输出
     $E’	id * id + id $	T -> FT’

     将 FT'逆序入栈

     栈	输入	输出
     $E’T’F	id * id + id $

  4. 弹出栈顶元素 F，输入队列的队头id，在分析表中对应的产生式为：F -> id'，输出为id'

     栈	输入	输出
     $E’T’	id * id + id $	F -> id

     将 id 逆序入栈

     栈	输入	输出
     $E’T’id	id * id + id $

     此时栈顶与队头相同，弹出栈顶与队头

     栈	输入	输出
     $E’T’	* id + id $

  5. 以此类推，每当栈顶为终结符时，与输入队列队头对比，若相同，弹出栈顶与队头

     若栈顶与队头不同，或栈顶无队头对应的输入，则拒绝该语句

• 完整的预测分析过程
  

• 根据输出，可以画出分析树
  

自下而上分析

概念

• 归约
  将产生式右侧的串，替换成产生式左侧的非终结符

  • 产生式：S -> ab
    若有串ab，则可以将ab归约成S

• 句柄 ：句型中，与产生式右侧相等的子串（可以被归约的串），并且该归约是最右推导中逆过程的一步

  最右推导：任何一次推导，都是对产生式最右侧的非终结符进行替换
  句型：从文法的开始符号出发，能够推导出的一切字符串（有限长度）

  • E -> E * E | E + E

    对于句型E * E + E，E + E 是该句型的句柄

    • 为什么E * E不是？

      因为E -> E + E 是句型中最右推导逆过程的一步，若先归约E * E，则不满足最右推导的要求

移进-归约分析

算法

• 若栈内没有符号，输入队列队头移入栈
• 若栈顶的串可以被文法的某个产生式归约，则进行归约
• 若栈顶的串无法被文法的某个产生式归约，输入队列队头移入栈

示例

• 考虑文法

  E -> E + E
  E -> E * E
  E -> (E)
  E -> id
  1
  2
  3
  4

• 分析过程
  输入中 $i{d}_i$ 都表示$id$，只是用下标进行区分

  栈	输入	动作
  $	id1 * id2 + id3 $	移进
  $ id1	* id2 + id3 $	按 E -> id 归约
  $ E	* id2 + id3 $	移进
  $ E *	id2 + id3 $	移进
  $ E * id2	+ id3 $	按 E -> id 归约
  $ E * E	+ id3 $	移进
  $ E * E +	id3 $	移进
  $ E * E + id3	$	按 E -> id 归约
  $ E * E + E	$	按 E -> E + E
  $ E * E	$	按 E -> E * E
  $ E	$	ACCEPT

冲突

移进-归约冲突

• 考虑文法

  E -> E + E
  E -> E + E + id
  E -> id
  1
  2
  3

• 输入串为id + id + id

  栈	输入	动作
  $	id + id + id $	移进
  $ id	+ id + id $	按 E -> id 归约
  $ E	+ id + id $	移进
  $ E +	id + id $	移进
  $ E + id	+ id $	按 E -> id 归约
  $ E + E	+ id $	冲突

  对于栈$ E + E和输入+ id $有两种选择，发生冲突

  1. 对于栈顶串E + E，可以按E -> E + E进行归约
  2. 输入 + id 移入栈，先按 E -> id 归约，再按E -> E + E + id 归约

  这种不确定性可能会导致某种选择分析失败

归约-归约冲突

• 归约冲突的例子不是很好举
• 假设有产生式 $E\to X$， $E\to YX$
  当栈顶是 $YX$时，会有归约-归约冲突
• 假设有产生式 $E\to X$， $T\to X$
  当栈顶是 $X$ 时，会有归约-归约冲突

LR 分析器

介绍

• LR 分析器

  • 第一个 L 表示从左到右扫描串
  • 第二个 R 表示最右推导

• LR 分析算法需要借助分析表，分析表的构建方式有多种，但是分析方法是一样的

LR 分析算法

• 考虑文法

$$E\to E+T\text{\hspace{1em}(1)}$$

$$E\to T\text{\hspace{1em}(2)}$$

$$T\to T\ast F\text{\hspace{1em}(3)}$$

$$T\to F\text{\hspace{1em}(4)}$$

$$F\to (E)\text{\hspace{1em}(5)}$$

$$F\to id\text{\hspace{1em}(6)}$$

• 分析表

  状态	id	+	*	(	)	$	E	T	F
  0	s5			s4			1	2	3
  1		s6				acc
  2		r2	s7		r2	r2
  3		r4	r4		r4	r4
  4	s5			s4			8	2	3
  5		r6	r6		r6	r6
  6	s5			s4				9	3
  7	s5			s4					10
  8		s6			s11
  9		r1	s7		r1	r1
  10		r3	r3		r3	r3
  11		r5	r5		r5	r5

  • 分析表中符号的含义
    1. sj：将当前符号和状态j移入栈
    2. rj：将栈顶串按第j个产生式进行归约
    3. acc：接收
    4. 空白：拒绝输入串

• 对于输入串 $i{d}_1\ast i{d}_2+i{d}_3$，LR 的非递归预测过程如下图
  

  • $action[0,id]=s_5$，即状态 0 （栈顶）对应的行，id （输入队列队头）对应的列的值，表示移进符号 $id$，同时移入状态 5

活前缀

1. 该前缀是某个产生式右部的前缀
2. 活前缀是句柄的子集

• 示例
  有产生式 $A\to BCD$
  有串 $B$，$BC$，$BCD$ 都是活前缀，而 $BCDE$ 不是

构建分析表的前置知识

• 拓广文法

  设文法的开始符号为S，添加S' -> S

  • 为什么要引入拓广文法？

    • 考虑文法：

      E -> E + E
      E -> E * E
      E -> id
      1
      2
      3

    • 显然，该文法的开始符号为 E，若成功分析输入串，则必然由某条产生式归约到E

      但是，该文法有 3 条产生式都能够归约到E，这样接收状态对应的产生式就不确定

    • 若引入了E' -> E，则接收状态对应的产生式是唯一确定的

• LR(0)项目

  • 简称项目

  • 在产生式的右侧的某个位置加·

  • 考虑产生式：A -> XYZ

    共有 4 个项目

    A -> ·XYZ
    A -> X·YZ
    A -> XY·Z
    A -> XYZ·
    1
    2
    3
    4

• 项目集

  由多个项目组成的集合，一般用符号I表示

• 后继项目

  • 后继指的是·的出现位置向右移动一位
  • 考虑项目A -> ·XY
  • 该项目的后继项目为：A -> X·Y

• 归约项目

  若项目的·在产生式的最右侧，则称该项目为归约项目
  例如A -> XY·

• closure(I)

  • 项目集 I 的闭包

  • 构造规则

    1. 初始时，I 中的每一个项目都加入closure(I)

    2. 若I 中有形如A -> α·B的项目，将所有 B 的产生式 B -> ·C添加到closure(I)

       若C为非终结符，则将 C -> ·D 添加到closure(I)

       有点类似求 FIrst 集合这是一个递归的过程

• goto(I, X)

  • I ：项目集

  • X ：文法符号

  • 对于项目集 I中的每一个项目，输入文法符号 X 后的产生项目

    • 能否输入符号X：项目中·右侧的符号是否为X

    • 考虑项目：A -> ·BC，输入符号 C 无法产生任何项目

    • 考虑项目：A -> ·BC，输入符号 B 产生的项目为：B·C

• 项目集的规范族

  • 是一个项目集：核心项目 + 非核心项目
  • 核心项目：项目集的初始项目
  • 非核心项目：由核心项目经过colsure闭包得到的项目
  • 项目集的规范族内的所有项目，是等价的

项目集规范族求解

• 考虑文法

  E' -> E
  E -> E + T
  E -> T
  T -> T * F
  T -> F
  F -> (E)
  F -> id
  1
  2
  3
  4
  5
  6
  7

• I0表示初始项目集

  • 核心项目：E' -> ·E

  • 添加closure({E' -> ·E})

    E -> ·E + T
    E -> ·T
    T -> ·T * F
    T -> ·F
    F -> ·(E)
    F -> ·id
    1
    2
    3
    4
    5
    6

  • I0最终为：

    E' -> ·E
    E -> ·E + T
    E -> ·T
    T -> ·T * F
    T -> ·F
    F -> ·(E)
    F -> ·id
    1
    2
    3
    4
    5
    6
    7

• I1

  • I0可能的输入有：E, T, F, (, id

  • 其中 E 尚未作为I0的输入

  • I1 的核心项目为goto(I0, E) ，有：

    E' -> E·
    E -> E· + T
    1
    2

    其他的产生式都无法输入 E，例如E -> ·T，只能输入T

  • 核心项目的闭包为空

    1. E' -> E·，·的右侧为空
    2. E -> E· + T，·的右侧为终结符+

  • I1最终为：

    E' -> E·
    E -> E· + T
    1
    2

• I2

  • I0可能的输入有：E, T, F, (, id

  • 其中 T 尚未作为I0的输入

  • I2 的核心项目为goto(I0, T) ，有：

    E -> T·
    T -> T· * F
    1
    2

  • 核心项目的闭包为空

  • I2最终为：

    E -> T·
    T -> T· * F
    1
    2

• I3

  • I0可能的输入有：E, T, F, (, id

  • 其中 F 尚未作为I0的输入

  • I3 的核心项目为goto(I0, F)，有：

    T -> F·
    1

  • 核心项目的闭包为空

  • I3最终为：

    T -> F·
    1

• I4

  • I0可能的输入有：E, T, F, (, id

  • 其中(尚未作为I0的输入

  • I4 的核心项目为goto(I0, ( )，有：

    F -> (·E)
    1

  • 核心项目的闭包为：

    E -> ·E + T
    E -> ·T
    T -> ·T * F
    T -> ·F
    F -> ·(E)
    F -> ·id
    1
    2
    3
    4
    5
    6

  • I4最终为：

    F -> (·E)
    E -> ·E + T
    E -> ·T
    T -> ·T * F
    T -> ·F
    F -> ·(E)
    F -> ·id
    1
    2
    3
    4
    5
    6
    7

• I5

  • I0可能的输入有：E, T, F, (, id

  • 其中id尚未作为I0的输入

  • I4 的核心项目为goto(I0, id)，有：

    F -> id·
    1

  • 核心项目的闭包为空

  • I5最终为：

    F -> id·
    1

• I6

  • I1可能的输入有：+

  • 其中+尚未作为I1的输入

  • I6的核心项目为goto(I1, +)，有：

    E -> E +· T
    1

  • 核心项目的闭包为：

    T -> ·T * F
    T -> ·F
    F -> ·(E)
    F -> ·id
    1
    2
    3
    4

• 接下来考虑I2可能的输入

  需要注意的是，若I7与求出的I完全相同，那么视为无状态转换

• 若考虑完所有的 I，都没有状态转换，那么结束

• 最终的项目集规范族
  

构建 SLR 预测分析表

• 根据前面提到的，预测分析表应该如图
  

• 根据构建的项目集规范族，可以画出一个状态转换图
  

  • 项目集 $I_i$

    • 若 $A\to a\cdot b$ 在 $I_i$ 中，且 $goto(I_i,b)=I_j$，那么 $action[i,a]=s_j$
    • 若 $A\to a\cdot$ 在 $I_i$ 中，那么 $Follow(A)$ 中的所有符号 $k$，$action[i,k]=r_j$，$j$ 是产生式 $A\to a$ 的编号
    • 若 $S^{\prime }\to S$ 在 $I_i$ 中，那么 $$action[i,\$]=acc$$
    • 若 $A\to a\cdot B$ 在 $I_i$ 中，并且 $goto(I_i,B)=j$，那么 $goto[i,B]=j$

  • I0 输入 E 到 I1 ，E 是非终结符，因此I0 行， E 列，就应该填 1（从 0 转移到 1）

  • I0 输入 ( 到 I4，I4 中没有归约状态，因此 I0 行 ( 列，填 $s_4$

  • I2 中有 $E\to T\cdot$，因此 F o l l o w ( E ) = { + , ) , ＄ } Follow(E) = \{+, ), ＄ \} Follow(E)={+,),＄} 对应的元素 $k$，$action[2,k]=r_2$，2 是 $E\to T$ 的编号

  • 状态转换图中，没有指向其他状态的状态，都是归约状态

• 最终的预测分析表
  

构建规范的 LR 分析表

引言

• 考虑文法

  S -> V = E
  S -> E
  V -> * E
  V -> id
  E -> V
  1
  2
  3
  4
  5

  • 构建的 SLR 分析表中，action[2, =] = s6，且 Folllow(E) 包含 = ，使得 action[2, =] = r5

    那么状态 2 遇到 = 有 2 种动作，这种不确定性可能导致分析失败

• 移进归约冲突的原因
  

  对于项目A -> α·，SLR 分析会将 action[i, Follow(A)] 按照 rj 进行归约，i 为当前项目集的编号，j 为A -> α的编号

  • 但是观察分析树，第一层的V = E，E 只有遇到 $ 时，才会按照S -> V = E进行归约
  • 而 E 的 Follow 集合中还有 =，按照 SLR 分析action[i, =] = rj，这就会导致不应该的归约
  • 换言之，归约时后继符号集合只是 Follow 集合的子集

LR(1) 项目

• 考虑文法

  S -> V = E
  S -> E
  V -> * E
  V -> id
  E -> V
  1
  2
  3
  4
  5

• 最右侧的叶子节点V归约成E时，只有遇到$才会进行E -> V·归约（自下而上分析）

  • 将项目E -> V· 改写为E -> V·,$
  • 该项目表示，只有遇到$时，才能将栈顶的V归约成E
  • 同理有：E -> v,=

• 规范 LR（1）项目定义为
  $$A\to \alpha \cdot \beta ,a$$

  • a：展望符（也叫搜索符）

    • 只有β = ε时，遇到 a 才能按照A -> α进行归约
    • 当β ≠ ε 时，a 没用

等价 LR（1）项目

• $A\to \alpha \cdot B\beta ,a$

• $B\to \cdot \gamma ,b$

• 其中 b 为 $B\to \gamma$ 的展望符

• $b=First(\beta )$

• 而$\beta$ 有可能是 $ϵ$，因此 $b=First(\beta a)$

• 当 $\beta \to ϵ$ 时，$b=a$称为继承的后继符，否则叫自生的后继符

LR（1）项目集规范族

• 考虑文法
  $$S^{\prime }\to S\text{\hspace{1em}(0)}$$

  $$S\to L=R\text{\hspace{1em}(1)}$$

  $$S\to R\text{\hspace{1em}(2)}$$

  $$L\to \ast R\text{\hspace{1em}(3)}$$

  $$L\to id\text{\hspace{1em}(4)}$$

  $$R\to L\text{\hspace{1em}(5)}$$

• I0
  $$S^{\prime }\to \cdot S,\$$$

  $$S后为空串，那么由S推出的产生式中，展望符继承S^{\prime }\to \cdot S,\$的展望符$$

  $$S\to \cdot L=R,\$$$

  $$S\to \cdot R,\$$$

  $$S\to \cdot L=R,\$中，\cdot 后为L，而L后的第一个终结符为=，所以由L推出的产生式，展望符为=$$

  $$L\to \cdot \ast R,=$$

  $$L\to \cdot id,=$$

  $$R后为空串，由R推出的产生式中，展望符继承S\to \cdot R,\$的展望符$$

  $$R\to \cdot L,\$$$

  $$L后为空串，由L推出的产生式中，展望符继承R\to \cdot L,\$的展望符$$

  $$L\to \cdot \ast R,\$$$

  $$L\to \cdot id,\$$$

• I1

  I0输入S
  $$S^{\prime }\to S\cdot ,\$$$

• I2

  I0输入L

  S -> ·L=R,$
  R -> ·L,$
  1
  2

  $$\cdot 移动一位称为后继项目，后继项目的展望符继承自原项目$$

  $$S\to L\cdot =R,\$$$

  $$R\to L\cdot ,\$$$

• I3

  I0输入R
  $$S\to R\cdot ,\$$$

• I4

  I0输入*
  $$L\to \ast \cdot R,=$$

  $$L\to \ast \cdot R,\$$$

  $$R后是\$，R推出的产生式的展望符继承L\to \ast \cdot R,=的展望符$$

  $$R\to \cdot L,=$$

  $$R后是\$，R推出的产生式的展望符继承L\to \ast \cdot R,\$的展望符$$

  $$R\to \cdot L,\$$$

  $$L后面是空串，L推出的产生式继承R\to \cdot L,=、R\to \cdot L,\$的展望符$$

  $$L\to \cdot \ast R,=$$

  $$L\to \cdot id,=$$

  $$L\to \cdot \ast R,\$$$

  $$L\to \cdot id,\$$$

• I5

  I0输入id
  $$L\to \cdot id,=$$

  $$L\to \cdot id,\$$$

• I6

  I2输入=
  $$S\to L=\cdot R,\$$$

  $$R后面是空串，R推出的产生式继承S\to L=\cdot R,\$的展望符$$

  $$R\to \cdot L,\$$$

  $$L后面是空串，L推出的产生式继承R\to \cdot L,\$的展望符$$

  $$L\to \cdot \ast R,\$$$

  $$L\to \cdot id,\$$$

• I7

  I4输入R
  $$L\to \ast R\cdot ,=$$

  $$L\to \ast R\cdot ,\$$$

• I8

  I4输入L
  $$R\to L\cdot ,=$$

  $$R\to L\cdot ,\$$$

• I9

  I6输入R
  $$S\to L=R\cdot ,\$$$

• I10

  I6输入L
  $$R\to L\cdot ,\$$$

• I11

  I6输入*
  $$L\to \ast \cdot R,\$$$

  $$R\to \cdot L,\$$$

  $$L\to \cdot \ast R,\$$$

  $$L\to \cdot id,\$$$

• I12

  I6输入id
  $$L\to id\cdot ,\$$$

• I13

  I11输入R
  $$L\to \ast R\cdot ,\$$$

求解项目集规范族（手写）

• 考虑文法

  S' -> S
  S -> BB
  B -> bB
  B -> a
  1
  2
  3
  4

构建预测分析表

• 根据项目集规范族，得到状态转换图
  
• 状态转换图中，没有指向其他状态的状态，都是归约状态
• 预测分析表
  

构建 LALR 分析表

• 考虑文法

  S' -> S
  S -> BB
  B -> bB | a
  1
  2
  3

• 规范 LR 的项目集规范族，得到状态转换图
  

• 考虑两个相似的项目集合
  $$B\to a\cdot ,b|a\text{\hspace{1em}(I4)}$$

  $$B\to a\cdot ,\$\text{\hspace{1em}(I7)}$$

  这两个项目集合除了展望符（搜索符）不同以外，其余都是相同的

  • 只有展望符不同的项目称为：同心项目

• 可以将同行项目进行合并，例如合并 I4 和 I7，命名为 I47
  $$B\to a\cdot ,b|a|\$$$
  转换图中，原先到达I4或I7的，现在都转移到I47

• 找到所有的同心集
  

• 对同心集进行合并
  

• 状态转换图中，没有指向其他状态的状态，都是归约状态

• 构建预测分析表
  

• 冲突

  • 同心集的合并不会引起新的移进-归约冲突
  • 同心集的合并有可能产生新的归约-归约冲突

4.语法制导翻译

回顾概念

• 编译的几个阶段

  1. 词法分析
  2. 语法分析
  3. 语义分析
  4. 中间代码生成
  5. 代码优化
  6. 目标代码生成
  • 语义分析和中间代码生成可以同时进行，称为语义翻译
  • 语法分析、语义分析、中间代码生成可以同时进行，称为语法制导翻译

• 句子：属于该语言的串

• 语法分析树

  • 考虑文法

    E -> E + T
    E -> id
    T -> id
    1
    2
    3

  • 分析句子 $id+id$
    

    语法分析树是针对分析过程的，语法树是针对串的

概念

• SDD

  语法制导定义（Syntax-Directed Definition）

• 语法制导翻译

  仅用语法分析对源代码进行翻译

• 语法制导

  带属性和语义规则的上下文无关文法

  • 每个文法符号都有一组属性

    例如文法符号 S，S 可能有 name，val 属性，等等。

    这些属性名（name、val，等等）都是自定义的

  • 每个产生式有一组语义规则

    例如产生式E -> E + T

    • 这样的产生式只是符号的推导，没有任何意义，并且+只是个符号，不一定是数学中的加法

    • 但是如果定义一组语义规则，例如E.val = E.val + T.val

      那么这个产生式的语义就是：将 E 的 val 属性和 T 的 val 属性相加，再赋值给 E 的 val 属性

• 综合属性

  • 在语义规则中，产生式左侧的属性是由产生式右侧的属性通过某种计算得到的

  • 体现在语法分析树中，就是产生式左侧符号的属性，只能通过子节点或自身经过某种计算得到
    
    $E_1$ 和 $E$ 是同一个东西，只是用 $E_1$ 来区分计算顺序

• 继承属性

  • 在语义规则中，产生式右侧的属性是由该符号左侧的符号通过某种计算得到的
  • 在语法分析树中，产生式右侧符号的属性，只能通过父节点、兄弟节点、本身 经过某种计算得到
    
    所以 in 是 L 的继承属性

• 定义终结符的属性为：综合属性

  终结符是无法作为产生式左侧符号的，终结符的值由词法分析器提供

• 判断一个属性是继承属性还是综合属性

  只要看这个属性来自产生式左侧还是右侧即可，来自左侧是综合，来自右侧是继承

• 副作用

  语义规则不是表达式，而是一些其他功能，例如打印

• 属性文法

  一个没有副作用的文法称为属性文法

• 注释分析树：每个节点的属性值都标出出来

  例如：
  

• 如果一条语义规则的作用和求值无关，如打印一个值或向符号表中添加记录，则成为产生式左侧非终结符的虚拟综合属性

• 语法树
  

  语法分析树是针对分析过程的，语法树是针对串的

SDD 示例

只有综合属性的文法

• 考虑 SDD
  
• 分析串
  

带有继承属性的文法

• 考虑 SDD
  

  • addtype(param1, param2)

    • 创建一个属性 param1，属性值为 param2
    • 是 L （产生式左侧）的虚拟综合属性

• 分析串
  
  
  (4)是一个继承属性
  L 使用到了自身、子节点id

属性依赖图

引入

• 考虑 SDD
  

• 分析串 $inti{d}_1,i{d}_2,i{d}_3$
  

  • 如果只看语法分析树，会发现，分析过程是完全自上而下的

  • 但是如果考虑属性值，则并非如此

    • 自下而上

      T -> int，将 int（integer） 赋值给了 T.type

    • 兄弟节点

      D -> TL， T.type赋值给L.in，那么就要求 T.type 先计算出来

    • 自上而下

      L -> L1 , id，将 L.in 赋值给 L1.in，那么就要求 L1.in 先计算出来

• 分析树上属性的计算有依赖关系，可以用依赖图（有向图）来表示

• 依赖图本质上是一个拓扑图

示例

• 考虑 SDD
  
• 注释分析树
  
• 属性依赖图
  

  • 综合属性写在符号的右边

  • 继承属性写在符号的左边

  • 属性的编号，从小到达，表示先后顺序

  • 顺序并不是固定的

    • 例如1, 2, 3, 4是没有依赖关系的，因此可以任意替换顺序

    • 4, 5 显然不能替换顺序，因为 L.in = T.type，5 是依赖 4 的

    • 6 （addType(id.entry, L.in)）是有多个依赖项的

      前面提到，这种非表达式的属性，称为副作用，也叫虚拟综合属性

      addType这个操作需要 id.entry 和 L.in，因此 6 是依赖 3 和 5 的

S 属性 与 L 属性

• S 属性定义

  • 仅使用综合属性的 SDD

  • 如果一个 SDD 是 S 属性的，那么可以根据语法树的任何 自底向上 顺序来计算属性值

• L 属性定义

  • 依赖图的边可以从左到右，但是不能从右到左

  • 若一个SDD是L属性定义的，那么它的每个属性有 2 种情况

    1. 是综合属性

    2. 对于产生式 $A\to X_1{X}_2...X_i{X}_{i+1}...$
       其中 Xi 的继承属性只依赖A的继承属性或X1 ~ Xi，并且 Xi 的全部属性不能在依赖图中形成环

       • 若可以依赖 A 的综合属性，那么 A 有可能依赖 Xi 的继承属性，若 Xi 的继承属性依赖 A 的综合属性，就会成环
         

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

  综合属性定义，产生式左侧的依赖产生式右侧的属性，也就是依赖图的边从左到右

翻译方案

介绍

• 语法制导翻译SDT（Semantic Directed Translation）

• 翻译方案中，将语义规则改了个名字，叫语义动作

  将语义动作写在{}内，并插入到产生式右侧

• 对于综合属性，语义动作插入到产生式最右侧

• 对于继承属性，语义动作插入到该符号的左侧

示例

• 考虑 SDD
  
  • 翻译方案
    
  • $S\to B$ 对应的翻译方案是 S → { B . p s = 10 } B { S . h t = B . h t } S \to \{B.ps=10\}B\{S.ht=B.ht\} S→{B.ps=10}B{S.ht=B.ht}
    • B.ps 是继承属性，因此要写在 B 的左侧，而 S.ht 是综合属性，要写在产生式的最右侧
    • 注意到图片中翻译方案有换行，和写道一行是同一个意思

自下而上计算

代码段翻译

• 语法制导翻译中，不仅要分析输入串，分析过程中，还要执行相应的语义动作。语义动作中，一般会设计属性的计算，因此属性也需要保存在栈中

• 示例

  • 考虑产生式 $E=E_1+T$，该产生式的语义规则是 $E.val=E_1.val+T.val$
  • 假设栈中有 $E_1+T$，那么应该是这样
    
  • 要保存属性，由于属性只有一个 val，可以简化一下，属性栈就是 val 栈
    那么，当 $E_1+T$ 归约成 $E$ 时，$E.val=stack[top].val+stack[top-2].val$
    其中，$stack[top]$ 就是 T，而 $stack[top-2]$ 就是 $E_1$

• 形如 $E\to T$ 的产生式，语义规则只要不是副作用，代码段可以省略
  因为 $E.val=T.val$ 这种语义规则，翻译成代码段就是 $stack[top].val=stack[top].val$，没有改变值，因此可以忽略

• 示例

  • 考虑SDD
    
  • 翻译代码段
    

S属性的自下而上计算

• 考虑SDD
  

• 翻译代码段
  

• S 属性自下而上计算，需要用到 LR 分析器，这里选用 SLR
  进行 SLR 分析后，预测表如图
  

• 与 LR 分析不同的是，S 属性定义的计算中，多出了状态栈

  但由于 SDD 中，只有一个 val 属性，因此将状态栈简化为 val 栈

• 分析输入串 $digit+digit$，其中词法分析器的输入为 $1，2$，即 $1+2$
  

• 对于每一个移进状态，将输入串同时移入 stack 栈和 val 栈

• 对于每一个归约状态

  考虑代码段，代码段主要对应 val 栈

  • 若是 $E\to T$ 这类无对应代码段的产生式
    • stack 栈弹出右侧符号数量的 2 倍，考虑栈顶状态对产生式左侧符号的 goto，将产生式左侧移入 stack，并将 goto 移入 stack
      • 预测分析过程的第二行，根据分析表，状态 1 对应的行， + 对应的列 的条目值是 $r_7$，即根据 $F\to digit$ 进行归约
      • 此时栈中有元素 $0digit1$，弹出 $F\to digit$ 符号数量的 2 倍（$len(digit)\times 2=1\times 2$），并且 $F$ 入栈，栈中还剩下 $0F$
      • $goto(0,F)=4$，因此 $4$ 入栈，栈中剩下 $0F4$ （分析过程的第三行）
    • val stack 则不需要任何操作，因为没有代码段
  • 若是 $E\to E+T$ 这类有代码段的产生式
    • 解析对应的代码段：$val[top-2]=val[top]+val[top-2]$，$result=val[top-2]$
    • 弹出 val 栈中产生式右侧符号数量的 1 倍，并将 result 入栈

L 属性的自上而下计算

• 考虑 SDD
  

• SDD中存在左递归（如$E\to E+T$ 出现了左递归），而自上而下分析处理不了左递归，因此先消去左递归

  L -> En
  E -> TR
  R -> +TR
  R -> epsilon
  T -> FM
  M -> *FM
  M -> epsilon
  F -> (E)
  F -> digit
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 语法制导翻译方案 SDT

  L -> En {print(E.val)}
  E -> T {R.i = T.val} R {E.val = R.s}
  R -> +T {R1.i = R.i + T.val} R {R.s = R1.i}
  R -> epsilon {R.s = R.i}
  T -> F {M.i = F.val} M {T.val = M.s}
  M -> *F {M1.i = M.i * F.val} M {M.s = M1.i}
  M -> epsilon {M.s = M.i}
  F -> (E) {F.val = E.val}
  F -> digit {F.val = digit.lexval}
  1
  2
  3
  4
  5
  6
  7
  8
  9

  • R.i：R之前的表达式的值
  • R.s：分析完 R 后的值
  • M 同理

  

• 求解 First, Follow 集合

  符号	First	Follow
  L	(, digit	$
  E	(, digit	$, )
  R	+, epsilon	$, )
  T	(, digit	$, ), +
  M	*, epsilon	$, ), +
  F	(, digit	$, ), +, *

• 构建 LL(1) 分析表（非终结符的select集合）

  	(	)	+	*	digit	$
  L	L->E				L->E
  E	E->TR				E->TR
  R		R->epsilon	R->+TR			R->epsilon
  T	T->FM				T->FM
  M		M->epsilon	M->epsilon	M->*FM		M->epsilon
  F	F->(E)				F->digit

  • 遍历每一条产生式 $A\to a$

    • a 是 epsilon

      Follow(A) 中的每一个符号对应的列，添加产生式

    • a 不是 epsilon

      First(a) 中的每一个符号对应的列，添加产生式

• 分析串 $digit+digit$，词法分析器的输入是 1, 2

  • LL(1) 分析，用非递归的栈，过程更清晰

  • 由于该文法只有一种属性 val，因此属性栈可以默认为 val 栈

  • $ 的一侧为栈底

• 分析过程

  栈		输入	动作
  L$		digit + digit$	L -> E {print(E.val)}
  E {print(E.val)} $		digit + digit$	E -> T {R.i = T.val} R {E.val = R.s}
  T {R.i = T.val} R {E.val = R.s} {print(E.val)} $		digit + digit$	T -> F {M.i = F.val} M {T.val = M.s}
  F {M.i = F.val} M {T.val = M.s} {R.i = T.val} R {E.val = R.s} {print(E.val)} $		digit + digit$	F -> digit {F.val = digit.lexval}
  digit {F.val = digit.lexval} {M.i = F.val} M {T.val = M.s} {R.i = T.val} R {E.val = R.s} {print(E.val)} $	digit.lexval=1	digit + digit$	匹配 digit
  {F.val = digit.lexval} {M.i = F.val} M {T.val = M.s} {R.i = T.val} R {E.val = R.s} {print(E.val)} $	F.val=1	+ digit$	执行 {F.val = digit.lexval}
  {M.i = F.val} M {T.val = M.s} {R.i = T.val} R {E.val = R.s} {print(E.val)} $	M.i=1	+ digit$	执行 {M.i = F.val}
  M {T.val = M.s} {R.i = T.val} R {E.val = R.s} {print(E.val)} $		+ digit$	M -> epsilon {M.s = M.i}
  epsilon {M.s = M.i} {T.val = M.s} {R.i = T.val} R {E.val = R.s} {print(E.val)} $		+ digit$	匹配 epsilon
  {M.s = M.i} {T.val = M.s} {R.i = T.val} R {E.val = R.s} {print(E.val)} $		+ digit$	执行 {M.s = M.i}
  {T.val = M.s} {R.i = T.val} R {E.val = R.s} {print(E.val)} $	M.s=1	+ digit$	执行 {T.val = M.s}
  {R.i = T.val} R {E.val = R.s} {print(E.val)} $	T.val=1	+ digit$	执行 {R.i = T.val}
  R {E.val = R.s} {print(E.val)} $	R.i=1	+ digit$	R -> +T {R1.i = R.i + T.val} R {R.s = R1.i}
  +T {R1.i = R.i + T.val} R {R.s = R1.i} {E.val = R.s} {print(E.val)} $		+ digit$	匹配 +
  T {R1.i = R.i + T.val} R {R.s = R1.i} {E.val = R.s} {print(E.val)} $		digit$	T -> F {M.i = F.val} M {T.val = M.s}
  F {M.i = F.val} M {T.val = M.s} {R1.i = R.i + T.val} R {R.s = R1.i} {E.val = R.s} {print(E.val)} $		digit$	F -> digit {F.val = digit.lexval}
  digit {F.val = digit.lexval} {M.i = F.val} M {T.val = M.s} {R1.i = R.i + T.val} R {R.s = R1.i} {E.val = R.s} {print(E.val)} $		digit$	匹配 digit
  {F.val = digit.lexval} {M.i = F.val} M {T.val = M.s} {R1.i = R.i + T.val} R {R.s = R1.i} {E.val = R.s} {print(E.val)} $		$	执行 {F.val = digit.lexval}
  {M.i = F.val} M {T.val = M.s} {R1.i = R.i + T.val} R {R.s = R1.i} {E.val = R.s} {print(E.val)} $	F.val=2	$	执行 {M.i = F.val}
  M {T.val = M.s} {R1.i = R.i + T.val} R {R.s = R1.i} {E.val = R.s} {print(E.val)} $	M.i=2	$	M -> epsilon {M.s = M.i}
  epsilon {T.val = M.s} {R1.i = R.i + T.val} R {R.s = R1.i} {E.val = R.s} {print(E.val)} $	M.s=2	$	匹配 epsilon
  {T.val = M.s} {R1.i = R.i + T.val} R {R.s = R1.i} {E.val = R.s} {print(E.val)} $		$	执行 {T.val = M.s}
  {R1.i = R.i + T.val} R {R.s = R1.i} {E.val = R.s} {print(E.val)} $	T.val=2	$	执行 {R1.i = R.i + T.val}
  R {R.s = R1.i} {E.val = R.s} {print(E.val)} $	R1.i=1+2=3	$	R -> epsilon {R.s = R.i}
  epsilon {R.s = R.i} {R.s = R1.i} {E.val = R.s} {print(E.val)} $	R.s=3	$	匹配 esilon
  {R.s = R.i} {R.s = R1.i} {E.val = R.s} {print(E.val)} $		$	执行 {R.s = R.i}
  {R.s = R1.i} {E.val = R.s} {print(E.val)} $	R.s = 3	$	执行 {R.s = R1.i}
  {E.val = R.s} {print(E.val)} $	R.s = 3	$	执行 {E.val = R.s}
  {print(E.val)} $	E.val=3	$	执行 {print(E.val)}
  $		$	匹配 $
  			ACC

5. 中间代码生成

中间语言

后缀表示

• 若 E 是变量或常数，那么 E 的后缀表示就是本身

• 若 E 是形如 $E_{1}op{E}_2$ 的表达式，那么后缀表示是 $E_1^{\prime }{E}_2^{\prime }op$

  • $op$ 是二元运算符
  • $E_1^{\prime }$ 是 $E_1$ 的后缀表示
  • $E_2^{\prime }$ 是 $E_2$ 的后缀表示

• 若 E 是形如 $(E_1)$的表达式，那么后缀表达式是 $E_1$ 的后缀表达式

• 示例

  1. $1$ 的后缀表示是 $1$
  2. $1+2$ 的后缀表示是 $12+$
  3. $(1+2)-3$的后缀表示是 $12+3-$

图形表示

• 赋值语句 $a=(-b+c\ast d)+c\ast d$ 的语法树（不是语法分析树）如图
  
  • assgn 就是等号
    
    

  语法分析树是针对分析过程的，语法树是针对串的

• 还有一种图形表示就是有向无环图DAG（Directed Acyclic Graph）
  
  • DAG 和语法树很相似，区别在于公共子表达式，DAG 会用线直接指向（语法树中会画出整个表达式）
    

三地址代码

介绍

• 三地址代码的一般形式：$x=yopz$
• 之所以叫三地址代码，是因为指令包含两个运算对象的地址和一个结果的地址
• 示例
  表达式 $x+y\ast z$ 翻译成三地址指令序列

  t1 = y * z
  t2 = x + t1
  1
  2

  $t_1,t_2$ 是编译器产生的临时变量（的名字），用于保存中间结果。

图形表示与三地址代码

• 考虑表达式 $a=(-b+c\ast d)+c\ast d$
• 语法树
  
  • 语法树的三地址代码

    t1 = -b 
    t2 = c * d
    t3 = t1 + t2
    t4 = c * d
    t5 = t3 + t4
    a = t5
    1
    2
    3
    4
    5
    6

• DAG
  
  • DAG的三地址代码

    t1 = -b
    t2 = c * d
    t3 = t1 + t2
    t4 = t3 + t2
    a = t4    
    1
    2
    3
    4
    5

    DAG的三地址代码更简洁一些

6. 代码生成

指令代价计算

常见指令

• 二地址指令
  • 形式：$opsourcetarget$
    • op：操作码
    • source：源地址（from）
    • target：目标地址（to）
  • MOV a b：将 a 地址的内容，放到 b 地址中
    
  • ADD a b：将 a 地址的内容加到 b 地址中
  • SUB a b：将 b 地址的内容减去 a 地址的内容

地址模式和代价

• c 表示常数

• contents(a) ：a 地址中的内容

• 间接寄存器：寄存器中存的内容，是真正内容的地址
  

• 直接量：也叫立即数，就是常数

指令代价计算

• 1（每条指令的代价） + 源地址（source）模式的附加代价 + 目的地址（target）模式的附加代价

• 示例

  • MOV R0 R1
    把寄存器（Register）R0 的内容写到寄存器 R1，由于寄存器的附加代价是0，并且目标地址和源地址都是寄存器，指令本身代价为 1，因此这条指令的代价是：1
  • MOV R5 M
    把寄存器 R5 的内容写到 M，即内存中（Memory），其中源地址是寄存器，附加代价为 0，而目的地址为内存（绝对地址），附加代价为 1，指令本身代价为 1，因此这条指令的代价是：2
  • ADD #1 R3
    把常数 1 加到寄存器 R3 中，常数的附加代价是 1，寄存器的附加代价是 0，指令本身的代价是 1，因此这条指令的代价是：2
  • SUB 4(R0) *12(R1)
    将 contetns( contens( 12 + contens(R1) ) ) 减去 contents( 4 + contens(R0) )
    由于 c(R) 和 *c(R) 的附加代价都是 1，指令本身代价为 1，因此这条指令的代价是：3

• 相同表达式的不同指令

  • 考虑 $a=b+c$
  • a, b, c 都存在内存中
  • 指令序列 1

    MOV b R0
    ADD c R0
    MOV R0 a
    1
    2
    3

    代价是 6
  • 指令序列 2

    MOV b a
    ADD c a
    1
    2

    代价是 6
  • 指令序列 3
    假设R0, R1, R2 分别存放 a, b, c 的地址

    MOV *R1 *R0
    ADD *R2 *R0
    1
    2

    代价是 2
  • 指令序列 4
    假设 R1, R2 存放 b, c 的值

    ADD R2 R1
    MOV R1 a
    1
    2

    代价是 3