第三章词法分析 | Rainnn の Blog

3.1 词法分析器的设计

词法分析(Lexical Analysis)/扫描(Scanning)

词法分析器读入源程序的字符流，将其组织成有意义的词素(Lexeme)序列，产生如下的词法单元作为输出：

<token-name, attribute-value>

查找已扫描字符串中最后一个对应于某终态的字符

找到终态字符，并将该字符与其前面的字符识别成一个单词。随后将输入指针退回，扫描器重新回到初始状态，继续识别下一个单词

无法找到终态字符，则确定出错，采用错误恢复策略。

从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止（恐慌模式）

3.1.1 词法分析器的任务

从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。

输入源程序，输出单词符号

过滤空白、换行、制表符、注释等

将词素添加到符号表中

与语法分析的关系如下：

词法分析器（Lexical Analyzer）与语法分析器（Parser）之间的交互

词法分析器（Lexical Analyzer）与语法分析器（Parser）之间的交互（英文版）

在逻辑上独立于语法分析，但是通常和语法分析器处于同一趟中。

独立的词法分析器可以：

简化编译器的设计（词法分析器可以首先完成一些简单的工作，原理简单）

提高编译器效率

增强编译器的可移植性

词法分析的任务

输入源程序

输出单词符号(词法单元)

词法规则表示：正则表达式

识别方法：有穷自动机

3.1.2 词法分析器的输出

词法单元 (Token)

<词法单元名、属性值 (可选) >

单元名是表示词法单位种类的抽象符号，语法分析器通过单元名即可确定词法单元序列的结构

属性值通常用于语义分析之后的阶段

模式 (Pattern)

描述了一类词法单元的词素可能具有的形式

词素 (Lexeme)

源程序中的字符序列

它和某个词法单元的模式匹配，被词法分析器识别为该词法单元的实例

常用的程序语言词素可分为以下几类：

关键字：由程序语言定义的具有固定意义的标识符。也称为保留字或基本字。关键字统归为一种，根据属性值分别是什么；也可以一字一种，一个关键字对应一个词法单元（常见）

标识符：用来表示程序中各种名字的字符串。统归为一种。

常数：常数的类型一般有整型、实型、布尔型、文字型。按类型（整、实、布尔等）分种。

运算符：如+、－、*、/ 等。一符一种。

界符：如逗号、分号、括号等。一符一种。

3.2 识别词法单元

LexemeBegin指针：指向当前词素的开始处。

forward指针：一直向前扫描，直到发现某个模式被匹配为止。

一旦确定了下一个词素，forward指针将指向该词素结尾的字符。词法分析器将这个词素作为某个返回给语法分析器的词法单元的属性值记录下来。然后使LexemeBegin指针指向刚刚找到的词素之后的一个字符。

3.2.1 识别词法单元——状态转换图

一个状态转换图可用于识别（或接受)一定的字符串。

词法分析器的重要组件之一

状态转换图 (Transition diagram)

状态 (State)：表示在识别词素时可能出现的情况

状态看作是已处理部分的总结

某些状态为接受状态或最终状态，表明已找到词素

加上*的接受状态表示最后读入的符号不在词素中

开始状态 (初始状态)：用Start边表示

边 (Edge)：从一个状态指向另一个状态

边的标号是一个或多个符号

当前状态为s，下一个输入符号为a，就沿着从s离开，标号为a的边到达下一个状态

3.3 正则表达式

语言 L={a}{a,b}*({ε}∪({.,_}{a,b}{a,b}*))

正则表达式(Regular Expression，RE ) 是一种用来描述正则语言的更紧凑的表示方法

例：

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 r 定义（表示）一个语言，记为L(r )。这个语言也是根据r 的子表达式所表示的语言递归定义的

3.3.1 定义

ε是一个RE(正则表达式)， L(ε) = {ε}

如果 a∈∑ ，则a是一个RE正则表达式， L(a) = {a}

假设 r和 s都是 RE ，表示的语言分别是L(r)和L(s)，则

选择：r|s 是一个RE， L( r|s ) = L(r)∪L(s)

连接：rs 是一个RE， L( rs ) = L(r) L(s)

闭包：r* 是一个RE，L( r*)= (L(r))*

括号：(r) 是一个RE， L( (r) ) = L(r)

运算的优先级（从大到小）：* 、连接、| 例：(a)|((b)*(c))=a|b*c

C语言无符号整数的RE

十进制整数的RE：(1|...|9)(0|...|9) |0

八进制整数的RE：0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)

十六进制整数的RE：0x(0|1|...|9|a|...| f |A| … |F)(0|...|9|a|...| f |A| … |F )*

可以用RE 定义的语言叫做正则语言(regular language)或正则集合(regular set)

3.3.2 RE的代数定律

定律	描述
r｜s = s｜r	｜是可以交换的
r｜（ s｜t ）= （ r｜s ）｜t	｜是可结合的
r（ s t ）=（ r s ）t	连接是可结合的
r（ s｜t ）= r s｜r t ; （ s｜t）r = s r｜t r	连接对｜是可分配的
εr = rε = r	ε 是连接的单位元
r * =（ r｜ε ）*	闭包中一定包含 ε
r *= r	* 具有幂等性