编译原理第二章练习题
- 格式:pdf
- 大小:230.97 KB
- 文档页数:5
编译原理2014—2015学年第二学期第二单元测试试卷(闭卷考试)时间:45分钟满分:100分姓名班级出题人刘兵班级 02一、选择题(5*2分)(每题1分,共10分)1.文法分为四种类型,即0型、1型、2型、3型。
其中3型文法是_____。
A. 短语文法B.正则文法C.上下文有关文法D.上下文无关文法2.文法G[N]=({b},{N,B},N,{N→b│bB,B→bN}),该文法所描述的语言是_____A. L(G[N])={bi│i≥0}B. L(G[N])={b2i│i≥0}C. L(G[N])={b2i+1│i≥0}D. L(G[N])={b2i+1│i≥1}3.一个上下文无关文法G包括四个组成部分,它们是:一组非终结符号,一组终结符号,一个开始符号,以及一组_______A. 句子B. 句型C. 单词D. 产生式4.一个句型中的最左______称为该句型的句柄。
可选项有:A. 短语B. 简单短语C. 素短语D. 终结符号5.文法G[E]:E→T∣E+T T→F∣T﹡F F→a∣(E)该文法句型E+F﹡(E+T)的简单短语是下列符号串中的______ 。
①(E+T)②E+T ③F ④F﹡(E+T)可选项有:A) ①和③B) ②和③C) ③和④D) ③二、简答题(2*10分)(每题10分,共20分)1.解释语言、语法和语义的概念。
2. 文法 S→S(S)S|ε(1) 生成的语言是什么?(2) 该文法是二义的吗?说明理由。
三、分析题(4题共70分)1.文法 G[S]为:S→Ac|aBA→abB→bc该文法是否为二义的?为什么?2.考虑下面上下文无关文法:S→SS*|SS+|a(1)表明通过此文法如何生成串 aa+a*(2)G[S]的语言是什么?3.令文法 G[E]为:E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明 E+T*F 是它的一个句型,指出这个句型的所有短语、直接短语和句柄。
第二章 文法和语言p48 4、6(6)、11、 12(2)(6)、18(2)4 证明文法G=({E,O},{(,),+,*,v ,d},P ,E )是二义的,其中P 为 E → EOE | (E) | v | d O → + | * 证明:因为E=〉 EOE =〉EOEOE =〉EOEOv =〉EOE+v=〉EOv+v =〉E*v+v =〉v*v+v , 句子v*v+v 有两棵不同的语法树所以文法G 是二义的。
问题:1)只有文字说明,比如v*v+v 有两棵语法树,但没有画出语法树或者最左(最右)推导过程2)给出的是不同句子(v*v+d v+v*d )的语法树 6、已知文法G :EEEE OO v*v+ vE EE E O O v+v* v〈表达式〉∷=〈项〉|〈表达式〉+〈项〉〈项〉∷=〈因子〉|〈项〉*〈因子〉〈因子〉∷=(〈表达式〉)| i试给出下述表达式的推导及语法树(6)i+i*i推导过程:〈表达式〉=〉〈表达式〉+〈项〉E=〉E+T =〉〈表达式〉+〈项〉*〈因子〉=〉E+ T*F=〉〈表达式〉+〈项〉* i =〉E+ T*i=〉〈表达式〉+ 〈因子〉* i =〉E+F*i=〉〈表达式〉+ i* i =〉E+i*i=〉〈项〉+ i* i =〉T +i*i=〉〈因子〉+ i* i =〉F +i*i=〉i +i*i =〉i +i*i 共8步推导语法树:〈表达式〉+〈因子〉〈项〉i 〈因子〉i〈项〉〈项〉〈因子〉i*11、一个上下文无关文法生成句子abbaa的推导树如下:(1)给出该句子相应的最左推导和最右推导(2)该文法的产生式集合P可能有哪些元素?(3)找出该句子的所有短语、简单短语、句柄。
(1)最左推导:S=〉ABS=〉aBS=〉aSBBS=〉aBBS=〉abBS=〉abbS =〉abbAa=〉abbaa最右推导:S =〉ABS=〉ABAa=〉ABaa=〉ASBBaa=〉ASBbaa=〉ASbbaa=〉Abbaa=〉abbaa(2)该文法的产生式集合P可能有下列元素:S→ABS | Aa|εA→a B→SBB|b(3)因为字符串中的各字符有相对的位置关系,为了能相互区别,给相同的字符标上不同的数字。
第二章 词法分析2.1 完成下列选择题:(1) 词法分析器的输出结果是。
a. 单词的种别编码b. 单词在符号表中的位置c. 单词的种别编码和自身值d. 单词自身值(2) 正规式M1和M2等价是指。
a. M1和M2的状态数相等b. M1和M2的有向边条数相等c. M1和M2所识别的语言集相等d. M1和M2状态数和有向边条数相等(3) DFA M(见图2-1)接受的字集为。
a. 以0开头的二进制数组成的集合b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合d. 含偶数个0的二进制数组成的集合【解答】(1) c (2) c (3) d图2-1 习题2.1的DFA M2.2 什么是扫描器?扫描器的功能是什么?【解答】 扫描器就是词法分析器,它接受输入的源程序,对源程序进行词法分析并识别出一个个单词符号,其输出结果是单词符号,供语法分析器使用。
通常是把词法分析器作为一个子程序,每当词法分析器需要一个单词符号时就调用这个子程序。
每次调用时,词法分析器就从输入串中识别出一个单词符号交给语法分析器。
2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机,其中f 定义如下:f(x,a)={x,y} f {x,b}={y}f(y,a)=Φ f{y,b}={x,y}试构造相应的确定有限自动机M ′。
【解答】 对照自动机的定义M=(S,Σ,f,So,Z),由f 的定义可知f(x,a)、f(y,b)均为多值函数,因此M 是一非确定有限自动机。
先画出NFA M 相应的状态图,如图2-2所示。
图2-2 习题2.3的NFA M 用子集法构造状态转换矩阵,如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名,形成表2-2所示的状态转换矩阵,即得到 M ′=({0,1,2},{a,b},f,0,{1,2}),其状态转换图如图2-3所示。
表2-2 状态转换矩阵将图2-3所示的DFA M ′最小化。
第二章高级语言及其语法描述1、设有文法G[S]:S→NN→D|NDD→0|1|2|…|9试写出028和4321的最左推导和最右推导过程。
2、证明文法G[S]是二义性文法:S→if E then S else S |if E then S |sE→0|13、设有文法G[E]:E→E-T|TT→T/F|FF→i|(E)(1)试写出i/(i-i-i)的推导树。
(2)试写出(F-i)/F的短语、简单短语和句柄。
4、设∑={0,1},请给出∑上下列语言的文法(1)所有以0开头的串(2)所有以0开头,以1结尾的串5、证明文法G1和G2等价G1:S→0S1,S→01G2:A→0R,A→01,R→A1第三章有限状态自动机和词法分析1、请用中文描述下列正规式表示的正规集(1)0(0|1)*0(2)0*10*10*10*2、试写出∑={0,1}上下列集合的正则表达式:(1)所有以1开始和结束的符号串。
(2)恰含有3个1的所有符号所组成的集合。
(3)集合{01,1}。
(4)所有以111结束的符号串。
3、试写出∑={0,1}上下述集合的正则表达式: (1)试写出非负整数集的正则表达式。
(2)试写出以非5数字为头的所有非负整数集的正则表达式。
4、试将图3.1中所示的有限状态自动机M 最小化。
图3.1 M 的状态转换图5、设∑={a,b},试构造下述正则表达式的确定性有限状态自动机: (1)a(a|b)*baa (2)(a|b)*bbb *6、对于下列的状态转换矩阵:(1)分别画出相应的状态转换图。
(2)用自然语言分别描述它们所识别的输入串的特征 7、将图3.2所示的非确定的有限状态自动机确定化和最小化。
图3.2 非确定的有限状态自动机M第四章 自顶向下语法分析 1、从下列文法中消去左递归。
(1)S→Aa|bA→Ac|Sd(2)A→A∨B|BB→B∧C|CC→⌝D|DD→(A)|i2、请消去下面文法G[S]中的回溯G[S]:S→aBc|aB→bB|ε3、有文法G[S]:S→ABA→a|εB→b|ε(1)验证该文法是LL(1)文法;(2)请构造预测分析表4、考虑文法G[A]:A→aABc|d|εB→Bb|b(1)改写为LL(1)文法;(2)请构造预测分析表(3)给出句子adbc的分析过程第五章自底向上语法分析1、请对下列文法G[S]构造算符优先分析表S→bAbA→(B|aB→A a)2、文法G[S]:S→S(SaS→b该文法是LR(0)还是SLR(1)文法?3、文法G[A]:A→(A)|a构造该文法的LR(0)分析表,并请描述((a))的分析过程。
编译原理第二章练习题
专业班级: 学号: 姓名: 一,单选题
1.给定文法:A →bA|cc,下面的符号串为该文法句子的是( )。
① cc ② bcbcc ③ bccbcc ④ bbbcc
A. ①④
B. ①②③
C. ①③
D. ②③④
2.文法G[Z]和语言L ( G[Z ])存在如下关系( )。
A.一一对应:一个文法对应唯一的语言;并且反过来,一 个语言对应唯一的文法。
B.一个语言对应唯一的文法,反之则不然。
C.一个文法对应唯一的语言,反之则不然。
D.若G 为非二义性文法,则C 是正确的;若G 为二义性文法
,则一个文法不对应唯一的语言。
3. 有文法G[E]:E →-EE , E →-E ,E →a|b|c 则文法的句子--a -bc 的所有可能的语法树有( )棵。
A. 1
B. 2
C. 4
D. 3
4.有文法G[S],如果S * x ,( x ∈V ),则x 是( )。
A. 句型
B. 句子
C. A 和B
D. 非A 和B
二.构造一个上下文无关文法G ,使得:
L(G)={ m m b a
2 |m>0}
三.已知文法G[E]: E →ET+ | T
T →TF* | F
F →FP ↑| P
P →(E) | i
有句型TF*PP ↑+,问此句型的短语,简单短语和句柄是什么?(画语法树说明)
四.请用语法树证明文法G[s]是二义性的,G[s]:
S→SS | (S) | ( )。
五.已知文法G[Z]:Z→AB
A→aAb |ab
B→Bc | ε则,L(G[Z] )=?。
第2章习题解答1.文法G[S]为:S->Ac|aBA->abB->bc写出L(G[S])的全部元素[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}2.文法G[N]为:N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么?[答案]G[N]的语言是V。
V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D……D3.已知文法G[S]:Sf dAB Af aA|a B|bB问:相应的正规式是什么?G[S]能否改写成为等价的正规文法? [答案]正规式是daa*b* ;相应的正规文法为(由自动机化简来):G[S]:S —dA A —a|aB B —aB|a|b|bC C —bC|b也可为(观察得来):G[S]:S —dA A —a|aA|aB B —bB| &4.已知文法G[Z]:Z->aZb|ab写出L(G[Z])的全部元素。
[答案]Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={a n b n|n>=1}5.给出语言{a n b n c1 n>=1,m>=0}的上下文无关文法。
[分析]本题难度不大,主要是考上下文无关文法的基本概念。
上下文无关文法的基本定义是:A-> B ,A € Vn ,B€( VnU Vt) *,注意关键问题是保证a n b n的成立,即“ a与b的个数要相等”,为此,可以用一条形如A->aAb|ab的产生式即可解决。
[答案]构造上下文无关文法如下:S->AB|AA->aAb|abB->Bc|c[扩展]凡是诸如此类的题都应按此思路进行,本题可做为一个基本代表。
基本思路是这样的:要求符合a n b n c m,因为a与b要求个数相等,所以把它们应看作一个整体单元进行,而c m做为另一个单位,初步产生式就应写为S->AB,其中A推出a n b n,B推出c m。
编译原理习题参考答案第⼆章2.构造产⽣下列语⾔的⽂法(2){a n b m c p|n,m,p≥0}解: G(S) :S→aS|X,X→bX|Y,Y→cY|ε(3){a n # b n|n≥0}∪{cn # dn|n≥0}解: G(S):S→X,S→Y,X→aXb|#, Y→cYd|# }(5)任何不是以0 打头的所有奇整数所组成的集合解:G(S):S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8, J→1|3|5|7|9}(6)(思考题)所有偶数个0 和偶数个1 所组成的符号串集合解:对应⽂法为 S→0A|1B|ε,A→0S|1C B→0C|1S C→1A|0B3.描述语⾔特点(2)S→SS S→1A0 A→1A0 A→ε解:L(G)={1n10n11n20n2… 1nm0nm |n1,n2,…,nm≥0;且n1,n2,…nm 不全为零}该语⾔特点是:产⽣的句⼦中,0、1 个数相同,并且若⼲相接的1 后必然紧接数量相同连续的0。
(5)S→aSS S→a解:L(G)={a(2n-1)|n≥1}可知:奇数个a5. (1) 解:由于此⽂法包含以下规则:AA→ε,所以此⽂法是0 型⽂法。
7.解:(1)aacb 是⽂法G[S]中的句⼦,相应语法树是:最右推导:S=>aAcB=>aAcb=>aacb最左推导:S=>aAcB=>aacB=>aacb(3)aacbccb 不是⽂法G[S]中的句⼦aacbccb 不能从S推导得到时,它仅是⽂法G[S]的⼀个句型的⼀部分,⽽不是⼀个句⼦。
11.解:最右推导:(1) S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb上⾯推导中,下划线部分为当前句型的句柄。
对应的语法树为:3 假设M:⼈ W:载狐狸过河,G:载⼭⽺过河,C:载⽩菜过河6 根据⽂法知其产⽣的语⾔是L={a m b n c i| m,n,i≧1}可以构造如下的⽂法VN={S,A,B,C}, VT={a,b,c}P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c} 其状态转换图如下:7 (1) 其对应的右线性⽂法是:A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B(2) 最短输⼊串011(3) 任意接受的四个串: 011,0110,0011,000011(4) 任意以1 打头的串.9.对于矩阵(iii)(1) 状态转换图:(2) 3型⽂法(正规⽂法)S→aA|a|bB A→bA|b|aC|a B→aB|bC|b C→aC|a|bC|b(3)⽤⾃然语⾔描述输⼊串的特征以a 打头,中间有任意个(包括0个)b,再跟a,最后由⼀个a,b 所组成的任意串结尾或者以b 打头,中间有任意个(包括0个)a,再跟b,最后由⼀个a,b 所组成的任意串结尾。
第二章高级语言及其语法描述本章要点1. 程序语言的定义;2. 高级程序语言一般结构和主要共同特征;3. 正确理解上下文无关文法基本概念,包括:文法的定义、推导、句型、句子、语言、语法树、二义性等;4. Chomsky文法分类;本章目标掌握和理解程序语言的定义、高级语言的一般特征及程序语言的语法描述。
本章重点1. 语法,词法规则与语法规则;2. 语义和语义规则;3. 数据类型与操作;4. 推导,最左推导和最右推导;5. 语法分析树和二义性;本章难点1. 二义性文法;2. Chomsky各个文法类;作业题一、单项选择题:(按照组卷方案,至少15道小题)1. Chomsky把文法分成四种类型,0型、1型、2型和3型。
3型文法也称为,2型文法也称为。
a.上下文无关文法b.上下文相关文法c.正则文法d.短语文法2. 许多广为使用的语言,如Fortran、C、Pascal等,属于。
a. 强制式语言b. 应用式语言c. 基于规则的语言d. 面向对象的语言3. 设G是一个文法,S是开始符号。
若S⇒*α,α∈(V T∪V N)*,则称α是一个。
a. 句子b. 句型c. 推导d. 语言4. 一个数据类型通常包括的三种要素中,没有下面的。
a. 用于区别这种类型的数据对象的属性;b. 这种类型的数据对象可以具有的值;c. 对这种类型的数据对象的内存分配;d. 可以作用于这种类型的数据对象的操作;5. Chomsky把文法分成四种类型,其中,也称正规文法a. 0型b. 1型c. 2型d. 3型6. 语言的词法规则一般用Chomsky的型文法来描述:a. 0b. 1c. 2d. 37. 文法S→(L)|aL→L,S|S中,下面是该文法中的终结符号。
a. Sb. ,c. Ld. |8. 文法G所描述的语言是的集合。
a. 文法G的字母表∑中的所有符号组成的符号串;b. 文法G的字母表∑的闭包∑*中的所有符号串;c. 文法G的识别符号推出的所有符号串;d. 文法G的识别符号推出的所有终结符号串;9. 语言L={αcα | α∈(a|b)*},该语言是_____________语言。
第2章习题1、文法G[S]为:S->Ac|aBA->abB->bc写出L(G[S])的全部元素。
[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}2、令文法G为:N →D|NDD → 0|1|2|3|4|5|6|7|8|9(1)G的语言L(G)是什么?(2)给出句子0568的最左推导和最右推导。
3、令文法为:E→T|E+T|E-TT→F|T*F|T/FF→(E)|i(1)i+i*i、i*(i+i)的最左推导和最右推导;(2)给出i+i+i、i+i*i和i-i-i的语法树。
解答:(1)i+i*i、i*(i+i)的最左推导分别为:E=>T=>E+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iE=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=>i*(i+i)i+i*i、i*(i+i)的最右推导分别为:E=>T=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*iE=>T=>T*F=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>T*(i+i)=>F*(i+i)=>i*(i+i)4、写一个文法,使其语言是奇数集,要求:(1)允许0开头; (2)不允许0开头。
[答案](1)允许0开头的偶正整数集合的文法E->NT|G|SFMT->NT|GN->D|1|3|5|7|9D->0|GG->2|4|6|8S->NS|εF->1|3|5|7|9|GM->M0|0(2)不允许0开头的偶正整数集合的文法E->NT|DT->FT|GN->D|1|3|5|7|9D->2|4|6|8F->N|0G->D|05、证明下面的文法是二义的: S→iSeS|iS|i 对于句子iiiei,存在如下两个最右推导:S=>iSeS=>iSei=>iiSei=>iiieiS=>iS=>iiSeS=>iiSei=>iiiei由此,该文法是二义的。
例题2.1 是非题1.因名字都是用标识符表示的,故名字与标识符没有区别。
()2.正规文法产生的语言都可以用上下文无关文法来描述。
()3.上下文无关文法比正规文法具有更强的描述能力。
()分析1.标识符是高级语言中定义的字符串,一般是以英文字母开头(包括大小写字母)的,由数字、字母和一些特殊字符(如下划线等)组成的一定长度(不同的高级语言对标识符的长度的规定不同)的字符串,它只是一个标志,没有其它含义。
名字是用标识符表示的,但名字不仅仅是一个字符串,它还具有属性和值,就象一个人的名字不仅仅是一个符号,对于认识这个人的人来说,它还代表着这个人,因此本题错。
2.乔姆斯基把文法分成4种类型,从4种文法的形式化描述来看,它们的差别主要在对规则形式的约束上。
0型文法的规则形式是:每个产生式α→β都满足,α∈(VN ∪VT)*且至少含有一个非终结符,β∈(VN∪VT)*,0型文法也叫短语文法。
1型文法的规则形式是:每个产生式α→β均满足|α|≤|β|,仅仅S→ε例外,且S不得出现在任何产生式的右部,1型文法也称上下文有关文法,从两种文法的规则形式来看,1型文法对规则形式的约束比0型文法强,1型文法能描述的语言0型文法也能描述,而0型文法能描述的语言1型文法不一定能够描述,1型文法是0型文法的特例。
2型文法的规则形式是A→β,其中A∈VN ,β∈(VN∪VT)*,2型文法也称上下文无关文法,分析2型文法的规则形式不难发现,2型文法是1型文法的特例,也是0型文法的特例。
3型文法的规则形式是A→αB或A→α,其中α∈,A、B∈VN,3型文法也称正规文法,可以看出3型文法是前面3种文法的特例。
从上面的分析可以,正规文法是上下文无关文法的特例,可以用正规文法描述的语言,其正规文法描述的形式也是上下文无关文法的描述形式,即可以用上下文无关文法描述,因此本题对。
3.上下文无关文法是2型文法,正则文法是3型文法,从上题的分析可以看出,3型文法是2型文法的特例,3型文法可以描述的语言都可以用2型文法来描述,而2型文法可以描述的语言则不一定能用3型文法来描述。
1.构造正规式的DFA。
(1)1(0|1)*101状态转换表:化简后得:(2)(a|b)*(aa|bb)(a|b)*化简后得;2.将下图确定化和最小化。
⇒解: 首先取A=ε-CLOSURE({0})={0},NFA确定化后的状态矩阵为:NFA确定化后的DFA为:⇒将A,B 合并得:⇒3.构造一个DFA,它接受∑={0,1}上所有满足如下条件的字符串,每个1都有0直接跟在后边。
解:按题意相应的正规表达式是0*(0 | 10)*0*构造相应的DFA,首先构造NFA为DFA为4.给出NFA等价的正规式R。
方法一:首先将状态图转化为得0,1消去其余结点NFA等价的正规式为(0|1)*11方法二:NFA→右线性文法→正规式A→0A|1A|1BB→1CC→εA=0A+1A+1BB=1A=0A+1A+11A=(0+1)*11→(0|1)*115.试证明正规式(a|b )*与正规式(a *|b *)*是等价的。
证明: (1)正规式(a|b)*的NFA 为=>其最简DFA 为(2)正规式(a*|b*)*的 NFA 为: 其最简化DFA 为:DFA由于这两个正规式的最小DFA 相同,所以正规式(a|b)*等价于正规式(a*|b*)*。
6.设字母表∑={a,b},给出∑上的正规式R=b*ab(b|ab)*。
(1)试构造状态最小化的DFA M,使得L(M)=L(R)。
(2)求右线性文法G,使L(G)=L(M)。
解: (1)构造NFA:(2)将其化为DFA,转换矩阵为:再将其最小化得:(2)对应的右线性文法G=({X,W,Y},{a,b},P,X)P: X→aW|bX W→b Y|b y→a W|bY|b3.8文法G[〈单词〉]为:〈单词〉-〉〈标识符〉|〈整数〉〈标识符〉-〉〈标识符〉〈字母〉|〈标识符〉〈数字〉|〈字母〉〈整数〉-〉〈数字〉|〈整数〉〈数字〉〈字母〉-〉A|B|C〈数字〉|->1|2|3(1)改写文法G为G’,使L(G’)=L(G)。