编译原理与技术 词法分析.ppt
2023/4/26,编译原理与技术讲义,1,编译原理与技术,词法分析(1),2023/4/26,编译原理与技术讲义,2,词法分析,词法分析器介绍正规式与正规集有限自动机词法分析器的自动生成Lex,2023/4/26,编译原理与技术讲义,3,词法分析器介绍,词法分析器的功能,高级语言源程序,词法分析器,语法分析器,token,get_next_token,编译器其它阶段,符号表,字符流,记号（流）,2023/4/26,编译原理与技术讲义,4,词法分析器介绍,词法分析器的功能读源程序，产生记号序列剥去源程序中的注释（块、行）和“空白”符预处理宏处理与文件包含,2023/4/26,编译原理与技术讲义,5,词法分析器介绍,词法分析器作为独立子程序简化设计提高编译效率增强可移植性,2023/4/26,编译原理与技术讲义,6,词法分析器介绍,记号、模式与单词记号同类单词的总称模式描述构成记号的字符串的规则单词源程序中能匹配任一记号的字符串,2023/4/26,编译原理与技术讲义,7,程序语言的记号（1）,2023/4/26,编译原理与技术讲义,8,程序语言的记号（2）,2023/4/26,编译原理与技术讲义,9,词法分析器介绍,词法分析器的二元输出,单词（字符串）的类别,匹配记号的单词多于一个时，须提供额外的信息以区别之,2023/4/26,编译原理与技术讲义,10,词法分析器介绍,词法分析器的二元输出,记号影响语法分析的决策,属性（如类型、偏移）则关系到记号的翻译,2023/4/26,编译原理与技术讲义,11,词法分析器介绍,e.g.1 pascal源程序片段：beginlength:=length+1;if length20 then read(nextch);end;,2023/4/26,编译原理与技术讲义,12,2023/4/26,编译原理与技术讲义,13,e.g.1 词法分析器的输出记号流(1),/不是多余的！/属性是常量“值”本身,2023/4/26,编译原理与技术讲义,14,e.g.1 词法分析器的输出记号流(2),2023/4/26,编译原理与技术讲义,15,词法分析器介绍,超前搜索FORTRAN中的关键字“不保留”1）DO100K=1,102）DO100K=1.103）IF(5.EQ.M)I=104）IF(5)=55有关算符的识别C/C+,java的+,-,=,!=,=等，与之对应+,-,!,=,2023/4/26,编译原理与技术讲义,16,词法分析器介绍,词法错误可检测非法字符的出现if VS fi词法分析器的设计手工编写采用汇编语言或高级语言自动生成Lex,2023/4/26,编译原理与技术讲义,17,词法分析器介绍,状态转换图用于记号的识别。状态之间用带有标记（字符）的有向边连接；每读入一个字符会引起状态变化，直至单词（记号）被识别出来。开始状态：状态转换图的初始状态（尚未读字符）接受状态：某个单词被识别时所处的状态（终态）单词（记号）的识别过程即是从开始状态出发到某接受状态的变化过程。,2023/4/26,编译原理与技术讲义,18,词法分析器介绍,状态转换图,2023/4/26,编译原理与技术讲义,19,词法分析器介绍,状态转换图,0,5,数字,.,识别Pascal无符号数的转换图,*,数字,6,7,8,9,10,11,数字,数字,E,+|-,数字,数字,其它,E,数字,其它,其它,2023/4/26,编译原理与技术讲义,20,词法分析器介绍,状态转换图,0,5,数字,.,（红线）识别Pascal无符号整数的转换图,*,数字,6,7,8,9,10,11,数字,数字,E,+|-,数字,数字,其它,E,数字,其它,其它,2023/4/26,编译原理与技术讲义,21,词法分析器介绍,状态转换图,0,5,数字,.,识别Pascal无符号小数的转换图,*,数字,6,7,8,9,10,11,数字,数字,E,+|-,数字,数字,其它,E,数字,其它,其它,2023/4/26,编译原理与技术讲义,22,状态转换图的实现e.g.2 简单词法分析的转换图（识别关键字、标识符、无符号整数、算符和界符）,to be continued,2023/4/26,编译原理与技术讲义,23,e.g.2简单词法分析的转换图,to be continued,2023/4/26,编译原理与技术讲义,24,e.g.2简单词法分析的转换图,10,=,11,return（LE,）,12,return（NE,）,13,return（LT,）,其它字符,=,14,return（EQ,）,*,15,=,16,*,return（GE,）,17,return（GT,）,其它字符,to be continued,2023/4/26,编译原理与技术讲义,25,e.g.2简单词法分析的转换图,18,：,=,19,return（ASSIGN,）,20,return（:,）,其它字符,*,；,21,return（；,）,其它,22,Error(),状态转换程序,2023/4/26,编译原理与技术讲义,26,串与语言,语言语言L s|s 是上任一字符串，s称为语言L的一个句子。字母表符号/字符的非空有限集合e.g.二进制数的0,1，而十进制数的0,1,9*表示上所有字符串的集合；L*字符串 上若干字符组成的有穷序列,2023/4/26,编译原理与技术讲义,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的前缀,2023/4/26,编译原理与技术讲义,28,语言的运算,2023/4/26,编译原理与技术讲义,29,语言e.g.L=a,b,z,D=0,1,9,B=_ LD=LD=L*=L(LD)*=(L B)(LDB)*=D+=,2023/4/26,编译原理与技术讲义,30,正规式与正规集,正规式用于描述记号的构成规则正规集正规式描述的语言（匹配正规式的串集）,2023/4/26,编译原理与技术讲义,31,正规式与正规集,如果R和S是上的正规式，分别对应上的正规集L(R)和L(S)，则,2023/4/26,编译原理与技术讲义,32,正规式与正规集,上的正规式，其运算有|、和*,2023/4/26,编译原理与技术讲义,33,正规式与正规集,上的正规式，满足如下代数定律,2023/4/26,编译原理与技术讲义,34,正规式与正规集,上的正规式，也具有如下代数定律(R*)*=R*(R|)*=R*R+=R R*,2023/4/26,编译原理与技术讲义,35,正规式与正规集,e.g.3 设=a,b,则,2023/4/26,编译原理与技术讲义,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开头的串集。,2023/4/26,编译原理与技术讲义,37,正规式与正规集,正规定义d1 r1d2 r2dn rn各个di的名字不同；每个ri是d1,d2,di-1上的正规式,2023/4/26,编译原理与技术讲义,38,正规式与正规集,e.g.4 Pascal 标识符letter A|B|Z|a|b|zdigit 0|1|9 id letter(letter|digit)*,英文字母集合,十进制数字集合,标识符的正规定义,2023/4/26,编译原理与技术讲义,39,正规式与正规集,e.g.5 Pascal 无符号数digit 0|1|9digits digit digit*fraction.digits|exponent(E(+|-|)digits|num digits fraction exponent,数字串集合,小数部分（可空）,指数部分（可空）,2023/4/26,编译原理与技术讲义,40,正规式与正规集,e.g.6 email 地址：name letter letter*field(.name)*email name name field,
