




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、2008-10-282.1 考虑下面的上下文无关文法:S SS+ | SS* |aa)试说明如何使用该文法生成串aa+a*。b)试为aa+a*构造一个分析树。c)该文法产生的语言是什么?ANSWER:a)S SS* SS+S* aa+a*b)图c)以a为变量,+和*为二元操作符的后缀表达式22.2 下面的文法产生什么语言?a)S0S1|010n1n(n=1,2,)b) S+SS|-SS|a以a为变量,+和-为二元操作符的前缀表达式c)SS(S)S|括号的匹配d)SaSbS|bSaS| 由相同数目的a、b组成的字符串,或者空串。3e)Sa|S+S|SS|S*|(S)以a为数据元素,具有合并、连接
2、、闭包和括号操作符的表达式。a是表达式,若S是表达式则S+S(表达式的合并)、SS(表达式的串联)、S*(表达式的闭包运算)都是表达式。4注意事项不是终结符,应该省略。但是如果包含空串,则需特别强调。产生式可以交替使用描述生成何种语言时,应当描述完整的字母表52.3 练习2.2中哪些文法具有二义性?c、d、e具有二义性。可通过画某个串的分析树来说明67 S aSbS | bSaS |a) 试说明此文法是二义性的. 可以从句子abab有两个不同的最左推导来说明. S aSbS abS abaSbS ababS abab lm lm lm lm lm S aSbS abSaSbS abaSbS a
3、babS abab lm lm lm lm lm 句子abab有两个不同的最左推导, 该句子是二义性的 . 所以此文法是二义性的.8(b) 对于句子abab构造两个相应的最右推导. S aSbS aSb abSaSb abSab abab rm rm rm rm rm S aSbS aSbaSbS aSbaSb aSbab abab rm rm rm rm rm (c)对于句子abab构造两个相应的分析树.判断一个文法是否具有二义性,可以通过判断是否存在一个具有多棵分析树的记号串。3.3 识别下面的各段程序中构成记号的词素,并给出每个记号的合理属性值: 程序:int max(i,j)int i
4、,j;/*返回整数i和j的最大者*/return ij? i:j;9词素记号属性intintmaxid指向符号表max条目的指针(标点符号左括号iid指向符号表i条目的指针,标点符号逗号jid指向符号表j条目的指针)标点符号右括号;标点符号分号returnreturn操作符大于号?操作符问号:操作符冒号标点符号右大括号标点符号左大括号10注意事项1.记号token(终结符),模式pattern,词素lexeme(源程序的字符序列)2.可构成token(记号)的:关键字,操作符,标识符,常量,字符串,标点符号3.每个词素都要一一记录4.注释是在词法分析时忽略的,而词法分析器对程序采取非常局部的观
5、点。 5.不是每个token都要有属性1112(a) 0 ( 0 | 1)* 0(b) ( ( | 0 ) 1* ) *由0和1组成且以0开始和结束的符号串全体.(c) ( 0 | 1 )* 0 ( 0 | 1) ( 0 | 1)由0和1组成的符号串全体.由0和1组成且以000,001,010或011结束的符号串全体.长度大于等于3且倒数第3个字符为0的01符号串全体.3.6 试描述下列正规表达式所表示的语言:13(d) 0*10*10*10*(e) ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )*有且只有3个1的
6、0、1字符串全体.带有偶数个0和偶数个1的由0和1组成的符号串全体.带有偶数个a和偶数个b的符号串全体.( (aa|bb) | (ab|ba) (aa|bb)* (ab|ba) )*注意事项在描述语言的时候应该准确,精简。语言给定字母表上任意一个字符串集合。句子(字)属于语言的字符串,字母表中符号的有穷序列。空字符串和空集143.7 试写出下列语言的正规定义:a)包含5个元音的所有字母串,其中元音按顺序出现。X=辅音字母全体(X|(A|a)*(A|a)(X|(E|e)*(E|e)(X|(I|i)*(I|i)(X|(O|o)*(O|o)(X|(U|u)*(U|u)X*15保证元音字母至少出现一次
7、b) 按词典递增序排列的所有字母串。( a | A)* ( b | B)* ( c | C)*.( z | Z)*1617 d)没有重复出现的数字的数字符号串全体. e) 最多有一个重复出现的数字的数字符号串全体令 ri = i | , i=0,1,2,.,9 R0|R1|R2|.|R9记为 Ri i(0,1,2.,9)P(0,1,2.,9)表示0,1,2.,9的全排列 ri0ri1.ri9 i0i1. i9P(0,1,2.,9) i ri0ri1.ri9i(0,1,2.,9) i0i1. i9P(0,1,2.,9)18 f) 带有偶数个0和奇数个1的由0和1组成的符号串全体. E为带有偶数个
8、0和1的由0和1组成的符号串全体.即 ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )* E 1 E | E 0 E 1 E 0 E h) 不包含子串011的由0和1组成的符号串全体. i) 不包含子序列011的由0和1组成的符号串全体1*0* (10* |) 1*( 0 | (01) )*19 h) 不包含子串011的由0和1组成的符号串全体. i) 不包含子序列011的由0和1组成的符号串全体1*( 0 | (01) )*1*0* (10* |) (00 | 11) ( (01 | 10) (00 | 11) (
9、01 | 10) (00 | 11) ) 所有由偶数个0和偶数个1构成的串。另外,和该正规式等价的正规式有( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 。更简单的描述( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 它是基于这样的考虑,满足要求的最简单的串有三种形式(空串除外):1002113(01 | 10) (00 | 11) (01 | 10)它们任意多次的重复构成的串仍然满足要求。20写出语言“由偶数个0和奇数个1构成的所有0和1的串”的正规定义。even_0_even_1 (00 | 11
10、) ( (01 | 10) (00 | 11) (01 | 10) (00 | 11) ) even_0_odd_1 1 even_0_even_1 |0 (00 | 11) (01 | 10) even_0_even_1对于偶数个0和奇数个1构成的串,其第一个字符可能是0或1。1.如果是1,那么剩下的部分一定是偶数个0和偶数个1。2.如果是0,那么经过若干个00或11,一定会出现一个01或10,才能保证0的个数是偶数,1的个数是奇数。若串还没有结束,剩余部分一定是偶数个0和偶数个1。21注意事项正规定义:为了让正规表达式的表示简洁,可以对正规式命名。 d1 r1 d2 r2 . . . dn
11、 rn各个di的名字都不同每个ri都是d1, d2, , di-1 上的正规式 应该写出正规定义或者正则表达式,状态图必须化简223.16 用算法用算法3.3 构造非确定有穷自动机,给出构造非确定有穷自动机,给出处理输入串处理输入串ababbab的状态转换序列:的状态转换序列:23ababbab的状态转换序列24c) (|a)b*)*25ababbab的状态转换序列263.17 用算法3.2把练习3.16中的NFA转换成DFA。给出它们处理串ababbab的状态转换序列。a)(a|b)*-closure(0) = 0,1,2,4,7 = A-closure(move(A,a) = -closu
12、re(3) = 1,2,3,4,6,7 = B-closure(move(A,b) = -closure(5) =1,2,4,5,6,7 = C-closure(move(B,a) = -closure(3) = 1,2,3,4,6,7-closure(move(B,b) = -closure(5) = 1,2,4,5,6,72728-closure(move(C,a) = -closure(3) = 1,2,3,4,6,7-closure(move(C,b) = -closure(5) = 1,2,4,5,6,7 则DFA为:3.17 用算法3.2把练习3.16中的NFA转换成DFA。给出它
13、们处理串ababbab的状态转换序列。-closure(0) = 0,1,2,3,4,6,7,8,10,11=A-closure(move(A,a) = -closure(5) = 1,2,3,4,5,6,7,8,10,11=B-closure(move(A,b) = -closure(9) =1,2,3,4,6,7,8,9,10,11=C29c) ( |a)b*)*-closure(move(B,a) = -closure(5) = 1,2,3,4,5,6,7,8,10,11=B-closure(move(B,b) = -closure(9) = 1,2,3,4,5,6,7,8,10,11=
14、C-closure(move(C,a) = -closure(5) = 1,2,3,4,5,6,7,8,10,11=B-closure(move(C,b) = -closure(9)= 1,2,3,4,5,6,7,8,10,11=C则DFA为:30画状态图注意事项应明确地指出开始状态应明确地指出终止状态,不一定只有一个NFA转化为DFA时,NFA的状态集合包含有接受状态,那么对应的DFA状态也是接受状态 313.22 如果两个正规表达式的最少状态如果两个正规表达式的最少状态DFA除状态名以外完除状态名以外完全相同,则这两个正规表达式等价。全相同,则这两个正规表达式等价。(a*|b*)*A: -
15、closure(0) = 0,1,2,3,5,6,7,9,10,11,B: -closure(move(A,a) = -closure(4) = 1,2,3,4,5,6,7,9,10,11C: -closure(move(A,b) = 1,2,3, 6,7,8,9,10,113233A状态状态abABCBBCCBC注意事项该题为证明题,做题思路为构造各个正规表达式的最小状态DFA。应该有中间步骤。a)和c)可以见3.17中的解答。343.23 对于下列正规表达式构造最小状态的DFA.解题步骤:1,从正则表达式到NFA2,从NFA到DFA(子集构造法)3,最小化DFA(算法3.6)353.23
16、对于下列正规表达式构造最小状态的DFA.a) (a|b)*a(a|b)36(b) (a|b)*a(a|b)(a|b) 解法一37AstartBabHGaCDaaaEFabaaabbbb最小化DFAa1start2a43babNFAbab) (a | b) a (a | b) (a | b) 解法二3820134567aabbaabbstartbaababab图图1.11 接收接收(a | b) a (a | b) (a | b)的的DFA20134567aaba,baabbstart图图1.12 构造过程的第一步构造过程的第一步c) (a | b) a (a | b) (a | b) (a |
17、 b)一共有16个状态,满足定理3.23 d)正规表达式(a | b) a (a | b) (a | b) (a | b)共有n-1个(a | b),对应的任何一个DFA至少有2n个状态。证明方法如前图方法所示。39400142233567119101213813141517182119202216startabaaaabbb图:带图:带转移的转移的NFA第一步:第二步A= -closure(0) B= -closure(3,8) C= -closure(5) D= -closure(3,8,10) E= -closure(5,12) F= -closure(3,8,10,15) G= -cl
18、osure(5,12,17) H= -closure(3,8,15) I= -closure(5,17) J= -closure(3,8,10,15,20) K= -closure(5,12,17,22) 41L= -closure(3,8,15,20) M= -closure(5,17,22) N= -closure(3,8,10,20) O= -closure(5,12,22) P= -closure(3,8,20) Q= -closure(5,22) 状态状态abABCBDECBCDFGEHIFJKGLMHNOIPQJIKKLMLNOMPQNFGOHIPDEQBC42状态转移表:状态转移表:第三步:应用算法3.6消除状态C之后得到的最少状态DFA:给出奇数个0奇数个1的正规表达式44012311110000start接受奇数个接受奇数个0和奇数个和奇数个1的的的的DFA偶0偶1
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 编辑中级职称试题及答案
- 深度解读2025年汽车共享平台运营数据与用户忠诚度提升策略报告
- 2025南航招聘笔试题目及答案
- 积极应变面试题及答案
- 有效团队沟通的商务英语试题及答案
- 教师教育教学反思在政策导向下的调整与适应研究试题及答案
- 电池技术进步对市场的效应试题及答案
- 深入解读2025年创业扶持政策与企业责任的关系试题及答案
- 教育游戏化在儿童教育中的创新应用:2025年教学设计策略与实践探索报告
- 深入探讨音符的组合与构建2025年乐理考试试题及答案
- GA/T 751-2024公安视频图像屏幕显示信息叠加规范
- 2025至2030中国长链氯化石蜡行业供需现状与前景策略研究报告
- 租地盖大棚合同协议
- 自体输血知识培训课件
- 人教A版高一下册必修第二册高中数学8.6.2直线与平面垂直【课件】
- 小学生涯课件
- 西藏拉萨中学2024-2025学年高三第二学期英语试题4月月考试卷含解析
- GB/T 45421-2025城市公共设施非物流用智能储物柜服务规范
- 档案相关法律法规知识复习试题及答案
- 汉语方言与地方文化认同的关系研究论文
- 西北四省(陕西山西青海宁夏)2025届高三下学期第一次联考数学试卷含答案
评论
0/150
提交评论