第二章 词法分析 (Lexical Analysis) 主讲：申春

词法分析在编译程序中的逻辑位置 词 法 分 析 表 处 理 源 程 序 语 法 分 析 语 义 分 析 中 间 代 码 生 成 中 间 代 优 化 目 标 代 码 生 成 目 标 程 序 错 误 处 理

主要内容 词法分析程序的功能 单词分类及内部表示 ※单词的描述技术—正则表达式和自动机 词法分析程序的设计与实现步骤

2.1 词法分析概述 词法分析器的任务： (1)对输入的字符串形式的源程序按顺序进行扫描，识别输出具有独立意义的单词序列; 2.1 词法分析概述 词法分析器的任务： (1)对输入的字符串形式的源程序按顺序进行扫描，识别输出具有独立意义的单词序列; (2)检查源程序中的词法错误。 源程序 字符序列 词法分析程序 （Scanner） 单词序列

单词：是指具有独立含义的最小的语义单位。 C语言源程序： void main() { int x1; x1= 1; if( x1>0 ) x1=x1+10; } 词法分析程序输出由单词内容和单词的类别组成的内部表示序列 单词：是指具有独立含义的最小的语义单位。

2.2 单词的分类 个数有限 个数无限 10, 3.14 个数有限

void main() { int x1; x1=1; if(x1>0) x1=x1+10; } 词法分析输出 单词序列 <保留字,void> <保留字,main> <界限符,(> <界限符,)> <界限符,{> <保留字,int> <标识符,x1> <界限符,;> <标识符,x1> <运算符,=> <常量,1> <界限符,;> <保留字,if> <界限符,(> <标识符,x1> <运算符,>> <常量,0> <界限符,)> <标识符,x1><运算符,=><标识符,x1><运算符,+><常量,10> <界限符,}>

如何实现词法分析器 1. 明确要分析的问题 2. 利用形式化方法描述各类单词的词法规则 正则表达式 自动机 3.设计词法分析算法

2.3 单词的形式描述工具 正则表达式 正则表达式，又称正规表示法、常规表示法（Regular Expression，代码中常简写为regex、regexp或RE）。正则表达式使用单个字符串来描述、匹配一系列符合某个句法规则的字符串。 在很多文本编辑器里，正则表达式通常被用来检索、替换那些符合某个模式的文本。

2.3.1 符号和符号串基本概念 (1).字母表（alphabet ) 2.3.1 符号和符号串基本概念 (1).字母表（alphabet ) 字母表是元素的非空有穷集合,通常用∑表示。字母表中的一个元素称为该字母表的一个字母（letter）,也可叫做符号（symbol）或者字符(character)。 例如： Σ={a,b,c,d,…,z,A,B,…Z}, Σ={0,1,…,9}, Σ=ASCII，Σ=unicode

(2).符号串 是由字母表中的符号组成的任意有穷序列。符号串还可以称为“字符串”、 “句子”，一般用，，….，x，y，z表示。 符号串中字符的个数称为符号串长度， 用||表示符号串的长度。 表示空串。 ||=0; 空串集{}不同于空集 。 例如：Σ={0,1} =01 , =101

(3).符号串连接 设和 均是字母表∑上的符号串， 和的连接是把的所有符号顺次地接在的所有符号之后所得到的符号串。记为: 。 例如: 设  = abc ,  = de ,则和的连接:  = abcde ||=||+||。 由于是不包含任何符号的字符串，特别有：  =  =  连接运算不满足交换律。

4.符号串的方幂 设x是字母表∑上的符号串，把x自身连接n次得到的符号串z，称作符号串x的n次幂，记作 z = xn 。根据定义有： x2 = xx x3 = x2x = xx2 = xxx …… xn = xn-1x = xxn-1 = xx…xx (n个x) 例: 设x = 001，则有: x0 = ε x1 = 001 x2 = 001001 x3 = 001001001

(6). 符号串集合：若集合A中的所有元素都是某字母表∑上的符号串，则称A为该字母表上的符号串集合。 (7).符号串集的乘积 设A、B 是两个符号串集合，AB表示A与B的乘积，具体定义为： AB = { xy | ( x∈A ) ∧ ( y∈B )} 例: 设 A = { a, bc } ， B ={ de, f } ,则： AB = { ade, af, bcde, bcf }

(8).符号串集合的方幂 设A为符号串的集合，则称Ａi为符号串集Ａ的方幂。具体定义如下： Ａ0＝ {  } Ａ1 ＝ A Ａ2 ＝ AA …… Ａn ＝Ａn-1A ＝ AAA……A (n个） 例：Ａ＝ { a,b } 则： Ａ0 ＝ {  } Ａ1 ＝ { a,b } Ａ2 ＝ AA ＝ { a,b }{ a,b }={ aa,ab,ba,bb } Ａ3 ＝ A2A ＝{ aa,ab,ba,bb }{ a,b } ＝{ aaa,aab,aba,abb,baa,bab,bba,bbb } Ａn ＝Ａn-1A ＝ AAA……A

Ａ0＝ {  } Ａ1 ＝ A Ａ2 ＝ AA …… Ａn ＝Ａn-1A ＝ AAA……A (n个） 例：Ａ＝ { a,b,c,d,…,z } 则： Ａ0 ＝ {  } Ａ1 ＝ { a,b,c,…,z } Ａ2 ＝ AA ＝ 长度为2的小写英文字符串集 Ａ3 ＝ A2A ＝长度为3的小写英文串集 Ａn ＝Ａn-1A ＝长度为n的小写英文串集

设A为符号串的集合，则称Ａ＋为符号串集Ａ的正闭包．具体定义如下： (9).符号串集合的正闭包 设A为符号串的集合，则称Ａ＋为符号串集Ａ的正闭包．具体定义如下： Ａ＋ ＝ Ａ1 ∪ A2 ∪ A3 ∪ …… ∪ An ∪ …… 例1：Ａ＝ { a,b } 则： Ａ+ ：表示所有由a,b组成的字符串集合。 例2：letter＝ { a,b ,c,….,z,A,B,…..,Z} 则： letter+ ：所有英文字符串集合。 ＺＺＺ 例3：digit＝ { 0,1，…9} 则： digit+ ：所有数字串集合。

例：letter＝ { a,b ,c,….,z,A,B,…..,Z} 则： letter* ：表示包含空串和所有英文字符串的集合。 (10).符号串集合的星闭包 设A为符号串的集合，则称Ａ＊为符号串集Ａ的星闭包．具体定义如下： Ａ＊ ＝ A0 ∪Ａ1 ∪ A2 ∪ A3 ∪ …… ＝ A0 ∪ Ａ+ = {  } ∪ Ａ+ 例：letter＝ { a,b ,c,….,z,A,B,…..,Z} 则： letter* ：表示包含空串和所有英文字符串的集合。 ＺＺＺ

2.3.2 正则表达式 正则表达式是用来描述正则集的一种代数表达式，也称为正规表达式。 形式：用事先定义好的一些特定字符，以及对这些特定字符进行组合运算，形成的一个“规则字符串”。如：(1|2|…|9)(0|1|2|…|9)*|0 作用：用来定义一类字符串的一种过滤逻辑。 所有符合正则表达式r所定义的规则（模式）的符号串集合, 称为正则集或正规集,表示为L(r)。L(r)也称为由r定义的语言。

（一）正则表达式和正则集的递归定义 设∑为字母表 （1） 和 是∑上的正则表达式，它们所表示的正则集分别为L(ε)={ε}， L()={}. （2） 对任何a∈∑,a 是∑上的正则表达式，它所表示的正则集L(a)={a}; （3）若r和s都是∑上的正则表达式，它们所表示的正则集分别为L(r)和L(s),则 (r)也是∑上的正则表达式，表示的正则集L((r))= L(r) r|s也是∑上的正则表达式，表示的正则集L(r|s)= L(r) ∪ L(s) r s也是∑上的正则表达式，表示的正则集L(r  s)= L(r)L(s) r*也是∑上的正则表达式，表示的正则集L(r*)= (L(r))* 有限次使用上述3条规则构成的表达式称为∑上的正则表达式，表示的字符串集合称为∑上的正则集或正规集。

正则表达式定义中的四种运算的作用 括号(r)：不改变r表示的正则集，主要是用于确定运算优先关系 或运算 |：把复杂问题分成几个种情况依次定义正则表达式，然后把这些正则表达式用或运算连接起来描述整个问题。 连接运算  ：把一个大问题分成前后关联的几个部分依次定义正则表达式，然后把各部分正则表达式按先后顺序用连接运算连接起来描述问题。为了方便表达，经常省略这个 。例如：rs也可表示为rs。 *运算：r*表示对正则表达式r所描述的文本进行0到若干次循环连接。 实际应用中会扩充很多正则表达式的运算，如： r+也是∑上的正则表达式，表示的正则集L(r+)= (L(r))+

（二）正则表达式示运算符优先级 括号（）> *运算 > 连接运算 > |或运算

例1： 正则表达式e L(e) 1.a {a} 2.a|b {a, b} 3.ab { ab } 4.(a|b) (a|b) {aa, ab, ba, bb} 5. a* {ε,a,aa,aaaa,…}

（三）正则表达式的性质 （1）交换律： A|B = B|A （2）结合律： A|B|C = (A|B)|C = A|(B|C) ABC = (AB)C = A(BC) （3）分配律： A(B|C) = AB|AC (A|B)C = AC|BC （4）幂等律： A** = A* （5）同一律： A = A = A

例2 ={ a,b }. 正则表达式r 表示的正则集L(r) ab* 2. a(a|b)* L(a(a|b)*) =L(a) L( (a|b)*) =L(a) (L(a|b))* ={a}{a,b}* L(ab*) =L(a) L(b*) ={a}{ε,b, bb,bbb,…} ={a,ab,abb,abb,…} ={ a,b }. 正则表达式r ab* 2. a(a|b)* 表示的正则集L(r) 上所有以a为首后跟0个或任意多个b的字符串集 上所有以a为首的字符串集

例3 表示整数的正则表达式 D=0|1|2…|9 ，D表示一位数字 则D+ ：可以表示允许0前导整数 D=0|1|…|9， D1=1|2|…|9 D1D*：表示无符号正整数 (+D1D*)|(-D1D*)|0：表示有符号整数 (+|-|)(D1D*)|0 ：表示整数

（四）词法分析中的单词描述 保留字： while|if|for|… 标识符：L(L|D)*， 其中L=A|B|…Z|a|b|…|z|_； 常数 1. 整数: (+|-|)(D1D*)|0， 其中 D1=1|2|…|9 2. 实数: (+|-|)(D1D*|0).D+ 特殊符号 1. 运算符：+|-|*|… 2. 分界符：{|}|;|… 3. 控制符：\t|\n|…

练习： 设字母表={0，1},试写正则表达式 所有上定义的串 表示二进制数 能被2整除的二进制