词法分析程序输出结果

f函数定义有错误，需要改成

int f(int x,char e)

{ int df[4][2]={{2,3},{4,3},{2,4},{4,4}};

int i;

if(e=='a')

i=df[x-1][0];

if(e=='b')

i=df[x-1][1];

return(i);

}

DFA或NFA是对计算机程序的行为的抽象模型你编写的程序其实就对应了一个自动机简单举例来说,如果a,b可以取值0或1; 程序：if(a==1) b=1; 这个程序对应了一个自动机

对应的自动机就有状态 (0,0),(0,1),(1,1),(1,0)

比如你自动机的初始状态是 (1,0)即a=1,b=0时,运行程序的下一个状态就是(1,1)

画图出来就是 这4个状态作为顶点,并且有下面几条边

(0,0) --> (0,0)（自环）,(1,0)-->(1,1),(1,1)-->(1,1)（自环）,(0,1)-->(0,1)自环

存在的意义就是一种理论模型,也可以认为是一种编程思想词法分析系也离不开 if else,这一系列的if else和条件也就组成自动机

最经典体现自动机思想的算法就是KMP算法,你肯定学过,字符串子串匹配的算法回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机!算法第二步将原串作为自动机输入,自动机的输出就是匹配到的子串位置或者无匹配

具有ε动作的NFA的确定化——子集法由于现在的NFA中具有ε动作，故下面要介绍的构造相应DFA的方法和定理3�1中所给出的方法有所不同。

设已给具有ε动作的非确定的有限自动机

M=(K,Σ,f,S0,Z)

则构造相应的DFA

M′=(K′,Σ,f′,q0,Z′)

的基本思路是： 首先把从S0出发，仅经过任意条ε矢线所能到达的状态所组成的集合作为M′的初态q0，然后分别把从q0出发，经过对输入符号a∈Σ的状态转移所能到达的状态 (包括转移后再经ε矢线所能到达的状态)组成的集合作为M′的状态，如此等等，直到不再有新的状态出现为止。具体地说，构造K′及f′的步骤可递归地描述如下。

1�令K′={εCLOSURE(S0)}(给出M′的初态q0)。

2�对于K′中任一尚未标记的状态qi={Si1,Si2,…,Sim},Sik∈K，做：

(1) 标记qi；

(2) 对于每个a∈Σ，置

T=f({Si1,Si2,…,Sim},a)

qj=εCLOSURE(T)

(3) 若qj不在K′中，则将qj作为一个未加标记的状态添加到K′中，且把状态转移

f′(qi,a)=qj

添加到M′。

3�重复进行步骤2，直到K′中不再含有未标记的状态为止。对于由此构造的K′，我们把那些至少含有一个Z中的元素的qi作为M′的终态。

例3�4再考虑图310所示的NFA，对它应用上述算法进行确定化，我们有：

1�因为εCLOSURE(S0)={S0,S1,S2,S3}，故将q0={S0,S1,S2,S3}作为未标记的状态置于K′中。

2�此时K′中仅有惟一的未标记状态q0，故

(1) 标记q0；

(2) 作

f′(q0,a)=εCLOSURE(f({S0,S1,S2,S3},a))=

εCLOSURE(S0)=q0

f′(q0,b)=εCLOSURE(f({S0,S1,S2,S3},b))=

εCLOSURE({S1,S3})={S1,S3}

且把q1={S1,S3}作为未加标记的状态加入K′中，再作

f′(q0,c)=εCLOSURE(f({S0,S1,S2,S3},c))=

εCLOSURE({S2})={S2,S3}

且把q2={S2,S3}作为未加标记的状态加入K′中。

3�此时，K′={q0,q1,q2}，其中q1,q2均未加标记，故

(1) 标记q1；

(2) 作

f′(q1,a)=εCLOSURE(f({S1,S3},a))=

εCLOSURE(�)=�

f′(q1,b)=εCLOSURE(f({S1,S3},b))=

εCLOSURE({S1,S3})=q1

f′(q1,c)=εCLOSURE(f({S1,S3},c))=此时，K′未增大，但q2尚未标记，故

(1) 标记q2；(2) 类似地可求得f′(q2,a)=f′(q2,b)=� f′(q2,c)=q2；至此，K′中的状态q0,q1,q2已全部标记完毕，故确定化的过程结束。最后，容易看到，Z′={q0,q1,q2}，且所得的DFA M′如图312所示。

例3�5对于图311所示的NFA，利用上述算法所得的DFA如图313所示。其中，圆圈中的数字都是原NFA的状态编号，在图313中，q0={0,1,7,11,14,19,24,26,28,30,33,35,38,40}。标有“#”的状态意指在这些状态之下，当扫视到未在其射出弧上出现过的字母或数字字符时，将转移到状态25。显然，在按图313实现词法分析程序时，同样应采取某种策略，以区别源程序中的关键字和标识符。

图3－13M确定化后的DFA

最后，顺便提及，上面所给出的NFA确定化的算法，同样可应用于不含ε动作的NFA的确定化。

DFA 引擎在线性时状态下执行，因为它们不要求回溯（并因此它们永远不测试相同的字符两次）。DFA 引擎还可以确保匹配最长的可能的字符串。但是，因为 DFA 引擎只包含有限的状态，所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式。

传统的 NFA 引擎运行所谓的“贪婪的”匹配回溯算法，以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。但是，因为传统的 NFA 回溯，所以它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现。

POSIX NFA 引擎与传统的 NFA 引擎类似，不同的一点在于：在它们可以确保已找到了可能的最长的匹配之前，它们将继续回溯。因此，POSIX NFA 引擎的速度慢于传统的 NFA 引擎；并且在使用 POSIX NFA 时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索。

使用DFA引擎的程序主要有：awk,egrep,flex,lex,MySQL,Procmail等；

使用传统型NFA引擎的程序主要有：GNU Emacs,Java,ergp,less,more,NET语言,PCRE library,Perl,PHP,Python,Ruby,sed,vi；

使用POSIX NFA引擎的程序主要有：mawk,Mortice Kern Systems’ utilities,GNU Emacs(使用时可以明确指定)；

也有使用DFA/NFA混合的引擎：GNU awk,GNU grep/egrep,Tcl。

举例简单说明NFA与DFA工作的区别：

比如有字符串this is yansen’s blog，正则表达式为 /ya(msen|nsen|nsem)/ (不要在乎表达式怎么样，这里只是为了说明引擎间的工作区别)。 NFA工作方式如下，先在字符串中查找 y 然后匹配其后是否为 a ，如果是 a 则继续，查找其后是否为 m 如果不是则匹配其后是否为 n (此时淘汰msen选择支)。然后继续看其后是否依次为 s,e，接着测试是否为 n ，是 n 则匹配成功，不是则测试是否为 m 。为什么是 m ？因为 NFA 工作方式是以正则表达式为标准，反复测试字符串，这样同样一个字符串有可能被反复测试了很多次！

而DFA则不是如此，DFA会从 this 中 t 开始依次查找 y，定位到 y ，已知其后为a，则查看表达式是否有 a ，此处正好有a 。然后字符串a 后为n ，DFA依次测试表达式，此时 msen 不符合要求淘汰。nsen 和 nsem 符合要求，然后DFA依次检查字符串，检测到sen 中的 n 时只有nsen 分支符合，则匹配成功！

由此可以看出来，两种引擎的工作方式完全不同，一个(NFA)以表达式为主导，一个(DFA)以文本为主导！一般而论，DFA引擎则搜索更快一些！但是NFA以表达式为主导，反而更容易 *** 纵，因此一般程序员更偏爱NFA引擎！ 两种引擎各有所长，而真正的引用则取决与你的需要以及所使用的语言！

词法分析是把构成源程序的字符串转换成单词符号序列。词法规则可用 3型文法 （正规文法）或正规表达式描述，他产生的集合是语言基本字符集Σ（字母表）上的字符串的一个子集，称为正规集。

正规式是一种表示正规集的工具，正规式是描述程序语言单词的表达式，对于字母表Σ。

正规式（正规表达式）的运算符有3个，优化级从高到低顺序排列为：（闭包）、·（连接，可省略）、|（或）。

正规式  →  正规集

ab  →  字符串ab构成的集合

a|b  →  字符串a、b构成的集合

a  →  由0个或多个a构成的字符串集合

(a|b)  →  所有字符a和b构成的串的集合

a(a|b)  →  以a为首字符的a、b字符串的集合

(a|b)abb  →  以abb结尾的a、b字符串的集合

有限自动机可以转换为正规式，正规式也可以转换为有限自动机。

词法分析器的构造步骤：

1）用正规式描述语言中的单词构成规则。

2）为每个正规式构造一个NFA，它识别正规式所表示的正规集。

3）将构造出的NFA转换成等价的DFA。

4）对DFA进行最小化处理，使其最简。

5）从DFA构造词法分析器。

既然你都知道它们是怎么回事儿了，怎么会不明白它们和词法分析程序的关系呢？

简单点儿说，词法分析就是进行正则表达式匹配。词法分析程序就是根据要匹配的正则表达式生成它的NFA或者DFA，再将待匹配的字符串放到这些NFA或者DFA中进行处理，从而分析出输入字符串是否匹配给定的正则表达式。

1、使用C/C++程序设计语言和递归下降子程序的方法编写该函数绘图语言的词法分析器。并要求设计一个词法分析器的测试小程序来调用自己编写的词法分析器测试各种不同的输入。

2、词法分析的任务是对输入的字符串形式的源程序按顺序进行扫描，在扫描的同时，根据源语言的词法规则识别具有独立意义的单词（符号），并产生与其等价的属性字流（内部编码）作为输出。通常属性字流即是对识别的单词给出的标记符号的集合。

二、分析与设计

词法分析程序一般具有如下功能:读入字符串形式的源程序;识别出具有独立意义的最小语法单位:单词。

事实上，由正规表达式到最小化DFA的转换源程序中的测试生成串部分就是对所输入的单词进行判断，看其是否能被生成的DFA接受（也就是这个单词是否符合正规式定义的要求）。这本质上就是一个简单的词法分析。

定义某种语言的单词，并给出编号。该语言单词包括：保留字、运算符、标识符、常量、格式符等。根据给定的语言子集构造词法分析器。输出为中间文件。

在设计时为了便于理解，不使用内部编码而用枚举对同类型的单词进行标识。例如所有的常量统一用“CONST_ID”对其进行标识，当扫描时遇到常量就输出该常量的值和“CONST_ID”标识。

这里给出词法分析程序大概的设计方法：

1、根据要求写出词法分析的正规文法G；

2、根据正规文法G，写出正则式RE；

3、根据正则式RE，画出NFA；

4、将NFA转化为DFA；

5、将DFA转化为mininum state DFA；

6、mininum state DFA就是词法分析程序的流程图，根据此流程图编写相应的词 法分析程序。

以下是较为详细的设计：

①总体结构与模块划分

以上就是关于词法分析程序输出结果全部的内容，包括:词法分析程序输出结果、编译原理，如何判断一个FA是DFA还是NFA、将NFA确定化的源程序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！