编译原理第二章词法分析-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”,单词与词义Token and lexeme 单词表示为 (种别,自身值) 种别是逻辑实体，表示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=a a2=aa a0=,4 语言,定义 字母表上的一些符号串的集合 例如 是一个语言 空集也是一个语言,5 语言的运算,连接 L和M的连接记为LM LM =st|sL,tM 例如: L=ab,cde M = 0,1 LM =ab0,ab1,cde0,cde1 A=A=A,方幂 L的方幂定义为: L0 = L1 = L , L2 = LL LK = LL.L (k个),闭包 L的闭包 ( 记为 L*) 表示为0个或多个L的连接 L * = L 0 L1 L 2 L 3 例如：L=0，1 L* =L0L1L2 =,0,1,00,01,10,11,000, L的正闭包(记为 L+) 表示1个或多个L的连接 L += L 1 L 2 L 3 L *= L 0 L+ L += LL*= L* L,2.2.2 正则表达式的定义,基本正则表达式集合 从已有的正则表达式生成新的正则表达式的运算,正则表达式是: and 是正则表达式 ,L()=,L()= 任何一个正则表达式, L()=,如果1 and2 是上的正则表达式,那么下面都是 上的正则表达式:,从已有正则表达式生成新的正则表达式的运算: 选择 ( | ) 连接( . ) 闭包( * ) 运算的优先顺序是: . 例如 L(a|bc*)=a (b ,c,cc,) =a b,bc,bcc=a,b,bc,bcc,例如: =a，b, 下面是正则表达式和它们生成的语言 正则表达式 r L(r) a a ab a,b ab ab (ab)(ab) L(r)=a,ba,b =aa,ab,ba,bb a ,a,aa, (ab) ,a,b,aa,ab ,正则表达式的名字 为了方便,为较长的正则表达式提供一个简化的名字 例如: 一个或多个数字序列的正则表达式 (0|1|9)(0|1|9)* 可写为 digit digit* 其中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|z d=0|1|9 标识符: l ( l | d)* 无符号整数: dd* 实数: dd*(.dd*| ) 保留字: if|while|do|,2 单词识别相关的问题,二义性 有些字符串可被不同的正则表达式匹配 语言定义必须给出无二义性规则 当串既可以是标识符也可以是关键字时，通常认为它是关键字 当串可以是单个记号也可以是若干单词序列时，则通常解释为单个符号(最长子串原理),单词分隔符 分隔符是肯定为其他记号一部分的字符 例如: 符号串“xtemp=ytemp”中, = 是分隔符 空格、新行、制位表、注释都是单词分隔符 例如:串 “while x”中, 两个单词 “while” 和 “x” 由空格分开 扫描程序必须在检查任意记号分隔功能之后舍弃掉空白格。,先行问题（lookahead) 扫描程序必须处理单个或多个字符先行问题 例如: 识别特殊符号 :=, 当遇到 :, 扫描程序必须先行处理是单词 : 还是 :=,2.3 有穷自动机,功能 : 有穷自动机是描述特定类型算法的数学方法 可用作描述在输入串中识别模式的过程，因此可以用作构造扫描程序。 分类: 确定的有穷自动机 (DFA) 不确定的有穷自动机 (NFA),有穷自动机和正则表达式之间的关系 例如 标识符的正则表达式是 让 letter=a|b|z digit=0|1|9 identifier=letter(letter|digit)* 识别这样的标识符过程可以被描述为有穷自动机,状态: 表示其中记录已被发现的模式的数量在识别过程中的位置 转换: 记录一个状态向另一个状态的转换 初始状态: 识别过程的开始 接受状态: 代表识别过程结束的状态,将真实字符串识别为标识符的过程可通过列出在识别过程中所用到的状态和转换的序列来表示 例如: 识别 “xtemp=.”为标识符的过程:,2.3.1 DFA的定义 2.3.2 NFA的定义 2.3.3 有穷自动机的代码实现,2.3.1 DFA的定义,DFA的定义 一个DFA M=（S，T，S0，A） S 是状态集合 是字母表 T是转换函数T: S X -S, T(Si,a)=Sj 表示当前状态时Si ,当前输入字符是a时，将转换到下一个状态 Sj S0S 是初始状态 A S 是接受状态的集合,例如 DFA M=(S，U，V，Q,a，b,f,S,Q) f 定义为： f（S，a）=U f（S，b）=V f（V，a）=U f（V，b）=Q f（U，a）=Q f（U，b）=V f（Q，a）=Q f（Q，b）=Q,确定的含义 给定当前的状态和当前的输入符号,能唯一地确定下一个状态,DFA的转换图 每个状态是图的一个结点 单箭头线表示初态 接受状态由双线结点表示 若T(Si,a)=Sj, 从结点Si 到结点Sj 画标记为a的弧,例如: DFA M=（S，U，V，Q,a，b,f,S,Q） f（S,a）=U f（S,b）=V f（V,a）=U f（V,b）=Q f（U,a）=Q f（U,b）=V f（Q,a）=Q f（Q,b）=Q,状态转换图为:,转换图的几点说明 定义的扩展: 转换也可以表示为字符集合的名字,惯例 出错转换在图中没有画出来,带有出错转换的标识符的有穷自动机,DFA的状态转换表 状态和输入字符 转换函数T的值 第一个状态为初始状态 用一列表示是否为接受状态,例如: DFA M=（S，U，V，Q,a，b,f,S,Q） f（S,a）=U f（S,b）=V f（V,a）=U f（V,b）=Q f（U,a）=Q f（U,b）=V f（Q,a）=Q f（Q,b）=Q,DFA的状态转换表为 :,L(M): 能被 DFA M识别的语言 DFA识别(接受)的