[农学]编译原理复习资料

《[农学]编译原理复习资料》由会员分享，可在线阅读，更多相关《[农学]编译原理复习资料（67页珍藏版）》请在金锄头文库上搜索。

1、基本概念 第一章 计算机程序设计语言 高级语言的执行过程 解释程序、编译程序及其区别 编译过程的五个阶段 编译程序的七个组成部分及其关系 “遍”的概念 编译程序的开发技术 构造编译程序所应掌握的内容基本概念 第二章 单词符号的分类和输出形式 状态转换图 正规表达式和正规集 符号、字母表、符号串、空符号串、符号串集合 自反闭包、正则闭包 有限自动机、确定有限自动机、非确定有限自动机 有限自动机的表示 词法分析器自动生成系统LEX、语法分析器自动生 成工具YACC基本概念 第三章 文法和语言 文法的开始符号、终结符、非终结符和产生式 直接推导和推导、最左推导、最右推导 文法产生的语言 形式语言分类

2、、四类文法的关系与区别 规范推导、短语、句柄、素短语 语法树、子树和短语 文法的二义性基本概念 第三章（续） 自上而下分析法：递归下降分析、LL(1)分析 递归下降分析法 要点:自上而下分析存在的不确定性如何实现确定的(即无回溯的)自上而下分析?消除左递归、消除回溯 LL(1)分析法 要点: LL(1)分析法的基本思想LL(1)分析器组成LL(1)文法的性质基本概念 第三章（续） 自下而上分析法：算符优先分析法、LR分析法 归约、规范归约、可归约串、最左素短语 算符文法和算符优先文法 算符优先关系表 LR分析法对文法的限制 LR分析器的工作原理 活前缀、 LR(0)项目、 LR(0)项目集规范

3、族 拓广文法、 LR(0)文法 SLR(1)分析法、 SLR(1)文法基本概念 第四章 语义分析的概念 语法制导翻译方法 文法的属性、继承属性与综合属性 属性文法 几种常见的中间语言 数组元素的地址计算 变址存数、变址取数基本概念 第五章 优化、优化三个不同的级别 局部优化、循环优化和全局优化 基本块、局部优化常用的优化技术 利用DAG进行基本块优化的基本思想 程序流图、必经结点、必经结点集、回边、循环 可归约流图 循环优化常用的优化技术基本方法 正规表达式和正规集 正规表达式到有限自动机的构造 文法和语言 推导和归约 文法二义性的消除 消除左递归、消除回溯 LL(1)文法的判别 FIRST集

4、合、FOLLOW集合的构造 LL(1)分析表的构造基本方法 算符优先文法的判别 FIRSTVT集合、LASTVT集合的构造 算符优先关系表的构造 LR(0)分析表的构造 SLR(1)分析表的构造 表达式翻译成逆波兰式 典型语句的翻译（生成四元式序列） 基本块的划分、基本块的优化 程序流图、必经结点集、回边、循环正规式到正规文法的转换与正规式R=a(a|d)*等价的正规文法G的产生过程为 1.正规式a(a|d)*的字母表=a,d,故G的VT=a,d 2.设定开始符号S,生成产生式S a(a|d)* 3.按分解规则:SaA,A(a|d)*SaA,A(a|d)A,ASaA,AaA|dA,A 故得到等

5、价的正规文法G:SaAAaA|dA|正规文法到正规式的转换与含有下列产生式的正规文法G:SaAAaA|aBBbCCcB|c 等价的正规式的产生过程为 将CcB|c代入BbC得Bb(cB|c),即BbcB|bc 也就是B(bc)*(bc)或者写成B(bc)+ 将B(bc)+代入AaA|aB得AaA|a(bc)+,即Aa+(bc)+ 将Aa+(bc)+代入SaA得Saa+(bc)+ 因此,与文法G等价的正规式为aa+(bc)+正规文法到FA的转换方法设有正规文法GS:SaA|bB|aAaB|bABaS|bA|b 则与GS等价的FA构造过程如下: 1.FA的=a,d. 2.GS有三个非终结符S、A、

6、B,对应FA的三个状态. 3.S为开始状态. 4.另设一个状态Z作为FA的终态. 5.对GS的每个产生式构造转换函数,画出FA的状态 转换图.SBZAabbbaaabFA到正规文法的转换方法有FA如右图所示。 构造其对应的正规文 法G=(VN,VT,S,P) 1.VT=0,1 2.VN=A,B,C,D 3.开始符为A 4.产生式为：A1D|0B|0B0D|1CC0B|1D|0D0D|1B|1ADBC01111000FA到正规式的转换方法02413 a,baba,ba,bbaFA到正规式的转换方法（续）02413 a,baba,ba,bbaXYFA到正规式的转换方法（续）024a|bbb a|b

7、a|baaXYFA到正规式的转换方法（续）0a|bbb(a|b)*aa(a|b)*XYFA到正规式的转换方法（续）0a|b (aa|bb)(a|b)* XYXY(a|b)*(aa|bb)(a|b)*正规式到FA的转换方法将正规式r=10|(0|11)0*1转换成等价的FA:XY10|(0|11)0*1XY(0|11)0*110正规式到FA的转换方法（续）XY(0|11)0*11 10正规式到FA的转换方法（续）XY0*1 1023 0|111正规式到FA的转换方法（续）XY0*1 10231110正规式到FA的转换方法（续）XY0*1 102311041正规式到FA的转换方法（续）XY1 10

8、231104150文法和语言1.已知文法G，求L(G): 例如：文法G:S0S1|01描述的语言是：L(G)=0n1n|n1 也可以用文字描述。特别，已知文法G和若干句子，判断哪个（些）句 子是由文法G产生的；文法和语言（续）已知语言L(G)，构造文法G:例如：L(G)=abna|n0，文法G=(VT,VN,S,P):其中：VT=a,b, VN=S,R,S为开始符,P为：Saa|aRaRb|Rb文法和语言（续） 1.L(G)=0n|n1 GS:S0|0S 2.L(G)=0n|n0 GS:S|0S 3.L(G)=1n0m|nm1 GS:SABA1|1AB0|0B 4.L(G)=1n0n|n1 G

9、S:S1S0|10 5.L(G)=1n0n|n0 GS:S1S0| 6.L(G)=anbmck|n,m,k1 GS:SABCAa|aABb|bBCc|cC词法分析程序的自动生成工具LEX简介LEX是一个已被广泛使用的词法分析程序的自 动生成工具，在UNIX系统中用lex命令调用，我们 只要告诉LEX某种语言的单词是如何构成的，它就 能够构造出该语言的词法分析程序。我们知道，程序设计语言的单词可以用正规式 进行描述，根据正规式可以构造出识别单词的词法 分析程序LEX接受这种正规式，然后自动生成单 词的识别程序（即词法分析程序），这一过程可以 理解为将正规式翻译成识别程序，所以LEX也被称 做LE

10、X编译程序。假定要做生成A语言的词法分析程序，则LEX 编译程序、A语言词法分析器的关系如下图所示。词法分析程序的自动生成工具LEX简介（续 ）A语言的LEX源程序LEX编译程序A语言词法分析器A语言源程序A语言源程序 中的单词词法分析程序的自动生成工具LEX简介（续 ）具体来说，LEX用自己的一种语言LEX 语言来对A语言的词法分析器进行说明，形成一 个LEX源程序，其一般格式为辅助定义部分识别规则部分用户子程序部分词法分析程序的自动生成工具LEX简介（续 ） 辅助定义部分这部分是为了给用户在后面的使用中提供方便而设计的， 如为一个复杂的正规式定义一个名字，定义的格式为名字 正规式例如，将标

11、识符（字母开头的字母数字串）的正规式a- zA-Za-zA-Z0-9定义为名字id、无符号整常数（数字 串）的正规式0-90-9定义为名字number，则可以 给出以下辅助定义：id a-zA-Za-zA-Z0-9number 0-90-9 正规式被定义后，在后面的识别规则中就可以用名字替代 这个正规式了，其使用方法是用“”将名字括起来，如id ，这样LEX就会自动用已定义的正规式去解释id。词法分析程序的自动生成工具LEX简介（续 ）.识别规则部分这部分是一串如下形式的LEX语句：P1 A1P2 A2Pn An其中：每一个Pi都是一个正规式，定义了一种单词的词形。每一个Ai是配备给Pi的一小

12、段程序代码，指出了即将生成的 词法分析程序在识别了Pi所定义的单词之后需要做的“动作” ，例如向语法分析程序返回该单词的机内码。事实上，LEX语言并不是一个完整的语言，它只是某种 程序设计语言的扩充，这种程序设计语言也称做宿主语言， LEX本身没有描述“动作”的语句，“动作”的描述是由宿主语 言完成的，例如，宿主语言是C语言，则每个Ai就是一段C语 言程序。词法分析程序的自动生成工具LEX简介（续 ） 用户子程序部分当词法分析程序对源程序完成扫描时，用户 可能希望词法分析程序再做某些工作，如输出表 格、输出统计结果等，这时，用户就可以编写一 个子程序，并将该子程序放在这里。若用户对A语言编写了

13、以上格式的LEX源程 序，则LEX编译程序会根据其中每个Pi的定义， 自动构造出识别这些单词的C程序段，并将其与 相应的Ai相结合，最后结合上“用户子程序”就形 成了一个完整的C语言程序，这个C语言程序也就 是A语言的词法分析程序。语法分析器自动生成工具YACC简介YACC(Yet Another Compiler_Compiler)是一 个已被广泛使用的语法分析程序的自动生成工具。YACC的输入是某种语言的语法描述，输出是该 语言的语法分析程序。假定要生成A语言的语法分析 程序，则YACC、A语言语法分析器的关系如下图所 示：YACCA语言语法分析器 yyparse词法分析器 yylexA语

14、言的YACC源程序A语言源程序语法分析的输出语法分析器自动生成工具YACC简介（续）1。 YACC对语言的要求YACC要求A语言必须是上下文无关语言，且描 述它的文法满足LALR(1)的要求，用户必须采用 YACC提供的语法描述规格说明来描述A语言的文法 ，这个A语言的语法描述规格说明也称作YACC源程 序。2。YACC的输入输出YACC以YACC源程序为输入，自动生成用 LALR(1)方法进行语法分析的A语言的语法分析程序 ，也就是生成文法的LALR(1)分析表，并与总控程序 和分析栈相结合，构成一个完整的LALR(1)语法分析 器yyparse。语法分析器自动生成工具YACC简介（续）与L

15、EX一样，YACC的宿主语言也是C，生成 的yyparse也是一个C语言的程序。yyparse要求有一个名为yylex的词法分析程 序与它配合，用户可以借助LEX来构造yylex，所以 LEX与YACC可以配合使用。YACC源程序的作用是对A语言的语法进行说 明，同时给出语义动作语法规则用于归约时应 完成的动作。yyparse的输出可以是语法树，也可以是生成 的中间代码、目标代码，或者是一些语法信息，究 竟是什么完全由语义动作及YACC源程序中给出的 一些辅助过程决定。语法分析器自动生成工具YACC简介（续）3。YACC源程序YACC源程序由三部分组成：说明部分、语法规则部分和 辅助过程部分，其一般格式为说明部分%语法规则部分%辅助过程部分说明部分这部分用以定义语法规则部分要用的终结符、语义动作 中使用的数据类型、变量、语义值的联合类型以及运算符的 优先级等，具体包括：头文件表：一系列的C语言的#include语句；宏定义：用C语言的#define语句定义程序中要用的宏；数据类型定义：定义语义动作或辅助过程中要用到的数 据类型；语法分析器自动生成工具