第三章词法分析 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版
许畅 南京大学计算机系 2022年春季 第三章 词法分析 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅
内容 ·词法分析器的作用 词法单元的规约（正则表达式） 词法单元的识别（状态转换图） ·词法分析器生成工具及设计 ·有穷自动机 2
内容 • 词法分析器的作用 • 词法单元的规约 (正则表达式) • 词法单元的识别 (状态转换图) • 词法分析器生成工具及设计 • 有穷自动机 2 南大编译许畅
词法分析器的作用 读入字符流，组成词素，输出词法单元序列 过滤空白、换行、制表符、注释等 将词素添加到符号表中 在逻辑上独立于语法分析，但是通常和语法分析 器处于同一趟中 词法单元 源程序 词法分 语法分 输出至语 析器 析器 义分析 getNextToken 符号表 图3-1词法分析器与语法分析器之间的交互 3
词法分析器的作用 • 读入字符流，组成词素，输出词法单元序列 • 过滤空白、换行、制表符、注释等 • 将词素添加到符号表中 • 在逻辑上独立于语法分析，但是通常和语法分析 器处于同一趟中 3 南大编译许畅
为什么要设立独立的词法分析器？ 简化编译器的设计 词法分析器可以首先完成一些简单的处理工作 。 提高编译器效率 相对于语法分析，词法分析过程简单，可高效实现（下 推自动机vS.有穷自动机) 增强编译器的可移植性 4
为什么要设立独立的词法分析器？ • 简化编译器的设计 – 词法分析器可以首先完成一些简单的处理工作 • 提高编译器效率 – 相对于语法分析，词法分析过程简单，可高效实现 (下 推自动机 vs. 有穷自动机) • 增强编译器的可移植性 4 南大编译许畅
词法单元、模式、词素 ·词法单元(Token) 单元名是表示词法单位种类的抽象符号，语法分析器 通过单元名即可确定词法单元序列的结构 属性值通常用于语义分析之后的阶段 模式(Pattern) 描述了一类词法单元的词素可能具有的形式 词素(Lexeme) 源程序中的字符序列 它和某个词法单元的模式匹配，被词法分析器识别为 该词法单元的实例 5
词法单元、模式、词素 • 词法单元 (Token) – – 单元名是表示词法单位种类的抽象符号，语法分析器 通过单元名即可确定词法单元序列的结构 – 属性值通常用于语义分析之后的阶段 • 模式 (Pattern) – 描述了一类词法单元的词素可能具有的形式 • 词素 (Lexeme) – 源程序中的字符序列 – 它和某个词法单元的模式匹配，被词法分析器识别为 该词法单元的实例 5 南大编译许畅
词法单元、模式、词素（例子） printf("Total =%d\n",score); printf和score.与标识符(id)的模式匹配 "Total=%d\n"与literal的模式匹配 词法单元 非正式描述 词素示例 if 字符i,f if else 字符e,1,s,e else comparison 或=或==或！= <=,!= id 字母开头的字母/数字串 Pi,score,D2 number 任何数字常量 3.14159,0,6.02e23 literal 在两个"之间，除”以外的任何字符 core dumped” 图3-2 词法单元的例子 6
词法单元、模式、词素 (例子) • printf("Total = %d\n", score)； – printf和score与标识符 (id) 的模式匹配 – "Total = %d\n"与literal的模式匹配 6 南大编译许畅
词法单元的属性 一个模式匹配多个词素时，必须通过属性来传递 附加的信息 ·属性值将被用于语义分析、代码生成等阶段 不同的目的需要不同的属性 属性值通常是一个结构化数据 如词法单元id的属性 词素、类型、第一次出现的位置、. 7
词法单元的属性 • 一个模式匹配多个词素时，必须通过属性来传递 附加的信息 – 属性值将被用于语义分析、代码生成等阶段 • 不同的目的需要不同的属性 – 属性值通常是一个结构化数据 • 如词法单元id的属性 – 词素、类型、第一次出现的位置、… 7 南大编译许畅
内容 。词法分析器的作用 。 词法单元的规约（正则表达式） 词法单元的识别（状态转换图） ·词法分析器生成工具及设计 ·有穷自动机 8
内容 • 词法分析器的作用 • 词法单元的规约 (正则表达式) • 词法单元的识别 (状态转换图) • 词法分析器生成工具及设计 • 有穷自动机 8 南大编译许畅
词法单元的规约 正则表达式可以高效、简洁地描述处理词法单元 时用到的模式类型 ·内容 串和语言 语言上的运算 正则表达式和正则定义 正则表达式的扩展 9
词法单元的规约 • 正则表达式可以高效、简洁地描述处理词法单元 时用到的模式类型 • 内容 – 串和语言 – 语言上的运算 – 正则表达式和正则定义 – 正则表达式的扩展 9 南大编译许畅
串和语言(1) 字母表(Alphabet)：一个有穷的符号集合 符号典型例子：字母、数字、标点符号 例子：{0,1}，ASCII,Unicode 在理论上，我们可以把任意的有限集合看作字母表 字母表上的串(String)是该表中符号的有穷序列 串s的长度，即Is|,是指s中符号出现的次数 空串：长度为0的串， 语言(Language)是某个给定字母表上的串的可数 集合 10
串和语言 (1) • 字母表 (Alphabet) ：一个有穷的符号集合 – 符号典型例子：字母、数字、标点符号 – 例子：{ 0, 1 }, ASCII, Unicode – 在理论上，我们可以把任意的有限集合看作字母表 • 字母表上的串 (String) 是该表中符号的有穷序列 – 串s的长度，即 |s|，是指s中符号出现的次数 – 空串：长度为0的串，ε • 语言 (Language) 是某个给定字母表上的串的可数 集合 10 南大编译许畅
