简介

概述

词法分析作为编译的第一步骤，需要将输入的字符串文本（即源代码），解析为基本词素（Token）。每个词素需要包含类型和对应源码的字符串（Lexeme）。 在实现上一般由语法解析器驱动词法分析器进行分析。 实现上一般被称作Lexer（词法分析器）。 一般词素类别有：

• Identifier（标识符）
• Keywords（关键词）
• (){}[]
• Numbers（数字）
• Whitespace（空白符）
• Operator（操作符）

在分割过程中，也需要检测非法地token。 词法分析程序产生器LEX，使用根据词法规则生成C语言词法分析器。

原理

Regular Language(正则语言)

基本定义

单个字符组成的集合为c={“c”}，“c”代表任意字符。 空字符集ε={““}，注意集合不为空，仅仅字符为空。 所有字符集合。

基本操作

Union（合并）： Concatenation（连接）： Iteration（迭代）：

示例

表示所有1元素的集合： 0元素的集合和所有1元素的集合，集合合并：

Formal Language(形式语言)

所有字符集合，即表示Alphabet字母表。 语言是基于字母表建立的字符串集合。 定义Meaning Function：

则可以表示：

Lexical Specifications（词法规范）

可以定义基本词素。 数值： 字符：，速记写为： 关键字： 整数：，速记写为： 标识符： 空白符：

流程

通用步骤

• 定义Token 具体可以参考[[#Lexical Specifications（词法规范）]]
• 构造R与匹配所有Token 利用定义的Token，构造正则式：

• 循环解析输入字符串 对于输入长度为n的字符串。 找到，使得； 若成功找到，可以根据正则式获取所有token；并将从输入字符串中移除；

要求

匹配R时采用最大匹配方式 token需要按照优先级排列匹配R列表 尽可能多的定义错误R，并将其放入列表尾部。可以反馈错误的地方

注意

一般词法分析有语法分析主导，不会单独解析。

实现

Finite Automata（有限自动机）

简介

正则式主要描述规则，则有限自动机实现这些规则。

符号定义

输入字母表： 有限状态集合： 起始状态： 可接受的状态子集： 输入为a时，集合中状态转换：

图形表示法

状态： 开始状态： 可接受状态：

输入为a时，状态转化：

基本规则

判定

若输入结束并且当前状态可接受，则完成转换。 其他情况拒绝。此时： 最终状态为非可接受状态；转换停止； 表示输入不移动，状态直接转换；

两类自动机区别

• DFA对于相同输入只有一条路径
• NFA对于相同输入存在不同的路径（有选择）
• DFA和NFA可以实现相同的语言
• DFA执行速度更快
• 一般来说，NFA实现体积小

Deterministic Finite Automata（确定的有限自动机）

DFA对于相同输入只有一条路径

表格实现

X轴为输入： Y轴为状态： 单元格为状态转换：

Non-Deterministic Finite Automata（不确定的有限自动机）

NFA对于相同输入存在不同的路径（有选择）

图形表示

表达式M：

解析：

解析：

解析：

解析：

解析：

闭包函数

（闭包函数）定义某个状态可以有选择转化为另一种状态的集合。

示例

图中可以获得部分闭包函数

转化为DFA

• 假定NFA有符号： 状态集合： 起始状态： 可接受的状态子集： 输入为a时，转换后集合：
• 假定被转化的DFA有符号： 状态集合： 开始状态： 最终状态： 能够转换的条件为：

示例

有如下NFA图形 转换后DFA图形

表格实现

X轴为输入： Y轴为状态： 单元格为状态转换：