编译原理

第一章 引言

语言之间的翻译

编译器与解释器

语言翻译两种基本形态

• 先翻译后执行
• 边翻译边执行

编译器的工作原理和基本组成

通用程序设计语言的主要成分

声明+定义

以阶段划分编译器

编译器的分析/综合模式

作业题

• 何谓编译器的前端和后端？
  • 前端主要由与源语言有关但与目标机无关的部分组成，通常包括词法分析、语法分析、语义分析和中间代码生成，有的代码优化工作也可包括在前端。
  • 后端包括编译程序中与目标机有关的部分，如与目标机有关的代码优化和目标代码生成等。通常，后端不依赖源语言而仅仅依赖中间语言。
• 画出编译程序的总体结构图，简述各部分的主要功能。
  • 词法分析：输入源程序，输出单词符号
  • 语法分析：对单词符号进行语法分析（根据语法规则进行推导或归约），识别出各类语法单位，最终判断输入串是否构成语法上正确的”程序“。
  • 语义分析与中间代码生成：按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码
  • 中间代码优化：对中间代码进行优化处理
  • 目标代码生成：把中间代码翻译成目标程序
  • 符号表管理：编译程序在工作中保持一系列的表格，以登记源程序的各类信息的编译中各阶段的进展状况。
  • 出错处理：如果程序中发现错误，编译器就将信息发送给用户。
• 试分析编译程序是否分遍应考虑的因素及多遍扫描的优缺点。
  • 决定遍数的因素：
    • 计算机存储容量大小
    • 编译程序功能强弱
    • 源语言繁简
    • 目标程序优化程度
    • 设计和实现编译程序时使用工具的先进程度
    • 参与人员多少和素质等
  • 多遍扫描的优点：
    • 加工充分
    • 出错处理细致
    • 目标程序质量高
  • 多遍扫描的缺点：
    • 编译时间长，开销大
• 编译程序：一种能够把高级语言程序翻译成低级语言（汇编语言、机器语言）程序的程序
• 语义：一种语言的单词符号和语法单位的意义
• 语法：所谓一个语言的语法是这样的一组规则，用它可以形成和产生一个合式的程序
• 遍：遍就是对源程序的中间结构从头到尾扫描一次，并做有关的加工处理，生成新的中间结果或目标程序。

第二章 词法分析

词法分析中的若干问题

记号、模式与单词

记号=记号的类别+记号的属性

模式的形式化描述

字符串与语言

• 定义2.1：语言$L$是有限字母表$\sum$上有限长度字符串的集合。

• 字符串：由字母表中的符号组成的任意有穷序列。

• 字符串的长度：字符串中的符号个数。

字符串基本概念

字符串集合的运算

正规式与正规集

正规式的递归定义

1. $\epsilon$和$\varnothing$都是$\sum$上的正规式，它表示$L(\epsilon)=\{ \epsilon \}$和$\varnothing$
2. 若$a$是$\sum$上的字符，则$a$是正规式，表示$L(a)=\{a\}$
3. 若正规式$r$和$s$分别表示$L(r)$和$L(s)$:
   • $r | s$是正规式，表示集合$L(r)\cup L(s)$
   • $rs$ 是正规式，表示集合$L(r)L(s)$
   • $r^* $ 是正规式，表示集合 $(L(r))* $
   • $r$是正规式，表示集合仍是$L(r)$

运算

• 运算符的优先级与结合性
  1. 三种运算均具有左结合性质
  2. 优先级从高到低排列顺序为：闭包运算、连接运算、或运算
• 正规式的等价：若正规式$P$和$Q$表示了同一个正规集，则称P和Q是等价的，记为$P=Q$
• 正规式等价的判定（证明）
  • 根据定义
  • 利用代数性质
    1. $ r|s = s|r $
    2. $r|(s|t) = (r|s)|t$
    3. $r(s|t) = rs|rt$
    4. $(s|t)r = sr|tr $
    5. $(rs)t = r(st)$
    6. $εr = rε = r$
    7. $r^* = (r+|ε) $
    8. $r^{**} = r^* $

记号的说明

例如：

relation = < | <= | <> | > | >= | =

id = (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
       |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)
     (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
     |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
     |0|1|2|3|4|5|6|7|8|9)*

num = (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*
      (ε|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)
      (ε|E(+|-|ε)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)

• 简化正规式描述
  • 正闭包：$r^+ = rr^* = r^* r，r^* = r^+|ε$
  • 可缺省：$r?=r|ε$
  • 字符组：如$[abc]$，它等价于：$a|b|c$
  • 非字符组：$[^r]$
• 引入辅助定义

char              = [a-zA-Z]
digit             = [0-9]
digits            = digit+
optional_fraction = ( . digits )?
optional_exponent = ( E (+|-)? digits )?

id  = char ( char|digit )*
num = digits optional_fraction optional_exponent

记号的识别-有限自动机

不确定的有限自动机（Nondeterministic Finite Automaton，NFA）

定义：$M=(S, \sum, move, s_0, F) $

• $S$是有限个状态(state)的集合
• $\sum$是有限个输入字符 包括 $ε$ 的集合
• $move(s_i, ch)=s_j$
• $s_0$是唯一的初态
• $F$是终态集

直观的表示方式

1. 状态转换图
2. 状态转换矩阵
   
   

NFA存在的问题

1. 只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长
2. 识别过程中需要大量的回溯，时间复杂度升高且算法趋于复杂

确定的有限自动机（Deterministic Finite Automaton，DFA）

定义：DFA是NFA的一个特例，其中

1. 没有状态具有$\epsilon$状态转移$(\epsilon -transition)$，即状态图中没有标记$\epsilon$的边
2. 对每个状态$s$和每个字符$a$，最多有一个下一状态

模拟DFA算法

s := s0; ch := nextchar;    -- 初值
while ch != eof             -- 循环
loop s := move(s, ch);
     ch := nextchar;
end loop;
if s in F
then return "yes"; else return "no";
end if;

从正规式到词法分析器

构造词法分析器的方法和步骤

1. 用正规式描述模式
2. 构造NFA
3. 确定化（转换成等价的DFA）
4. 最小化（优化DFA）
5. 从优化后的DFA构造词法分析器

从正规式到NFA

Thompson算法

1. 对$\epsilon$，$N(\epsilon)$：
   
2. 对于$\sum$上的每个字符$a$，$N(a)$：
   
3. 若$N(p)$和$N(q)$是正规式$p$和$q$的NFA
   1. 对于$p|q$，构造$N(p|q)$：
      
   2. 对于正规式$pq$，构造NFA $N(pq)$：
      
   3. 对于正规式$p^* $，构造NFA $N(p^{*})$：
      

从NFA到DFA

并行方法

• $smove(S, a)$：从状态集$S$中的每个状态出发，经过标记为$a$的边直接到达的下一状态全体
• $\epsilon$-闭包：从状态T出发，经过若干次$\epsilon$转移到达的状态全体

$\epsilon$-闭包 的定义

1. T中的所有状态属于$\epsilon$-闭包
2. 如果$t$属于$\epsilon$-闭包(T)且$move(t, \epsilon)=u$，则$u$属于$\epsilon$-闭包(T)
3. 再无其它状态属于$\epsilon$-闭包(T)

求$\epsilon$-闭包 的算法

function ε-闭包(T) is
begin
    for T中的每个状态t
    loop 加入t到U; push(t);
    end loop;
    while 栈不空
    loop pop(t);
        for 每个u=move(t, ε)
        loop if u不在U中 then 加入u到U中; push(u); endif;
        end loop;
    end loop;
    return U;
end ε-闭包;

模拟NFA

S := ε-闭包({s0});              -- 所有可能初态的集合
a := nextchar;
while a != eof
loop
    S := ε-闭包(smove(S, a));   -- 所有下一状态的集合
    a := nextchar;
end loop;
if S and F != nil then return "yes"; else return "no";
end if;

子集法构造DFA

Dstates = {ε-闭包({s0})};       // Dstates中仅有一个状态且未标记
while Dstates有尚未标记的状态T
loop 标记T;
    for 每一个输入字符a
    loop U := ε-闭包(smove(T, a))
        if U 非空
        then Dtran[T, a] := U;
            if U 不在Dstates中
            then U作为尚未标记的状态加入Dstates;
            end if;
        end if;
    end loop;
end loop;

例如用上述算法构造(a|b)*abb的DFA：

ε-闭包({0}) = {0, 1, 2, 4, 7}*                  A
ε-闭包(smove(A, a)) = {3, 8, 6, 7, 1, 2, 4}*    B
ε-闭包(smove(A, b)) = {5, 6, 7, 1, 2, 4}*       C
ε-闭包(smove(B, a)) = {3, 8, 6, 7, 1, 2, 4}     B
ε-闭包(smove(B, b)) = {9, 5, 6, 7, 1, 2, 4}*    D
ε-闭包(smove(C, a)) = {3, 8, 6, 7, 1, 2, 4}     B
ε-闭包(smove(C, b)) = {5, 6, 7, 1, 2, 4}        C
ε-闭包(smove(D, a)) = {3, 8, 6, 7, 1, 2, 4}     B
ε-闭包(smove(D, b)) = {5, 10, 6, 7, 1, 2, 4}    E
ε-闭包(smove(E, a)) = {3, 8, 6, 7, 1, 2, 4}     B
ε-闭包(smove(E, b)) = {5, 6, 7, 1, 2, 4}        C

最小化DFA

可区分:对于DFA中的任何两个状态$t$和$s$，若从一状态出发接受输入字符串$\omega$，而从另一状态出发不接受$\omega$，则称 $\omega$区分状态$t$和$s$。如果存在某个能够区分状态$s$和状态$t$的串，那么它们是可区分的。

最小化DFA算法

1. 初始划分$\Pi=\{S-F, F\}, \Pi_{new} = \Pi$。$F$是终态集，$S-F$是非终态集
2. 应用下述过程构造新的划分$\Pi_{new}$:
   1. for $\Pi$的每一个组$G$
   2. loop 划分$G$, $G$的两个状态$s$和$t$在同一组中的充要条件是： $$\forall a \in \Sigma \forall G_i \in \Pi (move(s, a) \in G_i \leftrightarrow move(t, a) \in G_i)$$用新的划分组替代$G$, 形成新的划分$\Pi_{new}$;
      end loop
3. 若$\Pi_{new}=\Pi$，令$\Pi_{final} = \Pi$，转4，否则令$\Pi = \Pi_{new}$并重复步骤2
4. 选代表并修改状态转移
5. 删除死状态，即不是终态且对所有输入字符均转向自身，或从初态不可到达的状态

由DFA构造词法分析器

• 表驱动的词法分析器(自动生成)
• 直接编码的词法分析器

正规式转换为正规文法

1. 令$V_T = \sum$
2. 令文法的开始符号$S = R$
3. 对形如$A \rightarrow ab$的规则转换为$A \rightarrow aB$和$ B \rightarrow b$
4. 在新的文法中，将形如$A \rightarrow a^{*}b$的规则进一步转换为$A \rightarrow aA | b$
5. 不断利用3和4，直到每条规则的右部最多只含有一个终结符为止

作业

• 表示源程序中信息单元的字符序列叫做记号
• LEX源程序的三个组成部分：定义部分、识别规则部分、辅助函数部分
• 词法分析器的功能：依次扫描字符串形式的源程序中的各个字符，逐个识别其中的单词，并将其转换为内部编码形式的单词符号作为输出。
• 简要叙述从正规式构造词法分析器的一般方法和过程
  • 用正规式对模式进行描述
  • 为每一个正规式构造NFA
  • 确定化
  • 最小化
  • 从简化后的DFA构造词法分析器
• 简述DFA与NFA有何区别？
  • NFA可以有$\epsilon$转移，而DFA没有
  • DFA的状态转移将产生一个状态机和而不是单个状态
• 正规式：又称正规式或正则表达式，是按照一组定义规则，由较简单的正规式构成的，每个正规式$r$表示一个语言$L(r)$。定义规则告诉我们$L(r)$是怎样以各种方式从$r$的子正规式所表示的语言组合而成的。

第三章 语法分析

基本术语

语法分析器的作用

1. 根据词法分析器提供的记号流，为语法正确的输入构造语法树。
2. 检查输入中的语法（可能还包含词法错误），并调用出错处理器进行适当处理。

语法错误的处理原则

基本恢复策略

1. 紧急方式恢复：使用同步记号
2. 短语级恢复：采用串替换的方式
3. 出错产生式：捕获错误
4. 全局纠正

例：

x := a + b
y := c + d;

• 紧急方式——丢弃b后若干记号，知道遇见+x := a + b + d;
• 短语级恢复——加入分号，使之成为一个赋值句y := c + d;

上下文无关法（Context Free Grammer，CFG）

上下文无关文法就是说这个文法中所有产生式左边只有一个非终结符。

CFG定义及表示

四元组$G=(N, T, P, S)$，其中

1. $N$——非终结符（Nonterminals）有限集合
2. $T$——终结符（Terminals）有限集合，$N \cup T = \emptyset $
3. $P$——产生式（Productions）有限集合，$A\rightarrow a$，其中$A \in N$(左部)，$a \in (N\cup T)^*$ (右部)，若$a = \epsilon$，则称$A \rightarrow \epsilon$为空产生式
4. $S$——$S$是非终结符，称为开始符号

由产生式集表示CFG

• $E \rightarrow E + E$
• $E \rightarrow E * E$
• $E \rightarrow (E)$
• $E \rightarrow -E$
• $E \rightarrow id$

终结符与非终结符书写上的约定

• 大写字母$A、B、C$表示非终结符
• 小写字母$a、b、c$表示终结符
• 小写希腊字母$\alpha、\beta、\delta $表示任意文法符号序列

CFG产生语言的基本方法——推导

• 直接推导：$\alpha A \beta => \alpha \gamma \beta $
• 零布或多步推导
• 至少一步推导

由CFG所产生的语言L(G)

$$L(G) = \{ \omega | S \overset{+}{\Rightarrow} and \ \omega \in T^* \} $$ $L(G)$称为 上下文无关语言 （Context Free Language, CFL）$\omega$称为句子，若$S \overset{ * }{\Rightarrow} \alpha, \alpha \in (N \cup T)^{ * } $，则称$\alpha$为$G$的一个 句型 。

最左推导和最右推导（规范推导）

最左推导产生的句型称为左句型

最右推导被称为规范推导 规范归约是指最右推导的逆过程

推导与语法树

语法树和抽象语法树

二义性与二义性的消除

• 二义性：一个句子可能对应多棵语法树

  • 文法二义性：若文法$G$对同一句子产生不止一棵语法树，则称语法树$G$是二义的。或者说，若文法$G$对同一个句子存在两个不同的最左（最右）推导，则称文法$G$是二义的。
  • 语言的二义性：如果产生上下文无关语言的每一个文法都是二义的，则此语言是二义的

• 二义性的消除

  • 改写二义文法为非二义性文法
    1. 引入一个新的非终结符，增加一个子结构并提高一级优先级
    2. 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性
       
       消除“悬空else”问题
       
       
  • 为文法符号规定优先级和结合性
  • 修改语言的语法end if

语言与文法简介

正规式与上下文无关法

正规式到CFG的转换

• 若$0$为初态，则$A_0$为开始符号
• 对于$move(i,a)=j$，引入产生式$A_i→aA_j$
• 对于$move(i,ε)=j$，引入产生式$A_i→A_j$
• 若$i$是终态，则引入产生式$A_i →ε$。

上下文有关语言

• 不能用CFG描述的语言
  • $L1=\{ \omega c \omega | \omega \in (a | b)^* \}$标识符声明与引用一致性的抽象
  • $L2=\{a^nb^mc^nd^m|n \ge 1\ and\ m \ge 1\}$ 形参与实参一致性的抽象
  • $L3=\{ a^nb^nc^n|n \ge 1\}$ 计数问题的抽象
• 相近的CFL
  • $L1^{’}=\{ \omega c \omega^r | \omega \in (a | b)^* \} (S\rightarrow aSa\ |\ bSb\ |c)$
  • $L2^{’}=\{ a^nb^mc^md^n|n\ge 1, m \ge 1\} (S \rightarrow aSd\ | aAd\ A \rightarrow bAc\ |\ bc)$
  • $L2^{’’}=\{ a^nb^nc^md^m | n \ge 1, m \ge 1\} (S \rightarrow AB\ A\rightarrow aAb\ |\ ab \ B\rightarrow cBd\ | cd) $
  • $ L3^{’}=\{ a^mb^mc^m | m, n \ge 1\}\ (S \rightarrow aAb | ab\ C\rightarrow cC|c)$

形式语言与自动机简介

• 0型文法：若文法 $G=(N, T, P, S)$ 的每个产生式 $α→β$ 中 均有 $α∈(N∪T)^* $ 且至少含有一个非终结符 $β∈(N∪T)^*$则称 G 为 0 型文法 。
• 限制
  • $G $的任何产生式 $α→β$ ($S→ε$ 除外) 满足$ |α|≤|\beta |$
  • $G$ 的任何产生式形如 $A→β$ 其中 $A∈N\ β∈(N∪T)^*$
  • $G$ 的任何产生式形如 $A→a$ 或者 $A→aB$( 或者 $A→Ba$) 其中 $A$ 和 $B$$∈N$ $a∈T$

自上而下语法分析

一般方法（试探＋回溯，边推导边匹配）

消除左递归

• 消除直接左递归: $A\rightarrow Aα|β$替换为$A \rightarrow \beta A^{’}\ \ A^{’} \rightarrow \alpha A^{’} | \epsilon$
• 消除文法的左递归（直接/间接左递归）：将不是左递归的非终结符右部展开到其它产生式中。 合理排序非终结符：$A_1,A_2,…,A_n$(排序方法不唯一) 用$A_j→δ_1|δ_2|…|δ_k$右部替换$A_i→A_jγ$中的$A_j$，得到$A_i→δ_1 γ|δ_2 γ|…|δ_k γ$； (如果有)消除$A_i$产生式中的直接左递归；
  

提取公因子

将$A \rightarrow \alpha {\beta}_1 | \alpha {\beta}_2$替换为$ A \rightarrow \alpha A^{’} \ A^{’} \rightarrow {\beta}_1|{\beta}_2$

递归下降分析

…

预测分析器

1. 非递归（表驱动）预测分析器的工作模式

   
   • 工作方式
     • 格局：三元组(栈内容^top，剩余输入^ip，改变格局的动作)
     • 改变格局的动作
       1. 匹配终结符：若^top = ^ip(但≠‘#’)，则pop且next(ip)；
       2. 展开非终结符：若^top = X且^ip=a且M[X, a] = α(X→α)，则pop且push(α)（α逆序入栈）;
       3. 报告分析成功：若^top = ^ip = #，则分析成功并结束;
       4. 报告出错：其它情况，调用错误恢复例程。
   • 预测分析表
     

2. FIRST集合和FOLLOW集合

   • FIRST集合：$FIRST(\alpha) = \{ a | \alpha \overset{*}{=>} a…, a \in T \} $ $\alpha$的FIRST集合就是由从$\alpha$开始可导出的文法符号序列的开头终结符构成的集合。

     • 求解
       • 直接收取：对形如$U \rightarrow a…$ 的产生式（其中$a$是终结符），把$a$收入到$FIRST(U)$中
       • 反复传送：对形如$U \rightarrow P…$ 的产生式（其中$P$是非终结符，把$FIRST(P)$的内容传送到$FIRST(U)$中

   • FOLLOW集合：$FOLLOW(A)=\{ a | S \overset{*}{=>} Aa \}$ $A$的$FOLLOW$集合，就是由从开始符号可导出的含A的文法符号序列中紧邻A之后的终结符构成的集合。

     • 求解
       • 加入$ \# $到$FOLLOW(S)$
       • 若有产生式$A \rightarrow \alpha B \beta $，则除$\epsilon$ 外，$FIRST(\beta)$的全体加入到$FOLLOW(B)$
       • 若有产生式$A \rightarrow \alpha B$或$A \rightarrow \alpha B \beta 且 \epsilon \in FIRST(\beta)$，则$FOLLOW(A)$的全体加入$FOLLOW(B)$

   • 例题

     

3. 构造预测分析表

   1. 对文法的每个产生式$A \rightarrow \alpha$，执行2和3；
   2. 对$FIRST(\alpha)$的每个终结符$a$，将$A \rightarrow \alpha$加入到$M[A, a]$中；
   3. 对$\epsilon \in FIRST(\alpha )$，则对$FOLLOW(A)$中的每个终结符$b$（包括$\#$)，将$A \rightarrow a$加入到$M[A, b]$中。

4. LL(1)文法

   • 判断LL(1)文法的方法
     • 构造分析表
     • 推论判断：$G$是$LL(1)$的，当且仅当$G$的任何两个产生式$A \rightarrow \alpha | \beta$条件
       1. $FIRST(\alpha) \cap FIRST(\beta) = \emptyset$
       2. 若$\beta \overset{*}{=>} \epsilon$，则$FIRST(\alpha) \cap FOLLOW(A)=\emptyset$
   • 弱点
     • 难写、难懂
     • 应用范围有限，往往写不出来某些语言的$LL(1)$文法
     • 实际编译器中使用更多的是一类$LL(1)$文法的真超集，即$LR(1)$文法。

自下而上语法分析

短语

设$\alpha \beta \delta$是文法$G$的一个句型，若存在$S \overset{*}{=>} \alpha A \delta$，$A \overset{+}{=>}\beta$，则称$\beta$是句型$\alpha \beta \delta$(相对于$A$)的短语。

• 直接短语：$A \rightarrow \beta$
• 句柄：一个句型地最左直接短语被称为句柄

最左归约——”剪句柄“过程

LR(k)文法

$L$表示从左到右扫描输入序列，$R$表示逆序的最右推导，$k$表示为确定下一动作向前看的终结符个数

LR分析法

• ACTION[s, a]：栈顶状态为s面临a时采取什么动作(shift or reduce)
• GOTO[s, X]：归约后对应的状态

LR(0)分析表的构造

活前缀：为了描述LR分析中栈内的符号的特点

如果在符号序列$\alpha$的右边增添零个或多个终结符之后，能够形成一个右句型并且$\alpha$不含该句型句柄之后的任何符号，则称$\alpha$为文法$G$的活前缀。

对于规范句型$\alpha \beta \delta$，$\beta$为句柄，如果$\alpha \beta = u_1 u_2 … u_r$，则符号串$u_1 u_2 …u_i(1 \le i \le r)$时$\alpha \beta \delta$的活前缀

• 举例说明以下文法的活前缀 $G: S \rightarrow aABe | aAbBec \ A \rightarrow b | bA \ B \rightarrow d $
• 活前缀：$a, aA, aAB, aABe, aAb, aAbBec, aAbd, aAd, ab, abb, abbb, ab+$

LR(0)项目

一个$LR(0)$项目(简称项目)是这样一个产生式，在它右部的某个位置有一个点$“.”$。对于$A \rightarrow \epsilon$，它仅有一个项目$A \rightarrow .$

• 意义
  • $A \rightarrow . XYZ$，说明希望从后面输入串中看到可以从$XYZ$推出的符号串，需要移进；
  • $A \rightarrow X . YZ$，说明已经从输入串中看到可以从$X$推出的符号串，希望进一步看到可以从$YZ$推出的符号串，需要继续移进。
  • $A→ XYZ . $，说明当前栈顶已经形成句柄，可以归约。

识别文法G的活前缀的NFA

• 若状态$i$为$X \rightarrow X_1 … X_{i-1} . X_i … X_n$，状态$j$为$X \rightarrow X_1 … X_{i-1} X_i . X_{i+1} … X_n$，则从状态$i$连一条$X_i$有向边到状态$j$
• 若状态$i$为$X \rightarrow \alpha .A \beta$，A为非终结符，则从$i$连一条$\epsilon$到所有状态$A \rightarrow . \gamma$

确定化后的DFA

LR(0)项目集规范族的构造

• 拓广文法$G^{’}= G \cup \{ S^{’} \rightarrow S\}$：为了使得最终构造的DFA状态集中具有唯一的接收状态
• NFA（项目）-> DFA（项目集）
  • $CLOSURE(I)$：从项目集$I$不经过任何文法符号到达的项目全体
  • $GO(I, X)$：所有从$I$经文法符号$X$能到达的项目全体（与$somve$不同，$GO$含有闭包计算）
• $CLOSURE(I)$计算方法：
  • $I$的任何项目属于$CLOSURE(I)$
  • 若$A \rightarrow \alpha . B \beta$属于$CLOSURE(I)$，项目$B \rightarrow .\gamma$也属于$CLOSURE(I)$
  • 重复以上步骤直到$CLOSURE(I)$不再增大
• $GO(I, X)=CLOSURE(J)$

有效项目

若存在最右推导$S^{’} \overset{*}{=>}\alpha A \omega => \alpha \beta_1 \beta_2 \omega $，则称项目$A \rightarrow \beta_1 . \beta_2$对活前缀$\alpha \beta_1$有效

• 意义
  • 到目前为止语法分析是正确的
  • 指导下一步的分析
    • $A \rightarrow \alpha a. \beta$（可移进项）
    • $B \rightarrow \beta.$（可归约项）

LR(0)分析表的构造

• 圆点后是终结符，需要填ACTION移进
• 圆点后是非终结符，需要填GOTO表
• 圆点后为空，需要填ACTION归约

SLR(1)分析表的构造

$LR(0)$规范族的一个项目集中含有m个移进项目：$A_1 \rightarrow \alpha_1. a_1 \beta_1, A_2 \rightarrow \alpha_2. a_2 \beta_2 … ,A_m \rightarrow \alpha_m. a_m \beta_m$，同时有$n$个归约项目：$B_1 \rightarrow \alpha_1., B_2 \rightarrow \alpha_2., …, B_n \rightarrow \alpha_n., $

如果集合$\{a_1, …, a_m\}, FOLLOW(B_1), …, FOLLOW(B_n)$两两不相交,则可以用SLR(1)来解决。

对于当前输入符号$a$

• 若$a \in \{ a_1, …, a_m \}$，则移进
• 若$a \in FOLLOW(B_i)$，则用产生式$B_i \rightarrow \alpha_i$归约
• 否则，报错

非SLR(1)文法

1. 二义文法
2. 非二义文法的非SLR(1)文法

作业

• LR分析法中，分析栈中存放的状态是识别规范句型活前缀的DFA状态。
• 一个上下文无关法所含的四个组成部分是一组终结符、一组非终结符、一个开始符号、一组产生式
• 自下而上的语法分析方法的基本思想是：从给定的终结符开始，根据文法的规则一步一步地向上进行直接归约，试图归约到文法的开始符号。
• $LR(0)$分析法的名称中，L的含义是从左向右扫描输入串，$R$的含义是最左归约，$0$的含义是向后查看$0$个输入符号。
• 仿照最左推导和左句型的定义，试叙述最右推导和右句型的定义。
  • 最右推导：在推导过程中，若每次直接推导均替换句型最右边的非终结符，称为最右推导
  • 右句型：在最右推导产生的句型被称为右句型
• 简述自上而下分析的宗旨 对给定输入串$w$，试图用一切可能的办法，从文法开始符号$S$出发，自上而下，从左到右地为输入串建立起一棵以$S$为根结点的语法树。或者说，为输入串寻找最左推导$S \overset{*}{=>} w$。这种分析过程本质上是一种试探过程，是反复使用不同的产生式谋求匹配输入串的过程，如果这一试探得到成功，则证明$w$是相应文法的一个句子，反之，则不是。
• 根据程序错误性质可以分为哪几种错误？
  • 词法错误
  • 语法错误
  • 静态语义错误
  • 动态语义错误
• 自下而上分析法的思想
  • 自下而上的思想就是从输入串开始，逐步进行”归约“，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上”归约“，直到根结点。
• 简述构造$LR$分析表的技术
  • $LR(0)$表构造。这种方法局限性大，但是它是建立其他较一般LR分析法的基础。
  • 简单$LR$表$(SLR)$构造：虽然一些文法构造不出$SLR$分析表，但是这是一种比较容易实现又极有使用价值的方法。
  • 规范$LR$表构造法：这种分析表能力最强，能够适应一大类文法，但是实现代价过高。
  • 向前$LR$表$(LALR)$构造法：这种分析表的能力介于SLR和规范LR之间，可以高效的实现。
• 活前缀：右句型的前缀且不包含句柄之后的符号

第四章 语法制导翻译与中间代码生成

语法制导翻译简介

属性文法

$$ A \rightarrow \alpha \ \ b := f(c_1, c_2, …, c_k)$$

• 综合属性：$b$是$A$的属性，$c_1, c_2, …, c_k$是$\alpha$中的文法符号的属性或$A$的其他属性，则称$b$是$A$的综合属性
• 继承属性：$b$是$\alpha$中的文法符号$X_i$的属性，$c_1, c_2, …, c_k$是$A$的属性或$\alpha$中的其他文法符号属性，则称$b$是$X_i$的继承属性
• $b$依赖于$c_1, c_2, …, c_k$
• 虚拟属性：$f(c_1, c_2, …, c_k)$

中间代码简介

后缀式（逆波兰）

例：$a := 1 + 2 * 3$ 后缀式为：$a 1 2 3 * + := $

三地址码

• 形式：

  • $result := arg1\ op\ arg2$
  • $result := op\ arg1$
  • $op\ arg1$

• 种类

  • 三元式：(i)(op, arg1, arg2)对应三地址码(i) := arg1 op arg2
  • 四元式：(op, arg1, arg2, result)对应三地址码result := arg1 op arg2
    • 四元式的运算结果与其位置无关，为代码优化提供了极大的方便。

图形表示

树的语法制导翻译

• mknode：生成根或内部节点
• mkleaf：生成叶子节点

(1)A → id := E		{A.nptr := mknode(:=, mkleaf(entry(id.name)), E.nptr)}
(2)E → E1 + E2	        {E.nptr := mknode(+, E1.nptr, E2.nptr)}
(3)E → E1 * E2		{E.nptr := mknode(*, E1.nptr, E2.nptr)}
(4)E → (E1)		{E.nptr := E1.nptr}
(5)E → - E1		{E.nptr := mknode(@, E1.nptr, )}
(6)E → id		{E.nptr := mkleaf(entry((id.name))} 

• 优化表示——有向无环图

先查看所要构造的节点是否已经存在，若存在则无需构造新的节点，直接返回指向已存在节点的指针即可。

符号表简介

相当于是一个内存，连接声明与引用的桥梁，一个名字在声明时，相关信息被填写进符号表，在引用时根据符号表中的信息生成可执行语句。

1. 静态作用域规则——总方针
2. 最近嵌套规则——总方针下的具体规则

声明语句的翻译

变量声明的文法

D -> D ; D
  | id : T  {enter(id.name, T.type, offset);
             offset := offset + T.width; }
T -> int    {T.type = integer; T.width := 4; }
   | real   {T.type = real; T.width := 8; }
   | array [num] of T1 {T.type = array(num.val, T1.type); T.width := num.val * T1.width; }
   | ^T     {T.type = pointer(T1.type); T.width := 4; }

例：a : array[10] of int; x : int

过程的定义与声明

• 左值和右值
  • 左值必须具有存储空间，右值可以仅仅是一个值
  • 左值是容器，右值是内容
• 参数传递
  • 值调用：C参数传递
  • 引用调用：C++引用传递
  • 复写——恢复
  • 换名调用：宏定义

简单算术表达式与赋值句

x := -a * b + c的语法制导翻译，x、a、b是整型数，c是实型数。

布尔表达式

直接计算