中科大2021－2022学年秋季第一学期《编译原理与技术》第二讲 词法分析（1）

1、2022/7/25编译原理与技术讲义1编译原理与技术词法分析(1)2022/7/25编译原理与技术讲义2词法分析词法分析器介绍正规式与正规集有限自动机词法分析器的自动生成Lex2022/7/25编译原理与技术讲义3词法分析器介绍词法分析器的功能高级语言源程序词法分析器语法分析器tokenget_next_token编译器其它阶段符号表字符流记号（流）2022/7/25编译原理与技术讲义4词法分析器介绍词法分析器的功能读源程序，产生记号序列剥去源程序中的注释（块、行）和“空白”符预处理宏处理与文件包含2022/7/25编译原理与技术讲义5词法分析器介绍词法分析器作为独立子程序简化设计提高编译效率

2、增强可移植性2022/7/25编译原理与技术讲义6词法分析器介绍记号、模式与单词记号同类单词的总称模式描述构成记号的字符串的规则单词源程序中能匹配任一记号的字符串2022/7/25编译原理与技术讲义7程序语言的记号（1）记号单词模式关键字WHILEwhilewhileFORforfor标识符IDtemp, i,max字母开头的字母数字串常数NUM3.14100数字字符串.数字字符串2022/7/25编译原理与技术讲义8程序语言的记号（2）记号单词模式运算符MUL*GT界符,串常量STRING“hello”there双（单）引号中间的字符串（不包括引号本身）2022/7/25编译原理与技术讲义9

3、词法分析器介绍词法分析器的二元输出 单词（字符串）的类别匹配记号的单词多于一个时，须提供额外的信息以区别之2022/7/25编译原理与技术讲义10词法分析器介绍词法分析器的二元输出记号影响语法分析的决策属性（如类型、偏移）则关系到记号的翻译2022/7/25编译原理与技术讲义11词法分析器介绍e.g.1 pascal源程序片段：beginlength := length + 1;if length20 then read(nextch);end;2022/7/25编译原理与技术讲义12e.g.1 pascal源程序片段的字符流(SP表示空格)beginntlengthSP:=SPlengthS

4、P+SP1;ntifSPlength20SPthenSPread(nextch);nend;2022/7/25编译原理与技术讲义13e.g. 1 词法分析器的输出记号流(1) /不是多余的！ / 属性是常量“值”本身2022/7/25编译原理与技术讲义14e.g. 1 词法分析器的输出记号流(2)2022/7/25编译原理与技术讲义15词法分析器介绍超前搜索FORTRAN中的关键字“不保留”1） DO100K=1,102） DO100K=1.103） IF(5.EQ.M) I=104） IF(5)=55有关算符的识别C/C+, java的+, -, =, !=, = 等，与之对应 + , -

5、, !, = 2022/7/25编译原理与技术讲义16词法分析器介绍词法错误可检测非法字符的出现if VS fi词法分析器的设计手工编写采用汇编语言或高级语言自动生成Lex2022/7/25编译原理与技术讲义17词法分析器介绍状态转换图用于记号的识别。状态之间用带有标记（字符）的有向边连接；每读入一个字符会引起状态变化，直至单词（记号）被识别出来。开始状态：状态转换图的初始状态（尚未读字符）接受状态：某个单词被识别时所处的状态（终态）单词（记号）的识别过程即是从开始状态出发到某接受状态的变化过程。2022/7/25编译原理与技术讲义18词法分析器介绍状态转换图012字母其它字母或数字识别标识符

6、的转换图*034数字其它数字识别整数的转换图*2022/7/25编译原理与技术讲义19词法分析器介绍状态转换图05数字.识别Pascal无符号数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它2022/7/25编译原理与技术讲义20词法分析器介绍状态转换图05数字.（红线）识别Pascal无符号整数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它2022/7/25编译原理与技术讲义21词法分析器介绍状态转换图05数字.识别Pascal无符号小数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它2022/7/25编译原理与技术

7、讲义22状态转换图的实现e.g. 2 简单词法分析的转换图（识别关键字、标识符、无符号整数、算符和界符）01空白符（n,t,SP）字母或数字字母非字母数字2*return( ID, 符号表条目指针） or return( 关键字，）3数字数字非数字字符4*return(NUM, 常量值或者常量表条目指针）to be continued 2022/7/25编译原理与技术讲义23e.g. 2简单词法分析的转换图+5return（+, ）-6return（-, ）7*非*字符8*return（*, ）9return（*, ）*to be continued 2022/7/25编译原理与技术讲义24e

8、.g. 2简单词法分析的转换图1013return（LT, ）其它字符=14return（EQ, ）*15=16*return（GE, ）17return（GT, ）其它字符to be continued 2022/7/25编译原理与技术讲义25e.g. 2简单词法分析的转换图18：=19return（ASSIGN, ）20return（:, ）其它字符*；21return（；, ）其它22Error()简单扫描程序状态转换程序2022/7/25编译原理与技术讲义26串与语言语言语言L s | s 是上任一字符串，s称为语言L的一个句子。字母表符号/字符的非空有限集合e.g. 二进制数的0,1

9、，而十进制数的0,1,9*表示上所有字符串的集合；L*字符串 上若干字符组成的有穷序列 2022/7/25编译原理与技术讲义27串与语言语言字符串e.g. 0,1上的0，1串（二进制数）如0111，10101；a,b上的 a, b, aa , abab, 空串， *，串长|s|s中所含字符的个数，| |=0串的连接运算任意串x，y，一般地，xyyx， x= x串的前缀 任意串x，从其第一个字符（最左字符）起的字符序列是其前缀。亦是。e.g. x = abc, 则，a，ab，abc均是x的前缀2022/7/25编译原理与技术讲义28语言的运算语言的运算 描述运算语言L和语言M连接（积）LM= x

10、y| xL 且 yM 合并（和）LM=x| xL 或 xM 闭包L*=L0L1L2=正闭包L+=L1L2L3=2022/7/25编译原理与技术讲义29语言e.g. L=a,b,z, D=0,1,9, B= _ LD = LD= L*= L(LD)*= (L B)(LDB)*= D+= 2022/7/25编译原理与技术讲义30正规式与正规集正规式用于描述记号的构成规则正规集正规式描述的语言（匹配正规式的串集）正规式正规集aa2022/7/25编译原理与技术讲义31正规式与正规集正规式正规集R | SL(R) L(S)R SL(R) L(S)R*(L(R)*(R)L(R)如果R和S是上的正规式，分

11、别对应上的正规集L(R)和L(S)，则2022/7/25编译原理与技术讲义32正规式与正规集运算符优先级结合性或|低左结合连接 高左结合闭包*最高左结合 上的正规式，其运算有 | 、 和 *2022/7/25编译原理与技术讲义33正规式与正规集代数定律描述交换律R | S S | R结合律R | (S|T) = (R|S) | TR (ST) = (RS) T分配律R (S|T) = (RS) | (RT)(R|S) T = (RT) | (ST)同一律 R = R = R上的正规式，满足如下代数定律2022/7/25编译原理与技术讲义34正规式与正规集上的正规式，也具有如下代数定律( R*

12、) * = R *( R | ) * = R * R+ = R R*2022/7/25编译原理与技术讲义35正规式与正规集e.g.3 设=a, b, 则正规式正规集a(a|b)*上以a开头的串集ba*上以b开头后跟任意个a的串集(a|b)*a(a|b)(a|b)上倒数第三个字符是a的串集2022/7/25编译原理与技术讲义36正规式与正规集e.g.3 设=a, b，R = a(a|b)*，事实上有 L(R) = L( a(a|b)* )= L(a) L(a|b)*)= L(a) ( L(a|b) )*= L(a) ( L(a) L(b) )*= a ( a b )*= a ( a, b )*=

13、 a , a, b, aa, ab, ba, bb, abb, = a,aa, ab, aaa, aab, aba, abb, aabb, 即L(R)是 上以a开头的串集。2022/7/25编译原理与技术讲义37正规式与正规集正规定义d1 r1d2 r2dn rn各个di的名字不同；每个ri是d1 ,d2, di-1上的正规式 2022/7/25编译原理与技术讲义38正规式与正规集e.g.4 Pascal 标识符letter A | B | | Z | a | b | | zdigit 0 | 1 | | 9 id letter ( letter | digit )*英文字母集合十进制数字集合标识符的正规定义2022/7/25编译原理与技术讲义39正规式与正规集e.g.5 Pascal 无符号数digit 0 | 1 | | 9digits digit di