第三章 词法分祈及词法分析程序
1 第三章 词法分析及词法分析程序
主要内容 3.1设计扫描景肘应考虑的问题 符号的内部表示、识别约定和篥略、憑程序的輪入和预处理 32正规文油和状态转换图 正规文渎——状态转换图,状态转换图的尖现 33有限旬动机(FA) DFA、NFA以及三者的等价性;具有E动作的NFA的确定化 DFA状态数的录小化 34正蚬表达式与正规集 正觌文油——正规式FA 3.5词法分析程序的实现(自学 编写、自动生成
2 主要内容 3.1 设计扫描器时应考虑的问题 符号的内部表示、识别约定和策略、源程序的输入和预处理 3.2 正规文法和状态转换图 正规文法——状态转换图，状态转换图的实现 3.3 有限自动机（FA） DFA、NFA以及二者的等价性；具有动作的NFA的确定化； DFA状态数的最小化 3.4 正规表达式与正规集 正规文法——正规式——FA 3.5 词法分析程序的实现（自学） 编写、自动生成
词法分析的任务 词法分析的任务 扫描输入串中的字符,从中识别出具有独立意义的基本 语法单位:单词,生成单词序列。 √剥去源程序中的注释(块、行)和“空白”符 √预处理—宏处理与文件包含 词法分析程序亦称为扫描器 设计和实现扫描器的相关问题 √描述语言中各种单词的结构:3型文法及其正规式 √识别源程序中的各个单词:状态转换图或有限自动机
3 词法分析的任务 ▪ 词法分析的任务 ✓ 扫描输入串中的字符，从中识别出具有独立意义的基本 语法单位：单词，生成单词序列。 ✓ 剥去源程序中的注释（块、行）和“空白”符 ✓ 预处理——宏处理与文件包含 ▪ 词法分析程序亦称为扫描器 ▪ 设计和实现扫描器的相关问题： ✓ 描述语言中各种单词的结构：3型文法及其正规式 ✓ 识别源程序中的各个单词：状态转换图或有限自动机
扫描器的功能 单词 流 token 高级语言 编译器其 源程序 词法分 语法分它阶段 析器| get next token析器 字符流 符号表
4 扫描器的功能 词法分 析器 语法分 get_next_token 析器 编译器其 它阶段 符号表 高级语言 源程序 字符流 token 单词 （流）
程序语言的单词(1) 单词:同类词文的总称 词文:源程序中能匹配某一记号的字符串 模式:描述用字符串构成单词的规则 单词 文 模式 WHILE While While 关键字 FOR for for 标识符D temp, I 字母开头的字母数字串 max 3.14 常数|NUM 100 数字串数字串} 5
5 程序语言的单词（1） 单词 词文 模式 关键字 WHILE while while FOR for for 标识符 ID temp, i, max 字母开头的字母数字串 常数 NUM 3.14 100 数字串{.数字串} 单词：同类词文的总称 词文：源程序中能匹配某一记号的字符串 模式：描述用字符串构成单词的规则
程序语言的单词(2) 单词 词文 模式 MUL 运算符GT 界符 helo°双(单)引号中间的字符 串常量 STRINGthere串(不包括引号本身)
6 程序语言的单词（2） 单词 词文 模式 运算符 MUL * * GT > > 界符 , , , 串常量 STRING “hello” ‘there’ 双（单）引号中间的字符 串（不包括引号本身）
3.1设计扫描景时应考虑的问题 3.1.1词法分析的两种处理方式 ■将词法分析纳入到语法分析中进行 ■词法分析与语法分析分开来进行 描述单词结构比描述语法结构简单,仅用3型文法就够了 将单词识别从语法分析中分离出来,可采用更有效的工 具(状态转移图、有限自动机等)实现; 有些语言(如 FORTRAN)的单词识别与前后文相关,将词 法分析独立出来,有利于实现统一的语法分析; 使编译程序各部分独立出来,有利于设计、调试和维护 逻辑上的划分,不是指编译程序的执行流程
7 3.1 设计扫描器时应考虑的问题 3.1.1 词法分析的两种处理方式 ◼ 将词法分析纳入到语法分析中进行 ◼ 词法分析与语法分析分开来进行 –描述单词结构比描述语法结构简单，仅用3型文法就够了； –将单词识别从语法分析中分离出来，可采用更有效的工 具（状态转移图、有限自动机等）实现； –有些语言（如FORTRAN）的单词识别与前后文相关，将词 法分析独立出来，有利于实现统一的语法分析； –使编译程序各部分独立出来，有利于设计、调试和维护 ◼ 逻辑上的划分，不是指编译程序的执行流程
两种具体的实现方式 ■词法分析作为单独的一遍(多遍扫描) ①大部分编译时间花在扫描字符上,独立出来便于集中 处理 ②单词的词法规则简单,可建立特别适用于这种文法的 有效技术,实现词法分析的自动生成 ③整个编译程序结构简单,清晰,产生中间文件,占内 存 词法分析作为一个独立的子程序,供语法分析程序调 用(单遍扫描) ①语法分析调用时,返回一个单词符号 ②无中间文件,省内存,编译效率高
8 ◼ 词法分析作为单独的一遍（多遍扫描） ①大部分编译时间花在扫描字符上，独立出来便于集中 处理. ②单词的词法规则简单，可建立特别适用于这种文法的 有效技术，实现词法分析的自动生成. ③整个编译程序结构简单，清晰，产生中间文件，占内 存. ◼ 词法分析作为一个独立的子程序，供语法分析程序调 用 （单遍扫描） ①语法分析调用时，返回一个单词符号. ②无中间文件，省内存，编译效率高. 两种具体的实现方式
3.12单词符号的内部表示 词法分析器的输出形式 (1)单词符号的种类 ①保留字:如 begin,end,do等用户不能使 用 ②标识符:由用户定义 ③无符号整数:如124 ④单字符分界符:+ ⑤双字符分界符:∥/,/,*,=等
9 3.1.2 单词符号的内部表示 —词法分析器的输出形式 (1) 单词符号的种类 ①保留字：如begin，end,do等用户不能使 用 ②标识符：由用户定义 ③无符号整数：如124 ④单字符分界符：+，－， * ，/ ，；，，， （ ，），： ⑤双字符分界符：//，/*， */，:=等
(2)单词符号的表示形式二元组 二元组:(单词类别,单词自身值) ①单词类别:说明单词属于哪一类,常用助记符或 整数编码表示 例:标识符用4表示 +‘用8表示 *用10表示 ②单词自身值 种类只有一个单词,不必给出单词自身值因为 根据类别编码能完全确定 种类含有多个单词,必须给出单词自身值予以 区别。 10
10 (2)单词符号的表示形式——二元组 二元组：（单词类别，单词自身值） ①单词类别：说明单词属于哪一类，常用助记符或 整数编码表示. 例：标识符用4 表示 ′+ ′用8表示 ′* ′用10表示 ②单词自身值 一种类只有一个单词，不必给出单词自身值.因为 根据类别编码能完全确定. 一种类含有多个单词，必须给出单词自身值予以 区别