《编译原理与技术 词法分析》由会员分享，可在线阅读，更多相关《编译原理与技术 词法分析（40页珍藏版）》请在金锄头文库上搜索。
1、编译原理与技术词法分析(1)9/1/20241编译原理与技术讲义词法分析词法分析器介绍正规式与正规集有限自动机词法分析器的自动生成Lex9/1/20242编译原理与技术讲义词法分析器介绍词法分析器的功能高级语言源程序词法分析器语法分析器tokenget_next_token编译器其它阶段符号表字符流记号（流）9/1/20243编译原理与技术讲义词法分析器介绍词法分析器的功能读源程序，产生记号序列剥去源程序中的注释（块、行）和“空白”符预处理宏处理与文件包含9/1/20244编译原理与技术讲义词法分析器介绍词法分析器作为独立子程序简化设计提高编译效率增强可移植性9/1/20245编译原理与技术讲
2、义词法分析器介绍记号、模式与单词记号同类单词的总称模式描述构成记号的字符串的规则单词源程序中能匹配任一记号的字符串9/1/20246编译原理与技术讲义程序语言的记号（1）记号单词模式关键字WHILEwhilewhileFORforfor标识符IDtemp, i,max字母开头的字母数字串常数NUM3.14100数字字符串.数字字符串9/1/20247编译原理与技术讲义程序语言的记号（2）记号单词模式运算符MUL*GT界符,串常量STRING“hello”there双（单）引号中间的字符串（不包括引号本身）9/1/20248编译原理与技术讲义词法分析器介绍词法分析器的二元输出 单词（字符串）的类
3、别匹配记号的单词多于一个时，须提供额外的信息以区别之9/1/20249编译原理与技术讲义词法分析器介绍词法分析器的二元输出记号影响语法分析的决策属性（如类型、偏移）则关系到记号的翻译9/1/202410编译原理与技术讲义词法分析器介绍e.g.1 pascal源程序片段：beginlength := length + 1;if length20 then read(nextch);end;9/1/202411编译原理与技术讲义e.g.1 pascal源程序片段的字符流(SP表示空格)beginntlengthSP:=SPlengthSP+SP1;ntifSPlength20SPthenSPrea
4、d(nextch);nend;9/1/202412编译原理与技术讲义e.g. 1 词法分析器的输出记号流(1) /不是多余的！ / 属性是常量“值”本身9/1/202413编译原理与技术讲义e.g. 1 词法分析器的输出记号流(2)9/1/202414编译原理与技术讲义词法分析器介绍超前搜索FORTRAN中的关键字“不保留”1） DO100K=1,102） DO100K=1.103） IF(5.EQ.M) I=104） IF(5)=55有关算符的识别C/C+, java的+, -, =, !=, = 等，与之对应 + , - , !, = 9/1/202415编译原理与技术讲义词法分析器介绍词
5、法错误可检测非法字符的出现if VS fi词法分析器的设计手工编写采用汇编语言或高级语言自动生成Lex9/1/202416编译原理与技术讲义词法分析器介绍状态转换图用于记号的识别。状态之间用带有标记（字符）的有向边连接；每读入一个字符会引起状态变化，直至单词（记号）被识别出来。开始状态：状态转换图的初始状态（尚未读字符）接受状态：某个单词被识别时所处的状态（终态）单词（记号）的识别过程即是从开始状态出发到某接受状态的变化过程。9/1/202417编译原理与技术讲义词法分析器介绍状态转换图012字母其它字母或数字识别标识符的转换图*034数字其它数字识别整数的转换图*9/1/202418编译原理
6、与技术讲义词法分析器介绍状态转换图05数字.识别Pascal无符号数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它9/1/202419编译原理与技术讲义词法分析器介绍状态转换图05数字.（红线）识别Pascal无符号整数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它9/1/202420编译原理与技术讲义词法分析器介绍状态转换图05数字.识别Pascal无符号小数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它9/1/202421编译原理与技术讲义状态转换图的实现e.g. 2 简单词法分析的转换图（识别关键字、标识符、无
7、符号整数、算符和界符）01空白符（n,t,SP）字母或数字字母非字母数字2*return( ID, 符号表条目指针） or return( 关键字，）3数字数字非数字字符4*return(NUM, 常量值或者常量表条目指针）to be continued 9/1/202422编译原理与技术讲义e.g. 2简单词法分析的转换图+5return（+, ）-6return（-, ）7*非*字符8*return（*, ）9return（*, ）*to be continued 9/1/202423编译原理与技术讲义e.g. 2简单词法分析的转换图1013return（LT, ）其它字符=14retur
8、n（EQ, ）*15=16*return（GE, ）17return（GT, ）其它字符to be continued 9/1/202424编译原理与技术讲义e.g. 2简单词法分析的转换图18：=19return（ASSIGN, ）20return（:, ）其它字符*；21return（；, ）其它22Error()状态转换程序9/1/202425编译原理与技术讲义串与语言语言语言L s | s 是上任一字符串，s称为语言L的一个句子。字母表符号/字符的非空有限集合e.g. 二进制数的0,1，而十进制数的0,1,9*表示上所有字符串的集合；L*字符串 上若干字符组成的有穷序列 9/1/202
9、426编译原理与技术讲义串与语言语言字符串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的前缀9/1/202427编译原理与技术讲义语言的运算语言的运算 描述运算语言L和语言M连接（积） LM= xy| xL且yM合并（和） LM=x| xL或xM闭包L*=L0L1L2=正闭包L+=L1L2L3=9/
10、1/202428编译原理与技术讲义语言e.g. L=a,b,z, D=0,1,9, B= _ LD=LD=L*=L(LD)*=(LB)(LDB)*=D+=9/1/202429编译原理与技术讲义正规式与正规集正规式用于描述记号的构成规则正规集正规式描述的语言（匹配正规式的串集）正规式正规集aa9/1/202430编译原理与技术讲义正规式与正规集正规式正规集R|SL(R)L(S)R SL(R) L(S)R*(L(R)*(R)L(R)如果R和S是上的正规式，分别对应上的正规集L(R)和L(S)，则9/1/202431编译原理与技术讲义正规式与正规集运算符优先级结合性或|低左结合连接 高左结合闭包*最
11、高左结合 上的正规式，其运算有 | 、 和 *9/1/202432编译原理与技术讲义正规式与正规集代数定律描述交换律R|SS|R结合律R | (S|T) = (R|S) | TR (ST) = (RS) T分配律R (S|T) = (RS) | (RT)(R|S) T = (RT) | (ST)同一律 R = R = R上的正规式，满足如下代数定律9/1/202433编译原理与技术讲义正规式与正规集上的正规式，也具有如下代数定律( R* ) * = R *( R | ) * = R * R+ = R R*9/1/202434编译原理与技术讲义正规式与正规集e.g.3 设=a, b, 则正规式正
12、规集a(a|b)*上以a开头的串集ba*上以b开头后跟任意个a的串集(a|b)*a(a|b)(a|b)上倒数第三个字符是a的串集9/1/202435编译原理与技术讲义正规式与正规集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开
13、头的串集。 9/1/202436编译原理与技术讲义正规式与正规集正规定义d1 r1d2 r2dn rn 各个di的名字不同；每个ri是d1 ,d2, di-1上的正规式 9/1/202437编译原理与技术讲义正规式与正规集e.g.4 Pascal 标识符 letter A | B | | Z | a | b | | z digit 0 | 1 | | 9 id letter ( letter | digit )*英文字母集合十进制数字集合标识符的正规定义9/1/202438编译原理与技术讲义正规式与正规集e.g.5 Pascal 无符号数digit 0 | 1 | | 9digits digit digit*fraction . digits | exponent ( E (+ | - | ) ) digits | num digits fraction exponent数字串集合小数部分（可空）指数部分（可空）9/1/202439编译原理与技术讲义正规式与正规集e.g.6 email 地址： name letter letter* field ( . name) *email name name field9/1/202440编译原理与技术讲义
