搜索
武汉大学计算机学院2018-2019学年第一学期2016级《编译原理》期末考试试卷（A）学号：姓名：专业：成绩：(注：1考试时间为120分钟；2所有的解答必须写在答题纸上，并注明题号。)一、设NFA𝑁的状态转换图如下所示：(25分,每小题5分)0start1234510𝜀1𝜀00𝜀𝜀𝜀(1)试写出NFA𝑁接受字符串“100101’’的过程；(2)设用子集构造法求出的与NFA𝑁等价的DFA𝑀有4个状态𝐴，𝐵，𝐶和𝐷，其中𝐴𝜀-closurept0uq，Dtransp𝐴;0q𝐵，Dtransp𝐵;1q𝐶.试求与状态𝐴，𝐵，𝐶和𝐷所对应的NFA𝑁的状态集，并画出DFA𝑀的状态转换图；(3)求DFA𝑀的最小状态自动机；(4)试用自然语言描述NFA𝑁所接受的语言；(5)求正规表达式𝑟，使得𝐿p𝑟q𝐿p𝑁q.二、嵌套链表文法𝐺p𝑆q定义如下：𝑆Ñr𝐿s𝐿Ñ𝐿;𝐿|𝑆|𝑎其中:‘𝑎’，‘r’，‘s’和‘;’为终结符，𝑆是文法开始符号.(25分,每小题5分)(1)试写出语句“r𝑎;r𝑎ss”的一个最左推导；(2)试消除文法𝐺p𝑆q中的左递归；(3)试对消除左递归后的文法所有非终结符求First集和Follow集；(4)试对消除左递归后的文法构造LL(1)分析表，从而说明消除左递归后的文法不是LL(1)文法；(5)试利用你的分析表写出语句“r𝑎;𝑎s”的一个正确的分析过程.1三、设文法𝐺p𝑆q如题二所示：(10分,5+5)(1)试对语句“r𝑎;𝑎;𝑎s”画出两颗不同的语法树，从而说明该文法为二义文法；(2)试设计一个与文法𝐺p𝑆q等价的无二义的文法，使得𝐿;𝐿为右结合.四、设题二文法𝐺p𝑆q的拓广文法𝐺p𝑆1q如下所示：(20分,5+5+5+5)𝑆1Ñ𝑆(0)𝑆Ñr𝐿s(1)𝐿Ñ𝐿;𝐿(2)|𝑆(3)|𝑎(4)文法𝐺p𝑆1q的识别活前缀LR(0)项目自动机如下图所示(注意每个状态仅列出了核心项目，状态𝐼6除外)：𝐼0:𝑆1Ñ𝑆start𝐼1:𝑆1Ñ𝑆𝐼3:𝑆Ñr𝐿s𝐿Ñ𝐿;𝐿𝐼2:𝑆Ñr𝐿s𝐼4:𝐿Ñ𝑆𝐼5:𝐿Ñ𝑎𝐼8:𝐿Ñ𝐿;𝐿𝐿Ñ𝐿;𝐿𝐼6:𝐼7:𝑆Ñr𝐿sr𝑆r𝐿𝑆𝑎;s𝐿r𝑆𝑎;(1)试求状态𝐼6所对应的LR(0)项目集；(2)正则表达式rpr𝐿;q𝑎s所生成的文法符号串是活前缀吗？为什么;(3)试构造该文法的SLR分析表，并对分析表中的移进/归约和归约/归约冲突选择正确的移进或归约动作，使得文法𝐺p𝑆q的所有语句能被正确地分析且运算的结合次序与题三所规定的一致；(4)试利用你的分析表写出语句“r𝑎;𝑎s”的分析过程.2五、设二叉树的线性表示文法𝐺p𝑇q定义如下：(10分,5+5)𝑇ÑΛp𝑇;𝑇q|𝑎|K其中:‘𝑎’，‘Λ’，‘K’，‘p’，‘q’和‘;’为终结符，𝑇是文法开始符号.现需将题二文法𝐺p𝑆q按题三的结合次序所生成的嵌套链表转换成二叉树的线性表示.如文法𝐺p𝑆q语句文法𝐺p𝑇q语句[a]Λ(a,K)[a;b]Λ(a,Λ(b,K))[[a];b]Λ(Λ(a,K),Λ(b,K))为此设计综合属性𝑆:tree和𝐿:tree,其取值为𝑆或𝐿所表示的语法成分所对应的二叉树线性表示；为了判断𝐿1;𝐿2合成𝐿时，𝐿2是否为链尾，特设计综合属性𝐿:is_list，其取值为True或False.𝐿:is_listTrue当且仅当𝐿是由𝐿1;𝐿2合成；𝑎:lexval为终结符𝑎所对应的词素(词形).(1)试设计将文法𝐺p𝑆q语句翻译为文法𝐺p𝑇q语句的SDD;(2)试求[[[a]];b;[c]]的二叉树线性表示.六、设有如下Pascal程序片段：(5分)whileabornot(cd)andefdobeginx:=x+1;ifnot(gh)andijthenbreak;elsex:=y+2;end;其对应的三地址码如下所示L1:[](ab)gotoL__|[](ij)gotoL__[](cd)gotoL__|L0:t1:=y+2[](ef)gotoL__|x:=t1L2:t0:=x+1|gotoL1x:=t0|L3:[](gh)gotoL__|试为其中空白“__’’填上正确的标号编号，并为空白“[]”填上if或ifnot.第七题见下页！3七、设有如下C语言程序：(5分)#includestdio.hvoidfoo(char*p[2]){staticchar*s[2]={happy,2019!};p=s;}intmain(){char*p[2];foo(p);printf(%s%s\n,p[0],p[1]);return0;}该程序编译正确，但运行时输出乱码，并没有输出期望的“happy2019!”.试分析原因.4