- 1、本文档共87页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
面临当前输入符号都能唯一确定选择哪个产生式进行推导。 若有文法G1[S]: S → pA |qB A →cAd|a B →d B |c 识别输入串w= pccadd是否是G1[S]的句子 若有文法G2[S]: S → Ap |Bq A →a|cA B →b|dB 识别输入串w=ccap是否是G2[S]的句子,那么试探推出输入串的推导过程为 : 若有文法G3[S]: S → aA|d A →bAS|ε 识别输入串w=abd是否是G3[S]的句子 词法分析程序的功能:逐个读入源程序字符并按照构词规则切分成一系列单词。 输入:源程序 输出:单词 (种类编码,单词自身的属性值) 4.2单词的描述工具4.2.1正规文法 例 文法G=(VN,VT,P,S) VN ={标识符,字母,数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={标识符→字母| 标识符→标识符字母 标识符→标识符数字 字母→a,…, 字母→z 数字→0,…, 数字→9 } S=标识符 4.2.2正规式 1)定义(正规式和它所表示的正规集): 设字母表为?,辅助字母表?`={?,?,?,?,?,?,?}。 1. ?和?都是?上的正规式,它们所表示的正规集分别为{?}和{ }; 2.任何a? ?,a是?上的一个正规式,它所表示的正规集为{a}; 3.假定e1和e2都是?上的正规式,它们所表示的正规集分别为L(e1)和L(e2),那么,(e1), e1? e2, e1?e2, e1?也都是正规式,它们所表示的正规集分别为L(e1), L(e1)?L(e2), L(e1)L(e2)和(L(e1))?。 4.仅由有限次使用上述三步骤而定义的表达式才是?上的正规式,仅由这些正规式所表示的集合才是?上的正规集。 其中的“?”读为“或”(也有使用“+”代替 “?” 的);“? ”读为“连接”;“?”读为“闭包”(即,任意有限次的自重复连接)。在不致混淆时,括号可省去,但规定算符的优先顺序为“?”、“? ”、“?” 。连接符“? ”一般可省略不写。“?”、“? ”和“?” 都是左结合的。 例子 令?={a,b}, ?上的正规式和相应的正规集的例子有: 正规式 正规集 a {a} a?b {a,b} ab {ab} (a?b)(a?b) {aa,ab,ba,bb} a ? {? ,a,a, ……任意个a的 串} 正规式 正规集 (a?b)? {? ,a,b,aa,ab ……所有由a 和b组成的串} (a?b)?(aa?bb)(a?b)? {??上所有含有两个相继 的a或两个相继的b组成 的串} 讨论下面两个例子 例3.1 令?={l,d},则?上的正规式 r=l(l ?d) ?定义的正规集为: {l,ll,ld,ldd,……},其中l代表字母,d代表数字,正规式 即是 字母(字母|数字) ? ,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和 多数程序设计语言允许的的标识符的词法规则. 例3.2 ?={d,?,e,+,-}, 则?上的正规式 d?(?dd ?? ? )(e(+?- ??)dd? ??)表示的是无符号数的集合。其中d为0~9的数字。 程序设计语言的单词都能用正规式 来定义. 若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。 例如: e1= (a?b), e2 = b?a 正规式服从的如下的代数规律 设r,s,t为正规式,则有: 1。r?s=s?r “或”服从交换律 2。r?(s?t)=(r?s)?t “或”的可结合律 3。(rs)t=r(st) “连接”的可结合律 4。r(s?t)=rs?rt (s?t)r=sr?tr 分配律 5。 ?r=r, r?=r ?是“连接”的恒等元素 6。 r?r=r 零一律 r?=??r?rr?… “或”的抽取律 练习1 设?={a,b}指出下列正规式的正规集 a(a|b)b ab* a(a|b)* 练习2 设?={a,b,c}则aa*bb*cc*是?上的正规式,求它所表示正规集 4.2.3正规文法和正规式的等价性 对?上的正规式r ,存在一个RG=(VN,VT,P,S):L(G)=L(r)
文档评论(0)