词法分析-软考在线

词法分析


知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 程序设计语言和语言处理程序知识 > 汇编、编译、解释系统的基本知识和基本工作原理 > 程序语言翻译基础 > 编译程序基本原理 >
被考次数：1次被考频率：低频率总体答错率：57% 知识难度系数：	由软考在线用户真实做题大数据统计生成
相关知识点：22个

语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言规定的基本字符集∑（字母表）上的字符串的一个子集，称为正规集。

正规表达式和正规集

对于字母表∑，其上的正规式及其表示的正规集可以递归定义如下：

（1）ε是一个正规式，它表示集合L（ε）=｛ε｝。

（2）若a是∑上的字符，则a是一个正规式，它所表示的正规集为｛a｝。

（3）若正规式r和s分别表示正规集L（r）和L（s），则：

①r\s是正规式，表示集合L（r）∪L（s）。

②r·s是正规式，表示集合L（r）L（s）。

③r^*是正规式，表示集合（L（r））^*。

④（r）是正规式，表示集合L（r）。

仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式，其中运算符“｜”“.”“*”分别称为“或”“连接”“闭包”。在正规式的书写中，连接运算符“.”可省略。运算符的优先级从高到低顺序排列为“*”“.”“｜”。

设∑=｛a，b｝，下表列出了∑上的一些正规式和相应的正规集。

正规式与正规集示例

若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如，b（ab）^*=（ba）^*b，（a｜b）^*=（a^*b^*）^*。设U、V和W均为正规式，正规式的代数性质如下表所示。

正规式的代数性质

有限自动机

有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为确定的有限自动机和不确定的有限自动机两类。

（1）确定的有限自动机（Deterministic Finite Automata，DFA）。一个确定的有限自动机是一个五元组（S，Σ，f，s₀，Z），其中：

.S是一个有限集，其每个元素称为一个状态。

.Σ是一个有穷字母表，其每个元素称为一个输入字符。

.f是S×Σ→S上的单值部分映像。f（A，a）=Q表示当前状态为A、输入为a时，将转换到下一状态Q。称Q为A的一个后继状态。

.s₀∈S，s₀称为开始状态，是唯一的。

.Z是非空的终止状态集合，

。

一个DFA可以用两种直观的方式表示：状态转换图和状态转换矩阵。状态转换图简称为转换图，是一个有向图。DFA中的每个状态对应转换图中的一个节点，DFA中的每个转换函数对应图中的一条有向弧，若转换函数为f（A，a）=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。

（2）不确定的有限自动机（Nondeterministic Finite Automata，NFA）。一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别如下：

①f是S×Σ→2^S上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一的。

②有向弧上的标记可以是ε。

（3）NFA到DFA的转换。

任何一个NFA都可以转换为DFA，下面先定义转换过程中需要的计算。

定义1：状态集I的ε_闭包。

若I是NFAN的状态集合的一个子集，定义ε_CLOSURE（I）如下：

.状态集I的ε_CLOSURE（I）是一个状态集。

.状态集I的所有状态属于ε_CLOSURE（I）。

.若s∈I，那么从s出发经过任意条ε弧到达的状态s'都属于ε_CLOSURE（I）。

状态集ε_CLOSURE（I）称为I的ε_闭包。

由以上的定义可知，I的ε_闭包就是从状态集I的状态出发，经ε所能到达的状态的全体。

定义2：状态集I的对字符a的状态转移。

假定I是NFAN的状态集的一个子集，a是Σ中的一个字符，定义：

I_a=ε_CLOSURE（J）

其中，J是所有那些可从I中的某一状态节点出发经过一条a弧而到达的状态节点的全体。

用子集法将一个NFA转换为一个DFA。

设NFAN=（S，Σ，f，s₀，Z），与之等价的DFAM=（S'，Σ，f'，q₀，Z'），用子集法将非确定的有限自动机确定化的算法步骤如下：

①求出DFAM的初态q₀，即令q₀=ε_CLOSURE（｛s₀｝），此时S'仅含初态q₀，并且没有标记。

②对于S'中尚未标记的状态q_i=｛s_i₁，s_i₂，…，s_im｝，s_ij∈S（j=1，…，m）进行以下处理：

.标记q_i，以说明该状态已经计算过。

.对于每个a∈∑，令T=f（｛s_i₁，s_i₂，…，s_im｝，a），q_j=ε_CLOSURE（T）。

.若q_j尚不在S'中，则将q_j作为一个未加标记的新状态添加到S'，并把状态转换函数f'（q_i，a）=q_j添加到DFAM中。

③重复进行步骤②，直到S'中不再出现未标记的状态时为止。

④令Z'=｛q｜q∈S'且q∩Z≠?｝。

识别ab*a的DFA示意图

对上图所示的自动机进行化简所得的DFA如下图所示。

识别ab*a的最小化DFA示意图

正规式与有限自动机之间的转换

正规式与有限自动机间可以相互转换。

（1）有限自动机转换为正规式。

对于Σ上的NFAM，可以构造一个Σ上的正规式R，使得L（R）=L（M）。

拓广状态转换图的概念，令每条弧可用一个正规式作标记。为Σ上的NFAM构造相应的正规式R，分为如下两步：

第一步：在M的状态转换图中加两个节点，一个x节点，一个y节点。从x节点到NFAM的初始状态节点引一条弧并用ε标记，从NFAM的所有终态节点到y节点引一条弧并用ε标记。形成一个与M等价的M'，M'只有一个初态x和一个终态y。

第二步：按下面的方法逐步消去M'中除x和y的所有节点。在消除节点的过程中，用正规式来标记弧，最后节点x和y之间弧上的标记就是所求的正规式。消除节点的规则如下图所示。

有限自动机到正规式的转换规则示意图

（2）正规式转换为有限自动机。

同样地，对于Σ上的每个正规式R，可以构造一个Σ上的NFAM，使得L（M）=L（R）。

①对于正规式R，可用下图所示的拓广状态图表示。

拓广状态图

②通过对正规式R进行分裂并加入新的节点，逐步把图转变成每条弧上的标记是∑上的一个字符或ε，转换规则如下图所示。

正规式到有限自动机的转换规则示意图

最后所得的图即为一个NFAM，x为初态节点，y为终态节点。显然，L（M）=L（R）。

词法分析器的构造

构造词法分析器的一般步骤为：用正规式描述语言中的单词构成规则；为每个正规式构造一个NFA，它识别正规式所表示的正规集；将构造出的NFA转换成等价的DFA；对DFA进行最小化处理，使其最简；最后用手工编码或表驱动的方式从最简DFA构造词法分析器。


	相关知识点：
	符号表管理出错处理上下文无关文法字母表、字符串、字符串集合及运.. 中间代码优化和目标代码生成动态存储分配和过程调用的翻译语法制导翻译和中间代码生成中间代码生成文法和语言的形式描述常见语言结构的翻译自底向上语法分析方法语法分析目标代码生成文法语义分析词法分析编译程序基本原理代码优化中间代码自顶向下语法分析方法语法分析编译过程概述

	软考在线指南
	优惠劵及余额
	在线支付
	修改密码
	下载及使用
	购买流程
	取消订单

	联系我们
	关于我们
	联系我们
	商务合作

旗下网站群

高级资格科目
信息系统项目管理师	系统分析师
系统架构设计师	网络规划设计师
系统规划与管理师
初级资格科目
程序员	网络管理员
信息处理技术员	信息系统运行管理员

中级资格科目
系统集成项目管理工程师	网络工程师
软件设计师	信息系统监理师
信息系统管理工程师	数据库系统工程师
多媒体应用设计师	软件评测师
嵌入式系统设计师	电子商务设计师
信息安全工程师

本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。

工作时间：9:00-20:00

客服

商务合作

客服邮箱service@rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5 |