电子商务概论多媒体电子教案-浙江科技学院信息与电子工程学院ppt课件.ppt

《电子商务概论多媒体电子教案-浙江科技学院信息与电子工程学院ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、词法分析掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的转换、DFA的化简理解：正规文法、正规式、DFA的概念、NFA的概念了解：词法分析程序的自动构造工具1$1词法分析的基本概念1.1词法分析的意义识别单词、并标记单词的属性、再转换成统一长度的属性字其它任务词法分析是语法分析的一部分21.2词法分析的输入和输出源程序的输入缓冲区：一分为二的区域词法分析的输出保留字标识符常量运算符界符二元组输出（单词类别，单词值）3例：假定单词类型用整数编码：标识符为1，常数为2，保留字为3，运算符

2、为4，分解符为5。则语句if（bc>9）y＝a；二元式形式的单词序列如下：（3，‘if’）（5，’（’）41.3词法分析实现方法把词法分析作为单独一遍独立出来。使词法分析和语法分析完全独立把词法分析工作穿插在语法分析过程中，即作为语法分析的子程序5$2正规文法和有限自动机2.1正规文法、正规集、正规式正规文法（3型文法）正规集：有正规文法产生的语言正规集是集合，有穷或无穷，可以通过正规式来形式化的表示6例如:用l表示a~z中的任一英文字母，d表示0~9中任一数字。描述标识符的正规文法为：<标识符>→l｜l<字母数

3、字><字母数字>→l｜d｜l<字母数字>｜d<字母数字>描述无符号整数的正规文法：<无符号整数>→d｜d<无符号整数>7正规式的定义（递归）：设A是非空的有限字母表，A＝｛ai

4、i＝1,2,…,n},则：1ε、φ和ai都是∑上的正规式。2若、是正规式，则

5、、•、*、*都是正规式正规式只能通过有限次使用1、2规则获得说明:算符的优先顺序:‘＊’>‘.’>‘｜’‘.’和‘｜’都是左结合仅由字母表A＝｛ai

6、i＝1,2,…,n}上的正规式所组成的语言称谓正规集，记为L（）8正规式正规集(ｅ1)Ｌ(ｅ

7、1)ｅ1｜ｅ2Ｌ(ｅ1)∪Ｌ(ｅ2)ｅ1.ｅ2Ｌ(ｅ1)Ｌ(ｅ2)ｅ1＊(Ｌ(ｅ1))＊9举例：令={a，b}，上的正规式和相应的正规集有正规式正规集a{a}ab{a,b}ab{ab}(ab)(ab){aa,ab,ba,bb}a{,a,aa,…任意个a串}(ab){,a,b,aa,ab……所有由a和b组成的串}10正规式的代数性质设r，s，t是正规式，正规式服从的代数规律是：r｜s=s｜r“或”满足交换律r｜(s｜t)=(r｜s)｜t“或”的结合律(rs)t=r(st)“连接”的结合律r(s｜

8、t)=rs｜rt(r｜s)t=rt｜st分配律εr=rε=rε是“连接”的恒等元素rr=r“或”的抽取律r=rrr…11程序中的单词都能用正规式来定义令l为a~z的字母，d为0~9的数字e1=l(l

9、d)*e1表示标识符集合e2=dd*e2表示无符号整数注：<标识符>→l｜l<字母数字><字母数字>→l｜d｜l<字母数字>｜d<字母数字>正规式比正规文法更容易让人理解单词是按怎样的规律构成的，且可以从某个正规式自动地构造识别程序。122.2正规文法和正规式间的转换等价性：对任意一个正规文法，存在一个定

10、义同一语言的正规式对任意一个正规式，存在一个定义同一语言的正规文法13将∑上的一个正规式r转换成文法G=(VN,VT,S,P)VT=∑,首先形成产生式S→r,S为G的开始符不断利用下面的规则做变换,直到每个产生式最多含有一个终结符为止原产生式变换后产生式规则1A→xyA→xBB→y规则2A→x*yA→xAA→y规则3A→x

11、yA→xA→y其中B为一新非终结符14例:将R=a(a

12、d)*转换成相应的正则文法令转换成文法G=(VN,VT,P,S)其中VT={a,d}，文法开始符为S首先形成S→a(a

13、d)*,然后变换

14、S→aAA→(a

15、d)*A→(a

16、d)AA→εA→aAA→dA最终有产生式：S→aA，A→ε，A→aA，A→dA15将正规文法转换成正规式将每条产生式改写为正规式用代入法解正规式方程组最后只剩下一个开始符号定义的正规式,其中不含非终结符正规文法到正规式的转换规则:文法产生式正规式规则1A→xBB→yA=xy规则2A→xA

17、yA=x*y规则3A→xA→yA=x

18、y16例：将文法G[S]转换成正规式G：S→aA

19、aA→dA

20、d先由产生式得:S=aA

21、aA=d*d将A代入S中得:S=ad*d

22、a利用正规式变换得S=a(

23、d*d

24、ε)=ad*说明:d*d

25、ε=(ε

26、d

27、dd

28、…)d

29、ε=d

30、dd

31、…

32、ε=d*所求正规式为ad*1718根据规则2：A→xA

33、yA=x*y19$3有穷自动机(也称有限自动机)是一种识别装置作用:能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合意义:为词法分析程序的自动构造寻找特殊的方法和工具。分类:确定的有穷自动机(DeterministicF