《广工编译原理试题.doc》由会员分享，可在线阅读，更多相关《广工编译原理试题.doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、如有侵权，请联系网站删除，仅供学习与交流广工编译原理试题【精品文档】第 8 页编译原理试题计算机学院_级 班 学号 姓名 题号一二三四五六七八九十总分满分 得分一 选择题1 有限状态自动机能识别：A.上下文无关语言 B.上下文有关语言 C.正规语言 D.0型文法定义的语言2 已知文法G是无二义的，则对G的任意句型：A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能相同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但他们对应的语法树相同3 _不是DFA的成分 A.有穷字母表B.多个初始状态的集合C.多个终态的集合D.转换函数4 有文法G(S,a,S:
2、=SaS,S:=,S)，该文法是_A.LL(1)文法 B.二义性文法C.算符优先文法 D.正规文法5 有一语法制导翻译如下所示: S-bAb print “1” A-(B print “2” A-a print “3” B-Aa) print “4” 若输入序列为b(aa)a)a)b,则采用自下而上的分析方法,则输出为: A.32224441 B.34242421 C.12424243 D.34442212二 判断题1、一个LL( l)文法一定是无二义的。 2、逆波兰法表示的表达式亦称前缀式。- 后缀式3、算符优先关系表不一定存在对应的优先函数。4、同心集的合并有可能产生“移进/归约”冲突。只
3、能是归约/归约5、若主程序为0层, 过程p层次为k，则p的DISPLAY表中就有k+1个元素。三 填空题1、词法分析的任务是从_源程序_中识别出一个个_ 单词符号_。2、在LR(0)分析法中，若a,V*且a则称“S a.A”为待约项目，称“S a.a”为移进 项目。3、规范规约每次规约的是句型的_句柄_。算符优先分析法每次规约的是当前句型的_最左素短语_。四 写一个文法，使其语言是奇数集，且每个奇数不以0开头。五 已知文法G（S）： Sa|(T) TT，S|S（1）给出句子（a，（a，a）的最左推导并画出语法树；（2）给出句型（T，s）,a ）的短语、直接短语、句柄。六 把语句 if x0 y
4、0 then z：xy else Begin x：x2 y：y3 End；翻译成四元式序列。七 设文法G（S）： SSaF|aF|aF F*aF|*a（1）消除左递归和左因子；（2）构造相应的FIRST和Follow集合；（3）构造预测分析表。 八 为下面的文法构造它的LR(1)项目集规范族，并判断它是否为LR(1)文法？若是，请构造它的分析表。S EE E + T | TT ( E ) | a九 下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。S S a b | b RR S | a十 文法S ( L ) | a L L, S | S(a) 给出句子(a, (a
5、, a), (a, a)的一个最右推导；(b) 按照(a)的最右推导，给出移进归约分析器的工作步骤。答案一 选择题c,a,b,b,b二 判断题三 填空题源程序 单词符号待约项目 移进项目句柄 最左素短语四.解：文法G（S）： SAB|B|A0 AAD|C B2|4|6|8 C1|3|5|7|9|B D0|C五 （2）短语：（2分） （T，S），a） （T，S），a （T，S） T，S a 直接短语：（1分）T，S a 句柄：（1分） T，S六 解：（1）（j0，x，0，3） （2）（j，8） （3）（j，y，0，5） （4）（j，8） （5）（，x，y，T1） （6）（：，T1，z） （7）（
6、j，12） （8）（，x，2，T2） （9）（：，T2，x） （10）（，y，3，T3） （11）（：，T3，y） （12）七. 解： （1）（消除左递归，提公因左因子） SaFS|aFS SaFS| F*aF FF| （2） FIRST（S）a，十 FOLLOW（S） FIRST（50）， FOLLOW（S） FIRST（F）* FOLLoW（F）（， FIRST（F）*， FOLLOW（， （3） 八 解：文法的拓广文法G为：(0) S S(1) S E(2) E E + T(3) E T(4) T ( E )(5) T a该文法的LR(1)项目集规范族为：I0 = SS, $, SE,
7、$, EE+T, $|+, ET, $|+,T(E), $|+, Ta, $|+I1 = SS, $I2 = SE, $, EE+T, $|+I3 = ET, $|+I4 = T(E), $|+, EE+T, )|+, ET, )|+, T(E), )|+,Ta, )|+I5 = Ta, $|+I6 = EE+T, $|+, T(E), $|+, Ta, $|+I7 = T(E), $|+, EE+T, )|+I8 = ET, )|+I9 = T(E), )|+, EE+T, )|+, ET, )|+, T(E), )|+, Ta, )|+I10 = Ta, )|+I11 = EE+T, $|
8、+I12 = T(E), $|+I13 = EE+T, )|+, T(E), )|+, Ta, )|+I14 = T(E), )|+, EE+T, )|+I15 = EE+T, )|+I16 = T(E), )|+识别该文法所有活前缀的DFA如下图所示：不存在冲突入口，该文法是LR(1)文法。构造LR(1)分析表如下：STATEactiongotoa+()$SET0S5S41231acc2S6r13r3r34S10S9785r5r56S5S4117S13S128r3r39S10S914810r5r511r2r212r4r413S10S91514S13S1615r2r216r4r4构造LALR文
9、法如下：首先合并同心的项目集，I0 = SS, $, SE, $, EE+T, $|+, ET, $|+,T(E), $|+, Ta, $|+I1 = SS, $I2 = SE, $, EE+T, $|+I3,8 = ET, $|+|)I4,9 = T(E), $|+|), EE+T, )|+, ET, )|+, T(E), )|+,Ta, )|+I5,10 = Ta, $|+|)I6,13 = EE+T, $|+|), T(E), $|+|), Ta, $|+|)I7,14 = T(E), $|+|), EE+T, )|+I11,15 = EE+T, $|+|)I12,16 = T(E) ,
10、 $|+|)DFA如下图所示：构造LALR分析表如下：STATAEactiongotoA+()$SET0S5,10S4,9123,81acc2S6,13r13,8r3r3r34,9S5,10S4,97,143,85,10r5r5r56,13S5,10S4,911,157,14S6,13S12,1611,15r2r2r212,16r4r4r4九. 该文法的拓广文法G为： (0) S S(1) S Sab (2) S bR(3) R S (4) R a其LR(0)项目集规范族如下: I0 : S SI3 : S Sab S SabI4 : S bR S bRI5 : R SS Sab I1 : S
11、 SI6 : R a S Sab I2 : S bRI7 : S Sab R S R a S Sab S bR文法G的识别活前缀的DFA如下所示：FOLLOW(S) = FOLLOW = a, $构造的SLR分析表如下：状态 actiongotoab$SR0S211S3acc2S6S2543S74r2r25r3/S3r36r4r47r1r1观察左表，对状态5，可归纳又可移进，即存在为重定义的入口。所以，该文法不是SLR(1)文法。十. (a) S ( L ) (L, S) (L, (L) (L, (L, S) (L, (L, (L) (L, (L, (L, S) (L, (L, (L, a)
12、(L, (L, (S, a) (L, (L, (a, a) (L, (S, (a, a) (L, (L), (a, a) (L, (L, S), (a, a) (L, (L, a), (a, a) (L, (S, a), (a, a) (L, (a, a), (a, a) (S, (a, a), (a, a) (a, (a, a), (a, a)(注：下划线部分为句柄) (b) 步骤栈输 入动 作1$(a, (a, a), (a, a)$移进2$(a, (a, a), (a, a)$移进3$(a, (a, a), (a, a)$归约，Sa4$(S, (a, a), (a, a)$归约，LS5$
13、(L, (a, a), (a, a)$移进6$(L,(a, a), (a, a)$移进7$(L, (a, a), (a, a)$移进8$(L, (a, a), (a, a)$移进9$(L, (a, a), (a, a)$归约，Sa10$(L, (S, a), (a, a)$归约，LS11$(L, (L, a), (a, a)$移进12$(L, (L,a), (a, a)$移进13$(L, (L, a), (a, a)$归约，Sa14$(L, (L, S), (a, a)$归约，LL, S15$(L, (L), (a, a)$移进16$(L, (L), (a, a)$归约，S(L)17$(L,
14、(S, (a, a)$归约，LS18$(L, (L, (a, a)$移进19$(L, (L,(a, a)$移进20$(L, (L, (a, a)$移进21$(L, (L, (a, a)$归约，Sa22$(L, (L, (S, a)$归约，LS23$(L, (L, (L, a)$移进24$(L, (L, (L,a)$移进25$(L, (L, (L, a)$归约，Sa26$(L, (L, (L, S)$归约，LL, S27$(L, (L, (L)$移进28$(L, (L, (L)$归约，S(L)29$(L, (L, S)$归约，LL, S30$(L, (L)$移进31$(L, (L)$归约，S(L)32$(L, S)$归约，LL, S33$(L)$移进34$(L)$归约，S(L)35$S$接受