编译原理复习整理总结.doc

资源描述

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

1、编译原理期末复习鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。1、简答题（或者名词解释）下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些

2、点到即可，不要重复啰嗦。（1）简述编译程序的概念及其构成答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。2)构成：（2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序(3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合）答：1）构造词法分析器：用于输入源程序进行词法分析，输出

3、单词符号； 2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。4）构造优化器：对中间代码进行优化。 5) 构造目标代码生成器：把中间的代码翻译成目标程序。6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。7)构造错误处理程序：对出错进行处理。(4) 说明编译和解释的区别：1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序； 2)编译程序运行效率高而解释程序便于人机对话。（5）文法：描述语言语法结构的形式规则，一

4、般用一个四元式表示： G=(VT，VN，S，P)，其中VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号，SVN P：产生式集合(有限)。（6）二义性文法：一个文法中存某个句子，它有两个不同的最左（或者最右推导），则称该文法是二义性的。例子如文法G：Sif expr then S |other Sif expr then S else S 句子if e1 then if e2 then s1 else s2是二义性的。（7）文法的形式（注：文法的形式一定要牢记，特别是2型和3型文法一定要牢记，不仅在概念题中有用，在下面的根据语言写文法题中也有重要作用，如

5、果所写的文法形式不对，一切都是无用功）1）0型文法(短语文法，图灵机)：产生式形式为：a b ，其中：a (VT VN)*且至少含有一个非终结符；b (VT VN)* 2）1型(上下文有关文法，线性界限自动机)：产生式形式为:a b 其中：|a| |b|，仅 Se 例外。 3）2型文法（上下文无关文法，非确定下推自动机)：产生式形式为：Pa， PVN， a (VT VN)* 。4）3型文法(正规文法，有限自动机)：右线性文法：产生式形如：A aB 或 A a其中：a VT*；A，BVN 左线性文法：产生式形如：A Ba 或 A a 其中：a VT*；A，BVN 例题：设G=(VT，VN，S，P

6、)是一个上下文无关文法，产生集合P中的任一个产生式应具有什么样的形式？若G是1型文法呢？若G是正则文法呢？上下文无关文法，产生式形式为：Pa， PVN， a (VT VN)* 。1型文法：产生式形式为:a b 其中：|a| |b|，仅 Se 例外。正则文法：右线性文法：产生式形如：A aB 或 A a其中：a VT*；A，BVN 左线性文法：产生式形如：A Ba 或 A a 其中：a VT*；A，BVN (8)什么是PDA(下推自动机)? 答：PDA是下推自动机，PDA M用一个七元组表示(K,f,H,h0,S,Z)K: 有穷状态集 S：输入字母表(有穷) H:下推栈符号的有穷字母表h0 :

7、H中的初始符号 f: K （e) H K H* S：属于K是初始状态。Z:包含于K，是终结状态集合。(9) 什么是DFA（有穷状态自动机）?自动机M是一个五元式M=(S, S, f, S0, F),其中：1）S: 有穷状态集， 2） S：输入字母表(有穷)，3） f: 状态转换函数，为SSS的单值部分映射，f(s，a)=s表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s。我们把s称为s的一个后继状态。4） S0S是唯一的一个初态； 5） FS ：终态集(可空)。（10）推导：所谓推导就是对于一个含非终结符A的符号串，利用规则A，把A替换成得到新符号串的过程。最左推导：在推导的每一

8、步，选择符号串最左边的非终结符进行替换。最右推导：在推导的每一步，选择符号串最右边的非终结符进行替换。(11)归约：归约是推倒的逆过程，即用产生式的左部非终结符替换右部符号串。(12)什么是句型？什么称为句子？什么是语言？句型：从文法的起始符号出发，经过有限步的推导能够推导出来的符号称为句子。句子：只由终结符构成的句型称为句子。语言：所有句子的集合构成该文法描述的语言。(13)什么是短语？什么是直接短语（也称为简单短语）？什么是句柄？什么是素短语？什么是最左素短语？（以下几个概念一定要理解，考试中肯定会考哪些是短语，直接短语，句柄等，具体方法请参见后面的）短语：如果存在某个文法非终结符P

9、,满足S P,并且P则称为句型相对于非终结符P的短语。直接短语：如果P,即从P出发一步推出，则称为直接短语。句柄：一个句型的最左直接短语称为该句型的句柄。素短语：至少含有一个终结符的短语，并且除了自身外，不包含更小的素短语。最左素短语：句型中最左边的素短语。（14）自顶向下的语法分析方法中需要解决的主要问题什么？如何表示？答：1）主要需要解决回溯和左递归问题。 2）表示方式，回溯：文法中存在形如A1|2|n ,即产生式右部存在多个候选，导致推导时不能确定到底应该选择哪个候选式。左递归：文法中存在形如PP的形式，推导时会导致推导过程无休止的进行下去。注：解决方法，对回溯采取的是提取左公因子，对

10、左递归使消除左递归（包括直接左递归和间接左递归）。(15)内情向量：一般编译程序对数组说明的处理是把数组的有关信息汇集在一个叫做“内情向量”或“信息向量”的表格中，以便以后计算数组元素的地址时引用这些信息。每个数组有一个内情向量。其中的信息包括，数组的类型，维数，各维的上、下界，以及数组的首地址。（16） C语言的活动记录：2、最左最右推导，画语法树，找短语、直接短语、句柄等。这种题目很简单，送分题，一定不能丢分！考题：1）文法GS为：SSdT | T TTG | G G(S) | a试给出句型(SdG)a的推导过程及语法树，并找出(SdG)a的短语，直接（简单）短语、句柄和最左素短语。分析：

11、（1）推导和画语法树这些都很简单，不再赘述。（2）根据所画出的语法树，可以很快的找出短语，直接短语，句柄和最左素短语等，先讲一个简单子树的概念，所谓简单子树是指仅具有单层分支的子树。具体方法如下：短语：任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语；直接短语：任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语；句柄：最左边的直接短语；素短语：至少含有一个终结符的短语，并且除了自身外，不包含更小的素短语。最左素短语：最左边的素短语。答：（1）ST TG GG(S)G(SdT)G(SdG)G(SdG)a语法树：（2）短语：G，SdG, (SdG), a, (SdG)a

15、运算|最低。 (3)考题1： 1）构造正则式a*b|(ab)*b对应的DFA。（15分）画出NFA 确定化DFAXIaIbX,1,2,3,41,2,5Y1,2,51,23,4,YY-1,21,2Y3,4,Y5Y5-3,43,45YXIaIbABCBDEC-DDCEFCF-GGFC注：C和E是终态最小化DFA首先将集合分为A,B,D,F,G,C,E。A,B,D,G都有a,b作为条件输出，F只有b输出，所以分为A,B,D,G和F 同理C,E分为C,E。A,B,Da=B,D Ga=F所以A,B,D,G分为A,B,D和G。Ab=C B,Da=D所以分为A B,D 综上所述：划分的结果为A,B,D,C

16、,E,G.考题2：将NFA确定化为DFA(10分)abSABAACBECDEDFEFDENFA: DFA:IaIbX,0,1,30,2,1,33,Y0,2,1,30,2,1,31,3,Y3,YY1,3,Y2Y21,3Y1,32Y含有Y的状态子集为DFA的终态,上例中的终态有B,C,E.题目中要求是确定化，没有要求最小化，如若最小化，划分的集合为S,A,B,CF,D,E然后再画出最小化后的DFA这里不再赘述。考题3：构造奇数个0和奇数个1组成的自动机。（10分）状态1：偶数个0 偶数个1 状态2：奇数个0偶数个1状态3：奇数个0 奇数个1 状态4：偶数个0奇数个1如果题目改成偶数个0，奇数个1

17、，只要将状态4转换成终态即可，其他类似。5、语法分析自顶向下分析法（LL（1）分析法和递归向下构造子程序法）注：自顶向下分析法本质是由开始符号，按照产生式逐步推导看能否产生需要分析的句子。（1）自顶向下分析中存在的问题左递归和回溯（具体请参见简答题中的第（14）题）（2）消除回溯提取公因子法提取公共左因子:假定关于A的规则 Adb 1 | db 2 | | db n | g 1 | g 2 | | gm(其中，每个g 不以d开头) 那么，可以把这些规则改写成AdA | g 1 | g 2 | | g m Ab 1 | b 2 | | b n （3）消除左递归1)消除直接左递归：直接消除见诸于产

18、生式中的左递归：假定关于非终结符P的规则为PPa | b ，其中b不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式：PbP PaP|e 注：一般而言，假定P关于的全部产生式是PPa1 | Pa2 | | Pam | b1 | b2|bn 其中，每个a都不等于e，每个b都不以P开头那么，消除P的直接左递归性就是把这些规则改写成： Pb1P | b2P | | bnP Pa1P | a2P | | amP | e 例：文法G(E):EET | T TT*F | F F(E) | i 经消去直接左递归后变成： ETE E+TE | e TFT T *FT | e F(E) | i

20、ea|fa|dAgb|Aegb|fgb|hb|c等价于AAea|Aegb |dAa|fa|dAgb |fgb|hb|c将A消除直接左递归AdAaA|fa A|dAgb A |fgb A|hb A|c A Aea A| egb A|e此时，对于BdA|Ae|f，CdAg|Aeg|fg|h由于未在任何产生式的右部出现，所以是多余的。综上所述:消除递归后的文法为：AdAaA|fa A|dAgb A |fgb A|hb A|c AAea A| egb A|e(4)LL(1)分析法1）含义：LL(1)分析方法（也叫预测分析法）：是指从左到右扫描、最左推导(LL)和只查看一个当前符号（括号中的 1）。2）

21、判断一个文法是否是LL(1)文法的充要条件：1. 文法不含左递归，2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若Aa 1|a 2|a n 则 FIRST(a i)FIRST(a j)f (ij)3. 对文法中的每个非终结符A，若它存在某个候选首符集包含e，则FIRST(a i)FOLLOW(A)=f i=1,2,.,n如果一个文法G满足以上条件，则称该文法G为LL(1)文法。(5)LL(1)文法分析表的构造与运用这类题目，主要就是判断文法是否满足LL(1)文法的三个充要条件，分为以下几步：1）首先将文法分解，判断是否有左递归好，有的话肯定不是LL(1)文法；2）算非

22、终结符的First集合和Follow集合，具体方法请参见期中考试的提纲，其实最本质的要抓住first集合是Ua，Follow集合石 Ua即可。3）算Select集合，书上没有提到Select集合，计算Select集合实质就是计算First(a)，当然考试时不一定非要写成Select集合形式，可以直接计算First(a)来判断交集是否为空，从而是否为LL(1)文法，请看考题1。4）至于判断一个句子的分析过程，大家注意一下，所给的句子不一定是能通过该文法分析出来的，实际上在分析之前可以自己根据文法推推看，请看考题1.5）分析表中没有填的空格代表出错，如果分析时遇到了代表该句子不符合该文法。考题1：

23、判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表并分析句子aabe的分析过程。（15分）SaD DSTe| TbM MbH HM|分析：判断一个文法是否为LL(1)文法是否为LL(1)文法，主要就是判断是否满足LL(1)文法的充要条件，有一个不满足就不是LL(1)文法。对于aabe根据文法SaDaSTeaaDTeaaTeaabMe由于M不能为空字，所以最后肯定推不出来，也就是该句子不能由该文法推出，出错。当然一般题目都是LL(1)文法，否则题目就不好往下做，没有意义。答：(1)经分析该文法无左递归；(2)非终结符的First和Follow集合如下表所示非终结符XFirst(

24、X)Follow(X)Sa# bD a# bTbe Mbe H be 将文法分解为：SaD DSte D TbM MbH HM H依次计算：First(aD)=a First(Ste)=aFollow(D)=# b First(bM)=bFirst(bH)=b First(M)=b Follow(H)= e First(Ste)Follow(D)= First(M)Follow(H)=该文法是LL(1)文法LL(1)分析表如下：abe#SSaDDDSTeDDTTbMMMbHHHMH(3)aabe的分析过程如下：步骤符号栈输入串所用产生式0#Saabe#1#Daaabe #SaD2#D abe#

25、3#eTS abe#DSTe4#eTDa abe#5#eTD be#6#eT be#D7#eMb be#TbM8#eM e# 出错考题2：判断下面文法是不是LL(1)文法，若是请构造相应的LL(1)分析表，写出aaabd的分析过程。SaH HaMd|d MAb|e AaM|e答：（1）可以判断该文法无左递归。（2）将文法分解为分解：SaH HaMd Hd MAb Me AaM Ae 求First和Follow集合非终结符XFirst(X)Follow(X)Sa#Ha,d#Me, a,ed,bAa,eb求Select集合Select(SaH)=First(aH)=a Select(HaMd)=

26、First(aMd)=a Select(Hd)=d Select(MAb)=First(Ab)=a,e Select(Me)=First(e)UFollow(M)= Follow(M)=d,b Select(AaM)=FirstaM=a Select(Ae)=First(e)=eSelect(HaMd) Select(Hd)= Select(MAb) Select(Me)= Select(AaM) Select(Ae)= 该文法是LL(1)文法。（3）LL(1)分析表如下：adbeSSaHHHaMdHdMMAbMeMeMAbAAaMAeaaabd#的分析过程如下：步骤符号栈输入串所用产生式0#

27、Saaabd#1#Haaaabd #SaH2#H aabd#3#dMa aabd#HaMd4#dM abd#5#dbA abd#MAb6#dbMa abd#AaM7#dbM bd#8#db bd#Me9#d d#10# #考题3：构造LL(1)分析方法的总控流程图6、构造递归下降识别程序这类题目首先看文法有无左递归和左公因子，有的话一定要消除，我期中给大家的答案错了，考题1为更正后的答案。考题1：为文法GE： E V | V+E V N | NE N i构造递归下降识别程序（10分）解：（1）提取左公因子：EVE E +E|e V NV VE| e N i(3) 构造递归下降识别程序PROCE

28、DURE E；BEGIN V; EEND;PROCEDURE E；IF SYM=+ THEN BEGINADVANCE； EENDPROCEDURE ；BEGIN N;VEND;PROCEDURE F；IF SYM= THEN BEGINADVANCE;E；IF SYM= THEN ADVANCEELSE ERROREND ELSE ERROR;PROCEDURE N；IF SYM=i THEN ADVANCEELSEERROR;考题2：为文法GE:EE+T|T TT*F|F F(E)|i构造递归下降识别程序解：（1）消除左递归：ETE E+TE | e TFT T*FT | e F(E) |

29、 i (2)构造递归下降识别程序PROCEDURE E；BEGIN T；E END；PROCEDURE T；BEGIN F；T ENDPROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THENBEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR ENDELSE ERROR;PROCEDURE E； IF SYM=+ THEN BEGINADVANCE； T；E ENDPROCEDURE T； IF SYM=* THEN BEGIN ADVANCE； F；T END7、自底向上分析法LR（0）分析法注

30、：自底向上分析法本质是从输入串开始，逐步进行“归约”，直到文法的开始符号,其关键问题是寻找句柄。自底向上分析法还有算符优先分析法，SLR(1),LR（1）等等，老师那天重点讲了一道LR(0)分析法的题目，他说算符优先分析法A卷不考，但是补考的B卷会考，按照他的意思，这次期末考试LR(0)是考定的了，SLR(1),LR（1）应该不考，因为LR(0)分析法个人感觉也是所有题目中最繁的了，下面已老师讲的题目为例这，也是一份试卷上的考题，首先介绍一些相关知识。（1） LR(0)项目：通俗点讲，文法G中的任何一个产生式的右部的任何位置添加一个圆点就成了LR(0)项目，比如AAb是产生式，则AAb AAb

31、 AAb都是该产生式对应的全部项目。项目动态的表示归约的一个阶段：对于项目AAb，可以这样理解它：“”之前的A表示的是在识别Ab过程中已输入到栈终的部分；“”之后的表示在识别Ab过程中期望出现的部分；“”表示则是在识别Ab过程中当前的识别进度的定位。项目AAb已经具备了识别Ab的一切条件，因此被称为归约项目。项目可以分为以下四类：Pa称为移进项目其中, PX称为待约项目，其中X为非终结符，P 称为归约项目，S S称为接收项目（2）LR(0)的分析栈可以看成两部分状态栈 LR分析器的核心是一张分析表：ACTIONs，a：当状态s面临输入符号a时，应采取什么动作.GOTOs，X：状态s面对文法符号

32、X时，下一状态是什么.下面几张PPT大家看看，对基本概念有个印象：这一章的概念较多较抽象，我一时半会也讲不完讲不清楚，这里不再赘述，直接看题目，知道怎么做就行，下面以一道考题这也是老师讲的原题为例讲解如何做这类题目，首先一般这种题目分三步走：(1)拓广文法：假定文法G是一个以S为开始符号的文法，我们构造一个G，它包含了整个G，但它引进了一个不出现在G中的非终结符S，并加进一个新产生式SS，而这个S是G的开始符号。那么，我们称G是G的拓广文法。这样，便会有一个仅含项目SS.的状态，这就是唯一的“接受”态。（2）构造识别文法活前缀的DFA:对于任意的项目即I,其闭包CLOSURE(I)计算方法如下

33、，I中的所有项目都属于CLOSURE(I);如果PX,并且X为非终结符，则所有形如X的项目也属于ClOSURE(I)定义函数GO(I,X)，其中I是项目集，X是任意的文法符号（终结符，非终结符都可以），GO(I，X)=CLOSURE(J).J是从I中项目出发后读取X后到达的后继项目,即J=PX| PXI 有了上述CLOSURE和GO的定以后，从CLOSURE(SS)出发，利用GO函数，产生出它在每个可能的文法符号下，要转移的项目集，再对新产生的项目集采取同样的方法直到没有新产生的项目集未被处理为止。(4) 根据计算出的项目集之间的关系画出DFA和LR(0)分析表，其中LR(0)构造方法如下:(

34、5) 对具体的句子运用LR(0)分析的方法如下：每一项ACTIONs，a所规定的四种动作:1. 移进把(s，a)的下一状态s和输入符号a推进栈，下一输入符号变成现行输入符号.2. 归约指用某产生式A进行归约. 假若的长度为r，归约动作是，去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s=GOTOsm-r, A和文法符号A推进栈.3. 接受（即acc）宣布分析成功，停止分析器工作.4. 报错考题：构造文法GE的LR(0)分析表，并给出accd的分析过程。（0）SE（1）EaA （2）EbB （3）AcA （4） Ad （5）BcB （6）Bd分析：题中已

35、经进行了推广文法，所以第一步就不需要了，下面就是开始构造识别活前缀的DFA，然后构造出LR（0）分析表，最后在进行分析，实际上对于accd我们自己可以先推一下，EaAacAaccAaccd所以该句子符合文法，那么最终构造出的LR（0）分析表对该句子进行分析后必定得到“acc”（接受的意思），否则构造的LR(0)分析表出错。答：（1）构造识别活前缀的DFA:I0=Closure(SE )= SE, EaA, EbB I1=GO(I0,E)=Closure(SE)= SE I2=GO(I0,a)=Closure( EaA )= EaA，AcA ，Ad I3=GO(I0,b)=Closure( Eb

36、B )=EbB, BcB ，Bd （为了方便，下面计算中的Closure不再写了，直接给出答案,考试时可以不写，当然计算I0是必须要的）I4=GO(I2,A)= EaA I5=GO(I2,c)= AcA，AcA ，Ad I6= GO(I2,d)= Ad I7=GO(I3,B)= EbBI8= GO(I3,c)= BcB，BcB ，Bd I9= GO(I3,d)= BdI10= GO(I5,A) = AcA GO(I5,c)=I5 GO(I5.d)=I6I11= GO(I8,B) BcB GO(I8,c)=I8 GO(I8.d)=I9画出DFA:注：实际上构造LR(0)分析表时这个图没有必要画，

37、根据上述计算结果即可填写下表。（2）画出LR(0)分析表注：至于怎么填这个表请参见上一页中的PPT,这里不再赘述,Action表中si代表跳转到第i个状态，ri代表选择文法中第i条规则进行归约,acc代表接受，即分析成功。Goto表中数字i代表跳转到第i个状态。（3）对accd#进行分析步骤分析栈输入串操作1#0accd#s22#0a2ccd#s53#0a2c5cd#s54#0a2c5c5d#s65#0a2c5c5d6#r46#0a2c5c5A10#r37#0a2c5A10#r38#0a2A4#r19#0E1#acc8、写出表达式或者程序的中间形式逆波兰式和四元式是三地址代码的两种记录表现形式

38、，当然表示形式还有三元式、间接三元式等等，根据老师的意思应该不考，四元式和逆波兰式必考。（1）逆波兰表达式逆波兰表达式即后缀表达式，就是中缀表达式（也就是我们一般看到的表达式形式）对应的后续遍历结果，这个方法有很多，个人认为搞清楚运算优先级，观察一下就可写出，先算谁就将其对应的操作数写出，运算符放在后面就行很简单：例如：写出下列各式的逆波兰表示（1） -a-(b*c/(c-d) + (-b)*a) (2) -A+B*C (D/E)/F 解：（1） abc*cd-/ba*+ - （2） ABCDE/*F/+ 注：代表负号“-”（2）四元式四元式形式如下（op,arg1,arg2,Result）从左至右分别代表运算符，第一操作数，第二操作数,运算结果。如：A + B * ( C - D ) + E / ( C - D ) N 对应的四元式序列如下:四元式 : (1) ( - ,C ,D,T1 ) (2) ( * ,B,T1,T2) (3) ( + ,A,T2,T3) (4) ( - ,C,D,T4)(5) ( ,T4,N,T5) (6)( / ,E ,T5,T6) (7) ( + ,T

展开阅读全文