2022年《编译原理》重点知识总结.docx

《2022年《编译原理》重点知识总结.docx》由会员分享，可在线阅读，更多相关《2022年《编译原理》重点知识总结.docx（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理学问点总结目录第一章 引论其次章 高级语言及其语法描述第三章 语法分析自上而下分析第四章 属性文法和语法制导翻译第五章 语义分析和中间代码产生第六章 优化第一章 引论一编译程序 compiler:把某一种高级语言程序等价地转换成另一种低级语言程序 如汇编语言或机器语言程序 的程序二编译程序的工作的五个阶段 :词法分析、语法分析、中间代码产生、优化、目标代码产生1. 词法分析任务:输入源程序, 对构成源程序的字符串进行扫描和分解, 识别出一个个单词符号；依循的原就：构词规章描述工具：有限自动机FORI:=1TO100DO保留字 标识符 等符 整常数 保留字 整常数保留字2. 语法分析任务

2、: 在词法分析的基础上,依据语言的语法规章把单词符号串分解成各类语法单位；依循的原就：语法规章 述工具：上下文无关文法3. 语义分析与中间代码产生任务: 对各类不同语法范畴按语言的语义进行初步翻译； （变量是否定义、类型是否正确等）依循的原就：语义规章中间代码 : 三元式,四元式,逆波兰记号,树形结构等；是一种独立于详细硬件的记号系统；例：将 Z:=X + * Y翻译成四元式为(1) *YT12+XT1T23 :=T2_Z4. 优化任务：对于前阶段产生的中间代码进行加工变换,以期在最终阶段产生更高效的目标代码；依循的原就：程序的等价变换规章FOR K:=1 TO 100 DO BEGINM :

3、= I + 10 * K;N := J + 10 * K;END4. 目标代码产生任务:把中间代码变换成特定机器上的目标代码；依靠于硬件系统结构和机器指令的含义目标代码三种形式 :a) 肯定指令代码 :可直接运行b) 可重新定位指令代码 :需要连接装配c) 汇编指令代码 :需要进行汇编其次章 高级语言及其语法描述语法词法规章：单词符号的形成规章；a) 单词符号是语言中具有独立意义的最基本结构；一般包括： 常数、标识符、基本字、算符、界符等；b) 描述工具：正规式和有限自动机语法规章：语法单位的形成规章；a) 语法单位通常包括： 表达式、语句、分程序、过程、函数、程序等;c) 描述工具：上下文无

4、关文法语义语义：一组规章,用它可以定义一个程序的意义；描述方法：a) 自然语言描述：隐匿错误、二义性和不完整性b) 形式描述：无二义性完整性多数语言中,算符的优先次序如下： 乘幂（ * 或）一元负（ - ） 乘、除加、减关系符（ ,=,）非（ .,not ） 与 , &,and 或 . ,|,or,隐含或 imp等值（或 epui ,或）2.3 程序语言的语法描述1. 几个概念 :a) 考虑一个有穷字母表 字符集b) 其中每一个元素称为一个字符c) 上的字 也叫字符串 是指由中的字符所构成的一个有穷序列d) 不包含任何字符的序列称为空字,记为e) 用 *表示上的全部字的全体 , 包含空字*例如

5、:设 =a , b ,就 = ,a,b,aa,ab,ba,bb,aaa,.f) *的子集 U和 V的连接（积）定义为 UVb |U & bV 例如:设： U a, aa ,V b, bb那么： UV= ab, abb, aab, aabb g) V自身的 n 次积记为 Vn=VVVh) 规定 V0= ,令 V* =V0V1 V2V3 称 V* 是 V 的闭包;记 VVV*,称 V+是 V的正规闭包；例如:设： U a, aa那么： U* = , a, aa, aaa, aaaa,U = a, aa, aaa, aaaa,i) 0 型 短语文法,图灵机 ：产生式形如：*其中：V TVN 且至少含

6、有一个非终结符；V T*VN任何 0 型语言都是递归可枚举的；j) 1 型 上下文有关文法,线性界限自动机 ： 产生式形如：其中： | ,仅 S例外；意味着对非终结符进行替换时务必考虑上下文,并且,一般不答应替换成空串；*k) 2 型 上下文无关文法,非确定下推自动机 ： 产生式形如：A其中： AV N；V TVN ；非终结符的替换可以不必考虑上下文；*l) 3 型 正规文法,有限自动机 ： 产生式形如： AB 或 A 其中：VT ；A,BVN 产生式形如： AB或 A 其中：VT ；A,BVN正规文法的才能要比上下文无关文法弱得多；四种类型描述才能比较m) 上下文无关文法的定义：一个上下文无

7、关文法 G是一个四元式G=VT,VN,S,P ,其中VT：终结符集合 非空 VN：非终结符集合 非空 ,且 VTVN= S：文法的开头符号, SVN*P：产生式集合 有限 ,每个产生式形式为P, PVN,V TVN开头符 S 至少必需在某个产生式的左部显现一次；例：文法 G1A ： Ac|AbG1A 的语言解： LG1=c , cb,cbb, ,以 c 开头,后继如干个 bn) 定义：假如一个文法存在某个句子对应两颗不同的语法树,就说这个文法是二义的；GE： Ei|E+E|E*E|E是二义文法；o) 语言的二义性： 一个语言是二义性的, 假如对它不存在无二义性的文法；可能存在 G和 G,一个为

8、二义的,一个为无二义的；但 LG=LG2. 状态转换图a) 概念：状态转换图是一张有限方向图；b) 结点代表状态,用圆圈表示；c) 状态之间用箭弧连结, 箭弧上的标记 字符 代表射出结状态下可能显现的输入字符或字符类；d) 一张转换图只包含有限个状态, 其中有一个为初态, 至少要有一个终态3. 正规运算符优先次序在不致混淆时,括号可以省去,但规定算符的优先次序为：* （闭包）.（连接）|（或）4. 3型文法- 正规式G的任何产生式为 AB 或 A*其中：VT ；A,BVN3型文法等价于正规式,所以也称正规文法；确定有限自动机 DFA对状态图进行形式化,就可以下定义：自动机 M是一个五元式 M=

9、S, f, S0 , F,其中：a) S: 有穷状态集,b) ：输入字母表 有穷 ,c) f:状态转换函数,为 SS的单值部分映射, fs , a=s 表示：当现行状态为 s,输入字符为 a 时,将状态转换到下一状态 s；我们把 s称为 s 的一个后继状态；d) S0S是唯独的一个初态；e) FS ：终态集 可空 ；例如： DFA M=0 ,1,2,3 ,a ,b ,f ,0,3 , 其中： f 定义如下：f0 , a=1f0 , b=2f1 , a=3f1 , b=2f2 , a=1f2 , b=3f3 , a=3f3 , b=3非确定有限自动机 NFA定义：一个非确定有限自动机 NFA M

10、 是一个五元式 M=S, f, S0, F ,其中：1 S:有穷状态集；2 ：输入字母表 有穷 ；3 f:状态转换函数,为 S*2S 的部分映射 非单值 ；4 S0S 是非空的初态集；5 FS ：终态集 可空 ；从状态图中看 NFA 和 DFA的区分：1 弧上的标记可以是*中的一个字,而不肯定是单个字符；2 同一个字可能显现在同状态射出的多条弧上；DFA是 NFA的特例；定义：对于任何两个有限自动机M和 M,假如 LM=LM ,就称 M与 M等价；自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的；对于每个 NFA M存在一个 DFA M,使得 LM=LM ；亦即 DFA与 NFA

11、描述才能相同；把上述 NFA确定化采纳子集法 .设 I 是 M的状态集的一个子集,定义I 的 - 闭包 -closureI为:i) 如 sI ,就 s-closureI；ii) 如 sI ,就从 s 动身经过任意条弧而能到达的任何状态 s都属于 -closureI即-closureI=Is | 从某个 sI 动身经过任意条弧能到达s例：设 a 是 中的一个字符,定义 I a=-closureJ其中, J 为 I 中的某个状态动身经过一条 a 弧而到达的状态集合；正规文法与有限自动机的等价性定理：1. 对每一个右线性正规文法G或左线性正规文法 G,都存在一个有限自动机FA M ,使得 LM LG

12、 ；2. 对每一个 FA M,都存在一个右线性正规文法 GR和左线性正规文法 GL,使得 LM LGR LGL ；3.3.5 正规式与有限自动机的等价性定理：1. 对任何 FA M,都存在一个正规式r ,使得 Lr=LM ；2. 对任何正规式 r ,都存在一个 FA M,使得 LM=Lr ；对转换图概念拓广,令每条弧可用一个正规式作标记； 对一类输入符号 确定有限自动机的化简对 DFA M的化简: 查找一个状态数比 M少的 DFA M,使得 LM=LM 假设 s 和 t 为 M的两个状态,称 s 和 t 等价: 假如从状态 s 动身能读出某个字 而停止于终态,那么同样,从 t 动身也能读出而停

13、止于终态； 反之亦然；两个状态不等价,就称它们是可区分的；对一个 DFA M最少化的基本思想 :把 M的状态集划分为一些不相交的子集,使得任何两个不同子集的状态是可区分的,而同一子集的任何两个状态是等价的；最终,让每个子集选出一个代表,同时消去其他状态；I 1 =0, 1, 2I2 =3, 4, 5, 6aI 1 =1, 3I11 =0, 2I12 =1 I2 =3, 4, 5, 611I 11 =0, 2I11a=1 Ib=2, 5I111 =0I112 =2 I12 =1 I2 =3, 4, 5, 6aI 2 =3, 6I2 =4, 5a第三章 语法分析自上而下分析语法分析的方法：自下而上

14、分析法 Bottom-up自上而下分析法 Top-down基本思想：它从文法的开头符号动身,反复使用各种产生式,查找 匹配 的推导；递归下降分析法：对每一语法变量 非终结符 构造一个相应的子程序,每个子程序识别肯定的语法单位,通过子程 序间的信息反馈和联合作用实现对输入串的识别；猜测分析程序优点：直观、简洁和宜于手工实现；LL1分析法构造不带回溯的自上而下分析算法要排除文法的左递归性 克服回溯左递归的排除直接排除见诸于产生式中的左递归：假定关于非终结符P 的规章为PP |其中 不以 P 开头；我们可以把 P 的规章等价地改写为如下的非直接左递归形式： P PP P|一般而言,假定 P 关于的全

15、部产生式是PP 1 | P2 | | Pm |1 |2 | | n其中,每个都不等于,每个都不以 P 开头那么,排除 P 的直接左递归性就是把这些规章改写成： P 1P|2P| |nPP 1P|2P| |mP|提取公共左因子 :假定关于 A 的规章是A1 |2 |n |1 |2 | |m 其中,每个不以 开头那么,可以把这些规章改写成A A|1 |2 | |mA1 |2 | |n经过反复提取左因子,就能够把每个非终结符 包括新引进者 的全部候选首符集变成为两两不相交；LL1分析条件假定 S 是文法 G的开头符号,对于 G的任何非终结符 A,我们定义FOLLOWA* a | S.Aa.,aVT

16、特殊是,如 S*. . .A,就规定FOLLOWA构造不带回溯的自上而下分析的文法条件1. 文法不含左递归,2. 对于文法中每一个非终结符 A 的各个产生式的候选首符集两两不相交；即,如A1 |2 | | n就 FIRSTi FIRSTj ij i=1,2,.,n3. 对文法中的每个非终结符A,如它存在某个候选首符集包含,就FIRSTA FOLLOWA=假如一个文法 G满意以上条件,就称该文法 G为 LL1 文法；第四章 语法分析自下而上分析语法分析的方法：自下而上分析法 Bottom-up基本思想：从输入串开头,逐步进行“归约”,直到文法的开头符号；即从树末端开头,构造语法树；所谓归约, 是

17、指依据文法的产生式规章,把产生式的右部替换成左部符号；算符优先分析法：依据算符的优先关系和结合性质进行语法分析；适合分析表达式；LR分析法：规范归约5.1.2 规范归约1. 定义：令 G是一个文法, S是文法的开头符号,假定是文法 G的一个句型,假如有*且SA, A就称 是句型相对于非终结符 A 的短语；特殊是,假如有 A, 就称 是句型相对于规章 A的直接短语；一个句型的最左直接短语称为该句型的句柄；2. 归约采纳“移进归约”思想进行自下而上分析；基本思想： 用一个寄存符号的先进后出栈, 把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成 归约为 该产生

18、式的左部符号；算符优先分析四就运算的优先规章：先乘除后加减,同级从左到右考虑二义文法文法 GE：GE： Ei| E+E|E-E|E*E|E/E|E它的句子有几种不同的规范规约；归约即运算表达式的值；归约次序不同,就运算的次序也不同,结果也不一样；假如规定算符的优先次序,并按这种规定进行归约,就归约过程是唯独的；起打算作用的是相邻的两个算符之间的优先关系；所谓算符优先分析法就是定义算符之间的某种优先关系,借助于这种关系查找“可归约串”和进行归约；算符优先文法及优先表构造一个文法,假如它的任一产生式的右部都不含两个相继 并列 的非终结符,即不含如下形式的产生式右部：QR就我们称该文法为算符文法；商

19、定：a、b 代表任意终结符；P、Q、R代表任意非终结符； 代表由终结符和非终结符组成的任意序列,包括空字；假定 G是一个不含- 产生式的算符文法；对于任何一对终结符a、b, 我们说：1. a=b当且仅当文法 G中含有形如 P ab或 P aQb的产生式；2. ab当且仅当 G中含有形如 P Rb的产生式,而 Ra或 RaQ；假如一个算符文法 G中的任何终结符对 a ,b 至多只满意下述三关系之一： a=b, ab ； 就称 G是一个算符优先文法；从算符优先文法 G构造优先关系表的算法；通过检查 G的每个产生式的每个候选式,可找出全部满意a=b 的终结符对；确定满意关系 的全部终结符对：第一需要

20、对 G的每个非终结符 P 构造两个集合 FIRSTVTP和LASTVTP：FIRSTVT P a | Pa . ., PQa . ., aVTQVN ab当且仅当 G中含有形如 P Rb的产生式,而 Ra或 RaQ；有了这两个集合之后,就可以通过检查每个产生式的候选式确定满意关系的全部终结符对；假定有个产生式的一个候选形为 aP 那么,对任何 b FIRSTVTP,有 ab ；按其定义,可用下面两条规章来构造集合FIRSTVTP：1. 如有产生式 Pa或 PQa,就 aFIRSTVTP；2. 如 aFIRSTVTQ,且有产生式 PQ,就 aFIRSTVTP；练习： P133-2 运算它的 FI

21、RSTVT和 LASTVT； 运算 G的优先关系 ；并确定 G是否是一个算符优先文法LR分析方法：把 历史 及 展望 综合抽象成状态；由栈顶的状态和现行的输入符号唯独确定每一步工作LR分析器的核心是一张分析表：ACTIONs, a ：当状态 s 面临输入符号 a 时,应实行什么动作 .GOTOs,X ：状态 s 面对文法符号 X 时,下一状态是什么文法 G的每个产生式的右部添加一个圆点称为G的 LR0 项目例：如:AXYZ有四个项目：A.XYZAAAXYZ.A.称为 归约项目 归约项目 S.称为 接受项目 A.aaVT称为 移进项目 A.BBVN称为 待约项目 .例：文法 GSSEE aA|b

22、B A cA|d B cB|d 该文法的项目有：EE aAaAaA cAcAcA dd bBbBbB cBcBcBd d构造识别文法全部活前缀的 NFA方法1. 如状态 i 为 XX1 X n ,状态 j 为 XX1 X i-1 Xi .X i+1Xn ,就从状态 i 画一条标志为 Xi 的有向边到状态 j ；2. 如状态 i 为 X.A,A 为非终结符,就从状态 i 画一条边到全部状态 A.；把识别文法全部活前缀的 NFA确定化；构成识别一个文法活前缀的 DFA的项目集 状态 的全体称为文法的LR0 项目集规范族；LR0 分析表的构造假如一个文法 G的拓广文法 G的活前缀识别自动机中的每个状

23、态 项目集 不存在下述情形：1) 既含移进项目又含归约项目,2) 含有多个归约项目就称 G是一个 LR0 文法；分析表的 ACTION和 GOTO子表构造方法：1. 如项目 A a 属于 I k 且 GOIk, a I j ,a 为终结符,就置ACTIONk,a为“ sj ”；2. 如项目 A 属于 I k,那么,对任何终结符a 或终止符 # ,置ACTIONk,a 为 “rj ” 假定产生式 A 是文法 G的第 j 个产生式 ；3. 如项目 SS属于 I k,就置 ACTIONk,# 为 “acc”；4. 如 GOIk ,A I j ,A 为非终结符,就置 GOTOk,A=j ；5. 分析表

24、中凡不能用规章1 至 4 填入信息的空白格均置上“报错标志”；按上述方法构造出的 ACTION与 GOTO表假如不含多重入口,就称该文法为 SLR1文法；使用 SLR表的分析器叫做一个 SLR分析器；每个 SLR1文法都是无二义的；但也存在很多无二义文法不是SLR1的.I 1、I 2 和 I 9 都含有“移进归约”冲突；FOLLOWE #, , +,规范 LR分析表的构造我们需要重新定义项目,使得每个项目都附带有k 个终结符；每个项目的一般形式是 A , a 1a2ak,这样的一个项目称为一个 LRk项目；项目中的 a 1a2ak 称为它的向前搜寻符串 或展望串 ；向前搜寻符串仅对归约项目A

25、, a1a2 ak 有意义；对于任何移进或待约项目 A , a 1a2 ak,搜寻符串 a 1a2ak没有作用；按上述算法构造的分析表,如不存在多重定义的入口 即,动作冲突 的情形,就称它是文法 G的一张规范的 LR1 分析表；使用这种分析表的分析器叫做一个规范的LR 分析器；具有规范的 LR1 分析表的文法称为一个 LR1 文法；LR1 状态比 SLR多, LR0SLRLR1无二义文法；第六章 属性文法和语法制导翻译属性文法属性文法（也称属性翻译文法）在上下文无关文法的基础上,为每个文法符号（终结符或非终结符）配备如干相关的“值”（称为属性）；属性代表与文法符号相关信息,如类型、值、代码序列

26、、符号表内容等属性可以进行运算和传递语义规章：对于文法的每个产生式都配备了一组属性的运算规章属性综合属性：“自下而上”传递信息继承属性：“自上而下”传递信息综合属性在语法树中,一个结点的综合属性的值由其子结点的属性值确定；使用自底向上的方法在每一个结点处使用语义规章运算综合属性的值仅仅使用综合属性的属性文法称S属性文法继承属性在语法树中,一个结点的继承属性由此结点的父结点和/ 或兄弟结点的某些属性确定用继承属性来表示程序设计语言结构中的上下文依靠关系很便利一遍扫描的处理方法一遍扫描的处理方法是在语法分析的同时运算属性值所采纳的语法分析方法属性的运算次序L属性文法适合于一遍扫描的自上而下分析S属

27、性文法适合于一遍扫描的自下而上分析L-属性文法和自顶向下翻译通过深度优先的方法对语法树进行遍历,运算属性文法的全部属性值LL1 ：自上而下分析方法,深度优先建立语法树第七章语义分析和中间代码产生静态语义检查类型检查掌握流检查 一样性检查 相关名字检查名字的作用域分析中间语言常用的中间语言：后缀式,逆波兰表示图表示： DAG、抽象语法树三地址代码三元式四元式间接三元式逆波兰表示法不用括号；只要知道每个算符的目数,对于后缀式,不论从哪一端进行扫描,都能对它进行唯独分解；后缀式的运算用一个栈实现；一般的运算过程是：自左至右扫描后缀式,每遇到运算量就把它 推动栈；每遇到 k 目运算符就把它作用于栈顶的

28、 k 个项,并用运算结果代替这 k 个项；布尔表达式的翻译布尔表达式的两个基本作用 :用于规律演算 , 运算规律值 ;用于掌握语句的条件式 .产生布尔表达式的文法 :EE or E | E andE |E | E | i rop i | i第十章优化优化：对程序进行各种等价变换,使得从变换后的程序动身,能生成更有效的目标代码；等价：指不转变程序的运行结果；有效：指目标代码运行时间短,占用的储备空间小；概述优化的三个不同级别： 局部优化循环优化全局优化优化的种类：删除余外运算 或称删除公用子表达式 代码外提强度消弱变换循环掌握条件合并已知量复写传播删除无用赋值局部优化局限于基本块范畴内的优化称为

29、基本块内的优化,或称局部优化；在一个基本块内通常可以实行下面的优化:删除公共子表达式删除无用赋值合并已知量 暂时变量改名交换语句的位置代数变换划分四元式程序为基本块的算法 :1. 求出四元式程序中各个基本块的入口语句:1) 程序第一个语句,或2) 能由条件转移语句或无条件转移语句转移到的语句,或3) 紧跟在条件转移语句后面的语句；循环优化对循环中的代码,可以实行： 代码外提强度消弱删除归纳变量 变换循环掌握条件 循环绽开循环合并代码外提循环不变运算 : 对四元式 A:=B op C, 如 B和 C是常数,或者到达它们的B和 C的定值点都在循环外；所谓变量 A 在某点 d 的定值到达另一点 u（

30、或称变量 A的定值点 d 到达另一点 u）,是指流图中从 d 有一通路到达 u 且该通路上没有 A的其它定值；d : A:=B op Cu : D:=A op E把循环不变运算提到循环体外；强度消弱把程序中执行时间较长的运算转换为执行时间较短的运算；强度消弱强度消弱主要是对与归纳变量有线性关系的变量赋值进行；经过强度消弱后,循环中可能显现一些新的无用赋值； 对于消弱下标变量地址运算的强度特别有效；删除归纳变量假如循环中对变量 I 只有唯独的形如 I:=IC的赋值,且其中 C为循环不变量,就称 I 为循环中的基本归纳变量；假如 I 是循环中一基本归纳变量, J 在循环中的定值总是可化归为 I 的同一线性函数,也即 J=C1 *IC2,其中 C1 和 C2 都是循环不变量,就称 J 是归纳变量,并称它与 I 与族；一个基本归纳变量也是一归纳变量；删除归纳变量是在强度减弱以后进行的；强度减弱和删除归纳变量的统一算法框架,其步骤如下：1. 利用循环不变运算信息,找出循环中全部基本归纳变量；2. 找出全部其它归纳变量 A,并找出 A与已知基本归纳变量 X的同族线性函数关系 F AX ；3. 对 2 中找出的每一归纳变量A,进行强度减弱；4. 删除对归纳变量的无用赋值；