第二章词法分析-1.ppt

第二章词法分析,学习目标:掌握编写正则表达式,正则表达式到DFA的转换，词法分析程序的构建理解正则表达式，NFA，DFA的概念,2.1扫描处理2.2正则表达式2.3有穷自动机2.4从正则表达式到DFA,2.1扫描处理,回顾扫描程序的任务从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个有意义的单元，称为记号或单词(Token)记号（单词）单词有若源程序中逻辑上紧密相连的一组字符，这些字符具有集体含义。若干种类型，保留字、标识符、特殊符号,1单词的种别,种别保留字语言中具有特殊意义的符号串，如：“if”and“then”特殊符号包括+,-,:=,=等,标识符:以字母起始的字母数字串常数:包括数值常数和符号串常数，例如：42,3.14,“hello”,“a”,单词与词义Tokenandlexeme单词表示为(种别,自身值)种别是逻辑实体，表示IF,THEN,PLUS,MINUS,NUM,ID等由记号表示的字符串称为它的串值或词义保留字和特殊符号仅有一个词义数字和标识符有无穷多个词义例如(IF,“if”)(PLUS,“+”)(ID,“x”),2词法分析器的接口,词法分析作为独立一遍将字符流的源程序变成单词序列，输出到一个中间文件上，做为语法分析的输入。词法分析作为语法分析的子程序每当语法分析程序需要一个单词时，则调用该子程序，从源程序中分析和返回一个单词,词法分析主要研究:词义结构的表示法:正则表达式识别系统:有穷自动机是对正则表达式给出的串格式的识别算法实际编写程序实现有穷自动机的识别过程.,2.2正则表达式,功能表示字符串的格式正则表达式的定义正则表达式r完全由它所匹配的串集来定义这个集合称为由正则表达式生成的语言,写作L(r)L(r)定义在正规符号的集合上,称为字母表,2.2.1符号串和语言,字母表定义符号的非空有穷集合例如=01=ab,c,2符号串,定义由字母表中的符号组成的任何有穷序列.例如0,00,10是=01的符号串a,ab,aaca是=ab,c的符号串,符号串的长度一个符号串s的长度,记为|s|,符号串中含有符号的个数.例如:|abc|=3空串表示为,是长度为0的特殊串并不等于空集合(),3符号串的运算,符号串的连接：设x、y是符号串,它们的连接是把y的符号写在x的符号之后得到的符号串xy例如x=ST，y=abu，则xy=STabu显然x=x=x符号串的方幂：把符号串a自身连接n次得到的符号串an=aaaa例如:a1=aa2=aaa0=,4语言,定义字母表上的一些符号串的集合例如是一个语言空集也是一个语言,5语言的运算,连接L和M的连接记为LMLM=st|sL,tM例如:L=ab,cdeM=0,1LM=ab0,ab1,cde0,cde1A=A=A,方幂L的方幂定义为:L0=L1=L,L2=LLLK=LL.L(k个),闭包L的闭包(记为L*)表示为0个或多个L的连接L*=L0L1L2L3例如：L=0，1L*=L0L1L2=,0,1,00,01,10,11,000,L的正闭包(记为L+)表示1个或多个L的连接L+=L1L2L3L*=L0L+L+=LL*=L*L,2.2.2正则表达式的定义,语言中描述单词的工具正则表达式基本正则表达式集合从已有的正则表达式生成新的正则表达式的运算,正则表达式是:和是正则表达式,表示L()=,L()=任何一个正则表达式,表示L()=,如果1和2是上的正则表达式,则运算后也是上的正则表达式:,从已有正则表达式生成新的正则表达式的运算:选择(|)连接(.)闭包(*)运算的优先顺序是:.例如L(a|bc*)=a(b,c,cc,)=ab,bc,bcc=a,b,bc,bcc,例如:=a，b,下面是正则表达式和它们生成的语言正则表达式rL(r)aaaba,babab(ab)(ab)L(r)=a,ba,b=aa,ab,ba,bba,a,aa,(ab),a,b,aa,ab,正则表达式的名字为了方便,为较长的正则表达式提供一个简化的名字例如:一个或多个数字序列的正则表达式(0|1|9)(0|1|9)*可写为digitdigit*其中digit=0|1|9是名字为digit的正则表达式,例如给定待匹配的字符串的描述,将其翻译为一个正则表达式=a,b,c,至少包含一个b的字符串的正则表达式是(a|c)*b(a|c)*最多包含一个b的字符串的正则表达式是(a|c)*|(a|c)*b(a|c)*or(a|c)*(b|)(a|c)*,解释相同的语言可以由许多不同的正则表达式生成不是所有我们能描述的字符串集合都能用正则表达式生成例如:字符串集合S=b,aba,aabaa,=anban|n0不能由正则表达式生成。,2.2.3编程语言单词的正则表达式,1单词的正则表达式让l=a|b|zd=0|1|9标识符:l(l|d)*无符号整数:dd*实数:dd*(.dd*|)保留字:if|while|do|,2单词识别相关的问题,二义性有些字符串可被不同的正则表达式匹配语言定义必须给出无二义性规则当串既可以是标识符也可以是关键字时，通常认为它是关键字当串可以是单个记号也可以是若干单词序列时，则通常解释为单个符号(最长子串原理),单词分隔符分隔符是肯定为其他记号一部分的字符例如:符号串“xtemp=ytemp”中,=是分隔符空格、新行、制位表、注释都是单词分隔符例如:串“whilex”中,两个单词“while”和“x”由空格分开扫描程序必须在检查任意记号分隔功能之后舍弃掉空白格。,先行问题（lookahead)扫描程序必须处理单个或多个字符先行问题例如:识别特殊符号:=,当遇到:,扫描程序必须先行处理是单词:还是:=,2.3有穷自动机,功能:有穷自动机是描述特定类型算法的数学方法可用作描述在输入串中识别模式的过程，因此可以用作构造扫描程序。分类:确定的有穷自动机(DFA)不确定的有穷自动机(NFA),有穷自动机和正则表达式之间的关系例如标识符的正则表达式是让letter=a|b|zdigit=0|1|9identifier=letter(letter|digit)*识别这样的标识符过程可以被描述为有穷自动机,状态:表示其中记录已被发现的模式的数量在识别过程中的位置转换:记录一个状态向另一个状态的转换初始状态:识别过程的开始接受状态:代表识别过程结束的状态,将真实字符串识别为标识符的过程可通过列出在识别过程中所用到的状态和转换的序列来表示例如:识别“xtemp”为标识符的过程:,2.3.1DFA的定义2.3.2NFA的定义2.3.3有穷自动机的代码实现,2.3.1DFA的定义,DFA的定义一个DFAM=（S，T，S0，A）S是状态集合是字母表T是转换函数T:SX-S,T(Si,a)=Sj表示当前状态时Si,当前输入字符是a时，将转换到下一个状态SjS0S是初始状态AS是接受状态的集合,例如DFAM=(S，U，V，Q,a，b,f,S,Q)f定义为：f（S，a）=Uf（S，b）=Vf（V，a）=Uf（V，b）=Qf（U，a）=Qf（U，b）=Vf（Q，a）=Qf（Q，b）=Q,确定性给定当前的状态和当前的输入符号,能唯一地确定下一个状态,DFA的转换图每个状态是图的一个结点单箭头线表示初态接受状态由双线结点表示若T(Si,a)=Sj,从结点Si到结点Sj画标记为a的弧,例如:DFAM=（S，U，V，Q,a，b,f,S,Q）f（S,a）=Uf（S,b）=Vf（V,a）=Uf（V,b）=Qf（U,a）=Qf（U,b）=Vf（Q,a）=Qf（Q,b）=Q,状态转换图为:,转换图的几点说明定义的扩展:转换也可以表示为字符集合的名字,惯例出错转换在图中没有画出来,带有出错转换的标识符的有穷自动机,DFA的状态转换表状态和输入字符转换函数T的值第一个状态为初始状态用一列表示是否为接受状态,例如:DFAM=（S，U，V，Q,a，b,f,S,Q）f（S,a）=Uf（S,b）=Vf（V,a）=Uf（V,b）=Qf（U,a）=Qf（U,b）=Vf（Q,a）=Qf（Q,b）=Q,DFA的状态转换表为:,L(M):能被DFAM识别的语言DFA识别(接受)的字符串对于*中的任何