第二、三章习题讲分解优秀PPT.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《第二、三章习题讲分解优秀PPT.ppt》由会员分享,可在线阅读,更多相关《第二、三章习题讲分解优秀PPT.ppt(48页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、2008-10-282.1 考虑下面的上下文无关文法:S SS+|SS*|aa)试说明如何运用该文法生成串aa+a*。b)试为aa+a*构造一个分析树。c)该文法产生的语言是什么?d)ANSWER:e)S SS*SS+S*aa+a*f)图g)以a为变量,+和*为二元操h)作符的后缀表达式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 ababS abab
3、 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,j;/*返回整数i和j的最大者
4、*/return ij?i:j;9词素记号属性intintmaxid指向符号表max条目的指针(标点符号左括号iid指向符号表i条目的指针,标点符号逗号jid指向符号表j条目的指针)标点符号右括号;标点符号分号returnreturn操作符大于号?操作符问号:操作符冒号标点符号右大括号标点符号左大括号10留意事项1.记号token(终结符),模式pattern,词素lexeme(源程序的字符序列)2.可构成token(记号)的:关键字,操作符,标识符,常量,字符串,标点符号3.每个词素都要一一记录4.注释是在词法分析时忽视的,而词法分析器对程序实行特别局部的观点。5.不是每个token都要有属
5、性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的0、1字符串全体.带有偶数个0和偶数个1的由0和1组成的符号串全体.带有偶数个a和偶数个b的符号串全体.(aa|bb)|(ab|ba)(aa|bb
6、)*(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保证元音字母至少出现一次b)按词典递增序排列的全部字母串。(a|A)*(b|B)*(c|C)*.(z|Z)*1617 d)没有重复出现的数字的数字符号串全体.e)最多有一个重复出现的数字
7、的数字符号串全体令 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为带有偶数个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)不包含子序
8、列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)(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)它们
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 习题 分解 优秀 PPT
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内