编译原理复习总结-东北大学.ppt

《编译原理复习总结-东北大学.ppt》由会员分享，可在线阅读，更多相关《编译原理复习总结-东北大学.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译方法编译方法20132013年年1212月月复习复习.总结总结第一部分第一部分 考试范围考试范围一一.概念部分概念部分 概念词语解释概念词语解释(简单明确简单明确)概念词语填空概念词语填空(不求全，只求准不求全，只求准)二二.形式语言基础形式语言基础 简单文法构造简单文法构造 自己总结。自己总结。如：给定一符号串集合，如：给定一符号串集合，构造文法构造文法。主要语法成分的识别主要语法成分的识别 给定一文法和一个符号串给定一文法和一个符号串，证明，证明 是句型是句型(句子句子)，并画并画语法树语法树求短语、简单短语和求短语、简单短语和句柄句柄。(接上页接上页)简单文法变换技术简单文法变换技术

2、如如 消除文法的直接左递归！主要是三种常用的文法消除文法的直接左递归！主要是三种常用的文法变换方法变换方法 圆括号圆括号、方括号方括号和和花括号花括号。三三.自动机基础自动机基础 简单有限简单有限自动机的构造自动机的构造 如如 给定一符号串集合给定一符号串集合(或正规式或正规文法或正规式或正规文法)，构，构造有限自动机（造有限自动机（DFADFA）求一个有限求一个有限自动机所定义的语言自动机所定义的语言(符号串集合符号串集合)。(接上页接上页)四四.词法分析词法分析1.1.2 2个实验个实验。五五.语法分析语法分析 给定文法，给定文法，构造递归子程序构造递归子程序（框图）（框图）判断一个文法是

3、否是判断一个文法是否是 LL(1)LL(1)文法文法；(1)(1)消除消除 边，边，NFA=DFANFA=DFA(2)(2)NFA=DFANFA=DFA。5.5.有限自动机的实现有限自动机的实现 有限自动机的有限自动机的确定化确定化。4.4.确定的有限自动机的确定的有限自动机的最小化最小化。2.2.会写会写TOKEN TOKEN 序列；序列；3.3.词法分析技术应用词法分析技术应用；(接上页接上页)七七.中间代码生成中间代码生成 会写常用语句的中间代码会写常用语句的中间代码(逆波兰式逆波兰式，四元式四元式)；会构造常用语法成分的会构造常用语法成分的翻译文法翻译文法；给定翻译文法和给定翻译文法和

4、动作序列动作序列，会走，会走翻译过程翻译过程。给定文法，给定文法，构造构造LL(1)LL(1)分析表，分析表，LR(0)LR(0)文法的判断和相应文法的判断和相应分析表的构造分析表的构造。六六.符号表组织符号表组织 符号表结构以及填写。符号表结构以及填写。5.5.简单优先简单优先文法的判断和相应文法的判断和相应分析表的构造分析表的构造。6.6.语法分析器的构造语法分析器的构造。4.4.语法制导翻译技术的应用。语法制导翻译技术的应用。(接上页接上页)九九.目标代码生成目标代码生成1.1.会写常用语句在会写常用语句在单寄存器下的目标代码生成过程单寄存器下的目标代码生成过程；八八.优化处理优化处理

5、3.3.基本块内四元式的优化。基本块内四元式的优化。1.1.基本块的划分。基本块的划分。2.2.局部优化的几种常见方法。局部优化的几种常见方法。1.1.编译程序编译程序(compilercompiler)目目标标语语言言词法词法分析分析源源语语言言语法语法分析分析语义语义分析分析优化优化处理处理代码代码生成生成 错错 误误 处处 理理 符符 号号 表表 管管 理理2.2.编译程序结构编译程序结构五个阶段五个阶段第二部分第二部分 基本概念总结基本概念总结 是一种语言是一种语言翻译程序翻译程序，它特指把，它特指把某种某种高级程序设计语言高级程序设计语言翻译成具体计算机上的翻译成具体计算机上的低级程

6、序设计语言低级程序设计语言。4.4.文法文法(上下文无关文法上下文无关文法)(接上页接上页)3.3.形式语言形式语言所有所有符号串符号串之之集合集合；其中的每个符号串称为；其中的每个符号串称为句子。句子。G(Z)=(VG(Z)=(VN N,V,VT T,S,P),S,P)V VN N:非终结符集（定义的对象集，如：语法成分等非终结符集（定义的对象集，如：语法成分等)；例：例：G(EG(E)E-E+T|E E-E+T|E T|T T|TT-T*F|T/F|FT-T*F|T/F|FF-i|(E)F-i|(E)简单简单算算术表达术表达式式文法文法其中：其中：V VN N=E E,T T,F F;V

7、VT T=i i,+,-,*,/,(,);Z Z=E E ;P P：可用可用四元组表示：四元组表示：V VT T:终结符集（字母表）；终结符集（字母表）；S:S:开始符号（研究范畴中，最大的定义对象）；开始符号（研究范畴中，最大的定义对象）；P:P:规则集（又称产生式集）；规则集（又称产生式集）；字母表字母表上的符号，按一定的上的符号，按一定的规则规则组成的组成的是定义语言的是定义语言的规则集，规则集，(接上页接上页)5.5.有限自动机有限自动机(finite automata(finite automata）FAFA是一种是一种数学模型，数学模型，用于描述用于描述正规语言正规语言,FA=(Q

8、,S,F,FA=(Q,S,F,)：变换（二元函数）：变换（二元函数）：Q Q(有限状态集有限状态集););F F(结束状态集结束状态集,F F Q Q ）；）；S S(开始状态集开始状态集,S S Q Q）；(字母表字母表)；i ij ja a或或(i,a(i,a）=j=j 确定的有限自动机确定的有限自动机(DFA)(DFA)特征特征：开始状态唯一开始状态唯一;变换函数单值；变换函数单值；不带不带 边。边。非确定的有限自动机非确定的有限自动机(NFA)(NFA)带有带有 边的边的非确定的有限非确定的有限自动机自动机(NFA)NFA)不带有不带有 边的边的非确定的有限非确定的有限自动机自动机(N

9、FA)(NFA)-不能全部具备上述特征者！不能全部具备上述特征者！6.6.有限自动机的分类有限自动机的分类其中其中可定义为可定义为五元组：五元组：(接上页接上页)(1)(1)识别单词识别单词从用户的源程序中把单词分离出来从用户的源程序中把单词分离出来;(2)(2)翻译单词翻译单词把单词转换成机内表示，便于后续处理。把单词转换成机内表示，便于后续处理。7.7.词法分析任务词法分析任务标识符标识符(i)(i)，常数，常数(c)(c)，关键字，关键字(k)(k)，界符，界符(p)(p)。8.8.单词的分类单词的分类9.9.有限自动机作为单词识别器有限自动机作为单词识别器+-#l ld d-d d I

10、|dI|d 标识符标识符|关键字关键字无符号整数无符号整数界符界符注注如何区别标识符如何区别标识符|关键字？关键字？通过查通过查关键字表关键字表决定之：决定之：若表中存在，则视为若表中存在，则视为关键字关键字；否则视为；否则视为标识符标识符！滤掉回车换滤掉回车换行、空格！行、空格！(接上页接上页)形式上说，语法分析是指对给定的符号串（形式上说，语法分析是指对给定的符号串（），），判定其是否是某文法判定其是否是某文法G(S)G(S)的句子。即的句子。即10.10.语法分析语法分析语法分析主要功能是识别短语和句型，语法分析主要功能是识别短语和句型，Z Z 成立吗成立吗?=+1.1.自顶向下法自顶向

11、下法（推导法推导法）2.2.自底向上法自底向上法（归约法归约法）11.11.语法分析方法分类语法分析方法分类12.12.四种实用分析方法及相应文法四种实用分析方法及相应文法 适应于自顶向下的分析法适应于自顶向下的分析法-LL(1)LL(1)文法文法 是指文法中，是指文法中，具有相同左部的各产生式，其选择集合不相交具有相同左部的各产生式，其选择集合不相交。适应于自底向上的分析法适应于自底向上的分析法-LR(0)LR(0)文法文法 是指文法的是指文法的句句柄识别器柄识别器(有限自动机有限自动机)无冲突项目无冲突项目。(接上页接上页)13.13.标识符标识符的的语义信息：语义信息：名字、类型、种类、

12、地址。名字、类型、种类、地址。14.14.语法制导翻译技术语法制导翻译技术 通俗地说，所谓通俗地说，所谓语法制导翻译技术语法制导翻译技术，是指：，是指：语法分析技术语法分析技术 翻译文法构造技术翻译文法构造技术 +15.15.优化处理优化处理 优化处理优化处理是指是指产生更高效的目标代码产生更高效的目标代码所做的工作。所做的工作。或者说或者说 为为提高目标程序质量提高目标程序质量所做的工作。所做的工作。第三部分第三部分 基本运算总结基本运算总结 1.1.判定一个符号串是否是某文法的句子：判定一个符号串是否是某文法的句子：A-d B b|c A-d B b|c B-B b|B-B b|G(S):

13、S-a A B|a A c G(S):S-a A B|a A c 哪个符号串是句子？哪个符号串是句子？adbb abc adbb abc 如：设有文法如：设有文法【解】【解】adbb?adbb?S S=adBbb=adBbb+S=adbb S=adbb=aAB=aAB也可以用也可以用 语法树证明：语法树证明：S Sa A Ba A Bd B bd B bB bB b=adBb=adBb=adbb=adbbadbb adbb 是句子是句子 abc?abc?S=aABS=aAB=adBbB=?=adBbB=?=acB=?=acB=?又又 S=aAc S=aAc=adBbc=?=adBbc=?=Ac

14、c=?=Acc=?abc abc 不是句子。不是句子。也可以用也可以用 语法树证明：语法树证明：a A ca A cS Sd d?a A Ba A BS Sc c?a A Ba A BS Sd d?a A ca A cS Sc c?(接上页接上页)2.2.简单的文法构造：简单的文法构造：设有符号串集合：设有符号串集合：L=a,baL=a,ban nc|n0 c|n0 (1)(1)构造上下文无关文法；构造上下文无关文法；(2)(2)构造正规文法。构造正规文法。解：解：(1)(1)构造上下文无关文法；构造上下文无关文法；(2)(2)构造正规文法。构造正规文法。G(S):G(S):S-a|b A c

15、S-a|b A cA-a A|A-a A|G(S):G(S):S-a|b AS-a|b AA-a A|cA-a A|c3.3.求解一个句型的短语和句柄：求解一个句型的短语和句柄：如：如：已知文法已知文法 G(S):G(S):A-a A c|b A-a A c|b 试指出句型试指出句型 abAb abAb 的短语和句柄：的短语和句柄：【解】【解】首先画该句型的语法树：首先画该句型的语法树：S Sa S Aa S Ab Ab Ab b句柄句柄 是是一个句型的一个句型的最左简单短语。最左简单短语。短语短语 是一个句型任一子树的树叶全体。是一个句型任一子树的树叶全体。简单短语简单短语 是一个句型任一简

16、单子树的树是一个句型任一简单子树的树叶全体。叶全体。根据语法树确认短语和句柄：根据语法树确认短语和句柄：短语：短语：abAb,bA,b abAb,bA,b简单短语：简单短语：bA,b bA,b句柄句柄：bAbAS-b A|a S AS-b A|a S A【解】【解】S-a A b|a S-a A b|a (首符号相同首符号相同)变换后得：变换后得：S-a S-a A b A b 或或 S-a S;S-A b|S-a S;S-A b|A-A b|d A-A b|d （直接左递归）（直接左递归）变换后得：变换后得：A-d A-d b b 或或 A-d A;A-b A|A-d A;A-b A|4.4

17、.简单的文法变换：简单的文法变换：如：如：有文法有文法 G(S):S-a A b|a G(S):S-a A b|a A-A b|dA-A b|d (1)(1)具有相同左部的各产生式，其首符号不相同；具有相同左部的各产生式，其首符号不相同；试进行文法变换，使其满足以下两个条件：试进行文法变换，使其满足以下两个条件：(2)(2)消除文法的左递归消除文法的左递归.变换后的文法变换后的文法 G(S):G(S):S-a S-a A b A b A-dA-d b b 5.5.有限自动机的构造：有限自动机的构造：如：已知符号串集合：如：已知符号串集合：A=A=a an n,ba,ban n|n0|n0 试构

18、造有限自动机。试构造有限自动机。【解】【解】a a+1 1b b-此集合有两种句型（还包含一个空串此集合有两种句型（还包含一个空串 ）分别构造之：分别构造之：2 2-+1 12 2+-a a 合成为一个：合成为一个：b b-2 2+1 1-a aa a错误错误3 3b b正确正确+1 1-aa a2 2-a a-6.6.有限自动机的确定化：有限自动机的确定化：如如 把下述把下述 NFA NFA 转换为转换为 DFA:(DFA:(消消 边边,DFA最小化最小化,略略)A1，2ba+ab bab b+-+C2,3B2C2,3C2,3B2C2,3B2-aab b+-DFA1DFA1:A AB BC

19、Cb bb bab bab b+-A1ba+B2,3B2,3B2,3-ab b+-DFA2DFA2:A AB B7.7.正规语言正规语言的三种表示方法：的三种表示方法：(2)(2)有限自动机：有限自动机：+-a ab bc cc c设有正规语言：设有正规语言：L=ac L=acn n,bc,bcm m|n0,m0|n0,m0(1)(1)正规式：正规式：e=ace=ac*|bc|bc+(3)(3)正规文法：正规文法：G(S):G(S):S-a A|b BS-a A|b BA-c A|A-c A|B-c AB-c AS SA AB BS S A A B B 令令35yax8.8.已知源程序片断已知

20、源程序片断,写出词法分析后的写出词法分析后的 TOKEN TOKEN序列序列:如：如：if(x 5)y=3*x if(x 5)y=3*x a;a;1float2for3if4int5struct6while71+2-3*4/5=6aASb|Bd S-aASb|Bd;A-cS|;A-cS|;B-;B-bB|dbB|d 遇终结符，判定之；遇终结符，判定之；遇非终结符，调用之；遇非终结符，调用之；遇遇 ，直接出口。，直接出口。算算法法入口入口 cNEXT(w)出口出口遇遇 时时nySA子程序子程序 bNEXT(w)出口出口nyB dNEXT(w)err3yn入口入口B子程序子程序11.11.会判定会

21、判定LL(1)LL(1)文法和构造文法和构造LL(1)LL(1)分析表分析表如如 已知文法已知文法 G(S)G(S)：S-a A S b|B d S-a A S b|B d A-c S|A-c S|B-b B|dB-b B|d （1 1）求选择集合；证明是）求选择集合；证明是LL(1)LL(1)文法；文法；select()=select()=select()=select()=select()=select()=select()=select()=select()=select()=select()=select()=【解】【解】（1 1）求选择集合）求选择集合a ab,db,dc cfoll

22、ow(A)follow(A)a,b,da,b,db bd d（2 2）LL(1)LL(1)分析表分析表:三对选择集合两两不相交三对选择集合两两不相交!G(S)G(S)是是 LL(1)LL(1)文法文法!dBAScba（2 2）构造）构造 LL(1)LL(1)分析表。分析表。如如12.12.会判定会判定LR(0)LR(0)文法和构造文法和构造LR(0)LR(0)分析表分析表G(Z):Z-aBAdG(Z):Z-aBAd A-bc|A-bc|c c B-bB|c B-bB|c B-c B-c9 9 Z-ZZ-Z1 1 (0)(0)Z Z -a-a2 2 B B3 3 A A4 4 d d5 5(1)

23、(1)A-b A-b6 6 c c7 7 (2)(2)|c c8 8(3)3)扩展扩展文法文法 LR LR（）分析表：）分析表：Z Z A A 0 0 d d#B B c c b b a a a a2 2 Z Z1 1 1 1 A A4 4 OK OKr r(1)(1)r r(1)(1)r r(1)(1)r r(1)(1)r r(1)(1)d d5 5r r(3)(3)r r(3)(3)r r(3)(3)r r(3)(3)r r(3)(3)r r(2)(2)r r(2)(2)r r(2)(2)r r(2)(2)r r(2)(2)c c8 8 b b6 6 B B3 3 c c9 9 5 5 4

24、 4 8 8 6 6 7 7 3 3 2 29 9r r(4)(4)r r(4)(4)r r(4)(4)r r(4)(4)r r(4)(4)c c7 7 分析表中无冲突项目，分析表中无冲突项目，是是LR(0)LR(0)文法！文法！0 0【例】【例】G(S):G(S):S SaAeB|baAeB|b，A ASb|eSb|e，B BaAaA S A B a b e S A B a e S A BFIRSTVT a,b S,e,a,b aLASTVT B,b,A,e b,e A,b,e 头符号集合头符号集合尾符号集合尾符号集合优先矩阵优先矩阵表项表项=空空表示两个表示两个符号不可符号不可能相临。能相

25、临。13.13.会判定简单优先文法和构造简单优先分析表会判定简单优先文法和构造简单优先分析表14.14.会写会写表达式表达式的的逆波兰式逆波兰式例：求下述表达式的逆波兰式：例：求下述表达式的逆波兰式：=pospos(a+b/da+b/d)e e*pospos(a+b/d)*e (a+b/d)*e)=pos pos(a+b/d)(a+b/d)pospos(e e)*=pos pos(a a)pospos(b/db/d)+)+e*e*=a bd/+e*a bd/+e*pospos(a+b/d)*e(a+b/d)*e)=a b d/+e*=a b d/+e*(a+b/d)*e,pos()?(a+b/

26、d)*e,pos()?脱括号脱括号a a b b d d/+e e*注注根据逆波兰式特点：根据逆波兰式特点：运算对象顺序不变；运算对象顺序不变；运算符紧跟运算对象之后。运算符紧跟运算对象之后。可直接写出：可直接写出：算术表达式算术表达式四元式翻译文法：四元式翻译文法：15.15.会会构造常见语法成分构造常见语法成分的的四元式四元式翻译文法翻译文法 【例】【例】算术表达式算术表达式逆波兰式翻译文法：逆波兰式翻译文法：E-T|E+T E-T|E+T“PUSH(+)PUSH(+)”T-F|T*F T-F|T*F“PUSH(*)PUSH(*)”F-i F-i“PUSH(i)PUSH(i)”|(E)|(

27、E)其中其中:PUSH(x)PUSH(x)-把把 x x 压入分析栈；压入分析栈；QUAT(+)QUAT(+)QUAT(*)QUAT(*)16.16.会走翻译过程的会走翻译过程的动作序列动作序列：符号串符号串 a*(b+c)a*(b+c)的分析的分析(翻译翻译)过程过程(推导法推导法):):E E=T=T=T*F=T*F*=F*F=F*F*=a=a a a*F*F*=a=a a a*(E)*(E)*=a=a a a*(E+T*(E+T+)*=a=a i i*(T+T*(T+T+)*a a a a*(b*(b b b+c+c c c+)*=+【例】【例】算术表达式算术表达式逆波兰式翻译文法逆波兰

28、式翻译文法 a:a:动作符号；动作符号；含义：含义：输出输出(a a)E-T|E+TE-T|E+T+|E-T|E-T-T-F|T*FT-F|T*F*|T/F|T/F/F-iF-i i i|(E)|(E)G(EG(E)abc+*abc+*动作序列的执行结果：动作序列的执行结果：相应的相应的四元式四元式动作序列：动作序列：PUSH(a)PUSH(b)PUSH(c)GEQ(+)GEQ(*)PUSH(a)PUSH(b)PUSH(c)GEQ(+)GEQ(*)执行的执行的 过程过程、结果结果如何如何?!?!G(S)G(S)：S-a|S-a|(T)|(T)T-T,S|ST-T,S|S【例例:】给定文法如下：

29、给定文法如下：(,(a,(,(a,),a),a)变换为变换为 (+(a+)+a)(+(a+)+a)1.1.给出翻译文法给出翻译文法,统计符号串中统计符号串中a a的个数和的个数和的个数；的个数；给定的符号串有如：给定的符号串有如：=(a,),a)=(a,),a)17.17.语法制导翻译技术应用：语法制导翻译技术应用：2.2.给出翻译文法给出翻译文法,进行符号串变换；进行符号串变换；如如:【解解:1:1】G(S)G(S)：S-a S-a“a1a1”|“a2a2”|(T)|(T)T-T,S|ST-T,S|S其中其中:a1:num1+;a1:num1+;a2:num2+;a2:num2+;19.19.会填写单寄存器下会填写单寄存器下 从从四元式四元式 =目标语言目标语言的生成表的生成表:如如设有语句序列：设有语句序列：If(a+b10)x=(a*b)/(i+(a*b);y=x;If(a+b10)x=(a*b)/(i+(a*b);y=x;18.18.基本块划分和优化基本块划分和优化1.1.写出四元式序列写出四元式序列;2.2.进行基本块划分进行基本块划分;3.3.进行必要的优化进行必要的优化;4.4.写出目标代码写出目标代码.放映结束！