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

第三章词法分析 戴新宇 南京大学 计算机科学与技术系

戴新宇 南京大学 计算机科学与技术系

Outline ●词法分析的作用 词法单元的规约(正则表达式) 词法单元的识别(状态转换图) ●有穷自动机 词法分析器生成工具及设计

Outline  词法分析的作用  词法单元的规约（正则表达式）  词法单元的识别（状态转换图）  有穷自动机  词法分析器生成工具及设计

词法分析器作用 口词法分析是读入源程序的输入字符、将它们组成词素,生成并输出 个词法单元序列,每个词法单元对应于一个词素。 常见的做法是: 由语法分析器调用,需要的时候不断读取、生成词法单元 可以避免额外的输入输出 在识别出词法单元之 理 比如删除 注释、将多 探金定盛不露结成词单的简单处 词法单元 源程序 词法分 语法分输出至语 析器 析器 义分析 getNext Token 符号表 图3-1词法分析器与语法分析器之间的交互

词法分析器作用  词法分析是读入源程序的输入字符、将它们组成词素，生成并输出一 个词法单元序列，每个词法单元对应于一个词素。  常见的做法是：  由语法分析器调用，需要的时候不断读取、生成词法单元  可以避免额外的输入输出  在识别出词法单元之外，还会完成一些不需要生成词法单元的简单处 理，比如删除注释、将多个连续的空白字符压缩成一个字符等

词法分析和语法分析 ●通常,将编译过程的分析划分成两个阶段的原因: 简化编译器的设计,任务分解 提高编译器的效率 ●增强编译器的可移植性

词法分析和语法分析  通常，将编译过程的分析划分成两个阶段的原因：  简化编译器的设计，任务分解  提高编译器的效率  增强编译器的可移植性

词法分析相关概念 词法单元( Token): 包含单元名( Token-name)和可选的属性值( (attribute-value) 单元名是表示某种词法单位抽象符号。语法分析器通过单元名 即可确定词法单元序列的结构。 ●词素( Lexeme) 源程序中的字符序列,它和某类词法单元的模式匹配,被词法 分析器识别为该词法单元的实例。 ●模式( Pattern) 词法单元的词素可能具有的形式。可以用正则表达式来表示

词法分析相关概念  词法单元（Token）：  包含单元名（Token-name）和可选的属性值(attribute-value)  单元名是表示某种词法单位抽象符号。语法分析器通过单元名 即可确定词法单元序列的结构。  词素（Lexeme）  源程序中的字符序列，它和某类词法单元的模式匹配，被词法 分析器识别为该词法单元的实例。  模式（Pattern）  词法单元的词素可能具有的形式。可以用正则表达式来表示

词法单元示例 词法单元 非正式描述 词素示例 if 字符i,f if Ise 字符e,1,s,e else comparison或=或==或!= 字母开头的字母/数字串 Pi, score, D2 number 任何数字常量 3.14159,0,6.02e23 literal 在两个"之间,除"以外的任何字符“ core dumped 图3-2词法单元的例子 printf("Total=8 dn",sclore)

词法单元示例

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

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

词法单元示例(名和属性值) E=M*C**2

词法单元示例（名和属性值）

词法分析器的构造实现 两种方法: ●基于词法单元的词法结构图或其它描述,手工编写代码 扫描输入中的每个词素,并返回识别到的词法单元信息。 使用词法分析器生成工具(如 llex flex)。给出描述词素 的模式,利用工具编译为具有词法分析器功能的代码。 高效且简单 正则表达式 种描述词素模式的重要表示方法

词法分析器的构造实现  两种方法：  基于词法单元的词法结构图或其它描述，手工编写代码 扫描输入中的每个词素，并返回识别到的词法单元信息。  使用词法分析器生成工具（如lex flex）。给出描述词素 的模式，利用工具编译为具有词法分析器功能的代码。 高效且简单。  正则表达式  一种描述词素模式的重要表示方法

Outline 词法分析的作用 词法单元的规约(正则表达式) 词法单元的识别(状态转换图) ●有穷自动机 词法分析器生成工具及设计

Outline  词法分析的作用  词法单元的规约（正则表达式）  词法单元的识别（状态转换图）  有穷自动机  词法分析器生成工具及设计