词法分析知识点总结NFA DFA
词法分析知识点总结(NFA DFA)2010年05月01日星期六22:12
词法分析是编译器工作的第一阶段,它的工作就是从输入(源代码)中取得token,以作为Parser(语法分析)的输入,一般在词法分析阶段都会把一些无用的空白字符(White Space,即空格、tab和换行)以及注释剔除,以降低下一步分析的复杂度,词法分析器一般会提供一个GetToken()这样的方法,Parser 可以在做语法分析时调用词法分析器的这个方法来得到下一个Token,所以词法分析器并不是一次性遍历所有源代码,而是采取这种On-Demand的方式:只在Parser需要时才工作,并且每次只取一个Token。Token和Lexeme
首先,Token不等于Lexeme。Token和Lexeme的关系就类似于面向对象语言中"类"和"实例"(或"对象")之间的关系,这个用中文不知该如何解释才好,比如语言中的变量a和b,它们都属于同一种Token:Identifier,而a的lexeme是"a",b则是"b",而每个关键字都是一种Token。Token可以附带有一个值属性,例如变量a,当调用词法分析器的GetToken()时,会返回一个Identifier类型的Token,这个token带有一个属性"a",属性可以是多样的,例如表示数字的Token可以带有一个表示数字值的属性,它是整型的。
如下代码:
int age=23;
int count=50;
可以依次提取出8个Token:INT(值为"int"),ID(值为"age"),ASSIGN(值为"="),NUMBER(值为整型数值23),INT(值为"int"),ID(值为"count"),ASSIGN(值为"="),NUMBER(值为50)
正则表达式
正则表达式可以用来描述字符串模式,例如我们可以用digit+来表示NUMBER的token,其中digit表示单个数字(这里说正则表达式并不完全和.NET
实现的正则引擎所识别的正则表达式等价,这里只是为了描述问题而已)。
然而像C语言的的多行注释,用正则表达式来描述就比较麻烦,此时更倾
向于直接用有穷自动机(Finite Automaton)来描述,因为用它来描述非常直观
且很容易。
有穷自动机(Finite Automata)
有穷自动机也称为有限状态机,状态在输入字符的作用下发生迁移,因此,它可以用来识别token,也因此,我们只要画
得出FA,之后再用代码实现这个FA,那词法分析器也就差不多弄好了。
有穷自动机分确定性(DFA)和非确定性(NFA)两种,如果对于同一个输入,
只会有一个确定的状态迁移路线,也就是只有一个确定的"下一状态",那就是DFA,否则就是NFA。
因为DFA对于同一个输入只有一个确定的下一状态,所以词法分析器当然
优先采用它,那NFA拿来干嘛用呢?NFA用来做描述用时更方便,我们可以非常
迅速地画出一个识别token的NFA图,但要想直接画出个DFA那要动不少脑筋。
根据正则表达式构建NFA
如上所述,NFA更容易画出,那我们就先研究NFA,在定义token时,我们
可以用正则表达式来描述它,因为正则表达式干这行很合适,例如一个digit+
就可以描述数字,多方便。因此,我们需要根据正则表达式画出与之等价的NFA。而这个算法非常简单,就是Tompson's construction,这个书上写得很
清楚了。
将NFA转化成DFA(NFA的确定化)
对于计算机来说,面对同一个输入,如果有多个下一状态,那计算机就不
清楚要转到哪个状态,所以我们期望能从正则表达式得到DFA,而不是NFA,因
为这样将来编程实现时比较自然(同一输入有确定的一个下一状态),而幸运的
是,每个NFA都可以转化成DFA。为什么NFA可以转化成DFA?因为FA(Finite Automata)中的状态都是我们自己画的,只要FA能正确的识别token,那就ok 了,也就是,如果NFA和DFA都可以达到一样的效果:识别token,那其它的
我们就不管了。
而NFA确定化的本质,就是将原来多个状态改用一个状态来表示,新状态
其实是一个状态集,比如NFA中状态s1在输入a下可以到达s2和s3,那么,
在DFA中,就把s2和s3合起来认为是一个状态。还有一个问题是NFA中的空
正则匹配到第一个关键字就停止转换(输入),如果s1在输入下可以到达s2,就表示s1可以无条件地转移到s2,那s1和s2自然可以合并起来作为DFA中的一个状态,于是NFA转DFA的算法
也就好理解了。但首先得先定义下空闭包(-closure):
-closure:状态s的-closure即s经过转换可以到达的状态集,s的-closure永远都会包含s自身。一个状态集的-closure即该状态集中各状态的-closure的集合。
NFA确定化算法(Subset Construction):
从开始状态开始,计算它的-closure,得到状态集set1,然后考察set1
在某个输入a的作用下会迁移到哪些状态,把这些状态集中到一起,再求这个
集合的-closure,得到set2,这样我们就可以画两个圈,一个标上set1,另一个标上set2,然后画条从set1到set2的线把这两圆连起来,在线上标上a,
这样DFA的一部分就画好了,然后我们再考察set1在其它输入下可以达到的状态集的-closure,同样画圈连线,以此类推,最后的时候,把包含了原NFA中
终结状态(final state或acceptin state)的DFA状态(在转换后的DFA中,每个状态都是包含了一个或多个原NFA中的状态)标记为终结状态。
最小化DFA状态数
由一个正则表达式,可以构建出一个等价的NFA,然后NFA又可以确定化
成DFA,似乎到此事情搞完了,但事实证明(有时也可以显然地发现),最终构
成的这DFA似乎有些复杂,有些状态好像很冗余,呃,是的,DFA是可以最小
化的。
最小化DFA状态数算法的思想是,在开始时,假设是最完美的情况,整个DFA只有两个状态,一个终结状态,一个开始(难道不能有只有一种状态的情况么?如果原DFA中存在非终结状态,当然就不能,非终结态怎么可以和终结态合并!),当然,这是假设,不是真的,所以这个算法,就是在这个完美的假设下,对假设进一步考察,如果发现有些状态不能合并,那就分出来吧,这样重复考察,直到发现没有状态会不能合并时,就做完了,此时不也正是最优解么。
嗯,就是这个,所以一开始,我们把所有非终结状态用一个袋子包起来,
看成是一个状态,把所有终结状态也用另一袋子包起来,也看成是一个状态,
注意,别把原DFA中各状态间的连线给扯断了。然后,我们抽出其中一个袋子,考察其中的各个状态,我们准备好所有的可能输入,然后逐个拿出来测试,如
果该袋子中的所有状态在某个输入a下达到的状态正好都在这个袋子中,那就
说明,这个袋子中的这些状态"在目前看来"是可以合并的,也就是说,如果在
所有的可能输入的作用下,袋子中的状态达到的新状态正好也都是这个袋子中
的状态,那它们就可以合并。而如果,在某个输入a下,袋子中的一部分状态
会转移到同一袋子中的其它状态,而有几个叛徒,假设是s1和s2,竟然在输
入a下会迁移到其它袋子中的状态,那就说明s1和s2是不可以和其它转移到
同一袋子中的状态合并的,于是,我们就把s1和s2装成一个新袋子,从原袋
子中分出来,当然,现在还是假设s1和s2可以合并,所以才把它们装一起,
究竟真的可不可以合并呆会还要再考察。考察完输入a,还要接着考察其它的
可能输入。如果在考察完一个袋子后,发现所有状态在a输入下都可以转移到
本袋子中的状态,那么最后的DFA它们就被合并成一个状态,并且在a输入下,它有一个到自身的状态迁移。
实现词法分析器
对于一个token,比如用来表示数字的token:NUM,我们可以用正则表达
式描述它,然后画出NFA,再将NFA转化成DFA,再最小化DFA的状态,但是我们的词法分析器是不是分析一个token,所以我们要把所有类型的token的DFA 合并成一个DFA,这样,这个DFA也就可以识别语言的所有token了,如果在
某一连串的输入下,DFA达不到终结状态,那就说明源代码有错误了。
我用C#实现了一个用于《Compiler Construction:Principles and Practice》中TINY语言的词法分析器,TINY语言有关键字:
if,then,else,end,repeat,until,read,write,有操作符+,-,*,/,=,,(,),;,:=(全角逗号不算,是文章的分隔符)这10个,然后其余的Token
有Number(一或多个数字)和Identifier(一或多个字母),其DFA如下图:
上面这张图和《编译原理及实践》中的一样,其中的带中括号的输入说明
这个输入是lookahead的,在匹配成功后是要重新放回输入流中的,比如识别NUM时,如果发现个非digit的,那就说明识别到了一个Number,但是最后识
别的那个非digit字符是要放回输入流的,因为它要留着下一次识别。
其中从Start到Done的那个other,指所有非white space,非{,非letter,非digit,也非:的字符,它有可能是合法的+,*,/这些,也可能是不
合法的其它输入,如#号。因此,DONE这个状态只是说本次getToken已经结束,状态机是有可能因为不合法的输入而进入DONE状态的。究竟从Start到Done
是因为合法的,如+号导致的,还是由不合法的如#号导致的,将在代码中实现
判断,但可以肯定的是,不管是+号还是#号作用于Start状态,都会进入Done
状态。

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。