编译原理复习(有答案)

第一章引论1.编译过程的阶段由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段2.编译程序的概念3.编译程序的结构例：（B）不是编译程序的组成部分。A.词法分析器；B.设备管理程序C.语法分析程序；D.代码生成程序4.遍的概念对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。5.编译程序与解释程序的区别例：解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（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.baB.bbaC.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|，B→cBd|cd，则B∈L(G)。A.ababcd；B.ccdd；C.ab；D.aabb等价文法例：如果两个文法描述了同一个语言，则这两个文法是等价文法。文法的类型0型：左边至少有一个非终结符1型：右边长度=左边长度2型：左边有且仅有一个非终结符3型：形如：A-aB,A-a各类型文法都是逐级包含关系，例：文法S→abC|c，bC→d是几型文法？0型例：文法S→abC，bC→ad是几型文法？1型例：文法G[A]：A→，A→aB，B→Ab，B→a是几型文法？2型例：文法S→a|bC，C→d是几型文法？3型最左（右）推导规范推导：最右推导被称为规范推导规范句型：由规范推导所得的句型称为规范句型规范归约:左归约为规范归约二义性例：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。例：已知文法G1：P-PaP|PbP|cP|Pe|f，G1是（A）。A二义文法；B无二义的例：证明下述文法G[表达式]是二义的。表达式→a|(表达式)|表达式运算符表达式运算符→+|-|*|/答：可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉a〈表达式〉*a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a短语、句柄、直接短语例：令文法G[E]为:E-E+T|E-TT-T*F|T/F|FF-(E)|i证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。例：已知文法G[S]S→aB|bAA→a|aS|bAAB→aBB|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xB,By转换成：A=xyAxAy转换成：A=xyAx,Ay转换成：A=xy例：给出下述文法所对应的正规式：S→0A|1BA→1S|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和DFANFA和DFA的组成例：指出哪些串是自动机可接受的（②④）xy②xyxxy③yyyx④xyyxyxyxxyNFA和DFA的相互转换例：将下图确定化：答：用子集法将NFA确定化：.01SVQQUVQVZQUQUVQUZVZZZVZ.QUZVZQUZZZZ重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。.01SABACBBDECFFDF.ECEFFFDFA的状态图：正规式与NFA的相互转换例：构造正规式1(0|1)*101相应的DFA答：先构造NFA：用子集法将NFA确定化.01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。.01X.AAABBCBCADDCBDFA的状态图：:第五章自顶向下语法分析方法语法分析常用的方法是__B___。①自顶向下②自底向上③自左向右④自右向左A.①②③④B.①②C.③④D.①②③会求FIRST、FOLLOW集计算FIRST(X)：(a)若X∈VT,则FIRST(X)＝{X}(b)若X∈VN,且有产生式X→a…,a∈VT,则a∈FIRST(X)(c)若X∈VN,X→,则∈FIRST(X)(d)若X∈VN,Y1,Y2,…,Yi∈VN,且有产生式X→Y1Y2…Yn;当Y1Y2…Yi-1都时,(其中1≤i≤n),则FIRST(Y1)、FIRST(Y2)、…、FIRST(Yi-1)的所有非{}元素和FIRST(Yi)都包含在FIRST(X)中(e)当(d)中所有Yi,(i=1,2,…n),则FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{}计算FOLLOW(A)：(a)设S为文法中开始符号，把{#}加入FOLLOW(S)中(这里“#”为句子括号)。(b)若A→B是一个产生式，则把FIRST()的非空元素加入FOLLOW(B)中。如果则把FOLLOW(A)也加入FOLLOW(B)中。计算SELECT(A-)：A→,A∈VN,∈V*,若,则SELECT(A→)=FIRST()若，则SELECT(A→)=(FIRST()-{})∪FOLLOW(A)例：文法：S→iCtS|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)文法的条件是___C___。A.对形如U::=x1|x2|…|xn的规则，要求First(xi)∩First(xj)=,(i≠j);B.对形如U::=x1|x2|…|xn的规则，若xi=*,则要求First(xj)∩Follow(U)=,(i≠j)C.a和bD.都不是构造LL(1)分析表例：已给文法G[S]：S→SaP|Sf|PP→qbP|q将G[S]改造成LL(1)文法，并给出LL(1)分析表。答：改造后的文法：S→PS'S'→aPS'|fS'|P→qP'P'→bP|各候选式的FIRST集，各非终结符的FOLLOW集为.产生式SELECT集FOLLOW集S→PS'{q}{#}S'→aPS'{a}{#}→fS'{f}→{#}P→qP'{q}{a,f,#}P'→bP{b}{a,f,#}→{a,f,#}LL(1)分析表为abfq#SPS'S'aPS'fS'PqP'P'bP第六章自底向上优先分析算符文法的定义如果不含空产生式的上下文无关文法G中没有形如A…BC…的产生式，其中B,C∈VN，则称G为算符文法（OG）。最左素短语的概念设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语例：给定文法G如下：E→E+T|T；T→T*F|F；F→P↑F|P；P→（E）|i句型P*P+i的最左素短语为（A）。A.P*P；B.P；C.P+i；D.P*P+i第七章LR分析LR(K)的含义L从左至右扫描输入符号串R构造一个最右推导的逆过程K向右顺序查看输入串的K个符号LR分析器的逻辑结构及活前缀等概念LR分析对文法的要求构造LR(0)分析表、SLR(1)分析表用SLR分析法分析非二义性的文法和二义性的文法。例：已知文法A→aAd|aAb|判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。答：文法：A→aAd|aAb|ε拓广文法为G′，增加产生式S′→A若产生式排序为：0S'→A1A→aAd2A→aAb3A→ε由产生式知：First(S')={ε,a}First(A)={ε,a}Follow(S')={#}Follow(A)={d,b,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：在I0中：A→.aAd和A→.aAb为移进项目，A→.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I0、I2中：Follow(A)∩{a}={d，b，#}∩{a}=所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：状态（State）ActionGotoadb#A012345S2r3r3r3accS2r3r3r3S4S5r1r1r1r2r2r21.3对输入串ab#的分析过程状态栈（statestack）文法符号栈剩余输入串（inputleft）动作（action）002023023501##a#aA#aAb#Aab#b#b###移进归约:A→ε移进归约:A→aAbacc分析成功，说明输入串ab是文法的句子