编译原理期末复习.pptx-得力文库

资源描述

《编译原理期末复习.pptx》由会员分享，可在线阅读，更多相关《编译原理期末复习.pptx（53页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1题型：题型：填空填空 20分，分，10个空个空选择选择 20分，分，10小题小题判断判断 10分，分，10小题小题简答题简答题 20分，分，4小题小题分析题分析题 30分，分，3小题小题第1页/共53页2编译原理复习纲要编译原理复习纲要第第第第1 1章章章章编译引论编译引论编译引论编译引论 2-4 2-4第第第第2 2章章章章形式语言与自动机理论形式语言与自动机理论形式语言与自动机理论形式语言与自动机理论 20-2520-25第第第第3 3章章章章词法分析词法分析词法分析词法分析 4-64-6第第第第4 4章章章章语法分析语法分析语法分析语法分析自上而下分析自上而下分析自上而下分析自

2、上而下分析 25-3525-35第第第第5 5章章章章语法分析语法分析语法分析语法分析自下而上分析自下而上分析自下而上分析自下而上分析第第第第6 6章章章章语义分析和中间代码生成语义分析和中间代码生成语义分析和中间代码生成语义分析和中间代码生成 10-1210-12第第第第7 7章章章章运行环境运行环境运行环境运行环境 4-64-6第第第第8 8章章章章代码优化代码优化代码优化代码优化 15-2015-20第第第第9 9章章章章代码生成代码生成代码生成代码生成 6-86-8第2页/共53页CH2.CH2.形式语言与自动机理论主要题型：所有题型主要题型：所有题型1.1.符号串、符号串集

3、合的运算符号串、符号串集合的运算符号串的长度、符号串的子串、符号串的连接、符号串的长度、符号串的子串、符号串的连接、符号串的方幂符号串的方幂符号串集合的乘积、符号串集合的方幂符号串集合的乘积、符号串集合的方幂例：例：(1)(1)设字符串设字符串=xyzabc=xyzabc，则下面哪个不是字符串，则下面哪个不是字符串的子串（的子串（C C ）A.xyz B.abc C.xyab D.A.xyz B.abc C.xyab D.zabzab第3页/共53页CH2.CH2.形式语言与自动机理论(2)(2)设字母表A=ab,x,yA=ab,x,y，字母表A A上的符号串=abxyabxy=abxya

4、bxy，则|=|=。(3)(3)设有字母表A=a,b,c,d,eA=a,b,c,d,e，字母表A A上的符号串1=add1=add，2=code2=code，则12=12=。(4)(4)设字符串=good=good，则3 3=。第4页/共53页CH2.CH2.形式语言与自动机理论(5)(5)设有A,BA,B两个符号串集合，其中A=a,abcA=a,abc，B=xx,yy,B=xx,yy,则AB=(A)AB=(A)A.axx,ayy,abcxx,abcyyA.axx,ayy,abcxx,abcyyB.axxyy,abcxxyy,abcyy,abcabc,xxxx,yyyyB.axxyy,abcx

5、xyy,abcyy,abcabc,xxxx,yyyyC.aabc,axx,C.aabc,axx,D.R1D.R1和R2R2代表不同正则集(6)(6)设有A=a,abcA=a,abc 则A A3 3=。第5页/共53页CH2.CH2.形式语言与自动机理论2.句子的判断：判断一个句子是不是合法的句子(1)根据文法(2)根据自动机第6页/共53页CH2.CH2.形式语言与自动机理论实例:给定文法AbA|ccAbA|cc，则符号串cc bcbc bcbcc bccbcc bbbcccc bcbc bcbcc bccbcc bbbcc中，是该文法句子的是(D )(D )A.A.B.B.C.C.D.D.第

6、7页/共53页8如图所示自动机M，请问下列哪个字符串不是M所能识别的(D )。A.bbaaB.abbaC.ababD.Aabb第8页/共53页93.判断句子、画分析树、文法符号集、终结符集、非终结符集1)设有文法：SaSbS|bSaS|c(1)判断符号串ababba是否为文法G(S)的句子，如果是画出其分析树。(2)给出G(S)的元语言符号集、文法符号集、终结符集、非终结符集第9页/共53页103.判断句子、画分析树、文法符号集、终结符集、非终结符集1)设有文法：SaSbS|bSaS|c(1)判断符号串ababba是否为文法G(S)的句子，如果是画出其分析树。(2)给出G(S)的元语言符号集、

7、文法符号集、终结符集、非终结符集第10页/共53页11练习：设有文法G(S)为SABx|xSxAxy|yAy|mnBxyA|m(1)判断符号串ymnyxyxy是否为文法G(S)的句子，如果是画出其分析树。(2)给出G(S)的元语言符号集、文法符号集、终结符集、非终结符集第11页/共53页125.5.有限自动机的表示状态函数、状态图、状态矩阵例：设有确定的有限自动机M:M:（0,1,2,3,a,b,0,1,2,3,a,b,，0 0，33）（0 0，a a）=1 =1 （0 0，b b）=2=2（1 1，a a）=3 =3 （1 1，b b）=2=2（2 2，a a）=1 =1 （2 2，b b

8、）=3=3（3 3，a a）=3 =3 （3 3，b b）=3=3画出其状态转换图和状态转换矩阵第12页/共53页13练习：设有确定的有限自动机M:（S,U,V,Q,0,1,f，S，Q）f（S，0）=U f（S，b）=Qf（U，0）=Q f（U，1）=Vf（V，0）=S f（V，1）=Qf（Q，1）=V画出其状态转换图第13页/共53页145.NFA转换为DFA(1)给定非确定的有限自动机M如下图所示将M确定化，并画出确定化后的状态转换图（要求：写出步骤）第14页/共53页155.NFA转换为DFA练习：练习：给定非确定的有限自动机给定非确定的有限自动机M M如下图所示如下图所示4f35621

9、i aaaabbbb将将M M确定化，并画出确定化后的状态转换图（要求：确定化，并画出确定化后的状态转换图（要求：写出步骤）写出步骤）第15页/共53页16给定非确定的有限自动机给定非确定的有限自动机M M如下图所示如下图所示将将M M确定化，并画出确定化后的状态转换图（要求：确定化，并画出确定化后的状态转换图（要求：写出步骤）写出步骤）第16页/共53页176 6 消除无关状态消除无关状态消除上图所示的消除上图所示的DFADFA的无关状态（要求写出步骤）的无关状态（要求写出步骤）第17页/共53页187 7 有限自动机和正规式的转换有限自动机和正规式的转换例例练习练习第18页/共53页CH3

12、F-(id)F|第24页/共53页CH4 CH4 语法分析自下而上分析4.LL(1)分析例：已知文法G(E)为：E-TEE-TEE-+TE|E-+TE|T-FTT-FTT-*FT|T-*FT|F-(E)|iF-(E)|i其预测分析表为：其预测分析表为：分析i*i+i*i是否为该文法的句子，写出分析过程第25页/共53页26第26页/共53页步骤步骤分析栈分析栈余留输入串余留输入串所用产生式所用产生式1#Ei*i+i*i#23456789第27页/共53页练习：练习：4.LL(1)分析例：已知文法G(E)为：E-TEE-TEE-+TE|E-+TE|T-FTT-FTT-*FT|T-*FT|F-(

13、E)|iF-(E)|i其预测分析表为：其预测分析表为：分析i+i+i*i是否为该文法的句子，写出分析过程第28页/共53页CH5 CH5 语法分析自下而上分析主要题型：所有题型主要题型：所有题型LRLR分析分析实例：实例：第29页/共53页CH5 CH5 语法分析自下而上分析文法文法GMGM及其及其LRLR分析表如下，请给出对串分析表如下，请给出对串dbba#dbba#的分析过程。的分析过程。GM:1)M VbAGM:1)M VbA2)V d2)V d3)V 3)V 4)A a4)A a5)A Aba5)A Aba6)A 6)A 第30页/共53页31nameACTIONGOTObdaMAV

14、0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5第31页/共53页32对串dbba#的分析过程如下表步步骤骤状态栈状态栈文法符号文法符号栈栈剩余输剩余输入符号入符号动作动作12345678900302024024602467024678024601#d#V#Vb#VbA#VbAb#VbAba#VbA#Mdbba#bba#bba#ba#ba#a#移进移进用用V d归约归约移进移进用用A 归约归约移进移进移进移进用用A Aba 归约归约用用M VbA 归约归约接受接受第32页/共53页33练习：文法练习：文法GSGS及其及其LRLR分析表如下，请分析表如下，请

15、给出对输入串给出对输入串da;aoa#da;aoa#的分析过程。的分析过程。GS:GS:0)SS0)SS1)SdSoS1)SdSoS2)S dS2)S dS3)S S;S 3)S S;S 4)S a 4)S a 第33页/共53页34nameACTIONGOTOdo;a#S0S2S3S311S4acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1第34页/共53页35输入串da;aoa#的分析过程如下表：步骤状态栈文法符号栈剩余输入符号动作123456789101112 002023025025402543025460250257025730257

16、801#d#da#dS#dS;#dS;a#dS;S#dS#dSo#dSoa#dSoS#Sda;aoa#a;aoa#;aoa#;aoa#aoa#oa#oa#oa#a#移进移进用S a 归约移进移进用S a 归约用S S;S 归约移进移进用S a 归约用SdSoS 归约接受第35页/共53页v2 FIRSTVT 和和LASTVT(一)FIRSTVT构造集合FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式Pa或PRa，则a FIRSTVT(P)；2.若a FIRSTVT(R)，且有产生式PR，则a FIRSTVT(P)。第36页/共53页37v构造

17、集合LASTVT(P)的算法。v按其定义，可用下面两条规则来构造集合LASTVT(P)：1.若有产生式P a或P aQ，则a LASTVT(P)；2.若a LASTVT(Q)，且有产生式P Q，则a LASTVT(P)。(二)LASTVT第37页/共53页38设有文法设有文法G(E)G(E)如下：如下：vEE+T|TvTT*F|FvFPF|PvP(E)|i(1)(1)计算该文法的计算该文法的FIRSTVTFIRSTVT和和LASTVTLASTVT(2)(2)计算该文法的有限关系并产生优先关系表计算该文法的有限关系并产生优先关系表第38页/共53页39v(1)vFIRSTVT(E)=+,*,i,

18、(vFIRSTVT(T)=*,i,(vFIRSTVT(F)=,i,(vFIRSTVT(P)=i,(LASTVT(E)=+,*,i,)LASTVT(T)=*,i,)LASTVT(F)=*,i,)LASTVT(P)=i,)第39页/共53页40第40页/共53页41练习：(1)计算该文法的FIRSTVT和LASTVT(2)计算该文法的有限关系并产生优先关系表第41页/共53页CH6 CH6 语义分析和中间代码生成v主要题型：所有题型主要题型：所有题型v中间代码表示中间代码表示写出表达式a:=b*c+b*d-e 的后缀表示、三元序列、四元序列。练习：写出表达式A+B*(C-D)*N的后缀表示、三元序

19、列、四元序列。第42页/共53页CH7 CH7 运行环境主要题型：主要题型：填空、选择、判断填空、选择、判断第43页/共53页CH8 CH8 代码优化主要题型：主要题型：填空、选择、判断、分析填空、选择、判断、分析第44页/共53页45基本块和控制流图基本块和控制流图将下面程序划分成基本块并作出其程序控将下面程序划分成基本块并作出其程序控制流图制流图第45页/共53页46（1）Read(A,B)（2）F=1（3）C=A*A（4）D=B*B（5）If C100 goto L2（16）halt（17）L2:F=F-1（18）goto L1 第46页/共53页47第47页/共53页48第48页/共5

20、3页49第49页/共53页50语句语句(1)(1)语句语句(5)(5)、(6)(6)(10)(10)、语句、语句(11)(11)(15)(15)、语句、语句(16)(16)、语句（、语句（1717）和（）和（1818）分别是）分别是一个基本块一个基本块设语句设语句(1)(1)语句语句(5)(5)为为语句（语句（6 6）语句（语句（1010）为）为语句语句(11)(11)语句（语句（1515）为）为语句（语句（1616）为）为语句语句(17)(17)和（和（1818）为）为、第50页/共53页512.DAG2.DAG图的构造（利用图的构造（利用DAGDAG图进行优化）图进行优化）第51页/共53页CH9 CH9 代码生成主要题型：主要题型：填空、选择、判断填空、选择、判断第52页/共53页53感谢您的观看。第53页/共53页

展开阅读全文