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

《编译原理复习总结-东北大学.ppt》由会员分享，可在线阅读，更多相关《编译原理复习总结-东北大学.ppt（32页珍藏版）》请在三一办公上搜索。

1、,编译方法,2013年12月,复习.总结,第一部分 考试范围,一.概念部分,概念词语解释(简单明确),概念词语填空(不求全，只求准),二.形式语言基础,简单文法构造,自己总结。,如：给定一符号串集合，构造文法。,主要语法成分的识别,给定一文法和一个符号串，证明 是句型(句子)，并画语法树求短语、简单短语和句柄。,(接上页),简单文法变换技术,如 消除文法的直接左递归！主要是三种常用的文法变换方法 圆括号、方括号和花括号。,三.自动机基础,简单有限自动机的构造,如 给定一符号串集合(或正规式或正规文法)，构造有限自动机（DFA）,求一个有限自动机所定义的语言(符号串集合)。,(接上页),四.词法

2、分析,1.2个实验。,五.语法分析,给定文法，构造递归子程序（框图）,判断一个文法是否是 LL(1)文法；,(1)消除 边，NFA=DFA,(2)NFA=DFA。,5.有限自动机的实现,有限自动机的确定化。,4.确定的有限自动机的最小化。,2.会写TOKEN 序列；,3.词法分析技术应用；,(接上页),七.中间代码生成,会写常用语句的中间代码(逆波兰式，四元式)；,会构造常用语法成分的翻译文法；,给定翻译文法和动作序列，会走翻译过程。,给定文法，构造LL(1)分析表，,LR(0)文法的判断和相应分析表的构造。,六.符号表组织,符号表结构以及填写。,5.简单优先文法的判断和相应分析表的构造。,6

3、.语法分析器的构造。,4.语法制导翻译技术的应用。,(接上页),九.目标代码生成,1.会写常用语句在单寄存器下的目标代码生成过程；,八.优化处理,3.基本块内四元式的优化。,1.基本块的划分。,2.局部优化的几种常见方法。,1.编译程序(compiler),目标语言,词法分析,源语言,语法分析,语义分析,优化处理,代码生成,错 误 处 理,符 号 表 管 理,2.编译程序结构,五个阶段,第二部分 基本概念总结,是一种语言翻译程序，它特指把,某种高级程序设计语言翻译成具体计算机上的,低级程序设计语言。,4.文法(上下文无关文法),(接上页),3.形式语言,所有符号串之集合；其中的每个符号串称为句

4、子。,G(Z)=(VN,VT,S,P),VN:非终结符集（定义的对象集，如：语法成分等)；,例：,G(E),E-E+T|E T|T,T-T*F|T/F|F,F-i|(E),简单算术表达式文法,其中：,VN=E,T,F;,VT=i,+,-,*,/,(,);,Z=E;,P：,可用四元组表示：,VT:终结符集（字母表）；,S:开始符号（研究范畴中，最大的定义对象）；,P:规则集（又称产生式集）；,字母表上的符号，按一定的规则组成的,是定义语言的规则集，,(接上页),5.有限自动机(finite automata）FA,是一种数学模型，用于描述正规语言,FA=(Q,S,F,),：变换（二元函数）：,Q

5、(有限状态集);,F(结束状态集,F Q）；,S(开始状态集,S Q）；,(字母表)；,或,(i,a）=j,确定的有限自动机(DFA),特征：开始状态唯一;变换函数单值；不带边。,非确定的有限自动机(NFA),带有边的非确定的有限自动机(NFA),不带有边的非确定的有限自动机(NFA),-不能全部具备上述特征者！,6.有限自动机的分类,其中,可定义为五元组：,(接上页),(1)识别单词从用户的源程序中把单词分离出来;(2)翻译单词把单词转换成机内表示，便于后续处理。,7.词法分析任务,标识符(i)，常数(c)，关键字(k)，界符(p)。,8.单词的分类,9.有限自动机作为单词识别器,注,滤掉回

6、车换行、空格！,(接上页),形式上说，语法分析是指对给定的符号串（），判定其是否是某文法G(S)的句子。即,10.语法分析,语法分析主要功能是识别短语和句型，,1.自顶向下法（推导法）,2.自底向上法（归约法）,11.语法分析方法分类,12.四种实用分析方法及相应文法,适应于自顶向下的分析法-LL(1)文法 是指文法中，具有相同左部的各产生式，其选择集合不相交。,适应于自底向上的分析法-LR(0)文法 是指文法的句柄识别器(有限自动机)无冲突项目。,(接上页),13.标识符的语义信息：,名字、类型、种类、地址。,14.语法制导翻译技术,通俗地说，所谓语法制导翻译技术，是指：,15.优化处理,优

7、化处理是指产生更高效的目标代码所做的工作。,或者说 为提高目标程序质量所做的工作。,第三部分 基本运算总结,1.判定一个符号串是否是某文法的句子：,A-d B b|c,B-B b|,G(S):S-a A B|a A c,哪个符号串是句子？adbb abc,如：设有文法,【解】,adbb?,S,=adBbb,+,S=adbb,=aAB,也可以用 语法树证明：,S,a A B,d B b,B b,=adBb,=adbb,adbb 是句子,abc?,S=aAB,=adBbB=?,=acB=?,又 S=aAc,=adBbc=?,=Acc=?,abc 不是句子。,也可以用 语法树证明：,(接上页),2.

8、简单的文法构造：,设有符号串集合：,L=a,banc|n0,构造上下文无关文法；构造正规文法。,解：,构造上下文无关文法；,(2)构造正规文法。,G(S):,S-a|b A c,A-a A|,G(S):,S-a|b A,A-a A|c,3.求解一个句型的短语和句柄：如：已知文法 G(S):,A-a A c|b,试指出句型 abAb 的短语和句柄：,【解】,首先画该句型的语法树：,S,a S A,b A,b,句柄 是一个句型的最左简单短语。,短语 是一个句型任一子树的树叶全体。,简单短语 是一个句型任一简单子树的树叶全体。,根据语法树确认短语和句柄：,短语：abAb,bA,b,简单短语：bA,b

9、,句柄：bA,S-b A|a S A,【解】,S-a A b|a(首符号相同),变换后得：S-a A b,或 S-a S;S-A b|,A-A b|d（直接左递归）,变换后得：A-d b,或 A-d A;A-b A|,4.简单的文法变换：,如：有文法 G(S):S-a A b|a,A-A b|d,(1)具有相同左部的各产生式，其首符号不相同；,试进行文法变换，使其满足以下两个条件：,(2)消除文法的左递归.,变换后的文法 G(S):,S-a A b,A-d b,5.有限自动机的构造：,如：已知符号串集合：,A=an,ban|n0,试构造有限自动机。,【解】,a,+,b,-,此集合有两种句型（还

10、包含一个空串）,分别构造之：,-,+,+,-,a,合成为一个：,b,-,+,-,a,a,错误,b,正确,+,-,a,a,-,a,-,6.有限自动机的确定化：,如 把下述 NFA 转换为 DFA:(消边,DFA最小化,略),C2,3,B2,C2,3,C2,3,B2,C2,3,B2,-,B2,3,B2,3,B2,3,-,7.正规语言的三种表示方法：,(2)有限自动机：,+,-,a,b,c,c,设有正规语言：L=acn,bcm|n0,m0,(1)正规式：,e=ac*|bc+,(3)正规文法：,G(S):,S-a A|b B,A-c A|,B-c A,令,3,5,y,a,x,8.已知源程序片断,写出词

11、法分析后的 TOKEN序列:,如：if(x 5)y=3*x a;,KTk,PTp,自己设定符号表：,(k,3),(p,7),(c,1),(p,8),(i,2),(p,5),(i,1),(p,2),(i,3),(p,9),TOKEN 序列：,(i,1),(p,6),(c,2),(p,3),9.2个实验,略,10.词法分析技术应用,已知定点数的结构如下:开始以数字开头,后随一串0 或多个数字,再后随一个点“.”,点后面一串0 或多个数字,在点后至少有一位数字。,2.在自动机的结点处插入适当的语义动作，分别统计点“.”的前后各有几个零。,1给出该定点数的正规式和自动机 FA,例:,解:,1,2,3,

12、4,+,d,.,d,-,d,d,0,0,0,Q2:if(ch=0)num1+;,Q3:if(ch=0)num2+;,Q1:num1=0;num2=0;,Q4:if(ch=0)num2+;,10.给定文法会构造递归子程序(框图)：,例：,err2,NEXT(w),err1,NEXT(w),S子程序,n,n,n,y,y,b,d,NEXT(w),y,S-aASb|Bd;A-cS|;B-bB|d,遇终结符，判定之；,遇非终结符，调用之；,遇，直接出口。,算法,NEXT(w),遇时,n,y,A子程序,NEXT(w),n,y,NEXT(w),err3,y,n,B子程序,11.会判定LL(1)文法和构造LL

13、(1)分析表,如 已知文法 G(S)：,（1）求选择集合；证明是LL(1)文法；,select()=,select()=,select()=,select()=,select()=,select()=,=,【解】,（1）求选择集合,a,b,d,c,follow(A),a,b,d,b,d,（2）LL(1)分析表:,三对选择集合两两不相交!,G(S)是 LL(1)文法!,（2）构造 LL(1)分析表。,如,12.会判定LR(0)文法和构造LR(0)分析表,B-c9,Z-Z1(0),Z-a2 B3 A4 d5(1),A-b6 c7(2)|c8(3),扩展文法,LR（）分析表：,a2,Z1,1,A4,

14、OK,r(1),r(1),r(1),r(1),r(1),d5,r(3),r(3),r(3),r(3),r(3),r(2),r(2),r(2),r(2),r(2),c8,b6,B3,c9,5,4,8,6,7,3,2,9,r(4),r(4),r(4),r(4),r(4),c7,分析表中无冲突项目，是LR(0)文法！,0,【例】,头符号集合尾符号集合,优先矩阵,表项=空表示两个符号不可能相临。,13.会判定简单优先文法和构造简单优先分析表,14.会写表达式的逆波兰式,例：求下述表达式的逆波兰式：,=pos(a+b/d)e*,pos(a+b/d)*e),=pos(a+b/d)pos(e)*,=pos(

15、a)pos(b/d)+e*,=a bd/+e*,pos(a+b/d)*e)=a b d/+e*,(a+b/d)*e,pos()?,脱括号,a,b,d,/,+,e,*,注,根据逆波兰式特点：,运算对象顺序不变；,运算符紧跟运算对象之后。,可直接写出：,算术表达式四元式翻译文法：,15.会构造常见语法成分的四元式翻译文法,【例】,算术表达式逆波兰式翻译文法：,E-T|E+T“PUSH(+)”T-F|T*F“PUSH(*)”F-i“PUSH(i)”|(E)其中:PUSH(x)-把 x 压入分析栈；,QUAT(+),QUAT(*),16.会走翻译过程的动作序列：,E,=T,=T*F*,=F*F*,=a

16、a*F*,=aa*(E)*,=aa*(E+T+)*,=ai*(T+T+)*,【例】算术表达式逆波兰式翻译文法,abc+*,动作序列的执行结果：,相应的四元式动作序列：,PUSH(a)PUSH(b)PUSH(c)GEQ(+)GEQ(*),执行的 过程、结果如何?!,【例:】给定文法如下：,(,(a,),a)变换为(+(a+)+a),1.给出翻译文法,统计符号串中a的个数和的个数；,给定的符号串有如：=(a,),a),17.语法制导翻译技术应用：,2.给出翻译文法,进行符号串变换；,如:,【解:1】,其中:,a1:num1+;,a2:num2+;,19.会填写单寄存器下,从四元式=目标语言的生成表:,如,设有语句序列：,If(a+b10)x=(a*b)/(i+(a*b);y=x;,18.基本块划分和优化,1.写出四元式序列;,2.进行基本块划分;,3.进行必要的优化;,4.写出目标代码.,放映结束！,