吉林大学：《编译原理》课程教学资源（PPT课件讲稿）第三章 有限自动机和词法分析器

第三章有限自动机和词法分析器 主要内容: 词法分析过程涉及的几个问题 词法分析器的生成技术 正则表达式 有限自动机

第三章有限自动机和词法分析器 主要内容： ⚫ 词法分析过程涉及的几个问题 ⚫ 词法分析器的生成技术 正则表达式 有限自动机

词法分析概述 有关词法分析器的几个问题和处理方法: 词法分析器的功能、分类 单词的分类、 Token表示 保留字 空格符、制表符和换行符 复合型符号 括号类匹配预检 字符串空间 词法错误校正 词法分析结束

词法分析概述 ⚫ 有关词法分析器的几个问题和处理方法： 词法分析器的功能、分类 单词的分类、Token表示 保留字 空格符、制表符和换行符 复合型符号 括号类匹配预检 字符串空间 词法错误校正 词法分析结束

词法分析器的功能 词法分析器功能: 读源程序的字符序列,逐个拼出单词,并 构造相应的内部表示T0KEN同时检查源程序 中的词法错误 ●引入 Token的原因 编译程序总是用某种程序语言书写的程 序,语言的操作对象只能是该语言规定的各种 数据。而编译程序的操作对象是程序中的各种 语法单位,因此,必须把它们表示成某种数据 结构形式

❖ 词法分析器的功能 ⚫ 词法分析器功能： ⚫ 读源程序的字符序列,逐个拼出单词,并 构造相应的内部表示TOKEN.同时检查源程序 中的词法错误. ⚫ 引入Token的原因： ⚫ 编译程序总是用某种程序语言书写的程 序，语言的操作对象只能是该语言规定的各种 数据。而编译程序的操作对象是程序中的各种 语法单位，因此，必须把它们表示成某种数据 结构形式

词法分析器的两种形式 ca l Charlist 附属 语法分析 词法分析器 Token Charlist 独立 词法分析器 Tokenlist语法分析

词法分析器的两种形式 CharList 独 立 词法分析器 语法分析 TokenList 附 属 词法分析器 语法分析 call Token CharList

令 Token定义 ● Token表示最小的语义单位一单词的信息 即单词内部表示的数据结构形式。 单词不是程序设计语言中的语法概念,是编译程 序中引进的一个概念。是最小的语义单位,不能 分割 ● Token中需要记录有关单词的信息: 单词的标志码($id,$intG,,)标识单词的种类 词法信息 单词的特征属性(标识符名,符号表地址等) 语义信息

❖ Token定义 ⚫ Token表示最小的语义单位--单词的信息。 即单词内部表示的数据结构形式。 单词不是程序设计语言中的语法概念，是编译程 序中引进的一个概念。是最小的语义单位，不能 分割 ⚫ Token中需要记录有关单词的信息： 单词的标志码($id,$intC,…)标识单词的种类--- 词法信息 单词的特征属性（标识符名，符号表地址等） -- -语义信息

Microl的单词的分类 ●标识符:字母打头的字母/数字串 ●整常数:数字打头的数字串 ●实常数:整数整数 ●保留字: begin,end,var;read write, integer, real ●符号:+,*,(,),:;:=,; ●控制:(换行符)

Micro的单词的分类 ⚫ 标识符：字母打头的字母/数字串 ⚫ 整常数：数字打头的数字串 ⚫ 实常数：整数.整数 ⚫ 保留字：begin，end，var，read， write，integer，real ⚫ 符号 ：+， * ，(，)，:，:=，; ⚫ 控制 ： (换行符）

Micro语言的 Token结构 ●标识符的 Token:($id,标识符)如($id,x) ●整常数的 Token:($intC,整常数)如 (S intC, 5) ●实常数的 Token:($ real,实常数)如 SreaIC, 0.5) ●保留字的 Token:($ begin,-),($end,-) ●符号词的 Token:($plus,-),($mult,-), (SLparen, - ●换行符的 Token:($line,-)

Micro 语言的Token结构 ⚫ 标识符的Token: （$id,标识符）如($id,x) ⚫ 整常数的Token: ($intC,整常数）如 （$intC,5) ⚫ 实常数的Token: ($realC,实常数）如 $realC,0.5) ⚫ 保留字的Token: ($begin,-),($end,-) ⚫ 符号词的Token: ($plus,-),($mult,-), ($Lparen,-) ⚫ 换行符的Token: ($line,-)

●例如下述Mcro的代码: begin var x: real 经词法分析器处理后,它将转换为如下的 Token序列: (Begin, - (Svar, -) (Sid, X) (Scolon,-) (Sreal, -) Semi,

($begin,-) ($var,-) ($id, x) ($colon,-) ($real,-) ($semi,-) …… ⚫例如下述Micro的代码： begin var x : real;…… 经词法分析器处理后，它将转换为如下的 Token序列：

标识符和常量的处理 词法信息可确定,语义信息形式的确定: a语义信息的长度有限制时,直接用 标识符或常量本身 b没有长度限制时,构造标识符或常 量表,语义信息中为其在表中的地 址(字符串空间节省存贮空间) 保留字的处理:识别保留字的方法 1建立保留字表;顺序、散列、散列十顺序 2拼写的同时进行判断自动机

❖ 标识符和常量的处理： 词法信息可确定，语义信息形式的确定： a 语义信息的长度有限制时，直接用 标识符或常量本身 b 没有长度限制时，构造标识符或常 量表，语义信息中为其在表中的地 址（字符串空间节省存贮空间） ❖ 保留字的处理：识别保留字的方法： 1.建立保留字表；顺序、散列、散列＋顺序 2.拼写的同时进行判断 自动机

冷运算符的处理: 不区分,统一成一类 区分,每个运算符为一类 空格符和制表符以及换行符的处理 1无用的空格符和制表符要删掉 2字符串內的空格不能删 3换行符不能删。用于错误定位 复合型特殊符,如“:=”的处理 读到“:”时不能判断是否为冒号,必须读下 字符

❖ 运算符的处理： 不区分，统一成一类 区分，每个运算符为一类 ❖ 空格符和制表符以及换行符的处理 1.无用的空格符和制表符要删掉； 2.字符串内的空格不能删； 3.换行符不能删。用于错误定位 ❖ 复合型特殊符，如“:=”的处理 读到“:”时不能判断是否为冒号，必须读下 一字符