四川大学编译原理复习要点

1、四川大学 编译原理复习要点2013 版一、编译器各个阶段的功能，输入、输出，前端、后端1） 词法分析： 将字符序列收集到称作记号(t o k e n）的有意义单元中扫描程序输入：源代码输出：记号2）语法分析： 从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析，语法分析定义了程序的结构元素及其关系。输入：记号输出：语法树3） 语义分析程序：分析程序的静态语义，包括声明和类型检查。输入：语法树输出：注释树4） 源代码优化程序：编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完成的，而此时代码改进可能只依赖于源代码。【对源代码进行优化，并产生中间代码】输入：

2、注释树输出：中间代码5） 目标代码生成：得到中间代码，生成目标机器的代码代码生成器输入：中间代码输出：目标代码6） 目标代码优化程序：编译器改进由代码生成器生成的目标代码。输入：目标代码输出：目标代码扫描程序、分析程序和语义分析程序是前端，代码生成器是后端，前后端分开的好处：可以给编译器带来更方便的可移植性，此时的编译器既能改变源代码，又能改变目标代码。【遍】 编译器发现， 在生成代码之前多次处理整个源程序很方便，这些重复就是遍。首遍是从源中构造一个语法树或中间代码，在它之后的遍是由处理中间表示、向它增加信息、更换结构或生成不同的表示组成二、 解释器和编译器的区别与联系？读入源语言后，解释器和

3、编译器都要进行词法分析、语法分析和语义分析，之后，二者开始有所分别。 解释器在语义分析后选择了直接执行语句； 编译器在语义分析后选择将将语义存储成某一种中间语言， 之后通过不同的后端翻译成不同的机器语言（可执行程序）编译器是把源语言（如 C,Pascal， java 等高级语言）转换为目标语言（汇编语言、机器语言等低级语言） ，要产生目标代码。解释器是以一个源语言（ C， Pascal， java 等高级语言）为输入，一边解释一边执行源程序，但不产生目标代码。1/10三、算法描述（伪代码）p41构造一个扫描程序的自动过程：正则表达式NFA DFA 程序1、正则表达式NFA（ 1） 建立字母表。

4、输入的正则表达式由于一般不输入“与”操作符，因此首先给表达式加入 .作为与操作。再利用逆波兰式的堆栈操作，把操作符与字母分开，便得到了字母表。（ 2） Thompson 构造法。首先将构成正则表达式的各个元素分解，对于每一个元素，按照下述规则1 和规则 2 生成 NFA 。 注意：如果r 中记号 a 出现了多次，那么对于 a 的每次出现都需要生成一个单独的NFA 。2、 NFA DFA从单个输入字符的某个状态中去除-转换和多重转换。（ 1）利用 -closure 规则即闭包规则，把 NFA 状态划分成集合，而后把每个集合作为 DFA 的状态。详细描述：从NFA 的状态 S 开始经过 到达的状态

5、存储下，然后再把存储结果中的状态有经过 到达的新状态也存储在一起，这样通过闭包规则就可以这些集合，再把集合作为DFA 的状态。（ 2）子集构造3、 DFA 程序DFA 状态最小化取出 DFA 状态中的不可达的状态。构造最小状态的等价DFA 的算法是通过创建统一到单个状态的状态集来进行。构造 NFA（使用 Thompson结构） :1) 基本正则表达式 基本正则表达式格式 a 或，其中 a表示字母表中单个字符的匹配，表示空串的匹配。与正则表达式 a 等同的 N FA （即在其语言中准确接受）的是：与等同的 N FA 是：2) 并置我们希望构造一个与正则表达式r s等同的 N FA ，其中 r 和

6、s 都是正则表达式。可将与 rs 对应的 N FA 构造如下：3) 在各选项中选择我们希望在与前面相同的假设下构造一个与r | s 相对应的 N FA 。如下进行：2/104) 重复我们需要构造与r * 相对应的机器，现假设已有一台与r 相对应的机器。那么就如下进行：构造 NFA的一个例子：例：根据 Thompson 结构将正则表达式 a b | a 翻译为 N FA 。首先为正则表达式 a 和b 分别构造机器：接着再为并置a b构造机器：现在再为 a 构造另一个机器复件，并利用它们组成a b | a完整的 N FA ，如下图：将 NFA转换成 DFA（最小子集法）： - 闭包（ - c l

7、o s u r e）是可由转换从某状态或某些状态达到的所有状态集合，3/10它总是包含状态本身子集构造相关题目： 2.1 ， 2.12 ， 2.16四、提左因子和消除左递归1、在建立 LL(1) 语法分析器的时候，提左因子和消除左递归的目的、原因目的：提取左因子- 避免程序回溯；消除左递归 - 消除无限循环原因：当有公因子存在时，不能立即区分出文法规则右边的选择；当有左递归时，将导致一个无限循环。2、提左因子和消除左递归的算法描述消除左递归伪代码P119for i:=1 tomdofor j:=1 toi-1doreplace each grammer rule choice of the f

8、orm AiAj by the ruleAi 1 | 2 |.| k , where Aj 1| 2|.| kisthe current rule for Ajremove,if necessary,immediate left recursion involving Aia) 把直接左递归改写为右递归【简单直接左递归】设有文法产生式： AA | 。其中 非空， 不以 A 打头。可写为： A A'A' A'| 一般情况下，假定关于 A 的产生式是 【普遍的直接左递归】 AA 1| A 2 | |A m| 1| 2 | | n其中， i (1 i m)均不为空， j (1

9、 j n) 均不以A 打头。则消除直接左递归后改写为：A 1A'|2 A' | | nA'A' 1A' | 2A' | | mA' |例4.12 ：有文法 G(E) ：EE +T |TTT*F | FFi| (E)消除该文法的直接左递归。解：按转换规则, 可得 :ETE'E' +TE'| 4/10TFT 'T' *FT'|Fi| (E)b) 消除间接左递归 【一般的左递归， 不带有 产生式且不带有循环的文法】对于间接左递归的消除需要先将间接左递归变为直接左递归，然后再按a) 清除左递归。例4

10、.13 ：以文法 G6为例消除左递归：(1)A aB(2 )ABb(3)B Ac(4)B d解：用产生式 (1) ， (2) 的右部代替产生式(3) 中的非终结A 得到左部为B 的产生式：(1)B aBc(2)B Bbc(3)B d消除左递归后得到：BaBcB' |dB'B' bcB' |再把原来其余的产生式AaB,ABb 加入，最终得到等价文法为:(1) A aB(2) A Bb(3) B (aBc|d)B'(4) B'bcB'|c) 消除文法中一切左递归的算法设非终结符按某种规则排序为A1， A2， ，An 。For i =1 to

11、n dobeginFor j =1 to i-1 dobegin若 Aj 的所有产生式为：Aj 1| 2 | | n替换形如Ai A j 的产生式为：Ai 1 | 2 | | nend消除 Ai 中的一切直接左递归5/10end提取左因子伪代码P122当两个或更多文法规则选择共享一个通用前缀时，需要提取左因子：A|按如下规则提取左因子：AAA |五、 first 集合 follow 集合 算法伪代码 P126P131具体看书上的例子First 集合求法：1.直接收取：对形如U a的产生式（其中a 是终结符），把 a 收入到 First(U) 中2. 反复传送：对形入 U P的产生式（其中 P

12、是非终结符），应把 First(P) 中的全部内容传送到 First(U) 中。Follow 集合求法：1. 直接收取： 注意产生式右部的每一个形如 “ Ua”的组合， 把 a 直接收入到 Follow(U) 中。2直接收取： 对形如“ UP”(P 是非终结符 )的组合，把 First(P) 除 直接收入到 Follow(U) 中。3反复传送：对形如 P U 的产生式（其中 U 是非终结符），应把 Follow(P) 中的全部内容传送到 Follow(U) 中。 (或 P UB 且 First(B) 包含 ，则把 First(B) 除 直接收入到Follow(U) 中，并把Follow(P)

13、中的全部内容传送到Follow(U) 中 )6/10六、 写递归下降子程序伪代码递归下降：将一个非终结符的文法规则看作将识别的一个过程的定义一个 if 语句（简化了的）文法规则是：if-stmt if (exp) statement|if (exp) statementelsestatement伪代码：procedureifstmt ；beginmatch （if ）；match（）；exp；match （）；statement；iftoken=else thenmatch（ else）；statement；end if；end ifstmt ；给出基于 DFA 进行词法分析的表驱动的实现算法

14、 p44 state:=1;ch:=next input character;while not acceptstate and not error(state) donew state:=Tstate,ch；if advancestate,ch then ch:=next input chracter; State：=newstate；end while;if acceptstate then accpet;7/10七、上下文无关文法BNF EBNF最左最右推导1、定义 ：上下文无关文法G 是一个四元组G = (N ， T， P， S)，其中N 是非终结符的有限集合；T 是终结符或单词的有限

15、集合，它与N 不相交；P 是形如 A 的产生式的有限集合，其中A N, V ,V=T NS 是 N 中的区分符号，称为开始符号或句子符号。V 中的符号称为文法符号，包括终结符和非终结符。2、 Backus-Naur 符号（就是众所周知的 BNF 或 Backus-Naur Form ）是描述语言的形式化的数学方法 ，由 John Backus (也许是 Peter Naur)开发，用于描述 Algol 60 编程语言的语法。3、 EBNF （扩展的BNF ）使用花括号 表示重复，方括号.表示可选EBNF中注意重复和可选的表示方法，语法图【可视的表示EBNF规则的图形表示法】上下文无关文法说明程

16、序设计语言的语法结构，利用了与正则表达式中极为类似的命名惯例和运算。二者的主要区别在于上下文无关文法的规则是递归的（recursive）最左推导（leftmost derivation ）是指它的每一步中最左的非终结符都要被替换的推导最右推导（rightmost derivation ）则是指它的每一步中最右的非终结符都要被替换的推导。最左推导和与其相关的分析树的内部节点的前序编号相对应；最右推导则和后序编号相对应最右推导的一个例子：文法规则： exp exp op exp | ( e x p)| n u m b e rop + | -| *分析树与抽象语法树有什么不同？对一个串按照某种文法进

17、行推导的过程 ，可以用一颗树表示出来， 这棵树就是分析树。分析树是表示记号串结构的一种十分有用的方法。抽象语法树是真正的源代码记号序列的抽象表示 ，包含了转换所需的所有信息，而且 比分析树效率更高 。8/10分析程序可以通过一个分析树表示所有步骤， 但却通常只能构造出一个抽象的语法树（或与它等同的） 。八、记号类型1、保留字，如 IF 何 THEN ，它们表示字符串“ if”和“ then”2、特殊符号，如算数符号加（PLUS）和减（ MINUS ），它们表示“ +”“ ”3、表示多字符串的记号，如NUM和 ，它们分别表示数字和标识符九、语言、句子、句型【语言】由推导从 exp 中得到的所有记

18、号符号的串集是被表达式的文法定义的语言【句型】从文法起始符号出发经过任意有限次推导出来的串【句子】 -的只有终结符的串十、自顶向下（第4 章） 自底向上（第 5 章）区别：自顶向下语法分析：从文法的开始符号出发，从顶部开始构造语法分析树。自底向上语法分析：从构成语法分析树的叶子节点的终结符号串开始，从底部开始构造语法分析树。1、自顶向下的分析算法通过在最左推导中描述出各步骤来分析记号串输入从文法的开始符号出发，从顶部开始构造语法分析树。自顶向下的分析程序有两类：回溯分析程序、预测分析程序。两类自顶向下分析的算法：递归下降分析、LL （ 1）分析。LL(1) ：第一个 L 指的是由左向右的处理输

19、入， 第 2 个 L 指的是为输入串描绘一个最左推导，括号里的 1 表示仅使用输入中的一个符号来预测分析的方向。P106-112递归下降：将一个非终结符的文法规则看作将识别的一个过程的定义First 集合follow 集合LL(1) 文法的判断及分析表2、自底向上 语法分析：从构成语法分析树的叶子节点的终结符号串开始，从底部开始构造语法分析树。自底向上分析法也称移进 -规约分析法。思想： 对输入串自左向右进行扫描，并将输入符逐个移入栈中，边移入边分析，一旦栈顶符号形成某个句型的句柄或可规约串时，就用产生式左部的非终结符代替之；这称为一步规约。9/10最普通的自底向上算法称作LR(1) 分析： L 表示自左向右处理输入，R 表示生成了最右推导SLR（ 1）分析是对LR （ 1）分析的改进LALR （1）比 SLR （1）略微强大且 比一般的LR （1）