第二讲词法分析

2026/5/2《编译原理与技术》讲义1编译原理与技术词法分析(1)2026/5/2《编译原理与技术》讲义2词法分析词法分析器介绍正规式与正规集有限自动机词法分析器的自动生成－Lex2026/5/2《编译原理与技术》讲义3词法分析器介绍词法分析器的功能高级语言源程序词法分析器语法分析器tokenget_next_token编译器其它阶段符号表字符流记号（流）2026/5/2《编译原理与技术》讲义4词法分析器介绍词法分析器的功能读源程序，产生记号序列剥去源程序中的注释（块、行）和“空白”符预处理－宏处理与文件包含2026/5/2《编译原理与技术》讲义5词法分析器介绍词法分析器作为独立子程序简化设计提高编译效率增强可移植性2026/5/2《编译原理与技术》讲义6词法分析器介绍记号、模式与单词记号－同类单词的总称模式－描述构成记号的字符串的规则单词－源程序中能匹配任一记号的字符串2026/5/2《编译原理与技术》讲义7程序语言的记号（1）记号单词模式关键字WHILEwhilewhileFORforfor标识符IDtemp,i,max字母开头的字母数字串常数NUM3.14100数字字符串{.数字字符串}2026/5/2《编译原理与技术》讲义8程序语言的记号（2）记号单词模式运算符MUL**GT>>界符,,,串常量STRING“hello”‘there’双（单）引号中间的字符串（不包括引号本身）2026/5/2《编译原理与技术》讲义9词法分析器介绍词法分析器的二元输出

<记号，记号的属性>单词（字符串）的类别匹配记号的单词多于一个时，须提供额外的信息以区别之2026/5/2《编译原理与技术》讲义10词法分析器介绍词法分析器的二元输出

<记号，记号的属性>记号影响语法分析的决策属性（如类型、偏移）则关系到记号的翻译2026/5/2《编译原理与技术》讲义11词法分析器介绍e.g.1pascal源程序片段：

begin length:=length+1; iflength<20thenread(nextch); end;2026/5/2《编译原理与技术》讲义12e.g.1pascal源程序片段的字符流(SP表示空格)begin\n\tlengthSP:=SPlengthSP+SP1;\n\tifSPlength<20SPthenSPread(nextch);\nend;2026/5/2《编译原理与技术》讲义13e.g.1词法分析器的输出记号流(1)<BEGIN,-><ID,指向符号表length条目的指针><ASSIGN,-><ID,指向符号表length条目的指针>//不是多余的！！<+,-><NUM,1>//属性是常量“值”本身<;,-><IF,->2026/5/2《编译原理与技术》讲义14e.g.1词法分析器的输出记号流(2)<ID,指向符号表length条目的指针><LT,-><NUM,20><THEN,-><READ,-><(,-><ID,指向符号表nextch条目的指针><),-><END,-><;,->2026/5/2《编译原理与技术》讲义15词法分析器介绍超前搜索FORTRAN中的关键字“不保留”

1）DO100K=1,10 2）DO100K=1.10 3）IF(5.EQ.M)I=10 4）IF(5)=55有关算符的识别

C/C++,java的++,--,>=,!=,==等，与之对应

+,->,!,= 2026/5/2《编译原理与技术》讲义16词法分析器介绍词法错误可检测非法字符的出现ifVSfi词法分析器的设计手工编写－采用汇编语言或高级语言自动生成－Lex2026/5/2《编译原理与技术》讲义17词法分析器介绍状态转换图

用于记号的识别。状态之间用带有标记（字符）的有向边连接；每读入一个字符会引起状态变化，直至单词（记号）被识别出来。 开始状态：状态转换图的初始状态（尚未读字符） 接受状态：某个单词被识别时所处的状态（终态） 单词（记号）的识别过程即是从开始状态出发到某接受状态的变化过程。2026/5/2《编译原理与技术》讲义18词法分析器介绍状态转换图 012字母其它字母或数字识别标识符的转换图*034数字其它数字识别整数的转换图*2026/5/2《编译原理与技术》讲义19词法分析器介绍状态转换图 05数字.识别Pascal无符号数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它2026/5/2《编译原理与技术》讲义20词法分析器介绍状态转换图 05数字.（红线）识别Pascal无符号整数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它2026/5/2《编译原理与技术》讲义21词法分析器介绍状态转换图 05数字.识别Pascal无符号小数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它2026/5/2《编译原理与技术》讲义22状态转换图的实现e.g.2简单词法分析的转换图（识别关键字、标识符、无符号整数、算符和界符）01空白符（\n,\t,SP）字母或数字字母非字母数字2*return(ID,符号表条目指针）orreturn(关键字，－）3数字数字非数字字符4*return(NUM,常量值或者常量表条目指针）tobecontinued

2026/5/2《编译原理与技术》讲义23e.g.2简单词法分析的转换图+5return（+,－）-6return（-,－）7*非*字符8*return（*,－）9return（**,－）*tobecontinued

2026/5/2《编译原理与技术》讲义24e.g.2简单词法分析的转换图10<=11return（LE,－）12return（NE,－）>13return（LT,－）其它字符=14return（EQ,－）*15>=16*return（GE,－）17return（GT,－）其它字符tobecontinued

2026/5/2《编译原理与技术》讲义25e.g.2简单词法分析的转换图18：=19return（ASSIGN,－）20return（:,－）其它字符*；21return（；,－）其它22Error()简单扫描程序状态转换程序2026/5/2《编译原理与技术》讲义26串与语言语言语言L＝{s|s是∑上任一字符串}，

s称为语言L的一个句子。字母表∑－符号/字符的非空有限集合e.g.二进制数的∑＝{0,1}，而十进制数的∑＝{0,1,…,9}∑*－表示∑上所有字符串的集合；L

∑*字符串－∑上若干字符组成的有穷序列

2026/5/2《编译原理与技术》讲义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的前缀2026/5/2《编译原理与技术》讲义28语言的运算语言的运算

描述运算语言L和语言M连接（积）LM={xy|x∈L且y∈M}合并（和）L∪M={x|x∈L或x∈M}闭包L*=L0∪L1∪L2∪…=正闭包L+=L1∪L2∪L3∪…=2026/5/2《编译原理与技术》讲义29语言

e.g.L={a,b,…,z},D={0,1,…,9},B={_} L∪D={…} LD={…} L*={…} L(L∪D)*={…}(L∪B)(L∪D∪B)*={…} D+={…}2026/5/2《编译原理与技术》讲义30正规式与正规集正规式－用于描述记号的构成规则正规集－正规式描述的语言（匹配正规式的串集）正规式正规集

{

}∅∅a∈

{a}2026/5/2《编译原理与技术》讲义31正规式与正规集正规式正规集R|SL(R)∪L(S)R·SL(R)·L(S)R*(L(R))*(R)L(R)如果R和S是上的正规式，分别对应上的正规集L(R)和L(S)，则2026/5/2《编译原理与技术》讲义32正规式与正规集运算符优先级结合性或|低左结合连接·高左结合闭包*最高左结合

上的正规式，其运算有|、

·和*2026/5/2《编译原理与技术》讲义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

上的正规式，满足如下代数定律－－2026/5/2《编译原理与技术》讲义34正规式与正规集

上的正规式，也具有如下代数定律－－(R*)*=R*(R|)*=R*R+=RR*2026/5/2《编译原理与技术》讲义35正规式与正规集e.g.3设

={a,b},则正规式正规集a(a|b)*

上以a开头的串集ba*

上以b开头后跟任意个a的串集(a|b)*a(a|b)(a|b)

上倒数第三个字符是a的串集2026/5/2《编译原理与技术》讲义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})* ={a}{,a,b,aa,ab,ba,bb,abb,…} ={a,aa,ab,aaa,aab,aba,abb,aabb,…}即L(R)是上以a开头的串集。

2026/5/2《编译原理与技术》讲义37正规式与正规集正规定义

d1

r1 d2r2 … dnrn

各个di的名字不同；每个ri是∪{d1,d2,

…

di-1}上的正规式

2026/5/2《编译原理与技术》讲义38正规式与正规集e.g.4Pascal标识符

letterA|B|…|Z|a|b|…|z

digit0|1|…|9

idlette