PPT《第三章 词法分析》

第三章 词法分析 赵建华南京大学计算机系2009年2月 内容 词法分析器的作用词法单元的规约词法单元的识别词法分析器生成工具Lex有穷自动机从正则表达式到自动机词法分析器生成工具的设计方法 词法分析器的作用 读入源程序字符流、组成词素,输出词法单元序列.

过滤空白、换行、制表符、注释等.将词素添加到符号表中.在逻辑上独立于语法分析,但是通常和语法分析器处于同一趟中 为什么要设立独立的词法分析器 简化编译器的设计词法分析器可以首先完成一些简单的处理工作.提高编译器效率相对于语法分析,词法分析过程简单,可高效实现.(下推自动机 vs 有穷自动机)增强编译器的可移植性 词法单元、模式、词素 词法单元单元名是表示词法单位种类的抽象符号;

语法分析器通过单元名即可确定词法单元序列的结构.属性值通常用于语义分析之后的阶段模式描述了一类词法单元的词素可能具有的形式词素源程序中的字符序列它和某个词法单元的模式匹配,被词法分析器识别为该词法单元的实例. 词法单元、模式、词素(例子) printf( Total = % d\n , score);

printf, score和标识符(id)的模式匹配 Total = % d\n 和literal的模式匹配 词法单元的属性 一个模式匹配多个词素时,必须通过属性来传递附加的信息.属性值将被用于语义分析、代码生成等阶段.不同的目的需要不同的属性.因此,属性值通常是一个结构化数据.词法单元id的属性词素、类型、第一次出现的位置、… 内容 词法分析器的作用词法单元的规约词法单元的识别词法分析器生成工具Lex有穷自动机从正则表达式到自动机词法分析器生成工具的设计方法 词法单元的规约 正则表达式可以高效、简洁地描述处理词法单元时用到的模式类型.内容串和语言语言上的运算正则表达式正则定义正则表达式的扩展 串和语言(1) 字母表(alphabet):一个有穷的符号集合.符号典型例子:字母、数位、标点符号.例子:{0,1};

ASCII;

Unicode在理论上,我们可以把任意的有限集合看作字母表.字母表上的串(string)是该字母表中符号的有穷序列.串s的长度,即|s|,是指s中符号出现的次数;

空串:长度为0的串,ε语言(language)是某个给定字母表上的串的可数集合. 串和语言(2) 和串有关的术语(bannana)前缀:从串的尾部删除0个或多个符号后得到的串.(ban、banana、 ε)后缀:从串的开始处删除0个或多个符号后得到的串.(nana、banana、ε)子串:删除串的某个前缀和某个后缀得到的串.(banana、nan、 ε)真前缀、真后缀、真子串:既不等于原串,也不等于空串的前缀、后缀、子串.(前面例子的红色部分)子序列:从原串中删除0个或者多个符号后得到的串.(baan) 串和语言(3) 串的运算连接(concatenation):x和y的连接时把y附加到x的后面形成的串,记作xy.x=dog,y=house,xy=doghouse指数运算(幂运算):s0=ε,s1=s,si=si-1s;

x=dog,x0=ε,x1=dog,x3=dogdogdog 串和语言(4) 语言的运算 串和语言(5) 例子L={A,B,……,Z,a,b,……,z}D={0,1,……,9}L U D={A,B,……,Z,a,b,……,z,0,1,……,9}LD:520个长度为2的串的集合L4:所有由四个字母构成的串的集合L*:所有字母构成的集合,包括ε.L(L U D),D+ 正则表达式 字母表Σ上的正则表达式的定义基本部分ε 是一个正则表达式,L(ε)={ε}如果a是Σ上的一个符号,那么a是正则表达式,L(a)={a}归纳步骤:选择:(r) | (s),L((r) | (s))=L(r) U L(s);