1、第二章 词法分析1 (Lexical Analysis),词法分析程序的功能;单词分类及内部表示;单词的描述技术正则表达式和自动机词法分析程序的设计与实现步骤.,词法分析在编译程序中的逻辑位置,表 处 理,错 误 处 理,目标代码生成,中间代码优化,中间代码生成,语义分析,语法分析,词法分析,目标程序,源程序,2.1 词法分析程序的功能,词法分析器读取源程序的字符序列，逐个拼出单词并构造相应的内部表示。同时检查源程序中的词法错误。,一类是仅作为语法分析的子程序：,词法分析器的接口,2.2 单词及单词内部表示,单词： 是指语言中具有独立含义的最小的语义单位。例如3.14*initial就可以划分
2、成3.14, *,initial这三个单词。但是3.14不可以继续划分成3,.,14,if (position 10) rate = 3.14 * initial;,单词的内部表示,TOKEN结构图 单词类别:又称词法信息，用来区分单词的不同种类，通常可以用整数编码来表示.语义信息:应该是唯一确定单词本身的内容.,单词的分类,例：,if (position 10) rate = 3.14 * initial;, , ,单词的描述工具,正则表达式 (y|z)*x(y|z)*x)*(y|z)*自动机,S,P,0,0,1,1,1,Z,2.2单词的形式描述工具正则表达式,正则表达式，又称正规表示法、常
3、规表示法（Regular Expression，代码中常简写为regex、regexp或RE）。正则表达式使用单个字符串来描述、匹配一系列符合某个句法规则的字符串。在很多文本编辑器里，正则表达式通常被用来检索、替换那些符合某个模式的文本。,2.2.1 符号和符号串基本概念,1.字母表（alphabet ) 字母表是元素的非空有穷集合,字母表中的一个元素称为该字母表的一个字母（letter）,也可叫做符号（symbol）或者字符(character)。字母表有时也称为符号表,通常用表示。 例如：=a,b,c,d,z,A,B,Z, =0,1,9, =ASCII，=unicode,2.符号串由字母表
4、中的符号组成的任何有穷序列称为字母表上的符号串。符号串还可以称为“字符串”、“字”或“句子”，一般用，.，x，y，z表示。表示空串。对任一字母表，都有是上的符号串。空串集不同于空集 。,3.符号串长度符号串中字符的个数。 用|表示符号串的长度。 |=0; 只有当两个符号串长度相等且相应位置的符号均相同时，这两个符号串才是相等的。,5.符号串的方幂 设x是字母表上的符号串，把x自身连接n次得到的符号串z, 即z = xxxx (n个x),称作符号串x的n次幂，记作 z = xn 。根据定义有： x0 = x1 = x x2 = xx x3 = x2x = xx2 = xxx xn = xn-1x
5、 = xxn-1 = xxxx (n个x)例2.1 设x = 001，则有: x0 = x1 = 001 x2 = 001001 x3 = 001001001,6. 子字符串 一个非空字符串 x ,同时删去它的一个前缀和一个后缀后所得到的字符串称为 x 的子字符串，简称子串。 如果删去的前缀和后缀不同时为,则称该子串为真子串。例如: 设 x = abc , 其子串为: abc , ab , a , , bc , c , b 。 真子串为: ab, a , , bc , b , c 。,8.符号串集的乘积 设A、B 是两个符号串集合，AB表示A与B的乘积，具体定义为： AB = xy | ( x
6、A ) ( yB ) 特别有：1、A = A = ，其中表示空集。 2、A = A = A例2.3 设 A = a, bc ， B = de, f ,则： AB = ade, af, bcde, bcf ,7. 符号串集合：若集合A中的所有元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。,9.符号串集合的方幂 设A为符号串的集合，则称i为符号串集的方幂。具体定义如下：0 1 A2 AA n n-1A AAAA (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,b
7、aa,bab,bba,bbb n n-1A AAAA,10.符号串集合的正闭包 设A为符号串的集合，则称为符号串集的正闭包具体定义如下： 1 A2 A3 An,11.符号串集合的星闭包 设A为符号串的集合，则称为符号串集的星闭包具体定义如下： A0 1 A2 A3 An 注意: A 或 A0 1,例:设A = ab, cd，则 : A+ = ab, cd, abab, abcd, cdab, cdcd, ababab, ababcd, A* = , ab, cd, abab, abcd, cdab, cdcd, ababab, ababcd, ,2.2.2 正则表达式,正则表达式r定义了一个符
8、号串集合S, S内的每个符号串都与r所定义的模式相匹配，S称为由r生成的语言L(r)，也称为正则集或正规集。 例：如正则表达式r: letter(letter|digit)*表示的语言L(r)为标识符的集合。,（一）正则表达式的递归定义归纳基础：1) 和 是上的正则表达式，L()=该语言只包含空串， L()=该语言为空.2) 对任何a,那么a 是上的一个正则表达式，L(a)=a，它所表示该语言仅包含一个长度为1的字符a;归纳步骤：由小的正则表达式构造较大的正则表达式的步骤有以下四种方法。假定和是正则表达式，分别表示语言L(A)和L(B),那么：1）(A)是一个正则表达式，表示语言L(A)= L
9、(A)2）A|B是一个正则表达式，表示语言L(A) L(B)3）A B是一个正则表达式，表示语言L(A)L(B)4）A*是一个正则表达式，表示语言 (L(A)*有限次使用上述规则构成的表达式称为上的正则表达式，表示的集合称为上的正规集。,（二）正则表达式示运算符优先级：先闭包运算*，次连接运算 ，最后或运算 | 例（1）,= a,b .,正则表达式示例（2）,= a,b .,L(ab*)=L(a) L(b*)=a,b, bb,bbb,L(a(a|b)*)=L(a) L( (a|b)*)=L(a) (L(a|b)*=aa,b*,上所有以a为首后跟任意多个（包括0个）b的字符串集,上所有以a为首的
10、字符串集,正则表达式示例（3）,设字母表=0，1，求二进制数字集合且为2的倍数。所有上定义的串的正则表达式为（1|0）*则二进制数表示为1(1|0)*|0其中能被二整除的表示为1（1|0）*0|0,（三）正则表达式的性质,正则表达式的等价 A | B = B | A | 的可交换性 A | B | C = A | (B | C) = (A | B) | C | 的可结合性 ABC =A(BC)=(AB)C 连接的可结合性 A (B | C) =A B | A C 连接的可分配性 (A | B ) C =A C | B C 连接的可分配性 A* =A* 幂的等价性 A = A=A 是连接的恒等元
11、素,作业：,设字母表=x，y，z，所有上定义的串。不包含y的所有符号串集合。包含偶数个x的所有符号串。不包含连续两个y的所有符号串集合。,（四）扩充的正则表达式,一次或多次重复: R+ 任何符号: “”匹配在字母表中任何符号. 符号范围: “-” ,如0-9 、 a-z、 A-Z. 排除型字符集合: “xyz”匹配未列出的任意字符 . 如: %a-zA-Z% 匹配含有两个百分号里面有一个非字母的字符串 . 0或1次(可选): “？”. r?=( |r) 如:colou?r,（五）词法分析中的单词描述,保留字 如 Beginbegin标识符 letter=a-zA-Z digit=0-9 identifier=letter(letter|digit)* 数字 整数:Int1-9digit*|0 实数:realInt.digit+ 特殊符号 Special=+|-|,
