源程序 本章内容 第 章词法分析 词法分析器 记号 (token 取下一个记号 符号表 语法分析器 词法分析器 : 把构成源程序的字符流翻译成记号流, 还完成和用户接口的一些任务 围绕词法分析器的自动生成展开 介绍正规式 转换图和有限自动机概念. 词法记号及属性.. 词法记号 模式 词法单元 记号名 词法单元例举 模式的非形式描述 if if 字符 i, f for for 字符 f, o, r reltion <,<=,=, < 或 <= 或 = 或 id sum, count, D 由字母开头的字母数字串 numer.,,.8 E 任何数值常数 literl seg. error 引号 和 之间的任意字符串, 但引号本身除外. 词法记号及属性 历史上词法定义中的一些问题 忽略空格带来的困难 ( 如 Fortrn 语言 DO 8 I. 7 DO8I. 7 DO 8 I, 7 关键字不保留 ( 如 Fortrn 语言 IF THEN THEN THEN=ELSE;ELSE 关键字 保留字和标准标识符的区别 保留字是语言预先确定了含义的词法单元 标准标识符也是预先确定了含义的标识符, 但程序可以重新声明它的含义. 词法记号及属性.. 词法记号的属性 position = initil + rte 6 的记号和属性值 : id, 指向符号表中 position 条目的指针 ssign _ op id, 指向符号表中 initil 条目的指针 dd_op id, 指向符号表中 rte 条目的指针 mul_ op numer, 整数值 6. 词法记号及属性.. 词法错误 词法分析器对源程序采取非常局部的观点 例 : 难以发现下面的错误 fi ( == f (x 在实数是. 格式下, 可以发现下面的错误.x 紧急方式的错误恢复删掉当前若干个字符, 直至能读出正确的记号 错误修补进行增 删 替换和交换字符的尝试. 词法记号的描述与识别.. 串和语言 字母表 : 符号的有限集合, 例 : = {, } 串 : 符号的有穷序列, 例 :, 语言 : 字母表上的一个串集 {,,,, }, {}, 句子 : 属于语言的串 串的运算 连接 ( 积 xy,s = s = s 幂 s 为,s i 为 s i - s(i >
. 词法记号的描述与识别 语言的运算 并 : L M = {s s L 或 s M } 连接 : LM = {st s L 且 t M} 幂 : L 是 {},L i 是 L i - L 闭包 : L = L L L 正闭包 : L + = L L 例 L: {,,, Z,,,, z }, D: {,,, } L D, LD, L 6, L, L(L D, D +. 词法记号的描述与识别.. 正规式 正规式用来表示简单的语言, 叫做正规集 正规式 定义的语言 备注 {} {} (r (s L(r L(s r 和 s 是正规式 (r(s L(rL(s r 和 s 是正规式 (r (L(r r 是正规式 (r L(r r 是正规式 (( ( (c 可以写成 c. 词法记号的描述与识别 正规式的例子 = {, } {, } ( ( {,,, } {,,, } 由字母 构成的所有串集, 含 ( 由 和 构成的所有串集, 含 复杂的例子 ( ( ( ( ( 句子 :. 词法记号的描述与识别.. 正规定义 对正规式命名, 使表示简洁 d r d r... d n r n 各个 d i 的名字都不同 每个 r i 都是 {d, d,,d i- } 上的正规式. 词法记号的描述与识别 正规定义的例子 语言的标识符是字母 数字和下划线组成的串 letter_ Z z_ digit id letter_(letter_ digit. 词法记号的描述与识别 正规定义的例子 无符号数集合, 例 6,.8,6E8,.E6 digit digits digit digit optionl_frction.digits optionl_exponent (E(+ digits numerdigits optionl_frction optionl_exponent 简化表示 numer digit + (.digit +? (E(+? digit +?
. 词法记号的描述与识别 正规定义的例子 ( 进行下一步讨论的例子 while while do do relop < < = = < > > > = letter Z z id letter (letter digit numer digit + (.digit +? (E (+? digit +? delim lnktnewline ws delim +. 词法记号的描述与识别.. 转换图 关系算符的转换图 < = > 6 other = > return(relop, EQ = other return(relop, LT 7 return(relop, LE return(relop, NE return(relop, GE 8 return(relop, GT. 词法记号的描述与识别 标识符和保留字的转换图 letter 或 digit letter other return(instllid(. 词法记号的描述与识别 无符号数的转换图 numer digit + (.digit +? (E (+? digit +? digit E digit digit digit digit. digit E +/ digit other other other return( instllnum(. 词法记号的描述与识别 空白的转换图 delim lnk t newline ws delim+ delim delim other.. 不确定的有限自动机 ( 简称 NF 一个数学模型, 它包括 : 有限的集合 S 集合 转换函数 move : S ( {} P(S s 是唯一的 F S 是接受集合 识别语言 ( 的 NF
NF 的转换表 例识别 的 NF 识别语言 ( 的 NF {, } {} {}.. 确定的有限自动机 ( 简称 DF 一个数学模型, 包括 : 有限的集合 S 集合 转换函数 move : S S, 且可以是部分函数 唯一的 s 接受集合 F S 例 DF, 识别 {,} 上能被 整除的二进制数 已读过 尚未读 已读部分的值 某时刻 读进 = 读进 + = 识别语言 ( 的 DF 个即可, 分别代表已读部分的值除以 的余数 例 DF, 识别 {,} 上能被 整除的二进制数 = = 7.. NF 到 DF 的变换子集构造法 DF 的一个是 NF 的一个集合 读了输入 n 后, NF 能到达的所有 :s, s,, s k, 则 DF 到达 {s, s,, s k } {} {, } 未画完 {, }
例 (,NF 如下, 把它变换为 DF = {,,,, 7} = {,,,, 7} = {,,,, 6, 7, 8} = {,,,, 7} = {,,,, 6, 7, 8} = {,,,, 7} = {,,,, 6, 7, 8} = {,,,, 6, 7}
= {,,,, 7} = {,,,, 6, 7, 8} = {,,,, 6, 7} = {,,,, 7} = {,,,, 6, 7, 8} = {,,,, 6, 7} = {,,,, 7} = {,,,, 6, 7, 8} = {,,,, 6, 7} D = {,,,, 6, 7, } D = {,,,, 7} = {,,,, 6, 7, 8} = {,,,, 6, 7} D = {,,,, 6, 7, } D D = {,,,, 7} = {,,,, 6, 7, 8} = {,,,, 6, 7} D = {,,,, 6, 7, } D D = {,,,, 7} = {,,,, 6, 7, 8} = {,,,, 6, 7} D = {,,,, 6, 7, } D D 6
D D D 识别语言 ( 的自动机 D 识别语言 ( 的自动机 子集构造法不一定得到最简 DF D.. DF 的化简 死 在转换函数由部分函数改成全函数表示时引入 左图需要引入死 E ; 右图无须引入死, E D D 可区别的 和 是可区别的 从 出发, 读过串, 到达非接受, 而 从 出发, 读过串, 到达接受 D 和 是不可区别的无任何串可用来像上面这样 区别它们 D 方法. {,, }, {D} move({,, }, = {} move({,, }, = {, D}. {, }, {}, {D} move({, }, = {} move({, }, = {} D 7
. 从正规式到有限自动机 从正规式建立识别器的步骤 从正规式构造 NF( 本节介绍 用语法制导的算法, 它用正规式语法结构来指导构造过程 把 NF 变成 DF ( 子集构造法, 已介绍 将 DF 化简 ( 合并不可区别的, 也已介绍 首先构造识别 和字母表中一个符号的 NF 重要特点 : 仅一个接受, 它没有向外的转换. 从正规式到有限自动机 i 识别正规式 的 NF f i 识别正规式 的 NF f. 从正规式到有限自动机 构造识别主算符为选择的正规式的 NF 重要特点 : 仅一个接受, 它没有向外的转换. 从正规式到有限自动机 构造识别主算符为连接的正规式的 NF 重要特点 : 仅一个接受, 它没有向外的转换 i N (s N (t f i N (s N (t 识别正规式 st 的 NF f 识别正规式 s t 的 NF. 从正规式到有限自动机 构造识别主算符为闭包的正规式的 NF 重要特点 : 仅一个接受, 它没有向外的转换. 从正规式到有限自动机 对于加括号的正规式 (s, 使用 N(s 本身作为它的 NF i N (s f 识别正规式 s 的 NF 8
. 从正规式到有限自动机 本方法产生的 NF 有下列性质 N(r 的数最多是 r 中符号和算符总数的两倍 N(r 只有一个接受, 接受没有向外的转换. 从正规式到有限自动机 本方法产生的 NF 有下列性质 N(r 的每个有一个用 的符号标记的指向其他的转换, 或者最多两个指向其他的 转换 (. 从正规式到有限自动机 ( 的分解 r r r r (. 从正规式到有限自动机 ( 的分解 r r r r r r r r (. 从正规式到有限自动机 ( 的分解 r r r r. 从正规式到有限自动机 ( 的分解 ( r r r r r r r r
(. 从正规式到有限自动机 ( 的分解 r r r r (. 从正规式到有限自动机 ( 的分解 r r r r r r r r (. 从正规式到有限自动机 ( 的分解 r r r r r r. 从正规式到有限自动机 ( 的两个 NF 的比较 手工构造 : 算法构造 :. 从正规式到有限自动机 例 DF, 接受 和 的个数都是偶数的字符串. 从正规式到有限自动机 小结 : 从正规式建立识别器的步骤 偶 偶 奇 偶 偶 奇 奇 奇 从正规式构造 NF 把 NF 变成 DF 将 DF 化简 存在其他办法
. 词法分析器的生成器. 词法分析器的生成器 用 Lex 建立词法分析器的步骤 Lex 源程序 lex.l lex.yy.c 输入流 Lex 编译器 编译器.out lex.yy.c.out 记号序列 Lex 程序包括三个部分声明 %% 翻译规则 %% 辅助过程 Lex 程序的翻译规则 p { 动作 } p { 动作 } p n { 动作 n}. 词法分析器的生成器 例 声明部分 %{ / 常量 LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMER, RELOP 的定义 / %} / 正规定义 / delim [ \t \n ] ws {delim}+ letter [ Z z] digit [] id {letter}({letter}{digit} numer {digit}+(\.{digit}+?(e[+\]?{digit}+?. 词法分析器的生成器 例 翻译规则部分 {ws} {/ 没有动作, 也不返回 /} while {return (WHILE;} do {return (DO;} {id} {yylvl = instllid ( ; return (ID;} {numer} {yylvl = instllnum( ; return (NUMER;} < {yylvl = LT; return (RELOP;} <= {yylvl = LE; return (RELOP;} = {yylvl = EQ; return (RELOP;} <> {yylvl = NE; return (RELOP;} > {yylvl = GT; return (RELOP;} >= {yylvl = GE; return (RELOP;}. 词法分析器的生成器 例 辅助过程部分 instllid( { / 把词法单元装入符号表并返回指向它的指针 yytext 指向该词法单元的第一个字符, yyleng 给出它的长度 / } instllnum ( { / 类似上面的过程, 但词法单元不是标识符而是数 / } 本章要点 词法分析器的作用和接口, 用高级语言编写词法分析器等内容 掌握下面涉及的一些概念, 它们之间转换的技巧 方法或算法 非形式描述的语言 正规式 正规式 NF 非形式描述的语言 NF NF DF DF 最简 DF 非形式描述的语言 DF( 或最简 DF
例题 例题 叙述下面的正规式描述的语言, 并画出接受该语言的最简 DF 的转换图 ( 描述的语言是 : 所有不含子串 的 和 的串. strt 刚读过的不是 连续读过一个 连续读过 不少于两个 用转换图表示接受 ( (( 的 DF strt 例题 例题 写出语言 所有相邻数字都不相同的非空数字串 的正规定义 76787 nswer ( no_ (no_ (no_ no_ no_ ( no_- (no_- (no_- no_-... no_-8 将这些正规定义逆序排列就是答案 下面 语言编译器编译下面的函数时, 报告 prse error efore else long gcd(p,q long p,q; { if (p%q == / then prt / return q 此处遗漏分号 else / else prt / return gcd(q, p%q; } 例题 现在少了第一个注释的结束符号后, 反而不报错了 long gcd(p,q long p,q; { if (p%q == / then prt return q else / else prt / return gcd(q, p%q; }