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