南京大学：《编译原理》课程教学资源（PPT课件讲稿）第三章 词法分析

第三章词法分析 赵建华 南京大学计算机系 2009年2月

第三章 词法分析 赵建华 南京大学计算机系 2009年2月

内容 ·词法分析器的作用 词法单元的规约 词法单元的识别 ·词法分析器生成工具Lex 有穷自动机 从正则表达式到自动机 词法分析器生成工具的设计方法

内容 • 词法分析器的作用 • 词法单元的规约 • 词法单元的识别 • 词法分析器生成工具Lex • 有穷自动机 • 从正则表达式到自动机 • 词法分析器生成工具的设计方法

词法分析器的作用 读入源程序字待流、组成词素,输出词法单元序列。 过滤空白、换行、制表符、注释等 ·将词素添加到符号表中 在逻辑上独立于语法分析,但是通常和语法分析器 处于同一趟中 词法单元 源程序 词法分 语法分输出至语 析器 析器 义分析 getNextToken 符号表 图3-1词法分析器与语法分析器之间的交互

词法分析器的作用 • 读入源程序字符流、组成词素，输出词法单元序列。 • 过滤空白、换行、制表符、注释等。 • 将词素添加到符号表中。 • 在逻辑上独立于语法分析，但是通常和语法分析器 处于同一趟中

为什么要设立独立的词法分析器 简化编译器的设讣 词法分析器可以首先完成一些简单的处理工作。 ·提高编译器效率 相对于语法分析,词法分析过程简单.可高效 实现。(下推自动机VS有穷自动机 ·增强编译器的可移植性

为什么要设立独立的词法分析器 • 简化编译器的设计 – 词法分析器可以首先完成一些简单的处理工作。 • 提高编译器效率 – 相对于语法分析，词法分析过程简单，可高效 实现。（下推自动机 vs 有穷自动机） • 增强编译器的可移植性

词法单元、模式、词素 ·词法单元 单元名是表示词法单位种类的抽象符号:语法分析 器通过单元名即可确定词法单元序列的结构。 属性值通常用于语义分析之后的阶段 模式 描述了一类词法单元的词素可能具有的形式 词素 源程序中的字符序列 它和某个词法单元的模式匹配。被词法分析器识别 为该词法单元的实例

词法单元、模式、词素 • 词法单元 – – 单元名是表示词法单位种类的抽象符号；语法分析 器通过单元名即可确定词法单元序列的结构。 – 属性值通常用于语义分析之后的阶段 • 模式 – 描述了一类词法单元的词素可能具有的形式 • 词素 – 源程序中的字符序列 – 它和某个词法单元的模式匹配，被词法分析器识别 为该词法单元的实例

词法单元、模式、词素(倒子 printf( Total n. score printf, score和标识(id)的模式匹配 Total=%dn?和 litera的模式匹配 词法单元 非正式描述 词素示例 if 字符i,f if else 字符e else comparison或=或==或 id 字母开头的字母/数字串 Pi, score, D2 number 任何数字常量 3.14159,0,6.02e23 literal 在两个"之间,除"以外的任何字符“ core dumped 图3-2词法单元的例子

词法单元、模式、词素（例子） • printf(“Total = % d\n”, score)； – printf, score和标识符（id）的模式匹配 – “Total = % d\n”和literal的模式匹配

词法单元的属性 一个模式匹配多个词素时,必须通过属性 来传递附加的信息。属性值将被用于语义 分析、代码生成等阶段。 不同的目的需要不同的属性。因此,属性 值通常是一个结构化数据。 词法单元jd的属性 词素、类型、第一次出现的位置

词法单元的属性 • 一个模式匹配多个词素时，必须通过属性 来传递附加的信息。属性值将被用于语义 分析、代码生成等阶段。 • 不同的目的需要不同的属性。因此，属性 值通常是一个结构化数据。 • 词法单元id的属性 – 词素、类型、第一次出现的位置、…

内容 词法分析器的作用 词法单元的规约 词法单元的识别 ·词法分析器生成工具Lex 有穷自动机 从正则表达式到自动机 词法分析器生成工具的设计方法

内容 • 词法分析器的作用 • 词法单元的规约 • 词法单元的识别 • 词法分析器生成工具Lex • 有穷自动机 • 从正则表达式到自动机 • 词法分析器生成工具的设计方法

词法单元的规约 正则表达式可以高效、简洁地描述处理词 法单元时用到的模式类型。 内容 串和语言 语言上的运算 正则表达式 正则定义 正则表达式的扩展

词法单元的规约 • 正则表达式可以高效、简洁地描述处理词 法单元时用到的模式类型。 • 内容 – 串和语言 – 语言上的运算 – 正则表达式 – 正则定义 – 正则表达式的扩展

串和语言(1) 字母表( alphabet):一个有穿的符号集合。 符号典型例子:字母、数位、标点符号。 例子:{0,1};ASCI; Unicode 在理论上,我们可以把任意的有限集合看作字母表。 字母表上的串( string)是该字母表中号的 有穷序列。 串s的长度,即s,是指s中符号出现的次数 空串:长度为0的串,￡ 语言( Clanguage)是某个给定字母表上的串的 可数集合

串和语言（1） • 字母表（alphabet）：一个有穷的符号集合。 – 符号典型例子：字母、数位、标点符号。 – 例子：{0,1}；ASCII；Unicode – 在理论上，我们可以把任意的有限集合看作字母表。 • 字母表上的串（string）是该字母表中符号的 有穷序列。 – 串s的长度，即|s|，是指s中符号出现的次数； – 空串：长度为0的串，ε • 语言（language）是某个给定字母表上的串的 可数集合