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