第3章词法分析(1)

1、1第三章词法分析第三章词法分析2本章内容q 词法分析器：将源程序的字符流翻译成记号流，以及用户接口等任务q 构造词法分析器手工自动生成q 重点正则表达式有限状态自动机自动生成工具：Lex/Flex3 词法分析器词法分析器语法分析器语法分析器符号表符号表记号记号取下一个记号取下一个记号源程序源程序3.1 词法分析器的作用词法分析器的作用 if(count5) sum+=count; if ( count 5 ) sum += count ; 4自动生成词法分析器自动生成词法分析器 词法分析器词法分析器字符流字符流词法单元流词法单元流词法分析的规则词法分析的规则词法分析器的词法分析器的产生器产生器

2、(eg.Lex或或Flex)5词法分析器的主要任务词法分析器的主要任务q 读入输入字符，产生token序列，交给语法分析使用；q 相关辅助任务过滤注释、空格等；为了报错，记录每个token在源文件中的位置63.1.1 词法分析与句法分析分开的原词法分析与句法分析分开的原因因q 简化编译器的设计，让句法分析器简单化。q 提高编译效率：使用适合词法分析的专门技术。q 增强编译器的可移植性：输入设备相关的特殊性可以被限制在词法分析器中。73.1.2 词法单元、模式、词素词法单元、模式、词素 q 词法单元词法单元(token)(token)：一个词法单元名和一个可选的属性值组成。用表示。它是源语言文法

3、的终结符。q 模式模式(pattern)(pattern)：源语言中特定记号的构成规则，可以用正则表达式示。(例如：变量名的命名规则）q 词素（词素（lexeme)lexeme)：是源程序中的一个字符序列，它和某个词法单元的模式匹配，并被词法分析器识别为该词法单元的一个实例。if ( count 5 ) sum += count ; Lexeme lksim 8例子例子q C语言语句：printf(“total=%d”, score);#define ID_TOKEN 300#define IF_TOKEN 400#define FOR_TOKEN 500struct Token int To

4、kenName; union int IntValue; double DblValue; IdItem * ptr; Attribute;9词法单元的例子词法单元的例子 词法单元名词法单元名 词素例举词素例举模式的非形式描述模式的非形式描述 constconst constforfor forrelation , = , = , 或 = 或 = 或 idsum, count, D5 由字母或下划线开头的字母数字串num 3.1, 10, 2.8E12任何数值常数literal“hello”双引号之间的任意字符串，但双引号本身除外10词法单元的例子词法单元的例子q 下列结构作为词法单元toke

5、n：关键字、操作符、标识符、常量、字符串、标点符号每个关键字对应一个词法单元（token）表示多个运算符的词法单元tokens一个表示所有标识符的词法单元一个或多个表示常量的词法单元，比如数字和字符串每一个标点符号有一个词法单元，比如左右括号、逗号和分号。113.1.3 词法单元的属性词法单元的属性q 用二元组表示；属性一般用符号表的指针来表示q 例如，position = initial + rate * 60id，指向符号表中position这个条目的指针assign _ op， id，指向符号表中initial这个条目的指针add_op，+id，指向符号表中rate这个条目的指针mul_

6、 op, *num，整数，值60#define ID 600123.1.4 词法错误词法错误q 词法分析器对源程序采取非常局部的观点q 难以发现下面的错误fi (a = f (x) ) q 在实数是a.b格式下，可以发现下面的错误123.q 此时，使用“恐慌模式”的错误恢复q 错误修补133.2 词素的描述词素的描述q 正则表达式是模式的重要表示方法。143.2.1 串和语言串和语言q 字母表：有限符号的集合. 例： = 0,1，a,b,a,b,z,A,B,Zq 字符串：符号的有穷序列，例：0110,q 字符串s的长度：出现在s中符号的个数，记作|s|q 空串：长度为的符号串，用表示q 语言：

7、给定字母表上的任意一个字符串集合,0,00,000, , a,b,aa,ab,ba,bb, , q 句子：属于语言的字符串。 本书中句子、字符串基本表达同一个意思。15字符串例子及术语字符串例子及术语q 串banana前缀前缀Prefix:从从s的尾部删除的尾部删除0个或多个符号后得到的串，个或多个符号后得到的串，例如：例如： , b, ba, ban, bana, banan, banana后缀后缀Suffix: , a, na, ana, nana, anana, banana子串子串(Substring): , b, a, n, ba, an, na, , ban, ana, nan,

8、bana, anan,nana, banan, anana, banana子序列子序列(Subsequence):bnan,nn真前缀真前缀Properprefix：b,ba,ban,bana,banan, 真后缀真后缀Propersuffix：a,na,ana,nana,anana16语言语言(Language)q 语言(Language)：某个给定字母表上一个任意可数的字符串集合。q Special Languages: and 可枚举17语言的例子语言的例子字符集字符集语言语言0,11,10,100,1000,1000000,1,00,11,000,111,a,b,cabc,aabbcc

9、,aaabbbccc,A,ZTEE,FORE,BALL,FOR,WHILE,GOTO,A,Z,a,z,0,9,所有合法的所有合法的C语言程序语言程序+,-,所有语法正确的英语句子所有语法正确的英语句子18串的运算串的运算q 连接xy 例如：x=ab y=cd, xy=abcds = s = s q 乘积（指数）定义s0为，si为si-1s（i 0）s1=s, s2=ss, s3=sss, 例如，s=ab, s1=ab, s2=abab, s3=ababab 193.2.2 语言上的运算语言上的运算OPERATIONDEFINITIONL和和M的的并并(union)L和和M的的连接连接(conc

10、atenation)L的的Kleene闭包闭包(Kleene closure)L的正闭包的正闭包( positive closure)L = L M=s|sL或或s ML = LM=st|sL且且s M L = L+=0iiLL的的0个或多个连接个或多个连接, L LL LLL L= L*=1iiLL的一个或多个连接的一个或多个连接, L LL LLL Kleene ，星号，德语称 Kleensche Hlle 20语言的运算语言的运算例如：L=a,b, M=cc,ddq 和：和：LM =s |s L 或或s M 例如： LM = a, b, cc, dd q 连接：连接：LM=st|s L且

11、且t M 例如： LM = acc, add, bcc, bdd q 指数：指数：L0= ，Li=Li -1L 例如： L1=L, L2=LL=aa,ab,ba,bb L3=aaa, aab, aba, abb, baa, bab, bba, bbbq 闭包：闭包：L =L0L1L2q 正闭包：正闭包：L+=L1L2Kleene闭包闭包Kleene 星号,克林星号21语言运算的例子语言运算的例子L = A, B, , Z, a, b, , z ，D = 0, 1, , 9 L D ：是字符和数字的集合;LD ：一个字符的后面接一个数字的集合;L4 ：四个字符的集合 L* = 以及 L 上的所有

12、可能的串 L (L D )* ：以字符开头的字符和数字组成的串的集合D+ ：一个或多个数字组成的串的集合。223.2.3 正则表达式正则表达式q 例如，C语言的标识符集可以定义为：letter_ (letter_ | digit )*其中 letter_ a,b,z, A,B,Z, _ q 正则式(Regular Expression)可以用来表示简单的语简单的语言言，叫做正则集（regular set）。231. 是一个正则表达式，L()= 2. 如果a是上的一个符号,那么a是一个正则表达式，并且L(a)= a3. 假设 r和s都是正则表达式，分别表示语言 L(r) and L(s)，那么

13、(a) (r) | (s) 是一个正则表达式，表示语言 L(r) L(s) (b) (r)(s) 是一个正则表达式，表示语言L(r) L(s) (c) (r)* 是一个正则表达式，表示语言 (L(r)* (d) (r) 是一个正则表达式，表示语言 L(r) 所有的运算符都是左结合的。.precedence定义字母表定义字母表 上的正则表达式的规则上的正则表达式的规则24正则式定义的语言备注aa a (r) | (s)L(r)L(s) r和s是正则式(r)(s)L(r)L(s) r和s是正则式(r)*(L(r)* r是正则式(r)L(r) r是正则式(a) (b)*)| (c)可以写成ab*|

14、c 都是左结合的。优先级从高到低：*，连接，|25正则表达式的例子正则表达式的例子( =a,b)q 正则表达式正则集合（regular set )a | ba, b(a | b) (a | b )aa, ab, ba, bbaa | ab | ba | bbaa, ab, ba, bba*由0个或多个a构成的所有字符串集合(a | b)*由a和b构成的所有字符串集合a | a*bq 复杂的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 偶数个和偶数个组成的偶数个和偶数个组成的01字符串字符串letter_ (letter_ | digit )

15、*letter_ a,b,.z,A,B,Z,0,1,9, _ 26AXIOMDESCRIPTIONr | s = s | rr | (s | t) = (r | s) | t(r s) t = r (s t) r = rr = rr* = ( r | )*r ( s | t ) = r s | r t( s | t ) r = s r | t rr* = r*| 是可交换的| 是可结合的“连接”是可结合的“连接”是可分配的* 和 之间的关系是“连接”的单位元* 的幂等性正则表达式的代数性质正则表达式的代数性质27(rs)* r*s*(r|s)* r*|s*正则表达式的代数性质正则表达式的代数性

16、质283.2.4 正则定义正则定义为了让正则表达式的表示简洁，可以对正则式命名。 d1 r1 d2 r2 . . . dn rn各个di的名字都不同, di每个ri都是d1, d2, , di-1 上的正则式 29正则定义的例子正则定义的例子1q C语言的标识符集合letter_ A | B | | Z | a | b | | z | _digit 0 | 1 | | 9id letter_ ( letter_ | digit)* 如果代入，则有标识符标识符的正则表达式为( A | | Z | a | | z | _ ) ( A | | Z | a | | z | _ | 0 | 1 | |

17、9 )*30正则定义的例子正则定义的例子2q 无符号数集合(integer or floating point)，例如1946, 11.28, 63.6E8, 1.99E6 digit 0 | 1 | | 9digits digit digit*optionalFraction .digits | optionalExponent (E ( + | | ) digits ) | number digits optionalFraction optionalExponen313.2.5 正则表达式的扩展正则表达式的扩展1. “+” : 一个或多个，表示一个正则表达式及其语言的正闭包， r+表示语

18、言(L(r)+ r* = r+ | r+ = r r*2. “?” : 零个或一个出现，也就是说，r?等价于r| 3. “”: 一个正则表达式a1|a2|an（其中ai是字母表中的各个符号）可以缩写成a1a2an。例如：ade=a|d|e范围 :如果a1|a2|an是连续字符集、数字集等， 例如：A-Z = A | B | C | | Z32使用简略的表达方式使用简略的表达方式Using Shorthands q C语言的标识符集合letter_ A | B | | Z | a | b | | z | _digit 0 | 1 | | 9id letter_ ( letter_ | digit)* q 简化为：letter_ A-Za-z_digit 0-9id letter_ ( letter_ | digit)* 33使用简略的表达方式使用简略的表达方式digit 0 | 1 | | 9digits digit digit*optionalFraction .