编译原理试卷

一、判断对错：（对√；错；每小问2分共24分）<1>算符优先分析法是一种规范归约分析法。（）<2>若文法Gs中不含形如T→…BD…的产生式，T、B、D∈VN，则称Gs为算符文法。（√）<3>若一个语言是有穷集合，则定义该语言的文法一定是递归的。（）<4>若两个正规式所表示的正规集相同，则认为二者是等价的。（√）<5>LR分析法是一种规范归约分析法。（√）<6>一个LR(0)项目集I={B→α.bβ,P→aA.},则说I中含有“移进—归约”冲突。（√）<7>SLR(1)文法是无二义性文法。（√）<8>消除左递归后的文法一定是LL(1)文法。（）<9>对任何编译程序而言，代码优化是必不可少的。（）<10>编译程序与具体的机器无关。（）<11>在自动机的概念中，终态与非终态是可区别的。（√）<12>逆波兰式ab+cd+*所代表的中缀表达式是：(a+b)*(c+d)（√）1.一个语言有文法是不惟一的。（√）2.若一个语言是无穷集合，则定义该语言的文法一定是递归的。（√）3.紧跟在条件转移语句后面的语句是基本块的入口语句。（√）4.算符优先分析法是一种规范归约分析法。（）5.自下而上语法自导翻译的特点：当栈顶形成句柄时，在归约的同时执行其语义动作。（√）6.LR(0)文法、SLR(1)文法都是无二义性文法。（√）7．K、∑分别表示有限状态集和有穷字母表,DFAM的转换函数f是一个从K∑到K的单值映射。（√）8.对任何编译程序而言，代码优化是必不可少的。（）9.直接短语是某规则的右部，它对应简单子树叶结点从左到右排列形成的符号串。（√）10.两个有穷自动机等价是指它们的状态数和有向弧数相等。（）11.一个LR(0)项目集为：I={A→.bβ,D→β.},则说I中含有“移进--归约”冲突。（√）12.若两个正规式所表示的正规集相同，则认为二者是等价的。（√）13.无左递归的文法是LL(1)文法。（）14.逆波兰式abcde/+*+所代表的中缀表达式是：a+b*(c+d/e)（√）15.编译程序结构中，中间代码优化及目标代码生成两个阶段与具体的机器有关。（）16.LALR分析法中，同心集的合并不会产生“移进--归约”冲突。（√）<1>算符优先分析法是一种规范归约分析法。（错）<2>若文法Gs中不含形如T→…BD…的产生式，T、B、D∈VN，则称Gs为算符文法。（对）<3>若一个语言是有穷集合，则定义该语言的文法一定是递归的。（错）<4>若两个正规式所表示的正规集相同，则认为二者是等价的。（对）<5>LR分析法是一种规范归约分析法。（对）<6>一个LR(0)项目集I={B→α.bβ,P→aA.},则说I中含有“移进—归约”冲突。（对）<7>SLR(1)文法是无二义性文法。（对）<8>消除左递归后的文法一定是LL(1)文法。（错）<9>对任何编译程序而言，代码优化是必不可少的。（错）<10>编译程序与具体的机器无关。（错）二、<1>将下图所示的NFA确定化。(状态转换矩阵4分；状态转换图2分)解：<1>状态转换矩阵4分状态转换图2分<2>给出语言L={danb|n≥1}相应的文法。GA：A→dBbGA：A→dBB→aB|aB→aB|ab三、①编译程序的工作过程一般划分为五个基本阶段：B；D、语义分析和中间代码生成、代码优化和目标代码生成。A.出错处理B.词法分析C.表格管理D.语法分析②已知文法GE：E→E+T|TT→T*F|FF→(E)|b那么，该文法终结符集合VT=A；C，GE称2型文法或上下文无关文法。A.{+,(,),*,b}B.{+,(,),*,E}C.{+,*,(,),b}D.{E,T,F}③已知文法GE：E→E+T|TT→T*F|FF→(E)|b那么，该文法的非终结符集VN=B，GE称2型文法或上下文无关文法。A.{+,(,),*,b}B.{E,T,F}C.{+,*,(,),b}D.{E,T,F,*,+}④文法用于描述语言的语法结构，它由如下四个部分组成：A；C；D和文法开始符号。A.文法终结符集B.字母数字串C.文法非终结符集D.文法产生式集⑤一个文法被称为是二义性的，如果A,D。A.文法的某一个句子有两个以上的最右或最左推导。B.文法的预测分析表中有多重入口。C.文法的某个LR(0)项目集中有冲突项目。D.文法的某一个句子有两棵以上不同的语法树。⑥程序设计语言的单词符号一般可分为五种，它们是保留字、A；D及运算符和定界符。A.常数B.表达式C.注解D.标识符⑦设有一个LR(0)项目集I={A→β.bδ，B→β.，D→δ.}，I中存在冲突项目，它们是A；D。A.“移进-归约”冲突B.“移进-接受”冲突C.“移进-待约”冲突D.“归约-归约”冲突⑧一个文法的SLR(1)方法和与其相应的LR(0)方法的状态数A。A.相同B.不相同的C.前者大于后者D.后者大于前者1．编译程序的工作过程一般划分为五个基本阶段：词法分析、BD、中间代码优化、目标代码生成。A.出错处理B.语法分析C.表格管理D.语义分析与中间代码生成2．识别某文法所有LR(0)项目集簇的DFA中，若项目集k中含有项目“A→δ.”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A→δ”归约的语法分析方法是D。A．LALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法3．程序设计语言的单词符号一般可分为五种，它们是常数、CD及运算符和定界符。A.注解B.表达式C.标识符D.保留字4．文法用于描述语言的语法结构，它由如下四个部分组成：ACD和文法开始符号。A.文法终结符集B.字母数字串C.文法非终结符集D.文法产生式集5．一个文法被称为是二义性的，如果AC。A.文法的某一个句子有两个以上的最右或最左推导。B.文法的预测分析表中有多重入口。C.文法的某一个句子有两棵以上不同的语法树。D.文法的某个LR(0)项目集中有冲突项目。6．已知文法GB：B→B+T|TT→T*F|FF→(B)|b那么，该文法终结符集合VT=AB，GE称2型文法或上下文无关文法。A.VT={+,*,(,),b}B.VT={b,(,+,*,)}C.VT={B,T,F}D.VT={B,T,F,+,*,(,b,)}7．在动态存储分配时，可以采用的分配方法有BC。A.分时动态存储分配B.栈式动态存储分配C.堆式动态存储分配D.最佳动态存储分配8．设有一个LR(0)项目集I={A→β.dδ；A→b.Bδ；B→βd.；D→dB.}，I中存在冲突项目，它们是AB。A.“移进-归约”冲突B.“归约-归约”冲突C.“移进-待约”冲突D.“移进-接受”冲突9．在编译程序采用的优化方法中，BCD是在循环语句范围内进行的。A.删除多余运算B.代码外提C.删除归纳变量D.强度消弱10．编译程序生成的目标代码通常有3种形式，它们是ACD。A.能够立即执行的机器语言代码B.中间语言代码C.汇编语言程序D.待装配的机器语言代码①编译程序的工作过程一般划分为五个基本阶段：BD、语义分析和中间代码生成、代码优化和目标代码生成。A.出错处理B.词法分析C.表格管理D.语法分析②已知文法GE：E→E+T|TT→T*F|FF→(E)|b那么，该文法终结符集合VT=AC，GE称2型文法或上下文无关文法。A.{+,(,),*,b}B.{+,(,),*,E}C.{+,*,(,),b}D.{E,T,F}③已知文法GE：E→E+T|TT→T*F|FF→(E)|b那么，该文法的非终结符集VN=B，GE称2型文法或上下文无关文法。A.{+,(,),*,b}B.{E,T,F}C.{+,*,(,),b}D.{E,T,F,*,+}④文法用于描述语言的语法结构，它由如下四个部分组成：ACD和文法开始符号。A.文法终结符集B.字母数字串C.文法非终结符集D.文法产生式集⑤一个文法被称为是二义性的，如果D。A.文法的某一个句子有两个以上的最右或最左推导。B.文法的预测分析表中有多重入口。C.文法的某个LR(0)项目集中有冲突项目。D.文法的某一个句子有两棵以上不同的语法树。⑥程序设计语言的单词符号一般可分为五种，它们是保留字、AD及运算符和定界符。A.常数B.表达式C.注解D.标识符⑦设有一个LR(0)项目集I={A→β.bδ，B→β.，D→δ.}，I中存在冲突项目，它们是AD。A.“移进-归约”冲突B.“移进-接受”冲突C.“移进-待约”冲突D.“归约-归约”冲突⑧一个文法的SLR(1)方法和与其相应的LR(0)方法的状态数A。A.相同B.不相同的C.前者大于后者D.后者大于前者四、计算题（共10分；画出语法树4分；其余按要求分别得：1分+1分+2分+2分）对于如下文法GB：B→B+D|DD→D*F|F给出句型D+D*d+d的最左素短语、句柄、F→(B)|d所有直接短语、短语。解：已知NFA如下图所示。(8分=6分+2分)<1>确定化。(状态转换矩阵4分；状态转换图2分)<2>写出与其等价的右线性文法。解：<1>计算出DFA的状态转换矩阵4分；画出相应的状态转换图2分<2>与其等价的右线性文法为：GA：A→dA|bB|bA→dA|bA|bB|BA代表结点1B→bB|dA|bB→bC|bB代表结点2按确定化后的DFA构造的结果；按NFA构造的结果对于文法GE：（共8分：语法树2分；其余按要求分别得1分、1分、2分、2分）E→E+B|BB→B*F|F给出句型B+B*b+b的最左素短语、句柄、F→(E)|b直接短语和所有短语。解：五、1给出以下表达式的三地址指令（或四元式序列）：(8分)d+b*d+b/m*(m-b*d+2)解：四元式序列为(三地址指令略)（*,b,d,T1）（+,d,T1,T2）（/,b,m,T3）（*,b,d,T4）(-,m,T4,T5)(+,T5,2,T6)(*,T3,T6,T7)(+,T2,T7,T8)2①给出以下表达式的三地址指令（即四元式序列）：(8分=3分+3分+2分)d+b*d+d*(d+b*d)②写出四种以上常用的代码优化技术？解：①四元式序列为：1（*,b,d,T1）2（+,d,T1,T2）3（*,b,d,T3）4（+,d,T3,T4）5（*,d,T4,T5）6（+,T2,T5,T6）上述中间代码可以采用的优化措施有：合并（或称删除）公共子表达式即合并公共四元式1和3合并4中T3改为T12和4合并5中T4改为T2删除四元式3和41（*,b,d,T1）2（+,d,T1,T2）3删除4删除5（*,d,T2,T5）6（+,T2,T5,T6）②常用的代码优化技术有：循环上的优化包括：代码外提；强度削弱；删除归纳变量等基本块上的优化包括：合并公共子表达式；合并常数等六、综合题（每小题4分，共32分。若缺少必要的计算或分析步骤，扣适当的分数）已知文法GS：S→dDb提示：.ε=ε.=.且|ε|=0D→aD|ε①求每个非终结符的First集、Follow集。求每条规则的Select集，判定是LL(1)文法。②构造GS的递归下降分析程序。③构造GS的预测分析表。④给出字符串daabb的LL(1)分析过程。⑤构造识别GS拓广文法的所有规范句型活前缀的DFA。⑥构造SLR(1)分析表。⑦GS是LR(0)文法吗？GS是SLR(1)文法吗？为什么？⑧给出字符串daab的SLR(1)分析过程。解：①每个非终结符的First集、Follow集:每条产生式的Select集，判断该文法是否为LL(1)文法。Select(S→dDb)={d}Select(D→aD)={a}<1>Select(D→ε)={b}<2>因为<1>式∩<2>式=Φ，因此，GS是LL(1)文法。②递归下降分析器：Read()函数读一个单词到全局变量SYM中ERROR()出错处理；SKIP空操作Main()函数；略S(){ifsym=’d’then{read();D();Ifsym=’b’thenread();}ElseError()}D(){ifsym=’a’then{read();D()}Elseifsym=’b’thenskip;ElseError();}③构造GS的预测分析表如下：④分析栈输入流动作#Sdaabb#dDb#bDddaabb#匹配#bDaabb#aD#bDaaabb#匹配#bDabb#aD#bDaabb#匹配#bDbb#D→ε#bbb#匹配#b#出错⑤识别GS拓广文法的所有规范句型活前缀的DFA构造如下：说明：产生式编号可以不从1开始，但是与归约符r的下标必须一致；SLR(1)表中的行可以任意排列，但是必须与项目集编号一致。⑥SLR(1)分析表构造如下：⑦显然项目集I2、I4中有“移进—归约”冲，GS不是LR(0)文法。因为SLR(1)分析表中无多重入口，所以GS是SLR(1)文法。⑧字符串daab的SLR(1)分析过程如下：状态栈符号栈输入流动作0#daab#S202#daab#S4024#daab#S40244#daab#r402446#daaDb#r30246#daDb#r3023#dDb#S50235#dDb#r201#S#OK已知文法GD：D→aD|dAb（共40分，每小题5分）A→dA|ε提示：.ε=ε.=.且|ε|=0①求每个非终结符的First集、Follow集。求每条规则的Select集，判定是LL(1)文法。②构造GD的递归下降分析程序。③构造GD的预测分析表。④给出字符串addb的LL(1)分析过程⑤构造识别GD拓广文法的所有规范句型活前缀的自动机。⑥构造SLR(1)分析表。⑦GD是LR(0)文法吗？GD是SLR(1)文法吗？GD是LL(1)文法吗？为什么？⑧给出字符串addbb的SLR(1)分析过程。解：①每个非终结符的First集、Follow集:每条产生式的Select集，判断该文法是否为LL(1)文法。Select(D→dDb)={d}<1>Select(D→aD)={a}<2>Select(A→dA)={d}<3>Select(A→ε)={b}<4>因为:<1>式∩<2>式=Φ;<3>式∩<4>式=Φ因此，GD是LL(1)文法。②递归下降分析程序构造如下：(1分+2分+2分)Main()/*Read函数表示把输入流首符读入变量SYM中*/{Read();D();/*SYM存放输入流首符的全局变量*/ifSYM=’#’then/*Write为输出函数；Skip为空操作*/write(“分析成功!”)/*Error出错处理程序*/elsewrite(“失败…”)}/*可以使用其它符合标识符定义规则的名称*/D(){ifSYM=’a’then{Read;D()}elseifSYM=’d’then{Read();A();ifSYM=’b’thenRead()ElseError();}ElseError();}A(){ifSYM=’d’then{Read();A();}ElseifSYM=’b’thenSkipElseError();}③构造GD的预测分析表如下：④字符串addb的LL(1)分析过程分析栈输入流动作分析栈输入流动作#Daddb#替换D→aD#Daaddb#匹配[a,a]#Dddb#替换D→dA