文档介绍：第二章词法分析
本章内容
词法分析器:把构成源程序的字符流翻译成记号流,还完成和用户接口的一些任务
围绕词法分析器的自动生成展开
介绍正规式、状态转换图和有限自动机概念
词法分析器
语法分析器
符号表
记号(token)
取下一个记号
源程序
词法记号及属性
词法记号、模式、词法单元
词法记号 词法单元例举 模式的非形式描述
var var var
for for for
relation < , < = , = , …< 或<= 或= 或…
id sum, count, D5 由字母开头的字母数字串
num , 10, E12 任何数值常数
literal “seg. error” 引号“和”之间的任意字符
串,但引号本身除外
词法记号及属性
历史上词法定义中的一些问题
忽略空格带来的困难
DO 8 I 3. 75 DO8I 3. 75
DO 8 I 3, 75
关键字是否保留
IF THEN THEN THEN=ELSE;ELSE …
关键字、保留字和标准标识符的区别
词法记号及属性
词法记号的属性
position := initial + rate * 60的记号和属性值:
id,指向符号表中position条目的指针
assign _ op,
id,指向符号表中initial条目的指针
add_op,+
id,指向符号表中rate条目的指针
mul_ op, *
num,整数值60
词法记号及属性
词法错误
词法分析器对源程序采取非常局部的观点
难以发现下面的错误
fi (a == f (x) ) …
,可以发现下面的错误
123.
紧急方式的错误恢复
错误修补
词法记号的描述与识别
串和语言
字母表:符号的有限集合, 例:= {0, 1}
串:符号的有穷序列,例:0110,
语言:字母表上的一个串集
{, 0, 00, 000, …}, {},
句子:属于语言的串
串的运算
连接 xy,s= s = s
积(指数) s0为,si为si -1s(i > 0)
词法记号的描述与识别
语言的运算
和:L M = {s | s L 或 s M }
连接:LM = {st | s L 且 t M}
指数:L0是{},Li是Li -1L
闭包:L= L0 L1 L2 …
正闭包: L+ = L1 L2 …
例
L: { A, B, …, Z, a, b, …, z }, D: { 0, 1, …, 9 }
L D, LD, L6, L*, L(L D )*, D+
词法记号的描述与识别
正规式
正规式用来表示简单的语言,叫做正规集
正规式定义的语言备注
{}
a {a} a
(r) | (s) L(r)∪L(s) r和s是正规式
(r)(s) L(r)L(s) r和s是正规式
(r)* (L(r))* r是正规式
(r) L(r) r是正规式
((a) (b)*)| (c)可以写成ab*| c
词法记号的描述与识别
正规式的例子= {a, b}
a | b {a, b}
(a | b) (a | b ) {aa, ab, ba, bb}
aa | ab | ba | bb {aa, ab, ba, bb}
a* 由字母a构成的所有串集
(a | b)* 由a和b构成的所有串集
复杂的例子
( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) )
句子:01001101000010000010111001
词法记号的描述与识别
正规定义
对正规式命名,使表示简洁。
d1 r1
d2 r2
. . .
dn rn
各个di的名字都不同
每个ri都是{d1, d2, …, di-1 }上的正规式