图2.58DFA；1.5.27（中科院计算所1997年研究生试题）；1.5.28（南开大学1998年研究生试题）写出；1.5.29（复旦大学1999年研究生试题）；将图2.59所示的非确定有限自动机(NFA)变换；图2.59NFA；其中，X为初态，Y为终态；1.5.30（上海交大1997年研究生试题）；请构造与正规式R=(a*|b*)b(ba)*等价；1.5
图2.58 DFA
（中科院计算所1997年研究生试题） 为正规式(a|b) *a(a|b)构造一个确定的有限自动机。
（南开大学1998年研究生试题） 写出正规式(alb) *(aa|bb)(a|b)*的DFA。
（复旦大学1999年研究生试题） 将图2.59所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。
NFA 其中，X为初态，Y为终态。
1.5.30 （上海交大1997年研究生试题） 请构造与正规式R=(a*|b*)b(ba)*等价且状态最少的DFA。
（国防科大1999年研究生试题） 构造一个确定的有限自动机DFA,它接受∑＝{0,1}上的所有不带前导0的二进制区数。
（国防科大2000年研究生试题） 已知DFA M如图2.60所示。
图2.60 DFA
M 请给出M所识别的字的全体L(M)。
（华中理工2001年研究生试题）
构造一个确定的有穷自动机DFA M,它识别∑={a,b}上所有满足如下条件的字符串：字 符串由a, b组成，且其中b的个数为3k (k≥0)。
（华中理工2001年研究生试题） 正规式(ab）*a与正规式a(ba) * 是否等价？请说明理由。
DFA与NFA有何区别 5 ※ 第三章
语法分析 典型例题: 单项选择题
3.1.1. 文法G: S-xSxly所识别的语言是_____（陕西省1997年自考题）
c. xnyxn(n≥0)
3.1.2. 文法G描述的语言L(G)是指_____。
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)<g(b)，则a<b
c.a~b都不一定成立
d. a~b一定成立
3.1.5．茹果文法G是无二义的，则它的任何句子α_＿。（西电1999年研究生试题）
a.最左推导和最右推导对应的语法树必定相同
b.最左推导和最右推导对应的语法树可能不同
c.最左推导和最右推导必定相同
d.可能存在两个不同的最左推导，但它们对应的语法树相同
3.1. 6.由文法的开始符经。步或多步推导产生的文法符号序列是____。
（陕西省2000年自考题）
d.句子 3.1.7．文法G：E-E+TIT
P-(E)|I 则句型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．产生正规语言的文法为____＿。
3.1.11．任何算符优先文法―优先函数。
c.有若干个
d.可能有若干个
3.1.12.采用自上而下分析，必须____＿。
a.消除左递归
b.消除右递归
c.消除回溯．
d.提取公共左因子
3.1.13．设a, b, c是文法的终结符，且满足优先关系a=b和b=c，则_____＿。
a.必有a=ｂ
b．必有c=a
d. a~c都不一定成立
3.1.14.在规范归约中，用___＿来刻画可归约串。（陕西省1999年自考题）
a.直接短语
c.最左素短语
3.1.15.有文法Ｇ：E→E*T|T
T→T+i|i 句子1+2*8+6按该文法G归约，其值为___＿。
3.1.16.规范归约是指________。（陕西省９８年自考题）
a.最左推导的逆过程
b.最右推导的逆过程
c.规范推导
d.最左归约的逆过程
3.1.17.一文法G:S→S+T|T．（陕西省1998年自考题）
P→(S)|i 则句型P+T+i的短语有___＿。
b. P,P+T,i,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年自考题）
e. 出错处理
3.2.5.算符优先文法与算符优先函数的关系描述中，下列__＿正确。（陕西省1997年自考题）
a、一个算符优先文法可能不存在算符优先函数与之对应
b. 一个算符优先文法可能存在多对算符优先函数与之对应
c.一个算符优先文法一定存在多对算符优先函数与之对应
d.一个算符优先文法一定存在算符优先函数与之对应
e.一个算符优先文法一定存在有限对算符优先函数与之对应
3.2.6.有一文法G: S--AB
（陕西省1998年自考题）
B一cBd|ε 它不产生下面__＿集合。
{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
B→bScA|b 则句型aAcbBdcc的短语是_______。
d. aAcbBdcc
3.2.9.在自下而上的语法分析中，应从_________开始分析。
c.以单词为单位的程序
d.文法的开始符
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把文法分为______＿种类型，编译器构造中采用______和_____＿文法，它们分别产生_____和_____语言，并分别用______和______自动机识别所产生的语三亿文库包含各类专业文献、中学教育、文学作品欣赏、幼儿教育、小学教育、高等教育、18《编译原理》期中及期末习题等内容。　
　《编译原理》模拟试题一一、是非题(请在括号内,正确的划√,错误的划×)(每个 2 分,共 20 分) 1.计算机高级语言翻译成低级语言只有解释一种方式。(×) 2.在... 　《编译原理》模拟期末试题... 35页 5财富值喜欢此文档的还喜欢 期末考试编译原理试卷及答... 12页 免费 编译原理期末试题(8套含答... 53页 2财富值 编译原... 　北方工业大学 序号 《编译原理》课程期末复习题(答案) 开课学院 考试方式:闭卷...编译原理期末试题(8套含... 51页 免费
编译原理期末复习题(含答... 20页... 　&. &. 第 16 页共 6 页 《编译原理》期末试题(二) 1、描述由正规式 b*(abb*)*(a| ε)定义的语言,并画出接受该语言的最简 DFA。 2、证明文法 E ... 　编译原理期末试题(8套含答案+大题集)_工学_高等教育_教育专区。编译原理 期末复习 八套试卷 含答案《编译原理》期末试题(五)一、单项选择题(共 10 小题,每小... 　编译原理期末试题 暂无评价 14页 免费 期末考试编译原理试卷及答... 12页 免费...《编译原理》考核形式:闭卷 班级: 姓名: 课程期中考试卷(A)学号: 题号 得分... 　学年1学期12级《编译原理》期末考试试题(A卷)_院校资料_高等教育_教育专区。试题参考 北京邮电大学世纪学院 2014――2015 学年第 1 学期期末考试试题(... 　编译原理期末试题_教育学_高等教育_教育专区。《编译原理》期末试题(一) 一、是非题(请在括号内,正确的划√,错误的划×)(每个 2 分,共 20 分) 1.编译程序...人教版一年级语文第三单元测试题(A、B卷)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
人教版一年级语文第三单元测试题(A、B卷)
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩5页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢