2012-2013学年第二学期期末考试试卷（B）
一、选择题（共20分，每小题2分）
1、用高级语言编写的程序经编译后产生的程序叫（ ）。 A、源程序
B、目标程序
C、连接程序
D、解释程序
2、编译的两种形式是编译方式和解释方式，这两种方式最本质的区别在（ ）。 A、编译方式速度快 B、解释方式不产生目标代码 C、解释方式更方便 D、编译比解释步骤更多 3、Chomsky的3型语言是这样一种语言，其产生式限制为（ ）。
(其中α、β为由终极符和非终极符组成的任意长度的串，A、B为非终极符，a、b为终极符号)。
A、A→ α B、A→a 或 A→Ab C、α→β D、aAb→bβa 4、自顶向下的语法分析方法有（ ）。
A、简单优先分析法 B、LL(1)分析法 C、算符优先分析法 D、LR(0)分析法
5、设有文法G[S]：S→S1|S0|Sa|Sc|a|b|c，下列符号串中不是该文法的句子有（ ）。 A、ab0 B、a0c01 C、aaa D、bc10 6、文法 G 产生的( )的全体是该文法描述的语言。 A、句型 B、终结符集
C、非终结符集 D、句子
7、词法分析器的输出结果是( )。 A、单词的种类编码
B、单词在符号表中的位置
C、单词的种类编码和自身值 D、单词自身值
8、若项目集 Ik含有 A→a· ，则在状态 k 时，仅当面临的输入符号 a∈FOLLOW(A)时，
才采取“A→a· ”动作的一定是( )。 A、 LALR 文法 C、 LR(1)文法
B、LR(0)文法 D、SLR(1)文法
9、后缀式ab+cd+/对应的中缀表达式是( )。
A、a+b/c+d B、(a+b)/(c+d) C、a+b/(c+d) D、a+b+c/d
10、对于错误信息“else 没有匹配的if”,最有可能是编译的（ ）阶段报告出来的。
A、词法阶段
B、语法阶段 C、语义阶段 D、代码生成阶段
二、计算题（共50分）
1、设文法G={{S}，{a,b}，P，S} P： S-> aSb S -> ab
请写出该文法所表达的语言。 （5分）
2、构造一个DFSA，它接受Σ={ a，b}上的符号串，符号串中的每个b都有a直接跟在右边；然后再构造该语言的正规文法。 （15分） 3、写出下列语句的四元式中间代码。（12分） （1） if ( x>0 ) x:=0; else x:=1; （2） while ( x>0 ) x:=x-1;
4、设当前层数为L，可用偏移量Offset值为101，下面分别用PASCAL和C两种语言给出了一个程序段，请写出相关的符号表和数据类型（内部表示）表。 （18分）
CONST m=123; const int m=123; const int n=321; typedef float at[10]; typedef record { i,j:integer } rt; at a,b; float x,y; n=321; rt=record i,j:integer end; TYPE at=array[0..9] of real; VAR a,b:at; x,y:real;
三、语法分析题（共30分）
1、已知文法G[S]：S→MH|a
H→LSo|ε K→dML|ε L→eHf M→K|bLM
判断G 是否是LL(1)文法，如果是，构造LL(1)分析表。 （20分） 2、已知文法G[S]：
S→aA A→Ab|b
判断该文法是否是LR（0）文法，并说明理由。 （10分）
2012-2013学年第二学期期末考试试卷（B）
评分标准及参考答案
课程名：编译原理 课程号：262006 出卷人：漆志群 联系电话：18970069697
一、选择题（共20分，每小题2分）
1、B 2、B 3、B 4、B 5、A 6、D 7、C 二、计算题（共50分）
1、（5分）L（G）= {an
bn
| n>=1}
2、（15分） DFSA: a b 0 1
a 正规文法： S→aS|bW|ε W→aS|a
3、（12分）
(1) (GT,x,0,t1) (JMP0,t1,L1) (ASSIG,0,x) (JUMP,L2) (LABLE,L1) (ASSIG,1,x) (LABLE,L2) （2） (LABLE,L1)
(GT,x,0,t1) (JUMP0,t1,L2) (SUBI,x,1,t2)
(ASSIG,t2,x) (JUMP,L1) (LABLE,L2)
8、D 9、B 10、B
4、（18分）
符号表的内容（其中atIR和rtIR表示类型的内部表示地址） m n at rt a b x y intPtr intPtr atIR rtIR atIR atIR realPtr realPtr constKind constKind typeKind typeKind varKind varKind varKind varKind 123 321 False False Dir Dir Dir dir L L L L 101 111 121 123
类型的内部表示：
atIR:
10 arrayTy 0 null j 9 realPtr recordTy rtIR: 2
i intptr 0
三、语法分析题（30分）
1、（20分） 文法展开为： 0） S→M H 1） S→a 2） H→L S o 3） H→ε
4） K→d M L 5） K→ε 6） L→e H f 7） M→K 8） M→b L M 非终结符 S M H L K FIRST 集 {a,d,b,ε,e} {d,ε,b}.. {ε,e} {e} {d,ε} intPtr 1 null FOLLOW 集 {#,o} {e,#,o} {#,f,o}.. {a,d,b,e,o,#} {e,#,o} 对相同左部的产生式可知：
SELECT(S→M H)∩SELECT(S→a) ={ d,b ,e，#,o }∩ { a }=Ф SELECT(H→L S o)∩SELECT(H→ε) ={ e }∩ { #,f,o }=Ф SELECT(K→d M L)∩SELECT(K→ε) ={ d }∩ { e,#,o }=Ф
SELECT(M→K)∩SELECT(M→b L M) ={ d，e,#,o }∩ { b }=Ф 所以文法是LL(1)的。
预测分析表： S M H L K a a o MH K ε ε d MH K dML e MH K LSo eHf ε f ε b MH bLM # MH K ε ε 由预测分析表中无多重入口也可判定文法是LL(1)的。 2、（10分）
0
s→.aA a 1
s→a.A A→.Ab A→.b b 2
A→b. A 3 s→aA. A→A.b b 4 A→Ab. 根据该文法的LR(0)自动机可以知道，每个状态都只包含移入型项目或者只含有一个归约型项目，所以该文法是LR(0)文法。