1、bAb print “1” A-（B print “2” a print “3” B-Aa） print “4” 若输入序列为b（aa）a）a）b,则采用自下而上的分析方法,则输出是 B 。A 32224441 B 34242421 C 12424243 D 3444221214. 局部优化是对 D 进行的优化。A 表达式 B 部分代码 C 循环体 D 基本块15. 削减运算强度是对 D 的一种优化。A 表达式 B 过程 C 基本块 D 循环二 填空题1词法分析阶段的任务式从左到右扫描 源程序 ，从而逐个识别 单词 。2对于文法GE：ET|E+T TF|T*F FPF|P P（E）|i，句型T
2、+T*F+i的句柄是 T 。3最右推导的逆过程称为 最左规约 ，也称为 规范规约 。4符号表的信息栏中登记了每个名字的有关属性，如 符号名 、 符号的类型 、 符号的存储类别 和 符号的作用域及可视性 等。5. 一个确定有穷自动机由五部分组成： 有穷状态集 、 有穷字母表 、 转换函数 、 初态 和 终态集 。6. 最常用的两类语法分析方法是 自顶向下 和 自底向上 分析法。7. 单词的三种描述工具： 正规文法 、 正规式 和 有穷自动机 互相之间具有等价性。8. 在PL/0的目标代码解释执行时，寄存器B总是指向当前执行过程活动记录的起始地址，而寄存器T总是指向栈顶 。9LR（0）分析法的名字
3、中”L”表示 自左向右扫描输入符号串 ，”R”表示 最右推导的逆过程 ，“0”表示 向前看的输入符号的个数 。10. 两种常用的动态存储分配办法是 栈式 动态分配和 堆式 动态分配。三 判断题（认为正确的填“T”，错的填“F”）【 T 】1同心集的合并有可能产生“归约/归约”冲突。【 T 】2一个文法所有句子的集合构成该文法定义的语言。【 F 】3非终结符可以有综合属性，但不能有继承属性。【 T 】4逆波兰表示法表示表达式时无需使用括号。【 F 】5一个确定有穷自动机有且只有一个终态。【 F 】6若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。四 解答题1给定文法G和句型（T+
4、F）*i+T, G: EE+T | T TT*F | F F（E） | i （1）画出句型的语法树； （2）写出句型的全部短语、简单短语和句柄。解：（略）2设有文法G：SS+S|S*S|i|（S）。（1）对于输入串i+i*i 给出一个最左推导；（2）该文法是否是二义性文法？请证明你的结论。（1）i+i*i的最左推导：S = S+S = i+S = i+S*S = i+i*S = i+i*i （2）该文法是二义性的。因为对于句子i+i*i可以画出两棵语法树（语法树略）。3给出语言ambmcn|m1,n0的上下文无关文法（2型）。 G: SAB|A AaAb|ab BcB|c4给出语言akbmcn
5、|k,m,n1的正规文法（3型）。 AaA|aB BbB|bC CcC|c5将文法G改写成等价的正规文法（3型）。 SdAB AaA|a BbB|b SdA AaA|aB6设有字母表a，b上的正规式R=（ab|a）*。（1）构造R的相应有限自动机；3（2）构造R的相应确定有限自动机；将（1）所得的非确定有限自动机确定化IaIb-+013123+12313+13-+（3）构造R的相应最小确定有限自动机；对（2）得到的DFA化简，合并状态0和2 为状态2：（4）构造与R等价的正规文法令状态1和2分别对应非终结符B和A AaB|a| BaB|bA|a|b|可化简为： AaB| BaB|bA|7已知正
6、规文法GS: S aS | bA | aA aS（1）构造与之等价的自动机NFA M（2）将NFA M确定化为DFA M I-0SSZA+18. 有穷自动机M接受字母表 0,1上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。（0|1）*（00|11）（0|1）*9对右图所示的有限自动机（1）若是确定的，则写出其转换矩阵；若不是，则将其确定化；（2）最小化。（注：确定化和最小化均应给出转换矩阵和图示）。（1） 符号 状态-14+35+46 （2）首先将状态按终态和非终态分成两个集合1,2,5,6和3,4检查子集1,2,5,6，由于f（1,a）=2，f（2,
7、a）=1，f（5,a）=4，f（6,a）=3，所以子集1,2,5,6可进一步划分为1,2和5,6检查子集3,4，由于f（3,a）=2，f（4,a）=1以及f（3,b）=5，f（4,b）=6，所以不用进一步划分了。检查子集1,2，由于f（1,a）=2，f（2,a）=2以及f（1,b）=3，f（2,b）=4，所以不用进一步划分了。检查子集5,6，由于f（5,a）=4，f（6,a）=3以及f（5,b）= ，f（6,b）= ，所以不需要进一步划分了。因此最终划分的结果是1,2、3,4和5,6，重新命名状态，令1,2为1，3,4为3和5,6为5，则得到化简后的DFA为 10写出在a,b上，不以a开头，但
8、以aa结尾的字符串集合的正规式（并构造与之等价的最简DFA）。依题意，“不以a开头”，则必以b开头，又要“以aa结尾”，故正规式为：b（a|b）*aa（构造与之等价的最简DFA，此略）11写一个LL（1）文法G，使其语言是L（G）= ambnc2n | m=0,n0 并证明文法是LL（1）。文法G（S）：S aS | EE bEE Ecc | ccSelect（S aS）Select （S E）= Select（E Ecc）Select （E cc） =故文法为LL（1）的12将文法G改写成等价的LL（1）文法，并构造预测分析表。 G：SS*aT|aT|*aT T+aT|+a（编写递归下降子程
9、序）消除左递归后的文法G: SaTS|*aTSS*aTS|T+aT|+a提取左公因子得文法G:SaTS|*aTST+aTTT|Select（SaTS）=aSelect（S*aTS）=*Select（SaTS）Select（S*aTS）=Select（S*aTS）=*Select（S）=Follow（s）=#Select（S*aTS）Select（S）= Select（T+aT）=+Select（TT）=First（T） =+Select（T ）=Follow（T）=*,#Select（TT）Select（T）= 所以该文法是LL（1）文法。预测分析表：*#STa, NTST, NS, PTTa
10、, NTT, P, NOK（递归下降子程序，略）13对文法GS: S aSb | PP bPc | bQcQ Qa | a构造简单优先关系表。该文法是否是简单优先文法？简单优先关系矩阵如下：PQc= 由于矩阵中有元素存在多种优先关系，故不是简单优先文法。14考虑文法 G: S AS | b A SA | a（1）构造文法的可归前缀图（活前缀的DFA）；（2）判断文法是否是LR（0）文法，并说明理由。（1）可归前缀图（2）因为存在冲突，所以不是LR（0）文法。15已知文法GS：S Uta | Tb T S | Sc | d U US | e （1） 试判断G是LR（0），SLR（1），LALR（
11、1）还是LR（1），说明理由。（2） 构造相应的分析表。（1） 首先拓广文法为G，增加产生式SS（0） SS （1）SUTa （2） STb （3） TS （4） TSc （5） Td （6） UUS （7） U eG的LR（0）项目集族及识别活前缀的DFA如下图所示：（2）在I1中：S S.为接受项目，T S. 为归约项目，T S.c为移进项目，存在接受-归约和移进-归约冲突，因此所给文法不是LR（0）文法。在I1中：Follow（S） Follow（T）= # a ，b=Follow（T） c= a ，b c=在I8中：Follow（U） Follow（T） c=d,e a ，b c=所以
12、在I1中的接受-归约和移进-归约冲突与I8中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR（1）文法。构造的SLR（1）分析表如下：状态（State）ActionGotoa b c d e#SUT78910 S5S4r3r3S6AccS9.r7r7r5r5. r4r4.S10S9.r3r3.S6r6r6. r2r2.r2r2r2r2r1r1.r1r1r1r1123.827 16文法G及其LR分析表如下，请给出对串dada#的分析过程。 S VdB V e V B a B Bda B 状态ACTIONGOTOdeBVr3 S3accS4r2r6S5r4S7r1S8r5对输入
13、串dada#的分析过程步骤状态栈符号栈剩余输入符号动作02024024502460246702467801#V#Vd#Vda#VdB#VdBd#VdBda#Sdada#ada#da#a#用V 归约移进用B a归约用B Bda 归约用S VdB 归约接受17对以下文法，请写出关于配对括号数目ps的属性文法。文法规则语 义 规 则S（T）SiTT,STSh表示配对括号数目（1）S.h = T.h + 1 （2）S.h = 0（3）T.h = T.h+S.h （4）T.h = S.h 18把下列语句if x0 and y0 then z：xyelse x：x2翻译成四元式序列。略19对传值、传地址和
14、传名3种参数传递方法分别写出下列程序的输出：void p（int x, int y, int z） y *= 3;z += x;void main（） int a=5, b=2;p（a*b,a,a）;printf（“%dn”, a）;这些参数传递机制如何实现？（1）传值 5； （2）传地址 25； （3）传名 45（参数传递机制，略）20将下面程序划分为基本块，并画出其程序流图。 b := 1= 2 if w = x goto L2 e := b goto L2 L1:goto L3 L2:c := 3= 4 c := 6 L3:if y = z goto L4 halt L4:g := g
15、+ 1 h := 8 goto L1（1）基本块： （2）程序流图= x goto L2 （1） goto L2 （2） goto L3 （3） c := 6 （4） if y = z goto L4 （5） halt （6） g : goto L1 （7）21对PL/0语言If ELSE子句填空: := IF THEN ELSE 注：FOR语句和WHILE语言的填空请在空缺处填空，完成条件语句的编译算法：switch （SYM） case IFSYM: ;CONDITION（SymSetUnion（SymSetNew（THENSYM）,FSYS）,LEV,TX）;if （SYM=THENSYM） GetSym（）;else Error（16）;CX1=CX; GEN（JPC,0,0）;STATEMENT（SymSetUnion（SymSetNew（ELSESYM）,FSYS）,LEV,TX）; CX2=CX; GEN（JMP,0,0）;If（ ）GetSym（）; STATEMENT（FSYS,LEV,TX）; ;break;（1） getSym（） （2） CodeCX1.A=CX （3） SYM=ELSESYM （4） CodeCX2.A=CX
