广工编译原理复习

1、编译原理复习 Always麦第一章 引论l 什么是编译程序：翻译程序：将一种语言（源语言）翻译成另一种逻辑上等价的语言（目标语言）的程序。编译程序：源语言为高级语言，目标语言是低级语言（汇编或机器语言）的翻译程序。l 与解释语言的区别：编译程序（器）解释程序（器）概念：翻译整个源程序，产生一份目标代码概念：边翻译边执行，不产生目标代码优：执行效率较高，空间开销较小劣：执行效率较低，空间开销大劣：交互性差，较复杂优：交互性好，较简单l 图1.2 高级语言程序的处理过程 P1需预处理的源程序预处理的程序源程序编译程序目标汇编程序汇编程序可再装配的机器代码装配/连接 -编译程序绝对机器代码可再装配目

2、标文件圈起来部分可以省略l 图1.10 编译程序结构框图 P6l 前端、后端的概念：前端：与源语言有关，而与目标机无关的编译程序后端：与目标机有关，而与源语言无关的编译程序l 遍、趟的概念：是对源程序或源程序的中间结果从头到尾扫描并完成规定任务的过程第二章 PL/0 编译程序的实现l P18 三个变量通过三个全程量 SYM 、ID和NUM 将识别出的单词信息传递给语法分析程序。SYM：存放单词的类别，用内部编码形式表示。ID：存放用户所定义的标识符的值。即标识符字符串的机内表示。NUM：存放用户定义的数。l P22 符号表 【画】TX： table表的下标指针,是以值参数形式使用的。DX：计算

3、每个变量在运行栈中相对本过程基地址的偏移量，每次都会初始化为3l P29 运行栈 【画】RA返回地址：记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址DL动态链：指向调用该过程前正在运行过程的数据段基地址。SL静态链：指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址l P28 I P T 寄存器I： 指令寄存器。存放当前正在解释的一条目标指令P： 程序地址寄存器。指向下一条要执行的目标程序的地址T： 栈顶寄存器。指向当前栈中最新分配的单元B: 总是指向当前执行过程活动记录的起始地址l CX 、 CODECX为目标代码CODE数组的下标指针l第三章 文法和语言3.1

4、 文法的直观概念ü 语法：每个程序的构成规律。判断“句子”是否为语言的合法程序的规则。包括：词法规则à字符组成的单词； 语法规则à单词组成语法单元ü 语义：每个程序的含义。赋予程序意义的规则ü 语用：每个程序和使用者之间的关系3.2 符号和符号串 àà基本不考3.3 文法和语言的形式定义l 文法的定义： 文法是描述语法的形式化工具文法G是一个四元组( VN, VT, P, S )VN为非终结符的有穷集合 VNVT = VT为终结符的有穷集合 P为产生式（或规则式）有穷集合 形如 xyS为文法的开始符号 SVN ，至少要在一条

5、产生式的左部出现l 推导：【按要求推导】 AAy 直接推导 A => Ay 间接推导 直接推导：每条产生式只能用一次最左推导：对于直接推导v=xAy=>xuy=w，若xVT*，即A是v中最左非终结符，则称此直接推导为最左直接推导，记作v=>w。若推导v=>w中的每个直接推导都是最左的，则称为最左推导最右推导（规范推导）：每次都扩展最右的非终结符最右推导的逆过程是 最左归约最左推导的逆过程是 最右归约l 句型：从识别符号推导出来的符号串l 句子：仅含有终结符的句型l 语言L(G)：文法描述的语言是该文法一切句子的集合l 等价：若L(G1) = L(G2)，则称G1和G2等

6、价，记作G1G2l 递归：递归规则是指在规则的左部和右部具有相同的非终结符的规则。形如AAy 的规则称为左递归规则；形如AxA 的规则称为右递归规则；形如AxAy且x,y<>的规则称为内递归规则，或自嵌入规则3.4 文法的类型 【构造文法】l 0型/短语结构文法： 最一般的文法，无限制l 1型/上下文有关：uw的限制：除了u，|u|w| ，意为串的长度不可压缩aAb aQb 只有A出现在 ab 的上下文中，才允许用 Q代替Al 2型/上下文无关： uVN，wV* u w = 用w取代非终结符u时，与上下文无关l 3型/正规文法不同时出现右线性文法：形式都是AaB和Aa，A,BVN

7、aVT左线性文法：形式都是ABa和Aa，A,BVN aVT3.5 上下文无关文法及其语法树l 语法树 【画】 推导树 4个条件 P40 。简单不多说叶子结点从左至右组成的符号串对应文法中的一个句型ü 叶子结点：没有孩子的结点ü 分支：非叶子结点连同其全部孩子(直接孩子)。ü 子树：非叶子结点连同其全部后裔（直接孩子和间接孩子）。 ü 简单子树：如果子树只有2层。ü 短语：每个子树的叶子串是相对于该子树的根的短语 ：i1 i2 i3 i1*i2 i1*i2+i3ü 简单短语(直接短语)：每个简单子树的叶子串是简单短语 ：i1 i2 i3

8、ü 句柄：最左的简单子树的叶子串是句柄 ： i1l 二义性文法 【判断】 定义：存在某个句子对应着两棵不同的语法树的文法。注意：二义性是指文法，不是指语言。ü 转换为无二义的：文法GE变换为文法GE GE: EE+E|E*E|(E)|i GE: EE+T|T TT*F|F F(E)|iü 附加去掉二义性的信息：例如规定 先做 * / 再做 + - 等3.6 句型的分析l 自上而下(推导)关键是确定当前推导的规则l 自下而上(归约)关键是确定当前归约的句柄3.7 文法的实用限制和变换 【老师木有圈概念】l 有害规则：文法G中形如U>U的规则l 多余规则：

9、52; 左部非终结符号U不出现在任何其他规则的右部（开始符除外），即该非终结符是不可到达的ü 若在推导中使用该规则，则再也不能推出终结符号串，即该非终结符是不可终止的l 其它：ü 不含有左递归规则A>Aa ü 不允许有空规则 A>本章有大题：1) 语言与文法的转换2) 写出推导过程、构造语法树3) 短语、简单短语、句柄4) 判断二义性，给出反例第四章 词法分析 词法分析是编译中的第一个阶段，它的主要任务是从左到右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。4.1 词法分析程序的设计 【木有概念】l 单词类别：保留字、标识符、常量、运算

10、符、界限符l 输出的单词符号：通常用二元式表示：（单词种别，单词自身的值）4.2 单词的描述工具 【将语言用正规式写出】l 正规式、正规集ü 是正则式，表示空集ü 2)是正则式，表示ü 每个aV是正则式，表示aü 若P和Q是正则式，分别表示正则集L(P)和L(Q)，则 P|Q是正则式，表示L(P)L(Q) “或” PQ是正则式，表示L(P)L(Q)“联结” P*是正则式，表示L(P)* “星闭包” (P)是正则式，表示L(P)ü 仅由有限次使用上述步骤得到的正则式，才是V上的正则式。运算优先次序为 * .|l 例子：以ab结尾的所有串： (a|

11、b)*ab只包含一个a的所有串： b*ab*包含偶数个b但不含a的所有串： (bb)*每个a之前必须都有一个b的所有串： (ba|b)*不包含ab子串的所有串： b*a*l 正规文法构造正规式设X是正则变量，a和b是正则式，且X=aX+b 则 X=a*b证明：正则式方程X=aX+b等价于以下正则规则：XaX|b4.3 有穷自动机FA4.3.1 确定的有穷自动机DFA “确定”即f是单值函数 - 初态 + 终态 可识别的l 是一个五元组： M =(K,VT,f,S,Z) K：有穷状态集；VT：有穷的输入字母表；f：K×VTK是状态转换函数，即f(W,a)=U表示当前状态W下，输入a，转

12、到状态U。S：唯一的开始状态，SK;Z：终止状态集，是K的非空子集l 可识别的定义：有一条从初态到终态的路径产生x，则x为DFA所能识别的符号串。l 不可识别的两种情况：读完状态不停在终态；出现不存在的映射，使自动机无法继续。l 所有DFA所能识别的字符串集合称为DFA所接受的语言，记为L(DFA)4.3.2 不确定的有穷自动机NFAl 与DFA的区别： “非确定”即f是多值函数，且输入可允许为；初态不唯一4.3.3 NFA转换为等价的DFA ll Ia即从I中任一状态出发，经a弧（可跳过a弧之后的任意条弧）可达到的状态集l move(I,a) 表示I中状态经过一条a边可到达的状态的集合初态S

13、 ： I =-CLOSURE(S)=S,3,1 Ia=3,1,5 记为 315 Ib=3,1,6 记为 316将新状态添入I，开一新行，求其Ia和Ib。如此反复，直至不再产生新的状态为止。含Z的状态均是终态。IMove(I,a)IaMove(I,b)IbS31353153631631535231524Z363163163531536231624Z31524Z352431524Z3643164Z31624Z3543154Z362431624Z3164Z3543154Z362431624Z3154Z352431524Z3643164Z得新初态： S31 。 终态集：31524Z、31624Z、31

14、64Z、3154Z4.3.4 确定有穷自动机的化简【最小化】l 最小DFA： 1、没有多余状态（不能到达，不能终止） 2、没有两个状态是互相等价l 化简方法：a) 将S划分为终态集和非终态集，得S=Z,S-Zb) 递归地分割S中的子集，使得任何两个不同子集的状态都是可区分的，而同一个子集中的状态都是等价的c) S中的每个子集合并为一个状态d) 含原初态的状态为初态；含原终态的状态为终态4.4 正规式和有穷自动机的等价性4.5 正规文法和有穷自动机的等价性本章大题：1、自动机的确定化 2、最小化 3、已知文法构造自动机第五章 自顶而下语法分析方法语法分析是编译程序的核心部分。作用是识别由词法分析

15、给出的单词符号序列是否是给定文法的正确句子。分为自顶向下分析（确定分析、不确定分析）、自底向上分析（算法优先分析、LR分析）。5.1 确定的自顶向下分析思想l First集： bÎ (VT È VN )*First(b)= aÎVT | Þba.È(if b Þ then ) l Follow集：Follow(A)= aÎVT | SÞ.Aa. È (if SÞ.A then # )l Select集：Select(Ab) = First(b) ， 当ÏFirst(b)=(First(

16、b)-e) È Follow(A), 当ÎFirst(b)l LL(1)文法：对于每个非终结符U有多个不同的产生式 U UbSelect(U) Select(Ub) = 【充要条件】第1个L表示从左向右扫描输入串，第2个L表示将用最左推导，1表示向右看一个符号便可决定选择哪个产生式进行推导5.2 LL(1)文法的判别 【建议：只写出select即可，免得first、follow出错扣分】l 举例：5.3 等价变换l 消除左公因子1) 产生式形如：Aba®1|ba2|ban| g g表示不以a开头的字符串2) 提取左公共因子： A®a(b1|b2|bn)|

17、 g3) 引进非终极符A，使产生式替换为：A ® a A¢ | g A¢ ® b1|b2 | bnl 消除左递归直接左递归：A®Ab AÎVN, b ÎV*间接左递归：A®Bb B®Aa A,BÎVN, a ,b ÎV*对直接左递归形如： A ® Aa1|Aa2|Aam|b1|b2|bn消除直接左递归,引入新的非终结符A¢： A ® b1A¢|b2A¢|bnA¢ A¢ ® a1A¢|a2A

18、2;|amA¢| e注意：1、不一定每个文法的左公共因子都能在有限步内替换成无公共因子的文法；2、没左公共因子、没左递归只是LL(1)的必要条件，但并非充分条件5.4 不确定的自顶向下分析思想【无】5.5 确定的自顶向下分析方法 【预测分析方法 = LL(1)方法】l 分析程序l 符号栈l 预测分析表【构造预测分析表】LL(1)分析步骤：1、 判断是否为LL(1)文法，求出select集2、 根据select集构造预测分析表3、 写出分析过程 è 分析栈、剩余输入串、推导所用产生式或匹配【3列】大题：1、判断是否为LL(1)文法 2、文法的等价变换 3、写分析过程 P95

19、表5.4第六章 自底而上优先分析 【也称移进-归约分析】ü > 就归约 ； < 、= 则移进 ü 归约顺序：等同：a=b 同时；先于：a<b b先a后；后于：a>b a先b后 ü b=c + c=b 不能推出 b=b。 è优先关系必须相邻l 归约中的动作有4类移入：读入一个符号并把它归约入栈。归约：当栈中的部分形成一个句柄（栈顶的符号序列）时，对句柄进行归约。接受：当栈中的符号仅有#和识别符号时，输入符号也到达结尾时，执行接受动作。当识别程序觉察出错误的时候，表明输入符号串不是句子。进行错误处理l 简单优先分析法ü 优先

20、关系的冲突当优先矩阵中出现值不唯一的元素时，文法不适合使用优先识别技术来识别句型ü 简单优先分析法是按照文法符号(终结符和非终结符)的优先关系确定句柄的l 算符优先分析法ü 与简单优先的区别：简单优先技术对符号表中的所有符号之间建立优先关系。算符优先分析技术只在终结符号之间建立优先关系ü 木有包含 相邻两个非终结符的句型 的文法 称为 算符文法。ü 人为确定：（0）i的优先级最高（1）­优先级仅次于i，右结合（2）*和/优先级次之，左结合（3）+和-优先级最低，左结合（4）括号(,)的优先级大于括号外的运算符，小于括号内的运算符，左括号的优先性

21、大于右括号（5）#的优先性低于与其相邻的运算符大题：判断文法是否为简单优先关系第七章 LR分析7.1 LR分析概述l LR分析方法是 无回溯的“移进-归约”方法l LR分析器的组成：ü 总控程序。也称为驱动程序ü 分析表或分析函数。可分为：动作(ACTION)、状态转换(GOTO)ü 分析栈。包括文法符号栈和相应的状态栈l 四种技术：如下 LR(0) SLR(1) LR(1) LALR(1)7.2 LR(0)分析l 能力最弱，理论上最重要l 活前缀：不包含句柄之后的符号的前缀l 可归前缀：包含句柄的活前缀l LR(0)的项目分类：1) 移进项目：圆点后面为终结符，

22、对应移进状态。分析时把a移进符号栈。2) 待约项目：圆点后为非终结符，表明等待B所能退出的串归约为B后，才可继续分析A的右部。3) 归约项目：圆点在最右端。表明已分析完，句柄已形成，可被归约。4) 接受项目：表明已分析成功l 冲突分类：移进和归约同时存在 ； 归约和规约项目同时存在。l 构造识别活前缀的DFAl 构造LR(0)分析表l 如果每个入口不含多重定义，则称它为文法G的一张LR(0)表。具有LR(0)表的文法G称为LR(0)文法。LR(0)文法是无二义的。l 当出现移进规约冲突时，文法不是LR(0)文法，为解决，引进SLR(1)法7.3 SLR(1)分析l 如果一个LR(0)项目集规范

23、族中含有如下的项目集II= X ®a×bb, A ® a× 存在移进-规约冲突但是若【条件】FOLLOW(A) Ç b = f ，冲突便可以解决l 解决办法：当在状态I面临符号a时：1、对 a=b 则action I , b = closure( X ®ab.b )移进2、对 aÎFOLLOW (A) 则 action I , a =用 A ®b×归约 l 就以上解决方法，称为SLR(1)分析。数字1的意思是，在分析过程中顶多只要向前看一个符号。l LR(0)与SLR(1)的区别：前者有归约项时，下一步马

24、上可以归约。后者只有下一符号是归约到的符号的follow集才可以归约。l SLR(1)的局限：有可能移进一个符号可以构造出两条路径，因上述的【条件】可能不成立。此时，既不是 LR(0)，也不是SLR(1)。为解决，引进LR(1)。7.4 LR(1)分析l 基本思想：如果存在规范推导 S Þ dAw Þ dbaw 当且仅当当前输入的符号为aÎFirst(w#)时，才能用产生式A>ba进行归约。因此，在LR(1)方法中重新定义项目,使每个项目附带一个向前搜索符。l A®a.b，a A®a.b：核，为LR(0)项目； a：向前搜索符，要么是一个

25、终结符，要么是输入结束标记#。 a只对规约项目起作用。多个时，可用a/b/cl LR(1)文法满足下面两个条件1) 如果一个项目集里有项目A > uxv, a，x是终结符，那就不会有项目B > u,x 2) 项目集里所有归约项目的向前搜索符不相交，即不能同时含有项目A > u,a 和B > v,al 每个SLR(1)文法都是 LR(1)文法7.5 LALR(1)分析 【不考大题？但要知道同心集的概念】l 同心集【概念】？状态内部的项目，除去各向前搜索符不一样外，其它都一样。合并后心仍相同，向前搜索符合并在一起，转换函数也合并在一起。l 基本思想：合并同心集（1） 合并同

26、心集后，对某些错误发现的时间会产生推迟，但是错误出现的位置仍是准确的。LR(1)分析法强于LALR(1)分析法，如果文法是LALR(1)文法，则也是LR(1)文法，反之不然。（2）LR（1）项目集不存在动作冲突，合并同心集后会不会产生新的冲突？ 1）不会产生新的移进-归约冲突（P148） 2）会产生新的归约-归约冲突（P152）大题：1、判断文法是否为LR(0)、SLR(1)、LR(1) 2、分析过程：符号栈、分析表第八章 语法制导翻译和中间代码生成【难点】【概念】l 属性文法:接近形式化的语义描述方法，是一组属性和属性等式（断言或谓词）组成。是一个三元组：A=(G,V,F)G:是一个上下文无

27、关文法。V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连。F:关于属性的属性断言或谓词集。每个断言与一个产生式相联。l 值：val； 类型：type； id.entry：id在符号表的位置l 综合属性：从其子结点的属性值计算出来的l 继承属性：从其兄弟结点和父结点的属性值计算出来的l è非终结符既有综合属性也有继承属性，开始符没有继承属性，终结符只有综合属性。l L-属性：既包括综合属性，又包括继承属性，其属性用深度优先的顺序从左至右计算。l S-属性：是L-属性的一个特例，仅含有综合属性的属性文法。属性的计算，采用自底向上的分析。l è归约句柄 相当于 执行动作。l 逆波兰式(后缀式)： a+b è ab+ ; a*b è ab* ; a:=b*c+b*d è abc*bd*+:=GOTO L è L jumpif E then s1 else s2 èES1S2¥l 三地址代码(四元式):显示引用l 语法结构树(三元式):临时变量lE.true 真出口 、 E.false 假出口、 拉链、 回