《编译原理复习09》由会员分享，可在线阅读，更多相关《编译原理复习09（50页珍藏版）》请在金锄头文库上搜索。
1、编译原理复习,2018/9/14,1,编译原理复习,编译原理复习,2018/9/14,2,编译原理复习 一、引论,1、编译原理”的目的和任务编译原理是计算机专业的一门重要的专业课程。介绍编译程序的基本构造、一般设计方法和常用实现技术。通过本课程的学习，要求学生掌握高级语言编译程序的初步设计和实现的基本技能，并能为不同模式和不同领域的语言的实现方案寻找解决途径。,编译原理复习,2018/9/14,3,2、什么是编译程序编译程序是一种翻译程序，它将高级语言所写的程序翻译成等价的机器语言或汇编语言的目标程序。,语法分析,代码优化,语义分析和中间代码产生,词法分析,错误检查和处理程序,信息表管理程序,
2、目标代码生成,源程序,编译原理复习,2018/9/14,4,二、编译基础,1、文法和语言 什么是文法：是规则的非空有穷集合，通常定义为四元组：GS=（Vn，Vt，P，S） 文法的分类：0型，1型，2型，3型用正规文法描述程序设计语言的词法规则；用上下文无关文法描述程序设计语言的语法规则。 什么是语言：文法G全体句子所组成的集合。L(GS)= w | S=w 且 wVt* 已知语言求文法；已知文法求语言。,编译原理复习,2018/9/14,5,例2：,例1：,编译原理复习,2018/9/14,6,例3,编译原理复习,2018/9/14,7,例4：,编译原理复习,2018/9/14,8,2、求句型
3、的短语、直接短语、句柄和最左素短语。,最左素短语为：i,例5：,编译原理复习,2018/9/14,9,3、文法二义性判断：,例6：已知文法G1:,若一个文法的某个句子对应两棵不同的语法树，或者有两个不同的最左（或最右）推导，则称这个文法是二义的。注意：每个句子有规范推导，而句型不一定有。,编译原理复习,2018/9/14,10,三、词法分析,1、正规文法与正规式的定义： 2、NFA、DFA的定义：M（S , , f , s0 , Z) NFA：f为多值映射函数，s0是初态集DFA：f为单值映射函数，s0是唯一初态 3、分裂法 子集法 分划法正规式 NFA DFA 最小化DFA正规文法 词法分析
4、程序,编译原理复习,2018/9/14,11,例: 构造自动机A，使得它识别字母表0,1上的符号串，这些符号串由任意的1、0和随后任意的11、00对组成。 解：正规表达式为 (1 | 0 )* (11 |00)*,编译原理复习,2018/9/14,12,编译原理复习,2018/9/14,13,四、语法分析,编译原理复习,2018/9/14,14,1、上下文无关文法所描述的语言，可以用四种分析程序来识别： 递归下降分析程序、预测分析器 算符优先分析程序、LR分析法 2、LL(1)文法的定义： .文法不含左递归 .对文法中每一个非终结符A，如有规则：A 1 | 2 | | n 则下面条件成立FIR
5、ST(i ) FIRST(j )= (ij) .对文法中每一个非终结符A，若它的某个产生式首符集包含 时 ，则：FIRST(A) FOLLOW(A) = 满足以上条件的文法称为LL(1)文法。,编译原理复习,2018/9/14,15,例4.1,例4.2,编译原理复习,2018/9/14,16,例4.3,编译原理复习,2018/9/14,17,例4.4 ：将文法改写成LL(1)文法。 SS*aP | aP | *aP P+aP | +a解：消除文法左递归、提取公共左因子得到：SaPS | *aPS S *aPS | P+aP PP | 计算每个非终结符的FIRST和FOLLOW集合： FIRST
6、(S)=a,* Follow(S)=# FIRST(S)=*, Follow(S)=# FIRST(P)=+ Follow(P)=*, # FIRST(P)=+, Follow(P)=*,# 以上文法是LL(1)文法。,编译原理复习,2018/9/14,18,3、递归下降分析程序的构造方法： 为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。 对于产生式：Ux1 | x2 | xn 则编写if ch in FIRST(x1) then p(x1)else if ch in FIRST(x2) then p(x2) else error ;
7、 对于符号串x=y1 y2yn ; p(x)的含义为：begin p(y1) ; p(y2) ; p(yn) end 如果yiVT 则if ch=yi then read(ch) else error 对于U;则 if chFollow(U) then returnelse error ;,编译原理复习,2018/9/14,19,4、预测分析器的构造方法-分析表的构造 输入：文法G 输出：分析表M 方法：对文法中每一个产生式A，按照下述规 则确定M中各个元素。 对于FIRST()中的每一个终结符a置为 MA , a=A 若空串 FIRST()，则对Follow(A)中的每一个终结符b置为 MA
8、 , b=A 或 MA , #=A 把M中未定义的元素置为error。,编译原理复习,2018/9/14,20,例4.5：已知文法GE: 试构造分析表。ETE E+TE| TFTT*FT | F(E) | i 对ETE产生式：First(TE)=( , i 置 ME , ( = ETEME , i = ETE,编译原理复习,2018/9/14,21,对产生式 E+TE| First(+TE )=+ 置 ME , + = E+TEFollow(E)= ) , # 置 ME , ) =E ME , # =E 对产生式 TFTFirst(FT)= ( , i 置 MT , ( = TFTMT , i
9、 = TFT 对产生式T*FT | First(*FT)=* 置 MT,*= T*FT Follow(T)= + , ) , # 置 MT,+= T MT,)= T MT,#= T 对产生式F(E) | i First( (E) )= ( 置 MF , ( = F(E) First( i )= i 置 MF , i = Fi,编译原理复习,2018/9/14,22,总控程序框图,J:=1; k:=1; sk:= #; k:=k+1; Z =sk,Sk VT?,Sk =Tj?,Sk =# ?,查M Sk , Tj =Xy1y2yn,Sk=Tj?,K:=k-1; J:=j+1;,error,N,N
10、,N,y,y,y,error,stop,y,N,将y1y2yn逆序推进栈中 若y1y2yn= 则k=k-1,error,N,y,编译原理复习,2018/9/14,23,分析过程,例如：已知文法G，请利用LL(1)分析表给出输入串i1*i2+i3的分析过程。 GE: ETE E+TE| TFTT*FT | F(E) | i,编译原理复习,2018/9/14,24,E,编译原理复习,2018/9/14,25,例4.6,编译原理复习,2018/9/14,26,编译原理复习,2018/9/14,27,5、算符优先分析程序的构造方法 方法：根据最左素短语定理，利用符号栈来识别最左素短语（先找尾，后找头）
11、，然后归约。,栈置初值：k:=1;sk:= #;,当前输入符号读入a ;,Sk VT,Q=Sj ; j:=j-1;,J:=k;,J:=k-1;,K=2 且a=#,Sj VT,Sj a,Sj+1 Sk是最左素短语并归约为N，k:=j+1;sk=N,Sj Q,结束,y,n,y,y,J:=j-1;,n,n,y,y,n,Sk:=a; K:=k+1;,n,编译原理复习,2018/9/14,29,例4.7,编译原理复习,2018/9/14,30,编译原理复习,2018/9/14,31,6、 LR分析器的构造方法-总控程序框图,编译原理复习,2018/9/14,32,例4.8：文法GS: S(S) | a
12、拓广： (0)SS (1)S(S) (2)Sa,编译原理复习,2018/9/14,33,编译原理复习,2018/9/14,34,例4.9：对下列文法： (0)SS (1)SbRST (2)SbR (3)RdSa (4)Re (5)TfRa (6)Tf 求各非终结符的First和Follow集合。 构造该文法的SLR(1)分析表。 解：,编译原理复习,2018/9/14,35,编译原理复习,2018/9/14,36,编译原理复习,2018/9/14,37,例4.10 有文法GA : AaABe | BaBdB | 该文法是否是SLR(1)文法？证明之。 解：将文法拓广为GS (0)SA (1)A
13、aABe (2) ABa (3)BdB (4)B 该文法的LR(0)项目有： S. A SA . A. aABe Aa .ABe AaA .Be AaAB .e AaABe. A .Ba AB .a ABa. B .dB Bd .B BdB. B .,编译原理复习,2018/9/14,38,Follow(B)=a,e 不是SLR(1)文法,SA AaABe ABa BdB B,无法用SLR(1)解决冲突,无法用SLR(1)解决冲突,可以用SLR(1)解决冲突,可以用SLR(1)解决冲突,编译原理复习,2018/9/14,39,例4.11：设有文法GE: (1)SA (2)SB (3)AaAb
14、(4)Ac (5)BaBb (6)Bd,编译原理复习,2018/9/14,40,例4.12,编译原理复习,2018/9/14,41,编译原理复习,2018/9/14,42,编译原理复习,2018/9/14,43,编译原理复习,2018/9/14,44,五、语义分析和中间代码产生,1、语法制导翻译法的基本思想：对文法的每一条产生式，设计语义子程序。在语法分析的过程中，当使用一条产生式推导或归约时，调用该语义子程序，完成预定的翻译工作。 2、中间代码：逆波兰式、四元式作用： 有利于目标代码优化有利于目标代码移植使各阶段的开发复杂性降低， 有利于编译程序的开发。,编译原理复习,2018/9/14,4
15、5,逆波兰式（后缀式）：每一运算符都置于其运算对象之后。（无括号表）中缀表示 后缀表示A*B AB*A+B*C ABC*+(A+B)*(C+D) AB+CD+*(a=0&b3)|(e&x!=y) a0=b3&exy!=&|acb=d acbd=,编译原理复习,2018/9/14,46,例1：算术表达式求值的属性文法。 规则式 语义规则 1.LE print(E.val) 2.EE1+T E.val:=E1.val+T.val 3.ET E.val:=T.val 4.TT1*F T.val:=T1.val*F.val 5.TF T.val:=F.val 6.F(E) F.val:=E.val 7.Fdigit F.val:=digit.lexval,
