编译原理必中(完全版v1.0)

1、题型：（左题目数，右题目分值）1、 判断 10*1分2、 选择 10*1分3、 设计 2*5分4、 设计 3*5分5、 设计 8分+5分6、 填空 4分+10分7、 证明 3*4分8、 综合题 8分+4分+4分写在必中之前的话，并不是说看了这份必中肯定会答了，但是这门课五五开，理论上卷面考个二三十就能过了，然而这门课很抽象，我看了蛮久的，希望大家看不懂多想想，只靠考前一晚上个人认为时间是不够的（除非你通宵+边上有人会教你）。我会陆续更新版本上传，在此期间大家可以看看后面大题目具体做法都是怎么做的（如果你只是想求过就当我没说这段话吧）编译原理考试必中猜想！（没中别打我）1、 二：20分（这部分不

2、要求背，看得懂会选择会判断就够）1、 正规文法的描述（正规文法跟正规式的比较）正规文法：<某个类型，如标示符、字母数字等等>l（关键字）|l<另一个类型>正规式（正则表示式）：定义一个辅助字母表：空集，e，|，*，.，（，）具体例子看一下p53例4.2你就知道这个东西到底怎么写了2、 语法分析，前端+后端划分的好处P51意思就是语法分析,和词法分析，原理是分而治之使整个编译程序的结构更简洁、清晰和条理化。（词法分析比语法分析简单）编译程序的效率会改进。（把词法分析独立出来，用专门的技术提高编译速度）增强编译程序的可移植性。3、 LR(0)项目集与SLR(1)区别，共同点

3、LL(1)就是向前只搜索1个符号,即与FIRST()匹配,如果FIRST为空则还要考虑FELLOW.LR需要构造一张LR分析表,此表用于当面临输入字符时,将它移进,归约（即自下而上分析思想）,接受还是出错.LR(0)找出句柄前缀，构造分析表，然后根据输入符号进行归约。 SLR(1)使用LR(0)时若有冲突，不知道归约，移进，活移进哪一个，所以需要向前搜索，则只把有问题的地方向前搜索一次4、 中间代码特点、好处（逆波兰、三元式、四元式）逆波兰：最简单，在编译程序出现之前就有。方便堆栈体系的计算机目标代码生成。原理：把运算符写在后面，比如a+b写成ab+，具体怎么弄看书本p177图8.11三元式：

4、（运算符，运算对象1，运算对象2）对中间运算结果有显示引用，可以用二叉树来表示（书本上说的是树形表示）四元式：（运算符，运算对象1，运算对象2，运算结果）与三元式不同在于，四元式对中间结果引用要通过给定的名字，三元式是编号。四元式之间的联系是通过临时变量实现的。好处：对代码优化和目标代码生成有利5、 PL/0基本保留字，对应的符号，语义等等语句类型：赋值语句，if.then., while.do., read, write, call, 复合语句begin. end， 说明语句： const., var., procedure13个保留字：if, then, while, do, read,

5、write, call, begin, end, const, var, procedure, odd< > 用左右尖括号括起来的语法成分为非终结符：=定义为|或 表示花括号内的语法成分可重复 表示方括号内的语法成分为任选项( )表示圆括号内的成分优先举个栗子！<整数>=+|-<数字><数字><数字>=0|1|2|3|4|5|6|7|8|9基本字（保留字）：BEGIN、 END、 IF、 THEN等运算符： 如+、-、*、/、：=、#、>=、<=等标识符： 用户定义的变量名、常数名、过程名常数： 如10、25、100等整数

6、界符： 如,、. 、; 、( 、)等想具体看的话看第二章，不过有点多，这个不是重点，看看就好6、 布尔表达式1表示T，0表示F举个栗子！1 or （not 0 and 0）or 0=1 or(1 and 0)or 0=1 or 0 or 0=1 or 0=1布尔表达式的翻译，具体看一下p182中间的四元式的例子，p182例8.57、 二义性文法和二义性语言的区别二义性：如果文法G中的某个句子存在不只一棵语法树，则称该句子是二义性的。二义性语言：用红墨水写一个“蓝”字，请问，这个字是红字还是蓝字？（我在书上找不到二义性语言这个概念，百度了一下，觉得老师可能要我们分别的是这种东西吧。）8、 自顶向

7、下方法：递归子程序、预测分析方法。自底向上：LR(0)和SRL(1)自顶向下：递归子程序法：要求文法满足LL（1），对文法中每一个非终结符编写一个递归void expr if (sym in plus, minus ) getsym; term;else term;while (sym in plus, minus) getsym; term;void term factor;while (sym in times,slash) getsym;factor;void factor if (sym=ident) getsym ; Else if (sym=number) getsym Else

8、if (sym=() getsym; expr; if (sym=) getsym; else error; else error; 预测分析方法：预测分析程序先进后出栈预测分析表对每一个终结符或“#”(用a表示)。如果a select(Aa),则把Aa放在MA,a中。所有无定义的MA,a标记为出错。首先把#和文法开始符号入分析栈S；第一个输入符号读进a; FLAG=TRUE；while （FLAG) X=S.pop();if (XÎVt) if (X=a) 把下一个输入符号读进a;else ERROR;else if (X=#) if (X=a) FLAG=FALSE; else

9、ERROR; else if MX,a=XX1X2.XK把XK，X K-1,.,X1一一推进栈 ; elseERROR;自底向上：LR(0)：LR(0)分析表构造的思想和方法是构造其他LR分析表的基础。LR分析需要构造识别活前缀的有穷自动机。项目（item）：在每个产生式的右部适当位置添加一个圆点构成项目。项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分，圆点右部表示待识别的部分。LR（0）项目集规范族的项目类型分为如下四种：看不懂吗？没关系的，后面有大题目要做这个鸟东西，会做大题目之后再回头过来看这些个概念。SLR(1)后面也会做的！SLR(1)：一个LR(0)规范族中含

10、有如下的项目集（状态）I若有：FOLLOW(A) FOLLOW(B) = Ø FOLLOW(A) b = Ø FOLLOW(B) b = Ø状态I面临某输入符号a1) 若a=b，则移进2) 若aÎFOLLOW(A), 则用产生式 A g 进行归约3) 若aÎFOLLOW(B), 则用产生式 B d 进行归约4) 此外，报错若一个文法的LR(0)分析表中所含有的动作冲突都能用上述方法解决，则称这个文法是SLR(1)文法9、 代码优化（不知道他想考什么东西，同学们还是把第11章全部看一遍吧）根据优化所涉及的程序范围分成:局部优化(基本块)循环优化:

11、对循环中的代码进行优化全局优化:大范围(整个模块)的优化基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。DAG：Directed Acyclic Graph无环路有向图基本块的DAG是在结点上带有标记的DAG叶结点：独特的标识符(名字,常数)标记内部结点：运算符号标记各个结点：附加标识符标记控制流程图（流图）：具有唯一首结点的有向图。控制流程图可以表示成三元组：G=(N,E,n0)，其中 N:结点集(基本块集) E:有向边集 n0 :首结点(包含程序第一个语句的基本块)有向边基本块j在程序中的位置紧跟在i后，且i的出口语句不是转移或停语句。i的出口是goto(S)或

12、if goto(S)，而(S)是j的入口语句 。 回边：假设a->b是流图中的一条有向边，如果b DOM a，则称a b是流图中的一条回边。 循环：对于回边n->d，组成的循环是由结点d和结点n以及有通路到达n而该通路不经过d的所有结点组成，并且d是该循环的唯一入口结点。10、 文法推导要求会，读程、写逆波兰式具体知识点看4、中间代码11、 简单短语，句柄书本44面定义3.8以及定义下面到45面3.7之上的那一块具体例子要看懂12、正规式，找出正规式所推出的符号串就是正规集的展开。看书本53-54面的例子13、栈空间分配情况书本29面的图三个联系单元+局部量是运行空间14、 LR项

13、目集冲突一个项目集可能包含多种项目a) 移进和归约项目同时存在。移进-归约冲突b) 归约和归约项目同时存在。归约-归约冲突对于有冲突的状态，向前查看一个符号，以确定采用的动作15、 词法语法分析、自动工具书本66面4.6（不知道要考什么，把这一节看一遍）16、 文法 0型、1型、2型、3型之间的关系 0>1>2>31：上下有关2：上下无关3：正则文法具体看书本p38的定义，概念，理解就好举个栗子：大写非终止符，小写终止符aA.：0型aBab|aA：1型AB|aB|a：2型AaB|a：3型17、 语法制导的翻译书本172-177面看一遍自上而下、自下而上两种方法要看得懂3、 设

14、计题 2*5分（第三章）文法、语言之间的转换：2型上下无关文法与谓词表示语言1、课后题目3.5写一文法，使其语言是正偶数的集合允许0开头E->NT|D T->NT|D N->D|1|3|5|7|9 D->0|2|4|6|8不允许0开头E->NT|DT->FT|GN->D|1|3|5|7|9D->2|4|6|8F->N|0G->D|02、 课后3.14给出生成下属语言的上下无关文法（也就是3型）（1） anbnambm|n,m>=0明显，前面的ab跟后面的ab为一组，每一组可以表示成anbn答案就是（2） 1n0m1m0n|n,m

15、>=0两侧的10为一组，内侧的01为一组不难写出（3）WaWr|W属于0|a*,Wr表示W的逆0|a*表示所有包含0跟a的串然后你就能发现他是关于a的一个对称所以答案就是Sa S a | 0 S 0 | a3.16转换成3型 (1)an|n>=0 解 SaS | (2) anbm|n,m>=1 解 Sa S | a A AbA | b 4、 设计题 3*5分（第四章）正规式正规文法，正规式自动机（DFA）首先看一下p68的几个经典例题解答4.5构造一个DFA，它接受0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边，并写出相应的正规式和正规文法。解：按题意相应的正规表

16、达式是0*(0 | 10)*0* 构造相应的DFA，首先构造NFA为 0 0 03 1 0 X Y 1 02 用子集法确定化II0I1S01X,0,1,3,Y0,1,3,Y21,3,Y0,1,3,Y0,1,3,Y1,3,Y1,3,Y22/212342244333DFA为 01 02 1 1 0 13 4 0可最小化，终态组为1,2,4，非终态组为3，1,2,401,2,4，1,2,413，所以1,2,4为等价状态，可合并。 0 13 1,2,4 04.8给出下述文法所对应的正规式:S0A|1BA1S|1B0S|0解:A和B代入S得:S01S|01|10S|10S01S|10S|01|10S(0

17、1|10)S|(01|10)S(01|10)S,S(01|10)S(01|10)*(01|10)故：=(01|10)*(01|10)或=(01|10)+求DFA解题方法总结：求正规式根据正规式画出NFA画出NFA转化过程表这个表就是在已知点的情况下经过给定的之后能到达的点的集合，然后把得到点的集合在去求。直到所有情况都遍历一遍根据表画出DFA表这个表就是将上表中所有已知的集合设为另一个点，然后得到另一个表画出初步DFA按照上表给出的点以及通过什么能到达另一个点，画出DFA化简化简方法标准写法是p70例题2，然而我并不是这么去做的，我是观察哪些点通过全部相同的可以到达同一个或同一些点来化简，以及

18、哪些点只是内部之间的转换没有与外界交流。看不出的话还是按照70面那个去写吧。求正规式的方法：然后一步一步的代入5、 中间代码的优化（第11章）基本块的优化（DAG）重写这一块内容不难，优化技术主要有1.删除多余运算2.循环不变代码外提3.强度削弱（乘除变成加减）4.变换循环控制条件（减少变量）5.合并已知量与复写传播（尽量直接赋值）6.删除无用赋值六、填空题（4分+10分）第八章 自底向上（归约） 表达式计算，中间代码（逆波兰，3,4元）生成表达式的属性文法（数字、布尔表达式）赋值、条件、循环语句 翻译成 四元式（缺少语句）1.给出表达式的逆波兰表示2、4、6可以看成布尔表达式具体方法，还是一

19、步一步写，按照运算优先度一步一步的化，随便尝试一下，很简单的2. 将 -(a+b)*(c+d)-(a+b+c) 表示成三元式和四元式3、采用语法制导翻译思想，给出表达式（5*4+8）*2的语法树并在各结点注明语义值 产生式 语义规则 0) S （.） 1) 1E 2 .1. E 2. 2) 1 * E 2 .1.× E 2. l 3）E（1 ） E.1. 4) En E.:n.语法树：5、 证明题 第五章 （3*4分）自顶向下的语法分析先说一下这一章的几个定义若终结符开头就是终结符，如果是非终结符开头就展开看哪些终结符开头简单的说就是什么能推出A，他的后面，包括#其次要能够判断这个文

20、法是否符合LL文法左公因子这个比较容易判断，左部相同的右部的最左是否相同比方说Aab|ac的左公因子是a但是有些公因子不是直接能看出来的，比方说Aad|Bc，BaA，也是不符合的消除方法，提取左公因子之后将|变成另一个东西比方说：Aa（b|c）变成AaB，Bb|c左递归A能够推导出A.，就说明左递归消除直接左递归方法：把直接左递归改写成右递归举个栗子！SSa，Sb改成SbS，SaS|e消除间接左递归方法：先通过产生式非终止符置换变成直接左递归，然后消除直接左递归举个栗子！ABa,BAc,Bd改成BBac,Bd然后再改成BdB,BacB|e第三，会改写成LL文法方法就是上面说的，先提取左公因子，

21、在消除左递归第四，证明是LL文法首先，算FIRST集，然后算FOLLOW集，然后再算SELECT集，然后算相同左部SELECT集的交集，非空就不是LL文法，下面给一道例题，这道题能自己做的话考试就没问题了（我也不知道这一步有什么用）6、 综合题（8分+4分+4分）第七章+第八章 LR(0)+SLR(1)+语法制导拓广文法：加一个SS构造项目规范族在每个产生式的右部适当位置添加一个圆点变成新项目比方说：产生式S aAcBe对应有6个项目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aAcB e 5 S aAcBe 在不符合LR(0)的时候，解决冲

22、突方法是向右看一个变成LR(1)我们先不管这个冲突，先说LR(0)分析怎么做我们就拿书本上给的例子来说吧，书本131面G文法给出拓广文法（这里已经做好了）构造项目规范族就是书本131面的1-18那些式子这两步还是很简单的，难的在下面画出识别活前缀的NFA（也就是画NFA）书本132面，图7.7，具体这个图是怎么画出来的（1）观察哪些中的式子是以为结尾的，那就是能归约的，也就是说要画成两个圈。（2）我们来讲这个图是怎么出来的，这里所有数字都代表中的那些式子，第一步画出拓广文法1，然后从这里出发，画出1（E）2（3）接下来我们看左部哪些式子左部是之前有过路径上的值，并且右部以开头的，这里有3和11

23、，然后就在箭头上写上e（表示空，什么都不写我觉得也没事）（4）然后我们先看3，看跟3一起由同一个产生式构成的项目集有哪些，这里有4跟5，就分别在箭头上写上过去的过程，接下来的方法同3出来，箭头上有A的左部课作为6跟9的出发点（5）注意点，7之后也有个A，所以7也要能够通过空到6跟9,11那边也同上想法。其实很简单，就是要注意如果式子多了可能会有漏掉，比如说7到6,7到9这些。画出识别活前缀的有限自动机DFA（就是画DFA）这一步就比较简单了，书本上图7.8中，I0表示，不通过或只通过空可以到的集合，然后看通过什么东西可以到什么，比如说3通过a到4,4通过空到6跟9，所以说4,6,9是一类的，画

24、到I2，其他都是这么画出来的。这个图的意思就是，能通过某个去下一个的是移近，然后不能就是归约，注意不要丢东西就好画出LR(0)分析表书本136面，表7.3首先要画好状态，ACTION，GOTO，ACTION中要包括结束符#，S表示移近，r表示归约（1） 中有一个I就写出几个状态，我们先看第0行，I0通过哪些可以移进到另一个非终止I，比方说通过a到I2，通过b到I3，那分别在a列跟b列下面写S2，S3，然后看通过哪些可以到终止I，这里通过E可以到终止I1，就在E下面写1。（2） 然后我们看第1行，是E，表示这次操作就成功了，就在#下面写acc（表示成功），然后第2345行做法跟第0行一毛一样，然

25、后看6到11，他后面已经没有东西了，里面所有式子都是为结尾了，说明他是只能归约不能移近了（3） 那我们再回到135面最下面的编号看，这些都归约到哪个式子了，就写r几画出输入串的LR(0)分析过程还是书本136面表7.4，（1）先记住要写哪些东西，步骤，状态栈，符号栈，输入串，ACTION,GOTO（2）先写步骤1，状态栈0，符号栈跟输入加起来是#bccd#，这里没有并没有进栈，就按照书上那么写，然后看表上0从哪里可以到b，查表得出是S3，是移进过程，在ACTION上写S3，若ACTION是移进，则不GOTO（3）步骤2，同上，观察是移进还是归约，一直到第5步的时候。发现d能归约了！（4）那就在ACTION上写