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

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

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

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

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

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

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

7、的所有状态集合,它总是包含状态本身子集构造相关题目：2.1 , 2.12 , 2.16四、提左因子和消除左递归1、在建立LL(1)语法分析器的时候，提左因子和消除左递归的目的、原因 目的：提取左因子-避免程序回溯；消除左递归-消除无限循环原因：当有公因子存在时，不能立即区分出文法规则右边的选择; 当有左递归时，将导致一个无限循环。2、提左因子和消除左递归的算法描述 消除左递归 伪代码P119for i:=1 to m dofor j:=1 to i-1 dorep lace each grammer rule choice of the form ATAj 3 by the rule Ai T

8、 a 1 3 | a 2 3 |.| a k 3 , where Aj Ta 1| a 2|.|a k isthe curre nt rule for Ajremove,if n ecessary,immediate left recurs ion inv olvi ng Aia)把直接左递归改写为右递归【简单直接左递归】设有文法产生式：AtA3 | 丫。其中3非空，丫不以a打头。可写为：At Y A'a t 3 A'| £般情况下，假定关于a的产生式是【普遍的直接左递归】AtA a 1| a a 2"TAa m| 3 1 | 3 2 | | 3 n其中，a

9、 i(1 Wi Wm)均不为空，3 j(1 Wj W n)均不以 A打头。则消除直接左递归后改写为:At3 iA'|3 2 A' | 二|3 nA'A' T a 1A' |a 2A' |I amA' |£例4.12 :有文法G(E):Et E +T |TTt T*F | FFt i| (E) 消除该文法的直接左递归。解：按转换规则，可得:Et TE'E't+tE'| £Tt FT'T't *FT'|£iil (E)b）消除间接左递归【一般的左递归,不带有

10、3;产生式且不带有循环的文法】对于间接左递归的消除需要先将间接左递归变为直接左递归，然后再按a）清除左递归。例4.13 :以文法Ge为例消除左递归:(1)A t aB(2 )A t Bb(3) B tAc(4) B Td解：用产生式（1） , （2）的右部代替产生式（3）中的非终结A得到左部为B的产生式:(1)B TaBc(2)B T Bbc(3) B Td消除左递归后得到:Bt aBcB' |dB'B' T bcB' | £再把原来其余的产生式 AtaB,ATBb加入，最终得到等价文法为(1) a taB a t Bb B T(aBc|d)B'

11、;B'T bcB'| £c）消除文法中一切左递归的算法设非终结符按某种规则排序为a, a,，A。For i : =1 to n do beginFor j : =1 to i-1 do begin 若a的所有产生式为:a t 5 1| 5 2 | |5替换形如a T Aj Y的产生式为:a T § 1 Y |5 2 Y |3 n Y end 消除a中的一切直接左递归end提取左因子伪代码P122当两个或更多文法规则选择共享一个通用前缀时，需要提取左因子:按如下规则提取左因子:五、first集合follow集合 算法 伪代码P126P131具体看书上的例子U

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

13、含£，则把 First(B)除£直接收入到 Follow(U)中，并把 Follow(P)中的全部内容传送到 Follow(U)中)六、写递归下降子程序伪代码P10 6递归下降：将一个非终结符A的文法规则看作将识别A的一个过程的定义 一个if语句（简化了的）文法规则是：if-stmt T if (exp) statement| if (ex p) stateme ntelsestateme nt伪代码:procedure ifstmt;beginmatch(if);matchexp；matchstateme ntif toke n = else thenmatch (els

14、e)stateme ntend if； end ifstmt;给出基于DFA进行词法分析的表驱动的实现算法p44 state:=1;ch:=next input character;while not acce ptstate and not error(state) donew state:=Tstate,ch if advancestate,ch then ch:=next input chracter;State： =newstate； end while;if acce ptstate then acc pet;七、上下文无关文法 BNF EBNF 最左最右推导1、定义：上下文无关文法

15、 G是一个四元组 G = （N，T，P，S），其中N是非终结符的有限集合；T是终结符或单词的有限集合，它与N不相交；P是形如A fa的产生式的有限集合，其中A N, a V * ,V=T U NS是N中的区分符号，称为开始符号或句子符号。V中的符号称为文法符号，包括终结符和非终结符。2、Backus-Naur符号（就是众所周知的 BNF或Backus-Naur Form）是描述语言的形式化的 数学方法，由John Backus （也许是Peter Naur）开发，用于描述 Algol 60编程语言的语法。3、EBNF （扩展的BNF）使用花括号表示重复，方括号.表示可选EBNF中注意重复和可选

16、的表示方法，语法图【可视的表示EBNF®则的图形表示法】上下文无关文法说明程序设计语言的语法结构，利用了与正则表达式中极为类似的命名惯例和运算。recursive)二者的主要区别在于上下文无关文法的规则是递归的（最右推导则和后序编号相对应最左推导（leftmost derivation ）是指它的每一步中最左的非终结符都要被替换的推导 最右推导（rightmost derivation ）则是指它的每一步中最右的非终结符都要被替换的推导。 最左推导和与其相关的分析树的内部节点的前序编号相对应；最右推导的一个例子：文法规则： exp f exp op exp | (e x p) | n

17、 u m b e rop f + |- | *exp => exp op exp=> exp op n umber=exp * lamsher(exp ) * exp op exp * niur(exp op jium&ez- * xtuz&ber (Exp - auzEtbez* * jaumbez*(-) * number=>=>啊> EXp op exp lejcp * nuobftrexp I ( etp > kg? > exp op exp kv f mtnber-exp f znioter图3-1算术表达式（34-3）*42

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

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

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