第三章 词法分析
第三章 词法分析 本章内容 词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务 围绕词法分析器的自动生成展开 第三章 词法分析 词法分析器 语法分析器 符号表 记号(token) 取下一个记号 源程序 本章内容 词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务 围绕词法分析器的自动生成展开 介绍正则式、状态转换图和有限自动机概念
词法分析初步：正则表达式，状态转换图 3.1~3.4
3.1 词法记号及属性 3.1.1 词法记号、模式、词法单元 if if 字符i, f for for 字符f, o, r 记号名 词法单元例举 模式的非形式描述 if if 字符i, f for for 字符f, o, r relation < , <= , = , … < 或 <= 或 = 或 … id sum, count, D5 由字母开头的字母数字串 number 3.1, 10, 2.8 E12 任何数值常数 literal “seg. error” 引号“和”之间任意不含 引号本身的字符串
3.1 词法记号及属性 历史上词法定义中的一些问题 关键字、保留字和标准标识符的区别 忽略空格带来的困难 DO 8 I 3. 75 等同于 DO8I 3. 75 DO 8 I 3, 75 关键字不保留 IF THEN THEN THEN=ELSE；ELSE … 关键字、保留字和标准标识符的区别 保留字是语言预先确定了含义的词法单元 标准标识符也是预先确定了含义的标识符，但程序可以重新声明它的含义
3.1 词法记号及属性 3.1.2 词法记号的属性 position = initial + rate 60的记号和属性值： id，指向符号表中position条目的指针 assign _ op id，指向符号表中initial条目的指针 add_op id，指向符号表中rate条目的指针 mul_ op number，整数值60
3.1 词法记号及属性 3.1.3 词法错误 词法分析器对源程序采取非常局部的观点 例：难以发现下面的错误 fi (a == f (x) ) … 在实数是“数字串.数字串”格式下，可以发现下面的错误 123.x 紧急方式的错误恢复 删掉当前若干个字符，直至能读出正确的记号 错误修补 进行增、删、替换和交换字符的尝试
3.2 词法记号的描述与识别 3.2.1 串和语言 串的运算 字母表：符号的有限集合， 例： = { 0, 1} 串：符号的有穷序列，例：0110, 语言：字母表上的一个串集 {, 0, 00, 000, …}, {}, 句子：属于语言的串 串的运算 连接（积） xy，s = s = s 幂 s0为，si为si-1s（i > 0）
3.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+
3.2 词法记号的描述与识别 3.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
3.2 词法记号的描述与识别 正则式的例子 = {a, b} 复杂的例子 句子：01001101000010000010111001 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
3.2 词法记号的描述与识别 正则式等价：表示同样语言的正则式
3.2 词法记号的描述与识别 3.2.3 正则定义 对正则式命名，使表示简洁 d1 r1 d2 r2 . . . dn rn 各个di的名字都不同 每个ri都是 {d1, d2, …, di-1 }上的正则式
3.2 词法记号的描述与识别 正则定义的例子 C语言的标识符是字母、数字和下划线组成的串 letter_ A | B | … | Z | a | b | … | z | _ digit 0 | 1 | … | 9 id letter_(letter_ |digit)*
3.2 词法记号的描述与识别 正则定义的例子 无符号数集合，例1946,11.28,63E8,1.99E6 digit 0 | 1 | … | 9 digits digit digit* optional_fraction .digits| optional_exponent ( E ( + | | ) digits ) | numberdigits optional_fraction optional_exponent 简化表示 number digit+ (.digit+)? (E(+|)? digit+)?
3.2 词法记号的描述与识别 正则定义的例子（进行下一步讨论的例子） while while do do relop < | < = | = | < > | > | > = letter A | B | … | Z | a | b | … | z id letter (letter | digit )* number digit+ (.digit+)? (E (+ | )? digit+)? delim blank | tab | newline ws delim+
3.2 词法记号的描述与识别 词法单元的识别 stmt if expr then stmt | if expr then stmt else stmt | ε expr term relop term | term term id | number
3.2 词法记号的描述与识别 词法单元的识别 stmt if expr then stmt | if expr then stmt else stmt | ε expr term relop term | term term id | number digit [0-9] digits digit+ number digits(.digits)?(E[+-]?digits)? letter [A-Za-z] id letter (letter | digit)* if if then then else else relop < | > | <= | >= | = | <>
3.2 词法记号的描述与识别 词法单元的识别 词素 词法单元名字 属性值 Any ws - if Then then else Any id 指向符号表条目的指针 Any number number < relop LT <= LE = EQ <> NE > GT >= GE
3.2 词法记号的描述与识别 3.2.4 转换图 关系算符的转换图 return(relop, LE) 2 = > 5 1 6 2 4 8 3 7 return(relop, LE) return(relop, NE) return(relop, LT) return(relop, GE) return(relop, GT) return(relop, EQ) 开始 < = > * other
3.2 词法记号的描述与识别 标识符和关键字的转换图 开始 letter other letter或digit 9 10 11 开始 letter other * letter或digit return(install_id())
3.2 词法记号的描述与识别 无符号数的转换图 number digit+ (.digit+)? (E (+ | )? digit+)? 开始 19 12 13 14 15 16 17 18 digit other . E +/ return( installNum( ) ) *
3.2 词法记号的描述与识别 空白的转换图 delim blank | tab | newline ws delim+ 21 22 开始 delim other * 20
3.2 词法记号的描述与识别 合成整体转换图 开始 9 12 20 … … … …
字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置。 作业 字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置。 如下面两个字符串： 时间复杂度<O(N2) char *str = "bacbababadababacambabacaddababacasdsd"; char *ptr = "ababaca";
重点 串和语言 语言的运算 正则表达式 状态转换图