第3章词法案例.ppt

  1. 1、本文档共101页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 3、确定化为DFA M’ * * 4、写出实现其功能的程序 PROGRAM LEX(input,output) BEGIN TOKEN:=’’; getchar; CASE char OF ‘0’..’9’:[while char IN[‘0’..’9’]DO BEGIN TOKEN:=TOKEN+char; getchar END; retract; IF VAL(token,value) THEN return(4,value)]; ‘A’..’Z’:[while char IN[‘A’..’Z’,’0’..’9’]DO BEGIN TOKEN:=TOKEN+char; getchar END; retract; Return(5,token)]; ‘*’:[getchar; IF char=’*’ THEN Return(7,-) ELSE [retract;Return(6,-)] ELSE:ERROR; END{of case}; END; * * 本章小结 词法分析概况 状态转换图 确定型有穷状态自动机 非确定型有穷状态自动机 正则表达式 词法分析程序的实现 词法分析器的自动生成 * * 基本要求 了解词法分析程序的功能和实质。 明确DFA与NFA的区别,掌握把NFA变为DFA的方法; 熟练掌握把正则文法变为状态转换图以及写出有穷状态自动机的方法。 掌握词法分析程序的基本实现方法。 * * 习题课 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 举例 例:正则表达式(A|B){A|B|0|1}的转换系统的构造过程如下: S Z (A|B){A|B|0|1} S Z (A|B) {A|B|0|1} S Z A B ? ? A|B|0|1 S Z A B ? ? 1 0 A B * * 概念1. 假设I是NFA M’的状态集的一个子集,我们定义ε-CLOSURE(I)为(I的ε-闭包)。 (1)若S∈I,则S∈ε-CLOSURE(I) (2)若S∈I ,则从s出发经过任意条ε弧而达到的状态s’,有s’∈ε-CLOSURE(I) 例1. 五、正规式和有限自动机的等价性 若I={1, 3},则ε-CLOSURE(I) ={1, 3, 2, 8} * * 概念2. 假定I是M’的状态子集,a是Σ中的字符,定义Ia= ε-CLOSURE(J),其中J是I中任意状态出发(跳过前面任意多条ε弧),经过一条a弧而能达到的状态结的全体。 例2.同例1 DFA, Ia={5,6,2} 利用概念1和概念2,便可把NFA确定化。 五、正规式和有限自动机的等价性 * * 五、正规式和有限自动机的等价性 令 ,构造一张如下的表,此表第0列为状态子集I,第1至m列分别为状态子集 ,设第一行第0列为ε-CLOSURE(X),,其中X为NFA M’的初态,求出第一个的 ,如果某个Iai(i=1,…,m)未曾在第0列中列出,则把Iai补入状态子集集合I中,即列于第0列新的一行。 重复上述各步,直至所有行的Iai(i=1,…,m)均在第0列I中出现过为止。这种循环必将在有限步内中止。(因为S是有限状态集,所以S中状态的组合数也是有限的) * * 显然,这张表可以看成一个状态转换表,也就是说可把I中每个子集看成一个状态,而状态转换表唯一地刻划了一个DFA M,其初态为该表的第1行第0列,含有原NFA M’终态的子集为新的终态。(证毕) 推论:一个子集是正规的,当且仅当它可由一个DFA(或NFA)所识别。 五、正规式和有限自动机的等价性 * * 例:设计一个DFA M,它识别二进制偶数(不以0开头的无符号数) 解: 1. 写出正规式 1(1|0)* 0 2. 画出NFA M’ 细化为: 3. 确定化为DFA M 五、正规式和有限自动机的等价性 * * 五、正规式和有限自动机的等价性 或: * * 举例 正则表达式{a}|{(a|b)a}的相应转换系统与状态转换图的构造过程。 A B {

文档评论(0)

1112111 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档