最新第二章词法分析-1教学讲义PPT.ppt

《最新第二章词法分析-1教学讲义PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章词法分析-12.1扫描处理2.2正则表达式2.3有穷自动机2.4从正则表达式到DFA2.1扫描处理回顾扫描程序的任务从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个有意义的单元，称为记号或单词(Token)记号（单词）单词有若源程序中逻辑上紧密相连的一组字符，这些字符具有集体含义。若干种类型，保留字、标识符、特殊符号2词法分析器的接口词法分析作为独立一遍将字符流的源程序变成单词序列，输出到一个中间文件上，做为语法分析的输入。词法分析作为语法分析的子程序每当语法分析程序需要一个单词时

2、，则调用该子程序，从源程序中分析和返回一个单词独立词法分析器语法分析Token序列源程序附属词法分析器语法分析调用Token源程序词法分析主要研究:词义结构的表示法:正则表达式识别系统:有穷自动机是对正则表达式给出的串格式的识别算法实际编写程序实现有穷自动机的识别过程.2.2正则表达式功能表示字符串的格式正则表达式的定义正则表达式r完全由它所匹配的串集来定义这个集合称为由正则表达式生成的语言,写作L(r)L(r)定义在正规符号的集合上,称为字母表∑2.2.1符号串和语言字母表定义符号的非空有穷集合例如∑={0‚1}Α={a‚b,

3、c}2符号串定义由字母表中的符号组成的任何有穷序列.例如0,00,10是∑={0‚1}的符号串a,ab,aaca是Α={a‚b,c}的符号串符号串的长度一个符号串s的长度,记为

4、s

5、,符号串中含有符号的个数.例如:

6、abc

7、=3空串表示为ε,是长度为0的特殊串{ε}并不等于空集合({})3符号串的运算符号串的连接：设x、y是符号串,它们的连接是把y的符号写在x的符号之后得到的符号串xy例如x="ST"，y="abu"，则xy="STabu"显然εx=xε=x符号串的方幂：把符号串a自身连接n次得到的符号串an=aa…aa例如:

8、a1=aa2=aaa0=ε4语言定义字母表上的一些符号串的集合例如ε是一个语言空集也是一个语言5语言的运算连接L和M的连接记为LMLM={st

9、s∈L,t∈M}例如:L=ab,cdeM=0,1LM=ab0,ab1,cde0,cde1{ε}A=A{ε}=A方幂L的方幂定义为:L0={ε}L1=L,L2=LLLK=LL...…L(k个)闭包L的闭包(记为L*)表示为0个或多个L的连接L*=L0∪L1∪L2∪L3∪…例如：L={0，1}L*=L0∪L1∪L2∪…={ε,0,1,00,01,10,11,000,…}L

10、的正闭包(记为L+)表示1个或多个L的连接L+=L1∪L2∪L3∪…L*=L0∪L+L+=LL*=L*L2.2.2正则表达式的定义语言中描述单词的工具——正则表达式基本正则表达式集合从已有的正则表达式生成新的正则表达式的运算正则表达式是:ε和φ是正则表达式,表示L(ε)={ε},L(Ф)=Ф任何一个正则表达式ａ∈∑,表示L(ａ)={ａ}如果ｅ1和ｅ2是∑上的正则表达式,则运算后也是∑上的正则表达式:(Ｌ(ｅ1))＊ｅ1＊Ｌ(ｅ1)Ｌ(ｅ2)ｅ1ｅ2Ｌ(ｅ1)∪Ｌ(ｅ2)ｅ1｜ｅ2Ｌ(ｅ1)(ｅ1)由正则表达式生成的语言正则表达式

11、从已有正则表达式生成新的正则表达式的运算:选择(

12、)连接(.)闭包(*)运算的优先顺序是:‘＊’>‘.’>‘｜’例如L(a

13、bc*)={a}∪({b}{,c,cc,…})={a}∪{b,bc,bcc…}={a,b,bc,bcc…}例如:={a，b},下面是正则表达式和它们生成的语言正则表达式rL(r)a{a}ab{a,b}ab{ab}(ab)(ab)L(r)={a,b}{a,b}={aa,ab,ba,bb}a{,a,aa,…}(ab){,a,b,aa,ab……}正则表达式的名字为了方便,为较长的正则表达式提供

14、一个简化的名字例如:一个或多个数字序列的正则表达式(0

15、1

16、…

17、9)(0

18、1

19、…

20、9)*可写为digitdigit*其中digit=0

21、1

22、…

23、9是名字为digit的正则表达式例如给定待匹配的字符串的描述,将其翻译为一个正则表达式∑={a,b,c},至少包含一个b的字符串的正则表达式是(a

24、c)*b(a

25、c)*最多包含一个b的字符串的正则表达式是(a

26、c)*

27、(a

28、c)*b(a

29、c)*or(a

30、c)*(b

31、)(a

32、c)*解释相同的语言可以由许多不同的正则表达式生成不是所有我们能描述的字符串集合都能用正则表达式生成例如:字符串集

33、合S={b,aba,aabaa,…}={anban

34、n≥0}不能由正则表达式生成。2.2.3编程语言单词的正则表达式1单词的正则表达式让l=a

35、b

36、…

37、zd=0

38、1

39、…

40、9标识符:l(l

41、d)*无符号整数:dd*实数:dd*(.dd*

42、)保留字:if

43、whil