《编译原理》期中及期末习题 下载本文

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 b.必有c=a

c.必有b=a d. a~c都不一定成立 3.1.14.在规范归约中,用____来刻画可归约串。(陕西省1999年自考题) a.直接短语 b.句柄 c.最左素短语 d.素短语 3.1.15.有文法G:E→E*T|T T→T+i|i

句子1+2*8+6按该文法G归约,其值为____。 a.23 b.42 c.30 d.17 3.1.16.规范归约是指________。(陕西省98年自考题) 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