《编译原理》期中及期末习题(3)

图2.58 DFA

1.5.27 （中科院计算所1997年研究生试题） 为正规式(a|b) *a(a|b)构造一个确定的有限自动机。

1.5.28 （南开大学1998年研究生试题） 写出正规式(alb) *(aa|bb)(a|b)*的DFA。

1.5.29 （复旦大学1999年研究生试题）

将图2.59所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。

图2.59 NFA

其中，X为初态，Y为终态。

1.5.30 （上海交大1997年研究生试题）

请构造与正规式R=(a*|b*)b(ba)*等价且状态最少的DFA。

1.5.31 （国防科大1999年研究生试题）

构造一个确定的有限自动机DFA,它接受∑＝{0,1}上的所有不带前导0的二进制区数。

1.5.32 （国防科大2000年研究生试题）

已知DFA M如图2.60所示。

图2.60 DFA M

请给出M所识别的字的全体L(M)。

1.5.33 （华中理工2001年研究生试题）

构造一个确定的有穷自动机DFA M,它识别∑={a,b}上所有满足如下条件的字符串：字 符串由a, b组成，且其中b的个数为3k (k≥0)。

1.5.34 （华中理工2001年研究生试题）

正规式(ab）*a与正规式a(ba) * 是否等价？请说明理由。

1.5.35 DFA与NFA有何区别

5

※<习题三>

第三章 语法分析

典型例题: 单项选择题

3.1.1. 文法G: S-xSxly所识别的语言是_____（陕西省1997年自考题） a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx* 3.1.2. 文法G描述的语言L(G)是指_____。

a. L(G)=｛α|S=>α，α ∈VT*｝b. L(G)={ α|SA=>α,α ∈VT*｝

c．L(G)={ α|S=>α，α∈(VT∪VN)*｝d. L(G)=｛α|S=>α,α∈(VT∪VN)*｝ 3.1.3. 有限状态自动机能识别＿。

a.上下文无关文法 b.上下文有关文法 c.正规文法 d.短语文法

3.1.4. 设G为算符优先文法，G的任意终结符对a, b有以下关系成立____。 a.若f(a)>g(b)，则a>b b.若f(a)

3.1.5．茹果文法G是无二义的，则它的任何句子α_＿。（西电1999年研究生试题） a.最左推导和最右推导对应的语法树必定相同 b.最左推导和最右推导对应的语法树可能不同 c.最左推导和最右推导必定相同

d.可能存在两个不同的最左推导，但它们对应的语法树相同

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把文法分为______＿种类型，编译器构造中采用______和_____＿文法，它们分别产生_____和_____语言，并分别用______和______自动机识别所产生的语

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《编译原理》期中及期末习题(3)在线全文阅读。