发布时间 : 星期一 文章《编译原理》期中及期末习题更新完毕开始阅读22792f0df12d2af90242e68e
3.1. 6.由文法的开始符经。步或多步推导产生的文法符号序列是____。
（陕西省2000年自考题）
a．短语 b.句柄 c.句型 d.句子
3.1.7．文法G：E-E+TIT T-T*P|P P-(E)|I
则句型P+T+i的句柄和最左素短语分别为__＿。 a. P+T和i b. P和P+T c. i和P+T+i d. P和P 3.1.8．设文法为：S--SA|A A→a|b
则对句子aba，下面____是规范推导．
a. S=>SA=>SAA=>AAA=>aAA=>abA=>aba b. S=>SA=>SAA=>AAA=>AAa=>Aba=>aba c. S=>SA=>SAA=>SAa=>Sba=>Aba=>aba d. S=>SA=>Sa=>Sba=>Aba=>aba 3.1.9.文法G: S→b|∧|(T) T-T,SIS
则FIRSTVT(T)=____。 a.｛b，∧，（｝ b.｛b，∧，）｝ c.｛b,∧，（，,｝ d.{b, ∧，），，｝
3.1.10．产生正规语言的文法为____＿。 a. 0型 b. 1型 c. 2型 d. 3型
3.1.11．任何算符优先文法—优先函数。
a.有一个 b.没有 c.有若干个 d.可能有若干个 3.1.12.采用自上而下分析，必须____＿。 a.消除左递归 b.消除右递归 c.消除回溯． d.提取公共左因子
3.1.13．设a, b, c是文法的终结符，且满足优先关系a=b和b=c，则_____＿。 a.必有a=ｂ b．必有c=a
c.必有b=a d. a~c都不一定成立 3.1.14.在规范归约中，用___＿来刻画可归约串。（陕西省1999年自考题） a.直接短语 b.句柄 c.最左素短语 d.素短语 3.1.15.有文法Ｇ：E→E*T|T T→T+i|i
句子1+2*8+6按该文法G归约，其值为___＿。 a.23 b.42 c.30 d.17 3.1.16.规范归约是指________。（陕西省９８年自考题） a.最左推导的逆过程 b.最右推导的逆过程 c.规范推导 d.最左归约的逆过程 3.1.17.一文法G:S→S+T|T．（陕西省1998年自考题） T→T*P|P P→(S)|i
则句型P+T+i的短语有___＿。
a. i,P+T b. P,P+T,i,P+T+i c. P+T+i d. P, P+T,i
多项选择题：
3.2.1.下面哪些说法是错误的___＿。（陕西省1998年自考题）
a. 有向图是一个状态转换图 b.状态转换图是一个有向图
c． 状态转换图可以用DFA表示 d. DFA可以用状态转换图表示 e.有向图是一个DFA
3.2.2.对无二义性文法来说，一棵语法树往往代表了___＿。 a.多种推导过程 b.多种最左推导过程 c.一种最左推导过程 d.仅一种推导过程 e.一种最右推导过程
3.2.3．如果文法G存在一个句子，满足下列条件___之一时，则称该文法是二义文法。
a.该句子的最左推导与最右推导相同 b、该句子有两个不同的最左推导 c.该句子有两个不同的最右推导 d,该句子有两棵不同的语法树 e.该句子的语法树只有一个
3.2.4.语法分析时通过___＿操作使用符号栈。（陕西省2000年自考题） a. 移进 b. 归约 c. 比较 d. 接受 e. 出错处理
3.2.5.算符优先文法与算符优先函数的关系描述中，下列__＿正确。（陕西省1997年自考题）
a、一个算符优先文法可能不存在算符优先函数与之对应 b. 一个算符优先文法可能存在多对算符优先函数与之对应 c.一个算符优先文法一定存在多对算符优先函数与之对应 d.一个算符优先文法一定存在算符优先函数与之对应
e.一个算符优先文法一定存在有限对算符优先函数与之对应
3.2.6.有一文法G: S--AB （陕西省1998年自考题）
A--aAb|ε B一cBd|ε 它不产生下面__＿集合。
a. {anbmcndm|n,m≥0} b. {anb\｝ c. {anbmcmdn|n,m≥0} d. {anbncmdm|n,m≥0} e. {anbncndn|n≥0}
3.2.7．文法的无二义性是指_________。
a.文法中不存在句子有两个不同的最左推导 b.文法中不存在句子有两个不同的最右推导 c.文法中不存在句子有不同的推导
d.文法中不存在句子有两裸不同的语法树 e.文法中不存在句子有不同的最左和最右推导 3.2.8. 文法G：S→aAcB|Bd A→AaB|c B→bScA|b
则句型aAcbBdcc的短语是_______。
a. Bd b. c c. bBdcc d. aAcbBdcc e. cbBd 3.2.9.在自下而上的语法分析中，应从_________开始分析。 a.句型 b.句子 c.以单词为单位的程序 d.文法的开始符 e.句柄
3.2.10.对正规文法描述的语言，以下_____＿有能力描述它。 a. 0型文法 b. 1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法
填空题：
3.3.1．规范归约中的可归约串是指______;算符优先分析中的可归约串是指______＿。
3.3.2.文法中的终结符和非终结符的交集是______。词法分析器交给语法分析器的文法符号一定是______，它一定只出现在产生式的_____＿部。
3.3.3.在自上而下的语法分析中，应先消除文法的_______递归，再消除文法的_____递归。
3.3.4.规范归约是指在移进过程中，当发现栈顶呈现_____时，就用相应产生式的_____符号进行替换。
3.3.5．当文法非终结符的所有_____两两___＿时，该文法对应的句子分析不含回溯。
3.3.6.最左推导是指每次都对句型中的____＿非终结符进行扩展。（陕西省1998年自考题）
3.3.7.在语法分析中，最常见的两种方法一定是_____分析法，另一是______分析法。 （陕西省1998年自考题）
3.3.8.______语法分析的关键问题是精确定义可归约串的概念。（陕西省2000年自考题）
3.3.9. Chomsky定义的4种形式语言文法为：
①______文法，又称______文法；②_____文法，又称_____文法； ③______文法，又称______文法；④______文法，又称_____＿文法。 （中国科技大学1999年研究生试题） 3.3.10. LL(K)文法中，第一个L表示_____＿，第二个L表示_____＿，K表示_____，通常情况下K_____。（西安电子科大2000年研究生试题）
3.3.11．采用_______＿语法分析时，必须消除文法的左递归。 3.3.12．_____树代表推导过程，______＿树代表归约过程。
3.3.13.自下而上分析法采用____＿、归约、错误处理、_____＿等四种操作。
（陕西省1999年自考题） 3.3.14．设αβδ是文法G的一个句型，A是非终结符，则β是句型αβδ相对于A的短语，若______＿；β是句型αβδ相对于A的直接短语，若_____＿；β是句型αβδ的句柄，若_______。（西安电子科大2000年研究生题）
3.3.15．Chomsky把文法分为______＿种类型，编译器构造中采用______和_____＿文法，它们分别产生_____和_____语言，并分别用______和______自动机识别所产生的语
言。 （西安电子科大2000年研究生试题）
判断题：
3.4.1语法分析之所以采用上下文无关文法是因为它的描述能力最强。 （ ）
3.4.2 欲构造行之有效的自上而下分析器，则必须消除左递归。 （ ） 3.4.3文法( 有图片 )描述的语言是（a|bc）* ( ) 3.4.4 在自下而上的语法分析中，语法树与分析树一定相同。（ ） 3.4.5 二义文法不是上下文无关文法。（陕西省1999年自考题）（ ） 3.4.6 每一个算符优先文法，必定能找到一组优先函数与之对应。（陕西省2000年自考题） （ ）
3.4.7 语法分析时必须先消除文法中的左递归。 （ ） 3.4.8 规范归约和规范推导是互逆的两个过程。 （ ） 3.4.9 一个文法所有句型的集合形成该文法所能接受的语言。 （ ）
3.4.10 LL(1)文法一定不含左递归和二义性。 （ ）
综合题
3.5.1 简答题 1．句柄 2.素短语 3．语法树 4.归约 5.推导
3.5.2给出上下文无关文法的定义。
3.5.3 Chomsky将文法分成四类。指明这四类文法与自动机的对应关系。指出右线性文法、左线性文法、正规文法之间的主要区别。
3.5.4 文法G是LL(1)文法的充分必要条件是什么？
3.5.5 文法G[S］：
S→aSPQ|abQ QP→PQ bP→bb bQ→be cQ→cc
（1)它是Chomsky哪一型文法？ （2）它生成的语言是什么？
3.5.6 指出下述文法的所有类型，并给出所描述的语言。 （1）S→Be （2）A→ε|aB（3）TS→abcA B→eC|Af B→Ab|a S→Aabc A→Ae|e A→ε C→Cf Aa→Sa
D→fDA cA→cS