第二章词法分析 记号 (token) 源程序一词法分析器 语法分析器 取下一个记号 符号表 本章内容 词法分析器:把构成源程序的字符流翻译成 记号流,还完成和用户接口的一些任务 围绕词法分析器的自动生成展开 介绍正规式、状态转换图和有限自动机概念
第二章 词法分析 本章内容 – 词法分析器：把构成源程序的字符流翻译成 记号流，还完成和用户接口的一些任务 – 围绕词法分析器的自动生成展开 – 介绍正规式、状态转换图和有限自动机概念 词法分析器 语法分析器 符号表 记号(token) 取下一个记号 源程序
21词法记号及属性 211词法记号、模式、词法单元 记号名词法单元例举模式的非形式描述 f 字符 for or 字符,0,r relation <, 或<=或=或 d sum, count,D5由字母开头的字母数字串 number3.1,10,28E12任何数值常数 literal seg. error”引号“和”之间任意不含 引号本身的字符串
2.1 词法记号及属性 2.1.1 词法记号、模式、词法单元 记号名 词法单元例举 模式的非形式描述 if if 字符i, f for for 字符f, o, r relation < , <= , = , … < 或 <= 或 = 或 … id sum, count, D5 由字母开头的字母数字串 number 3.1, 10, 2.8 E12 任何数值常数 literal “seg. error” 引号“和”之间任意不含 引号本身的字符串
21词法记号及属性 历史上词法定义中的一些问题 忽略空格带来的困难 DO8I=3.75等同于DO8I=3.75 DO8I=3,75 关键字不保留 IF THENTHENTHEN=ELSE: ELSE 关键字、保留字和标准标识符的区别 保留字是语言预先确定了含义的词法单元 标准标识符也是预先确定了含义的标识符,但程 序可以重新声明它的含义
2.1 词法记号及属性 • 历史上词法定义中的一些问题 –忽略空格带来的困难 DO 8 I 3. 75 等同于 DO8I 3. 75 DO 8 I 3, 75 – 关键字不保留 IF THEN THEN THEN=ELSE；ELSE … • 关键字、保留字和标准标识符的区别 –保留字是语言预先确定了含义的词法单元 – 标准标识符也是预先确定了含义的标识符，但程 序可以重新声明它的含义
21词法记号及属性 212词法记号的属性 position= initial t rate*60的记号和属性值: id,指向符号表中 position条目的指针〉 Assign op id,指向符号表中 initial条目的指针〉 Kadd op) id,指向符号表中rate条目的指针〉 mul op 〈 number,整数值60)
2.1 词法记号及属性 2.1.2 词法记号的属性 position = initial + rate 60的记号和属性值： id，指向符号表中position条目的指针 assign _ op id，指向符号表中initial条目的指针 add_op id，指向符号表中rate条目的指针 mul_ op number，整数值60
21词法记号及属性 213词法错误 词法分析器对源程序采取非常局部的观点 例:难以发现下面的错误 f(a==f(x)) 在实数是“数字串数字串”格式下,可以发现下 面的错误 123.x 紧急方式的错误恢复 删掉当前若干个字符,直至能读出正确的记号 错误修补 进行增、删、替换和交换字符的尝试
2.1 词法记号及属性 2.1.3 词法错误 –词法分析器对源程序采取非常局部的观点 –例：难以发现下面的错误 fi (a == f (x) ) … – 在实数是“数字串.数字串”格式下，可以发现下 面的错误 123.x –紧急方式的错误恢复 删掉当前若干个字符，直至能读出正确的记号 – 错误修补 进行增、删、替换和交换字符的尝试
22词法记号的描述与识别 221串和语言 字母表:符号的有限集合,例:∑={0,1} 串:符号的有穷序列,例:0110,ε 语言:字母表上的一个串集 {e,0,00,000,},{e},z 句子:属于语言的串 串的运算 连接(积)x,s=ε=s 幂 s为8,s为sls(i>0)
2.2 词法记号的描述与识别 2.2.1 串和语言 – 字母表：符号的有限集合， 例： = { 0, 1} – 串：符号的有穷序列，例：0110, – 语言：字母表上的一个串集 {, 0, 00, 000, …}, {}, – 句子：属于语言的串 • 串的运算 – 连接（积） xy，s = s = s –幂 s 0为，s i为s i-1s（i > 0）
22词法记号的描述与识别 语言的运算 并 L∪M={s|s∈L或s∈M} 连接: LM={ss∈L且t∈M} 幂 L0是{},L是LL 闭包: L*=L0∪L∪L2∪ 正闭包:L+=L1∪L2U 例 L:{A,B,…,Z,a,b,…,z},D:{0,1,…,9} L∪D,LD,L6,L,L(L∪D),D+
2.2 词法记号的描述与识别 • 语言的运算 –并： 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+
22词法记号的描述与识别 222正规式 正规式用来表示简单的语言,叫做正规集 正规式 定义的语言备注 ca 18 ∈ ∑ (r)|(s) L(rUL(S r和s是正规式 (r)(S) L(L(S) r和s是正规式 (L(r) r是正规式 L( r是正规式 (a)(b)(c)可以写成abc
2.2 词法记号的描述与识别 2.2.2 正规式 正规式用来表示简单的语言，叫做正规集 正规式 定义的语言 备注 {} 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
22词法记号的描述与识别 °正规式的例子∑={a,b a b (a|b)(a|b) Raa, ab, ba, bbj aa ab ba bb aa, ab, ba, bby 由字母a构成的所有串集 (a|b) 由a和b构成的所有串集 复杂的例子 (00|11((01|10)(00|11)*(01|10)))* 句子:01001101000100001001
2.2 词法记号的描述与识别 • 正规式的例子 = {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
22词法记号的描述与识别 223正规定义 对正规式命名,使表示简洁 → d2→ dn→>rn 各个d的名字都不同 每个r都是∑∪u{1,d2,…,dl1}上的正规式
2.2 词法记号的描述与识别 2.2.3 正规定义 – 对正规式命名，使表示简洁 d1 r1 d2 r2 . . . dn rn –各个di的名字都不同 –每个ri都是 {d1 , d2 , …, di-1 }上的正规式