编译原理试题
计算机学院2001级题号一满分12得分
一
【
班学号四7五8六8七12八12九7
二6
三8
姓名十十一66
十总分二8100
选择题（12分）
】1．词法分析器的输入是A．符号串B．源程序。C．语法单位。D．目标程序
【
】2．两个有穷自动机等价是指它们的A．状态数相等C．所识别的语言相等B．有向弧数相等
D．状态数和有向弧数相等。D．xyx。
【
】3．文法G：S→xSxy所识别的语言是A．xyxB．xyxC．xxyxx
【
】4．设abc为文法的终结符，且有优先关系ab和bc，则A．必有acC．必有baB．必有caD．选项A、B和C都不一定成立
【
】5．若状态k含有项目“A→α”，且仅当输入符号a∈FOLLOWA时，才用规则“A→α”归约的语法分析方法是。A．LALR分析法C．LR1分析法B．LR0分析法D．SLR1分析法。C．语义规则D．等价变换规则。
【
】6．生成中间代码时所依据的是A．语法规则B．词法规则
【
】7．表达式（┐a∨b）∧（c∨d）的逆波兰表示为A．┐ab∨∧cd∨C．ab∨┐cd∨∧B．a┐b∨cd∨∧D．a┐b∨∧cd∨。
【
】8．基本块
A．只有一个入口语句和一个出口语句C．有多个入口语句和一个出口语句
1
B．有一个入口语句和多个出口语句D．有多个入口语句和多个出口语句
f二
【【【【【【
判断题（6分。认为正确的填“T”，错的填“F”）
】1．同心集的合并有可能产生“归约归约”冲突。】2．一个文法所有句子的集合构成该文法定义的语言。】3．非终结符可以有综合属性，但不能有继承属性。】4．逆波兰表示法表示表达式时无需使用括号。】5．一个有穷自动机有且只有一个终态。】6．若过程p第k次被调用，则p的DISPLAY表中就有k1个元素。
三
填空题（8分）
和F→P↑FP分析法。P→Ei句型TTFi。项目，
1．最常用的两类语法分析方法是2．对于文法GE：E→TETT→FTF的直接短语为，句柄为
3．在LR0分析法中，若βV且aVT则称“A”为称“Saβ”为项目。
4．在PL0的目标代码解释执行时，寄存器B总是指向当前执行过程活动记录的，而寄存器T总是指向。
四（7分）有穷自动机M接受字母表＝01上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。五（8分）构造下列文法相应的有穷自动机。
GS：SABQDEF→→→→→→→aAbQaAbBbbDaQaQbDbbBaAaBbFbDaEb
2
f六（8分）写一个文法，使其语言是：L＝ambma
b
m
≥0七（12分）已知文法
Gr