全部科目 > 软件设计师 >
2018年上半年 上午试卷 综合知识
第 49 题
知识点 词法分析   有限自动机  
关键词 有限自动机   字符串   自动机  
章/节 计算机软件知识  
 
 
下图所示为一个不确定有限自动机(NFA)的状态转换图。该NFA识别的字符串集合可用正规式（49）描述。
 
  A.  ab*a
 
  B.  (ab)*a
 
  C.  a*ba
 
  D.  a(ba)*
 
 




 
 
相关试题     编译程序的基本原理 

  第53题    2021年上半年  
设有描述简单算术表达的上下文无关文法如下，其中id表示单字母。
E→E+T|T
T→F*T|F
F→id
与使用该文法描述的表达式a+b*c*d相符的语法树为(52)，
下图所示..

  第21题    2010年下半年  
编译程序分析源程序的阶段依次是（21)。

  第48题    2016年上半年  
移进—归约分析法是编译程序（或解释程序）对高级语言源程序进行语法分析的一种方法，属于（48）的语法分析方法。

 
知识点讲解
· 词法分析
· 有限自动机
 
        词法分析
        1）正规表达式和正规集
        对于字母表∑，其上的正规表达式（也称正则表达式，简称正规式）及其表示的正规集可以递归定义如下。
        （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)。
        仅由有限次地使用上述3个步骤定义的表达式才是∑上的正规式，其中运算符"|"".""*"分别称为"或""连接"和"闭包"。若两个正规式表示的正规集相同，则认为两者等价。
        2）有限自动机
        有限自动机是一种识别装置的抽象概念，它能够正确地识别正规集。
        （1）确定的有限自动机。
        一个确定的有限自动机（DFA）是个五元组：（S，∑，f，s0，Z），其中：
        ①S是一个有限集，其每个元素称为一个状态。
        ②∑是一个有限字母表，其每个元素称为一个输入字符。
        ③f是从S×∑→S上的单值部分映像。
        ④s0∈S是唯一的一个开始状态。
        ⑤Z是非空的终止状态集合。
        一个DFA可以用两种直观的方式表示，即状态转换图和状态转换矩阵。状态转换图简称为转换图，它是一个有向图。DFA中的每个状态对应转换图中的一个节点，DFA中的每个转换函数对应图中的一条有向弧，若转换函数为f(A,a)=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。状态转换矩阵可以用一个二维数组M表示，矩阵元素的行下标表示状态，列下标表示输入字符，M[A,a]的值是当前状态为A、输入为a时应转换到的下一状态。在转换矩阵中，一般以第一行的行下标所对应的状态作为初态，而终态则需要特别指出。
        （2）不确定的有限自动机。
        一个不确定的有限自动机（NFA）也是一个五元组，它与确定的有限自动机的区别如下。
        ①f是从S×∑→2S上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合。
        ②有向弧上的标记可以是ε。
        显然，DFA是NFA的特例。
        实际上，对于每个NFAM，都存在一个DFAN，且L(M)=L(N)。
        对于任何两个有限自动机M1和M2，如果L(M1)=L(M2)，则称M1和M2是等价的。
        3）NFA到DFA的转换
        设NFAN=(S,∑,f,s0，Z)，与之等价的DFAM=(S',∑,f',q0,Z')，用子集法将非确定的有限自动机确定化的算法步骤如下。
        （1）求出DFAM的初态q0，此时S'仅含初态q0，并且没有标记。
        （2）对于S'中尚未标记的状态qi={si1,si2,…,sim}和sij∈(j=1,2,…,m)进行下述处理。
        ①标记qi。
        ②对于每个a∈∑，令T=f(si1,si2,…,sim,a)，qj=ε_CLOSURE(T)。
        ③若qi尚不在S'中，则将qj作为一个未加标记的新状态添加到S'，并把状态转换函数f'(qi,a)=qj添加到DFAM。
        （3）重复步骤（2），直到S'中不再有未标记的状态时为止。
        （4）令Z'={q|q∈S'且q∩Z≠?}。
        注：若I是NFAN的状态集合的一个子集，其中ε_CLOSURE(I)的定义如下。
        ①状态集I的ε_CLOSURE(I)是一个状态集。
        ②状态集I的所有状态属于ε_CLOSURE(I)。
        ③若s在I中，那么从s出发经过任意条ε弧到达的状态s'都属于ε_CLOSURE(I)。
        从NFA转换得到的DFA不一定是最简化的，可以通过等价变换将DFA进行最小化处理。
        4）正规式与有限自动机之间的转换
        （1）对于∑上的NFAM，可以构造一个∑上的正规式R，使得L(R)=L(M)。
        构造过程分以下两步进行。
        ①在M的状态转换图中加两个节点x和y。
        ②按下图所示的方法逐步消去M中的除x和y的所有节点。
        
        状态转换图（消去中间节点）
        （2）对于∑上的每一个正规式R，可以构造一个∑上的NFAM，使得L(M)=L(R)。
        （3）构造过程分两步进行。
        ①对于正规式R，可用如下图所示的拓广状态图表示。
        
        拓广状态图
        ②通过对正规式R进行分裂并加入新的节点，逐步把图转变成每条弧上的标记是∑上的一个字符或ε，转换规则如下图所示。
        
        状态转换图（加入新节点）
        5）词法分析器的构造
        词法分析器的构造过程如下。
        （1）用正规式描述语言中的单词构成规则。
        （2）为每个正规式构造一个NFA，用于识别正规式所表示的正规集。
        （3）将构造出的NFA转换成等价的DFA。
        （4）对DFA进行最小化处理，使其最简。
        （5）根据DFA构造词法分析器。
 
        有限自动机
        有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为两类：确定的有限自动机和不确定的有限自动机。
        （1）确定的有限自动机（Deterministic Finite Automata，DFA）。一个确定的有限自动机是个五元组：（S，∑，f，s0，Z），其中：
        ①S是一个有限集合，它的每个元素称为一个状态。
        ②∑是一个有穷字母表，它的每个元素称为一个输入字符。
        ③f是S×∑→S上的单值部分映像。f（A，a）=Q表示当前状态为A、输入为a时，将转换到下一状态Q。称Q为A的一个后继状态。
        ④s0∈S，是唯一的一个开始状态。
        ⑤Z是非空的终止状态集合，
        一个DFA可以用两种直观的方式表示：状态转换图和状态转换矩阵。状态转换图是一个有向图，简称为转换图。DFA中的每个状态对应转换图中的一个结点；DFA中的每个转换函数对应图中的一条有向弧，若转换函数为f（A，a）=Q，则该有向弧从结点A出发，进入结点Q，字符a是弧上的标记。
        例如，DFAM1=（{s0，s1，s2，s3}，{a，b}，f，s0，{s3}），其中f为：
        f（s0，a）=s1，f（s0，b）=s2，f（s1，a）=s3，f（s1，b）=s2，f（s2，a）=s1，f（s2，b）=s3，f（s3，a）=s3
        与DFAM1对应的状态转换图如下图（a）所示，其中，状态s3表示的结点是终态结点。状态转换矩阵可以用一个二维数组M表示，矩阵元素M[A，a]的行下标表示状态，列下标表示输入字符，M[A，a]的值是当前状态为A、输入字符为a时，应转换到的下一状态。与DFAM1对应的状态转换矩阵如下图（b）所示。在转换矩阵中，一般以第一行的行下标对应的状态作为初态，而终态则需要特别指出。
        
        确定的有限自动机示意图
        对于∑中的任何字符串ω，若存在一条从初态结点到某一终止状态结点的路径，且这条路径上所有弧的标记符连接成的字符串等于ω，则称ω可由DFAM识别（接受或读出）。若一个DFAM的初态结点同时又是终态结点，则空字ε可由该DFA识别（或接受）。DFAM所能识别的语言L（M）={ω|ω是从M的初态到终态的路径上的弧上标记所形成的串}。
        例如，对于字符串"ababaa"，在上图（a）所示的状态转换图中，识别"ababaa"的路径是s0→s1→s2→s1→s2→s1→s3。由于从初态结点s0出发，存在到达终态结点s3的路径，因此该DFA可识别串"ababaa"。而"abab"和"baab"都不能被该DFA接受。对于字符串“abab“，从初态结点s0出发，经过路径s0→s1→s2→s1→s2，当串结束时还没有到达终态结点s3；而对于串"baab"，经过路径s0→s2→s1→s3，虽然能到达终态结点s3，但串尚未结束又不存在与下一字符"b"相匹配的状态转换。
        （2）不确定的有限自动机（Nondeterministic Finite Automata，NFA）。一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别如下。
        ①f是S×∑→2s上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一确定的。
        ②有向弧上的标记可以是ε。
        例如，已知有NFAN=（{s0，s1，s2，s3}，{a，b}，f，s0，{s3}），其中f为：
        f（s0，a）=s0，f（s0，a）=s1，f（s0，b）=s0，f（s1，b）=s2，f（s2，b）=s3
        与NFAM2对应的状态转换图和状态转换矩阵如下图所示。
        
        NFA的状态转换图和转换矩阵
        显然，DFA是NFA的特例。实际上，对于每个NFAM，都存在一个DFAN，且L（M）=L（N）。
        词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号，然后构造相应有限自动机的状态转换图，最后依据状态转换图编写词法分析器（程序）。



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2023 All Rights Reserved
软考在线版权所有