PDF《编译原理与技术》

0 5 数字 . (红线)识别Pascal无符号整数的转换图 * 数字

6 7

8 9

10 11 数字 数字 E +|- 数字 数字 其它 E 数字 其它 其它 2015/9/6 《编译原理与技术》讲义

21 词法分析器介绍 ? 状态转换图

0 5 数字 . 识别Pascal无符号小数的转换图 * 数字

6 7

8 9

10 11 数字 数字 E +|- 数字 数字 其它 E 数字 其它 其它 2015/9/6 《编译原理与技术》讲义

22 ? 状态转换图的实现 e.g.

2 简单词法分析的转换图(识别关键字、标识符、 无符号整数、算符和界符)

0 1 空白符(\n,\t,SP) 字母或数字 字母 非字母数字

2 * return( ID, 符号表条目指针) or return( 关键字,-)

3 数字 数字 非数字字符

4 * return(NUM, 常量值或者常量 表条目指针) to be continued ? 2015/9/6 《编译原理与技术》讲义

23 ? e.g. 2简单词法分析的转换图 +

5 return(+, -) -

6 return(-, -)

7 * 非*字符

8 * return(*, -)

9 return(**, -) * to be continued ? 2015/9/6 《编译原理与技术》讲义

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 ? 2015/9/6 《编译原理与技术》讲义

25 ? e.g. 2简单词法分析的转换图

18 : =

19 return(ASSIGN, -)

20 return(:, -) 其它字符 * ;

21 return(;

, -) 其它

22 Error() 状态转换程序 2015/9/6 《编译原理与技术》讲义

26 串与语言 ? 语言 ? 语言L={ s | s 是∑上任一字符串}, s称为语言L的一个句子. ? 字母表∑-符号/字符的非空有限集合 e.g. 二进制数的∑={0,1},而十进制数的∑= {0,1,…,9} ∑*-表示∑上所有字符串的集合;

L?∑* ? 字符串- ∑上若干字符组成的有穷序列 2015/9/6 《编译原理与技术》讲义

27 串与语言 ? 语言 ? 字符串 e.g. ∑={0,1}上的0,1串(二进制数)如0111, 10101;

∑={a,b}上的 a, b, aa , abab, … ?空串-ε, ε∈ ∑*, ?串长-|s|={s中所含字符的个数},| ε|=0 ?串的连接运算-任意串x,y,一般地,xy≠yx, xε= εx ?串的前缀- 任意串x,从其第一个字符(最左字符) 起的字符序列是其前缀.ε亦是. e.g. x = abc, 则ε,a,ab,abc均是x的前缀 2015/9/6 《编译原理与技术》讲义

28 语言的运算 语言的运算 描述 运算 语言L和语言M 连接(积) LM={ xy| x∈L 且y∈M } 合并(和) L∪M={x| x∈L 或x∈M } 闭包 L*=L0∪L1∪L2∪…= 正闭包 L+=L1∪L2∪L3∪…=

0 i i L ∞ = ?

1 i i L ∞ = ? 2015/9/6 《编译原理与技术》讲义

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+={…} 2015/9/6 《编译原理与技术》讲义

30 正规式与正规集 ? 正规式-用于描述记号的构成规则 ? 正规集-正规式描述的语言(匹配正规式的 串集) 正规式 正规集 ε {ε} ? ? a∈∑ {a} 2015/9/6 《编译原理与技术》讲义

31 正规式与正规集 正规式 正规集 R | S L(R) ∪ L(S) R ・ S L(R) ・ L(S) R* (L(R))* (R) L(R) 如果R和S是∑上的正规式,分别对应∑上的正规 集L(R)和L(S),则2015/9/6 《编译原理与技术》讲义

32 正规式与正规集 运算符 优先级 结合性 或|低左结合 连接 ・ 高 左结合 闭包 * 最高 左结合 ∑上的正规式,其运算有 | 、 ・ 和*2015/9/6 《编译原理与技术》讲义

33 正规式与正规集 代数定律 描述 交换律 R | S = S | R 结合律 R | (S|T) = (R|S) | T R (ST) = (RS) T 分配律 R (S|T) = (RS) | (RT) (R|S) T = (RT) | (ST) 同一律 ε R = R ε = R ∑上的正规式,满足如下代数定律-- 2015/9/6 《编译原理与技术》讲义