第三章词法分析 戴新宇 南京大学 计算机科学与技术系
戴新宇 南京大学 计算机科学与技术系
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 词法分析的作用 词法单元的规约（正则表达式） 词法单元的识别（状态转换图） 有穷自动机 词法分析器生成工具及设计