编译原理复习

第一章引论编译过程的阶段由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段编译程序的概念编译程序的结构例：（B）不是编译程序的组成部分。A.词法分析器； B.设备管理程序C.语法分析程序； D.代码生成程序遍的概念对源程序（或其中间形式）从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。编译程序和解释程序的区别例：解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（D）。A.单用户和多用户的差别 B.对用户程序的差错能力C.机器执行效率 D.是否生成目标代码第三章文法和语言文法的概念字母表、符号串和集合的概念及运算例：（ab|b）*c和下面的那些串匹配？（ACD）A.ababbc；B.abab； C.c； D.babc； E.aaabc例：ab*c*（a|b）c和后面的那些串匹配？（ BC）A.acbbcB.abbcacC.abcD.acc例：（a|b）a+（ba）*和后面的那些串匹配？ （ADE）A.ba B.bba C.ababaD.aaE.baa文法的定义（四元组表示）文法G定义为四元组（Vn,Vt，P，S）Vn:非终结符集Vt:终结符集P:产生式（规则）集合S:开始符号（或识别符号）例：给定文法，A::=bA|cc,下面哪些符号串可由其推导出（①②⑤）。①cc ②b*cc ③b*cbcc④bccbcc⑤bbbcc什么是推导例：已知文法G：E->E+T|E-T|TT->T*F|T/F|FF->（E）|i试给岀下述表达式的推导：i*i+i推导过程：E->E+T->T+T->T*F+T->F*F+T->i*F+T->i*i+T->i*i+F->i*i+i句型、句子的概念例：假设G一个文法，S是文法的开始符号，如果S=>*x,则称x是句型。例：对于文法G,仅含终结符号的句型称为句子。语言的形式定义例：设r=（a|b|c）（x|y|z），则L（r）中元素为9个。例：文法G产生式为S^AB,A^aAb|,BtcBd|cd，贝U B€L（G>A.ababcd；B.ccdd；C.ab；D.aabb等价文法例：如果两个文法描述了同一个语言，则这两个文法是 等价文法 。文法的类型0型：左边至少有一个非终结符1型：右边长度>=左边长度2型：左边有且仅有一个非终结符3型：形如：A->aB,A>a各类型文法都是逐级包含关系，0冒文建例：文法S^abC|c,bCTd是几型文法？0型例：文法S^abC,bCTad是几型文法？1型例：文法G[A]：at,iaB,B^Ab,B^a是几型文法？2型例：文法S^a|bC,CTd是几型文法？3

型最左（右）推导规范推导：最右推导被称为规范推导规范句型：由规范推导所得的句型称为规范句型规范归约：左归约为规范归约二义性例：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 二义的。例：已知文法G1:P-＞PaP|PbP|cP|Pe|f，G1是（A）。A二义文法；B无二义的例：证明下述文法G[＜表达式＞]是二义的。＜表达式＞ta|（＜表达式＞）|＜表达式＞＜运算符＞＜表达式＞＜运算符八+|-|*|/答：可为句子a+a*a构造两个不同的最右推导：最右推导1〈表达式〉=•〈表达式〉〈运算符〉〈表达式〉=■〈表达式〉〈运算符〉a=■〈表达式〉*a=■〈表达式〉〈运算符〉〈表达式〉*a=,〈表达式〉〈运算符〉a*a=■〈表达式〉+a*a=■a+a*a最右推导2〈表达式〉

例：已知文法G[S]StaB|bAA—a|aS|bAABtaBB|bS|b句型aabbAb的句柄是（D）A.aB.abC.bD.bA第四章词法分析词法输出的token表示法词法记号、模式、词法单元的概念词法输出的token表示：二元式表示（单词种别，单词自身的值）例：扫描器的任务是从 源程序中识别岀一个个 单词。正规式的概念及其代数性质词法分析中的单词符号的描述工具正规式代表的集合例：请描述下面正规式定义的串， 字母表S={0,1}1（0|1）*0答：必须以1开头0结尾的串例：为下边所描述的串写正规式， 字母表是{0,1}。以01结尾的所有串答：（0|1）*01正规文法和正规式相互转换正规文法到正规式的转换规则：=■〈表达式〉〈运算符〉〈表达式〉=■〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉=〈表达式〉〈运算符〉〈表达式〉〈运算符〉a二•〈表达式〉〈运算符〉〈表达式〉*a=■〈表达式〉〈运算符〉a*a=■〈表达式〉+a*a正规文法正规式AxB,By转换成:A=xyAxAy转换成:A=xyAx,Ay转换成:A=xy='a+a*a短语、句柄、直接短语例：令文法G[E]为：E-＞E+T|E-TT-＞T*F|T/F|FF-＞（E）|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。E^E+T^E+r-R.E+T^FrT*F.'玄接faii鼻VF.勺炳：T-F.

例：给岀下述文法所对应的正规式：S^0A|1BAt1S|1B^0S|0答：S->0A|1B->01S|01|10S|10->(01|10)S|(01|10)->(01|10)(01|10)* 即：r=(01|10)(01|10)*NFA和DFANFA和DFA的组成例：指岀哪些串是自动机可接受的(②④)xy②xyxxy ③yyyx ④xyyxyxyxxy用子集法将NFA确定化NFA和DFA的相互转换例：将下图确定化：答：用子集法将NFA确定化:01XAAAABABACABACAABYABYACAB01SVQQUVQVZQUQUVQUZVZZZVZQUZVZ(:JUZZZZ除X，A夕卜，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y(NFA的终态)，所以D为终态。01XAAABBCBCADDi CB重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。01SABACBBDECFFDFECEFFFDFA的状态图:语法分析常用的方法是__B①自顶向下②自底向上③自左向右④自右向左A.①②③④ B.①② C.③④D.①②③会求FIRSTFOLLOW集计算FIRST(X)若X€Vt,则FIRST(X尹｛X｝若X€Vn,且有产生式Xta…,a€Vt,贝Ua€FIRST(X)若X€Vn,Xt,则eFIRST(X)(d)若XeVn,Yi,Y2,…，丫eVn,且有产正规式和NFA的相互转换例：构造正规式1(0|1)*101相应的DFA答：先构造NFA:生式XtY1Y2-Yn；当YiY2…Yi-1都二时,(其中 1<i<n),则FIRST(Y)、FIRST(Y)、…、FIRST(Y1)的所有非｛｝元素和FIRST(Y都包含在FIRST(X中(e)当(d)中所有Yi— ,(i=1,2,…n),贝UFIRST(X)=FIRST(Y!)FIRST(Y2)J…UFIRST(Yn®{}计算FOLLOW(A)(a)设S为文法中开始符号，把{#}加入尸0110可心中(这里“釣句子括号)。(b)若2B是一个产生式，则把FIRST()的非空元素加入FOLLOW(B中。-*■如果匚则把FOLLOW(A也加入FOLLOW(B中。计算SELECT(->):A—,A€Vn, €V*,—则SELECT件)=FIRST()若，贝若，贝USELECT(—)=(FIRST()-{})为.产生式S—PS'SELECT集FOLLOW集{q}{#}S'—aPS{a}{#}—fS'{f}—{#}P—qP'{q}{a,f,#}P'—bP{b}{a,f,#}—{a,f,#}UFOLLOW(A)例：文法：IiCtS|iCtSeS|a,C^b中first(S)为(A),follow(S)为(B)。A.{i,a}; B.{e,#};C.{i,e,#}； D.{e,b}LL(1)文法的条件例：LL(1)文法的条件是 CoA.对形如U::=x1|x2|…的规则,要求First(xi)nFirst(xj)=工j);b.对形如u：：=xi|x2| …|xn规则,若xi=>*,贝U要求First(xj)nLL(1)分析表为abfq#SPS'S'aPS'fS'PqP'P'bP第六章自底向上优先分析算符文法的定义如果不含空产生式的上下文无关文法 G中没有形如A…BC・的产生式，其中B,C€Vn,则称G为算符文法(0G)。D.都不是构造LL(1)分析表例：已给文法G[S]:语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语最左素短语的概念设有文法G[S],其句型的素短语是一个短Follow(U)=,(iFollow(U)=,(i工j)C.a和bS—SaP|Sf|PP—qbP|q将G[S]改造成LL⑴文法，并给出LL(1)例：给定文法G如下：E—E+T|T;T—T*F|F;F—PfF|P;P—(E)|i句型P*P+i的最左素短语为( A)o分析表'答：改造后的文法:A.P*P;B.P;S—PS'S'—aPS'|fS'|P—qP'P'—bP|各候选式的FIRST集，各非终结符的 FOLLOW集C.P+; D.P*P+i第七章LR分析LR(K的含义L 从左至右扫描输入符号串R 构造一个最右推导的逆过程K 向右顺序查看输入串的K个符号LR分析器的逻辑结构及活前缀等概念LR分析对文法的要求构造LR(O分析表、SLR(1分析表用SLR分析法分析非二义性的文法和二义性的文法。例：已知文法A—aAd|aAb|判断该文法是否是SLR(1文法，若是构造相应分析表，并对输入串ab#给出分析过程。答：文法：A—aAd|aAb|e拓广文法为G,增加产生式S'—A若产生式排序为：0S'—AA—aAdA—aAbA—e由产生式知：First(S')={e,a}First(A)={e,a}Follow(S')={#}Follow(A)={d,b,#}G的LR(0)项目集族及识别活前缀的 DFA如下图所示：(State)abd#AS2r31r3r330acc1S2r32r3r33S44S55r1r1r1r2r2r2对输入串ab#的分析过程状态栈(statestack)文法符号栈剩余输入串(inputleft)动作(action)0#ab#移进归约:A02#ab#—