辽宁大学_编译原理课件part10

1、1总结总结2“编译原理编译原理”是一门非常好的课是一门非常好的课程程 Alfred Alfred V.AhoV.Aho：编写编译器的原理和技术具编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术都学家的研究生涯中，本书中的原理和技术都会反复用到会反复用到 “自顶向下自顶向下”和和“自底向上自底向上”的系统设计方的系统设计方法（思想、方法、实现全方位讨论）法（思想、方法、实现全方位讨论） 一些具体的表示和变换算法一些具体的表示和变换算法 一个相当规模的系统的设计（含总体结构）一个相当规模的系统的设计（含总体结构

2、）3“编译原理编译原理”是一门非常好的课程是一门非常好的课程 掌握掌握“编译原理编译原理”中的基本概念、基本理论、中的基本概念、基本理论、基本方法，在系统级上再认识程序和算法，基本方法，在系统级上再认识程序和算法，提升计算机问题求解的水平，增强系统能力，提升计算机问题求解的水平，增强系统能力，体验实现自动计算的乐趣体验实现自动计算的乐趣41 1 绪论绪论计算机语言的发展计算机语言的发展机器语言机器语言( (Machine Language)Machine Language)与汇编语言与汇编语言( (Assemble Language)Assemble Language)高级语言高级语言( (H

3、igh Level Language)High Level Language)强制式语言强制式语言( (Imperative Language)Imperative Language)函数函数( (应用应用) )式语言式语言( (Functional Language)Functional Language)逻辑式逻辑式( (基于规则基于规则) )语言语言( (Logical Language)Logical Language)面向对象语言面向对象语言( (Object-Oriented Language)Object-Oriented Language)命令语言命令语言( (Command)

4、Command)翻译系统翻译系统汇总汇总MLMLMLPMLPAssemblerAssemblerDisassemblerDisassemblerALAL ALP ALPTranslatorTranslator Compiler Compiler Data DataHLHLHLPHLPInterpreterInterpreterResultResultRun SystemRun SystemDataDataResultResult编译程序总体结构编译程序总体结构7编译的遍（编译的遍（PassPass） 根据系统资源的状况、运行目标的要根据系统资源的状况、运行目标的要求求等，可以将一个编译程序设计

5、成等，可以将一个编译程序设计成多遍扫描，在每一遍扫描中，完成不同多遍扫描，在每一遍扫描中，完成不同的任务的任务8编译的前端与后端编译的前端与后端 前端前端 与源语言有关、与目标机无关的部分与源语言有关、与目标机无关的部分 词法分析、语法分析、语义分析与中间代码生词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化成、与机器无关的代码优化 后端后端 与目标机有关的部分与目标机有关的部分 与机器有关的代码优化、目标代码生成与机器有关的代码优化、目标代码生成92 2 文法与语言文法与语言 字母表字母表 ：非空有穷集合：非空有穷集合 字母表的乘积：字母表的乘积： 1 12 2=ab|aab

6、|a1 1，bb2 2 * *、+ + xx* *, L , L * *, x L, x L 语句语句102 2 文法与语言文法与语言 文法：文法： = ( = (T T，N N，) ) P P BNFBNF： , , , , l lu u, m, m 候选式：候选式： 1 1|2 2| |n n 推导（派生）推导（派生） ： P P ； n n；* *； + + 句型：句型：S S * * ( (T TN N) )* * 句子：句子：S S * * x x， x xT T* * 112 2 文法与语言文法与语言 最左最左( (Left-most)Left-most)推导推导最左分析最左分析左

7、句型左句型最左推导对应最右归约最左推导对应最右归约 最右最右( (Right-most)Right-most)推导推导最右分析最右分析规范推导、规范句型（右句型）规范推导、规范句型（右句型）最右推导对应最左归约（规范归约最右推导对应最左归约（规范归约）2 2 文法与语言文法与语言 语言：语言：( () ) x x* * x & xx & xT T* * 短语：如果短语：如果S S* *+ + 直接短语、句柄直接短语、句柄+id3id1id2*132 2 文法与语言文法与语言142 2 文法与语言文法与语言 有的有的文法的二义性是可以消除的文法的二义性是可以消除的 语言可以用不同文法产生语言可以

8、用不同文法产生152 2 文法与语言文法与语言SaBCSaSBCCBBCaBdbBbbbCbcC ccEE+EEE*EE(E)EidEE-E EE/E SaBCSaSBCCBBCaBabbBbbbCbccC cc0型文法型文法(PSG)1型文法型文法(CSG)2型文法型文法(CFG)3型文法型文法(RG)3型文法型文法(RG)文法的文法的ChomskyChomsky体系体系163 3 词法分析词法分析 词法分析器的功能词法分析器的功能, ,在编译程序中的在编译程序中的“位置位置” 缓冲区设计（双缓冲）缓冲区设计（双缓冲） 正规正规( (表达表达) )式式 a|(a|b)a|(a|b)* *cc

9、(a|b)cc(a|b)+ + (0|1)(0|1)(0|1)(0|1)* * (00|01|10|11)(00|01|10|11)* * 正规定义式正规定义式 S S(0|1)(0|1)(0|1)(0|1)* * 正规式正规式( (表达式表达式) )与正规文法等价与正规文法等价 FAFA（状态转移图）是一个有力的工具状态转移图）是一个有力的工具17正规式正规式( (表达式表达式) )与正规文法等价与正规文法等价 引入引入 S Sl (l|d)* 引入引入A消除闭包消除闭包 Sl A A(l|d)A| 执行连接对执行连接对|的分配律的分配律 SlA AlA|dA| 183 3 词法分析词法分析

10、 词法分析器的实现词法分析器的实现 按状态转移图设计主程序按状态转移图设计主程序 设计适当的子程序设计适当的子程序uArsArs* *uAaBAaB Aa Aa194 4 自顶向下语法分析自顶向下语法分析 语法分析方法分类语法分析方法分类 回溯（虚假匹配）、左递归、二义性回溯（虚假匹配）、左递归、二义性 消除左递归消除左递归 AAAA1 1|A|A2 2| |A|An n|1 1|2 2| |mm A A1 1 B|B|2 2 B B | |n n B B B B1 1 B|B|2 2 B B | |n n B|B| 提取公共左因子提取公共左因子 AA1 1|2 2| |n n | |1 1|

11、2 2| | | | mm AA|AA|1 1|2 2| | | | mm和和 AA1 1|2 2| |n n204 4 自顶向下语法分析自顶向下语法分析 LL(1)文法文法 A1|2|n FIRST(i)FIRST(j)= ij 当当FIRST(j)时，时，FOLLOW(A)FIRST(i)= 求求FIRST()的算法的算法 =X1 X2Xn 求求FOLLOW(B)的算法的算法 # FOLLOW(S) AB 当当FIRST()时时 FOLLOW(B)=FOLLOW(B)(FIRST()FOLLOW(A)214 4 自顶向下语法分析自顶向下语法分析 LL(1)LL(1)分析分析器系统结构器系统

12、结构 输入缓冲区输入缓冲区( (符号序列符号序列) )控制程序控制程序P 77P 77预测分析表预测分析表MM22表达式文法的预测分析表表达式文法的预测分析表语法语法变量变量终极符号终极符号id+*()#EETTF 234 4 自顶向下语法分析自顶向下语法分析 语法图语法图 简化语法图简化语法图 递归子程序法递归子程序法 为每个语法变量编写一个处理子程序为每个语法变量编写一个处理子程序简化的语法图简化的语法图+TEi d（）25简单算术表达式的分析器简单算术表达式的分析器 的子程序的子程序( (E ET(+T)T(+T)* *) )procedure E;procedure E; begin

13、begin T; T; 的过程调用的过程调用 while while lookheadlookhead=+ do =+ do lookheadlookhead：当前符号当前符号 begin begin 当前符号等于时当前符号等于时 match(+); match(+); 处理终结符处理终结符 T T 的过程调用的过程调用 endend end; end;265 5 自底向上语法分析自底向上语法分析 思想思想 从输入串出发，反复利用产生式进行从输入串出发，反复利用产生式进行归约归约，如果最，如果最后能得到文法的开始符号，则输入串是句子，否则后能得到文法的开始符号，则输入串是句子，否则输入串有语法

14、错误输入串有语法错误 核心核心 寻找句型中的当前归约对象寻找句型中的当前归约对象“句柄句柄”进行归约进行归约, ,用不同的方法寻找句柄，就可获得不同的分析方法用不同的方法寻找句柄，就可获得不同的分析方法 方法方法 算符优先分析法算符优先分析法 LRLR分析法分析法 移进归约移进归约控制程序控制程序栈内容栈内容 输入缓冲区内容输入缓冲区内容 # “ # “当前句型当前句型 ” # ” #？LL(1)LL(1)分析法分析法栈栈输入缓冲区输入缓冲区 分析器结构分析器结构v4 4种操作：移进、归约、接受、出错种操作：移进、归约、接受、出错28算符优先分析法算符优先分析法 根据当前输入符号根据当前输入符

15、号a a与栈顶符号与栈顶符号b b的优先级的优先级确定动作：确定动作：if ba then if ba then 移进移进归约对象未形成归约对象未形成if ba then if ba then 移进移进归约对象未形成归约对象未形成if ba then if ba then 归约归约归约对象已形成归约对象已形成if a=b=# then if a=b=# then 接受接受分析成功分析成功If aIf a与与b b无优先关系无优先关系 then then 出错出错29算符优先分析法算符优先分析法 算符文法（不含形如算符文法（不含形如 ABC ABC 的产生式）的产生式） 算符优先级算符优先级 栈

16、内栈外、优先函数栈内栈外、优先函数 算符优先文法算符优先文法 素短语和最左素短语素短语和最左素短语句型句型# #NN1 1a a1 1 NN2 2a a2 2 NNn na an n # #的最左素短语是满足下列条的最左素短语是满足下列条件的最左子串件的最左子串NNi ia ai i NNi+1i+1a ai+1i+1 NNj ja aj j NNj+1j+1其中：其中：a ai-1i-1aai iaai+1i+1aaj-1j-1aaj jaaj+1j+130 关键概念关键概念 规范句型活前缀规范句型活前缀规范句型（右句型）的不规范句型（右句型）的不含句柄右边任何符号的前缀含句柄右边任何符号的

17、前缀 句柄形成情况的表示句柄形成情况的表示LR(0)LR(0)项目：项目：A.A. 移进项目：移进项目： A.aA.a 待约项目：待约项目： A.BA.B 归约项目：归约项目： A. A. 动作表动作表action状态状态/符号栈符号栈输入缓冲区输入缓冲区分析表分析表32actions,aactions,a；gotos,Xgotos,X 33 拓广文法拓广文法给出分析开始和结束状态给出分析开始和结束状态 G=(VG=(VN N S, V S, VT T, P , P SSSS, S), S) S S V V 对应对应S.SS.S（分析开始）和分析开始）和SS.SS.（分析成功）分析成功） 识别

18、识别CFG GCFG G的拓广文法的所有规范句型活前缀的的拓广文法的所有规范句型活前缀的DFADFA 以项目集以项目集 S.S S.S 的闭包为启动状态的闭包为启动状态 分析器的状态分析器的状态某个项目集闭包某个项目集闭包 后继项目后继项目 项目集规范族项目集规范族DFADFA的全部状态的全部状态I0:S.SS.L=RS.RL.*RL.idR.LI1:SS.I2:SL.=RRL.LI3:SR.RI4:L*.RR.LL.*RL.idI5:Lid .*idI6:SL=.RR.L L.*RL.id=I7:L*R.RI8:RL.LI9:SL=R.R*LidS1. SL=R2. SR3. L*R4. L

19、id5. RL产生式编号产生式编号*id35 项目集项目集 I I 的相容的相容 归约归约归约冲突归约冲突 移进移进归约冲突归约冲突 LR(0)LR(0)文法文法GG的项目集规范族中的所有的项目集规范族中的所有项目集闭包是相容的项目集闭包是相容的 SLR(1)SLR(1)分析法分析法 SLR(1)SLR(1)分析表的构造：仅当分析表的构造：仅当aaFOLLOW(A)FOLLOW(A)时执行关于时执行关于AA的归约（的归约（rj rj） ; ; 36分析表的构造分析表的构造设设GG的的LR(0)LR(0)项目集规范族：项目集规范族：I I0 0,I ,I1 1, ,I ,In n 用用i i表示

20、闭包表示闭包I Ii i对应的分析器状态对应的分析器状态( (即相应的即相应的DFADFA状态状态) )1 01 0为开始状态为开始状态2 2 对对I Ii iCC： if A.aIif A.aIi i and go(Iand go(Ii i,a)=,a)=I Ij j then actioni,a=then actioni,a=sj sj ; ; if A.BI if A.BIi i and go(Iand go(Ii i,B)=,B)=I Ij j then actioni,B=then actioni,B=sj sj ; ; if A.I if A.Ii i then then for

21、for aaV VT T#/ /FOLLOW(A)FOLLOW(A)dodo actioni,a=actioni,a=rj rj ; ; if SS.I if SS.Ii i then actioni,#=acc; then actioni,#=acc;3 3 所有空格置所有空格置 errorerror37 语法制导翻译语法制导翻译 在完成语法分析的同时完成语义分析在完成语法分析的同时完成语义分析 属性文法属性文法 A=(G, V, F) A=(G, V, F) 一种实现一种实现 用属性表示一些语义值用属性表示一些语义值38 综合属性综合属性 AXAX1 1X X2 2X Xn n A.s=f

22、(cA.s=f(c1 1,c ,c2 2, ,c ,ck k) )Ax1x2xnA.sc1c2cnA.in39 继承属性继承属性 AXAX1 1X X2 2X Xn nX Xi i.in.in=f(c,c=f(c,c1 1,c ,c2 2, ,c ,ck k) ) 1kin1kinAx1x2xnxkXi.inc1c2ckcnc40 S S属性文法属性文法: :只含综合属性的属性文法只含综合属性的属性文法产生式产生式属性（计算）规则属性（计算）规则/ /语义规则语义规则E EE E1 1 + E + E2 2E.valE.val := E := E1 1.val + E.val + E2 2.v

23、al.valE EE E1 1 * * E E2 2E.valE.val := E := E1 1.val .val * * E E2 2.val.valE (EE (E1 1) )E.valE.val := E := E1 1.val.valE idE idE.valE.val := id . := id .valval L L属性文法属性文法 包含综合属性和继承属性的属性文法包含综合属性和继承属性的属性文法41 翻译模式翻译模式 语义动作被嵌入到产生式右部的适当位置，在语义动作被嵌入到产生式右部的适当位置，在推导过程中完成语义处理推导过程中完成语义处理 属性文法与翻译模式属性文法与翻译模式

24、 属性文法将产生式和语义动作相关联属性文法将产生式和语义动作相关联 翻译模式进一步指出动作执行的时机翻译模式进一步指出动作执行的时机42 类型类型 三地址代码（四元式三地址代码（四元式, ,三元式）三元式） 语法语法( (结构结构) )树树 后缀式后缀式逆波兰表示逆波兰表示 算术表达式的翻译算术表达式的翻译 E EE E1 1 + E + E2 2 E.codeE.code:=E:=E1 1.code|E.code|E2 2.code.code gen(E.placegen(E.place:=E:=E1 1.place+E.place+E2 2.place).place) E idE id E

25、.placeE.place:=id.place :=id.place E.codeE.code=43 在符号表中记录种别、类型、相对地址、在符号表中记录种别、类型、相对地址、作用域作用域等等 计算相对地址计算相对地址变量说明的翻译变量说明的翻译44P offset := 0 DP offset := 0 DDD ; DDD ; DDid : T Did : T enter( , T.type, offset );enter( , T.type, offset ); offset := offset + T.width offset := offset + T.wid

26、thTinteger T.type := integer; T.width := 4Tinteger T.type := integer; T.width := 4Treal T.type := real; T.width := 8Treal T.type := real; T.width := 8Tarray num of TTarray num of T1 1 T.type := array( T.type := array( num.valnum.val, T, T1 1.type);.type); T.width := T.width := num.valnum.val * * T T

27、1 1.width.widthTTTT1 1 T.type := pointer( T T.type := pointer( T1 1.type);.type); T.width := 4T.width := 445动态分配方案下数组说明的代码结构动态分配方案下数组说明的代码结构D id:array low1:up1 , , lown:upn of Tlowlow1 1.code.code送工作单元送工作单元WW1 1upup1 1.code.code送工作单元送工作单元WW2 2lowlown n.code.code送工作单元送工作单元WW2n-12n-1upupn n.code.code送

28、工作单元送工作单元WW2n2n动态分配子程序其动态分配子程序其它参数它参数( (n,type)n,type)转动态分配子程序转动态分配子程序入口入口? D id:array num of T47赋值语句的翻译赋值语句的翻译 布尔表达式的翻译布尔表达式的翻译 数值表示数值表示 真假出口真假出口S id := E S.code := E.code | gen( id.place:=E.place ) E E1 + E2 E.place := newtemp; E.code := E1.code | E2.code | gen(E.place:=E1.place+E2.place)48if if语句

29、的翻译语句的翻译C.codeS1.beginC.trueS.nextS1.codeC.falseC.true := C.true := newlabelnewlabel; ; S S1 1.next := S.next;.next := S.next;S.code := C.code |S.code := C.code |gen( C.true: ) |Sgen( C.true: ) |S1 1.code.code49if if语句的翻译语句的翻译C.codeS1.beginC.trueS.nextS1.codeC.falseS2.beginS2.nextS1.nextC.true := C.

30、true := newlabelnewlabel; ; C.false := C.false := newlabelnewlabel; ;S S1 1.next := S.next := S2 2.next := S.next;.next := S.next;S.code := C.code | S.code := C.code | gen( C.true: ) |gen( C.true: ) |S S1 1.code | gen( .code | gen( gotogoto S.next ) | S.next ) |gen( C.false: ) | Sgen( C.false: ) | S

31、2 2.code.code50whilewhile语句的翻译语句的翻译C.codeS1.codegoto S.beginC.trueS1.beginC.falseS.nextS.beginS.begin := SS.begin := S1 1.next := .next := newlabelnewlabel; ;C.true := SC.true := S1 1.begin := .begin := newlabelnewlabel; ;C.false := S.next; C.false := S.next; S.code := gen( S.begin: ) |S.code := gen( S.begin: ) | C.code | C.code |gen( C.true: ) | gen( C.true: ) | S S1 1.code |.code |gen( gen( gotoS.begingotoS.be