软件学院编译原理试题2

1、北京工业大学年度第学期计算机学院 级【编译原理】考 试题（A）考试形式：开卷 考试时间：200年月日学号姓名1234567附加题总分分 数1.（ 6分）回答下列问题1）在存储管理中，为什么在活动记录内为临时变量分配空间？解：活动记录为一次过程调用 （函数调用）中的局部数据提供栈式存储空间， 随过程调用被分配, 随过程调用的结束而释放； 临时变量用于保存表达式计算中的中间结果， 在活动记录中为临时变 量分配空间，可以保证该空间随过程调用被分配，随活动记录的释放被自动释放。2）在符号表管理中，为什么将变量名保存在符号表中？解：符号表中将保存变量名及其各种属性，变量名将用于变量的识别、涉及变量的语义

2、分析、变 量名与存储空间的绑定、以及类型、作用域、存储地址等各种变量属性的设置、获取等各种维护 功能。2.（8分）试消除下列文法中的左递归S t SaA|Se|BA t BbA|BB t cSd|；解：消除左递归提取左因子改写后的文法S t SaA|Se|BA t BbA | BS t BSt S (aA | e ) | Bt B ( bA | )S t aA S|e S引进非终结符S引进非终结符AA tb AS t bsA t b AA t bA | ；St (aA | e ) Sl ；At bA | ；B t cSd|；3. (15分)写出下列文法中各候选式的FIRST集和各非终结符的FO

3、LLOW!,构造该文 法的LL( 1)分析表，并说明它是否为LL( 1)文法。S t aA|BAA t cB| ；B t bB|； 解：各候选式的FIRST集(4分)FIRST (aA) =a FIRST (BA) = b, c, ； FIRST (cB) =cFIRST ( ；) = FIRST (bB) = b FIRST ( ；) = ；各非终结符的FOLLOW! (4分)FOLLOVS)= # FOLLOW(A)= # FOLLOW(B)= c, #LL (1)分析表 (5 分)abc#SS t aAS t baS tBASt baAA tcBAt 名BB t bBB t $Bt 呂说

4、明它是否为LL (1)文法(2分)判断1分，理由1分因为LL (1)分析表无冲突，所以该文法是 LL (1)文法。4. (18分)给定文法GSSt L + L | LL t LB|BB t 0|1(1)构造拓广文法，按LR(O)分析的需要画出识别这个拓广文法的所有规范句型活前 缀的DFA0SXT 0S 11ST 0L 2 +6 L82ST 0L 23LT 0,6 L 2, 8B 74LT 0,6 B 35BT 0,2, 6, 8 0 46BT 0,2, 6, 8 1 5Io：(0,0), (1,0),(2,0),(3, 0), (4L, 0), (5, 0), (6, 0) |1：(0,1)|

5、2：(1,1), (2,1),(3,1),(5, 0), (6i, 0) I3：(4,1)|4：(5,1)15：(6,1)16：(1,2), (3,0),(4,0),(5, 0), (6i, 0) 17：(3,2) 18：(1,3), (3,1),(5,0),(6, 0) (2)求出这个文法的SLR( 1分析表。解：给产生式编号：S L + LS LLt LBLt BB T 0 B 1FOLLOW(S)=#FOLLOW(L)=0,1,+,#FOLLOW(B)=0,1,+,#状态ACTONGOTO01+#SLB0S4S51231acc2S4S5S6r273r4r4r4r44r5P r5 nr5r

6、55r6r6r6r66S4S5837r3r3r3r38S4S5r175. (7分)写出能产生字母表x,y上的不含两个相邻的X,且不含两个相邻的y的全 体符号串的有限状态自动机。解:6. ( 16分)设文法GE:E t RP|PP t (E)|iR t rp+| rp* |P+|P*画出句子i+i*(i+i)的语法分析树，给出其最右推导和最左归约，并指出它的句柄解：(1)语法分析树:(2)E RPR(E)R(RP)R(Ri)R(P+i)R(i+i)RP*(i+i)P+i*(i+i)i+i*(i+i)最左归约：i+i*(i+i)P + i*(i+i)P+i*(i+i)Ri*(i+i)Ri*(i+i

7、)RP*(i+i)RP*(i+i)R(i+i)R(i+i)R(P+i)R(P+i)R(Ri)最右推导:Ri*(i+i)R(Ri) R(RP)R(RP) R(E)R(E) RPRP E句子 i+i*(i+i) 的句柄为： i ；7. (10分)下面是关于文法S t xYS|yXS| gX t yXX|xY t xYY|y 的一个语法制导定义, SxYS1S. nx=Y. nx + S1.nx + 1S. ny=Y. ny + S1.nyyXS1S. nx=X. nx + S1.nxS. ny=X. ny + S1.ny + 1zS. nx=0S. ny=0yX1 X2X. nx=X1. nx +

8、 X2. nxX. ny=X1. ny + X2.ny +xX. nx=1X. ny=0xY1 Y2Y. nx=Y1. nx + Y2.nx +Y. ny=Y1. ny + Y2. nyyY. nx=0Y. ny=1SSXXYY11(1) 请说明上述语法制导定义的作用是什么。(2) 按照此语法指导定义给出句子xxxyyyxy的语义分析过程或画出带注释的语法分析树.解：(1) 该语法制导定义的作用是统计句子中的x和y的个数；(4分)(2) 按照该语法制导定义对句子xxxyyyxy进行语义分析的结果为：S.nx = 4 ; S.ny = 4 ; (6 分)附加题 将左线性文法 G=(Vn,Vt,P,S转换成等价的有限状态自动机M=(Q,Vt,S ,qo,F)的一种等价变换中认为“对产生式 A - Ba P则M中用移动A S (B, a)与 之对应”，请问这种对应使用的是自顶向下的分析思想还是自底向上的分析思想？为 什么？(本题第一问最高奖励 3 分,第二问最高奖励 7 分)解：使用的是自底向上的分析方法归约。A S (B, a)表示在状态B遇到输入a时，到达状态A，将状态看成是目前已经 分析出来的中间结果，这样就相当于目前的分析已经得到了前缀B,加上a后相当于获得前缀A，也就是相当于B和紧接着的a可以归约成A，这与产生式ABa所表 示出来的意义是相同的，所以产生式A-Ba P则