资源描述：
《【精品】词法分析小结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、词法分析小结》简介：词法分析是编译器工作的第一阶段，它的工作就是从输入（源代码）屮取得token,以作为Parser（语《词法分析小结》正文开始>>词法分析是编译器工作的第一阶段，它的工作就是从输入（源代码）中取得token,以作为Parser（语法分析）的输入，一般在词法分析阶段都会把一些无用的空口字符（WhiteSpace,即空格、tab和换行）以及注释剔除，以降低下一步分析的复杂度，词法分析器一般会提供一个GetToken（）这样的方法,Parser可以在做语法分析时调用词法分析器的这个方法来得到下
2、一个Token,所以词法分析器并不是一次性遍历所冇源代码，而是采取这种On-Demand的方式：只在Parser需要时才工作，并口每次只取一个Token。Token和Lexeme首先，Token不等于Lexeme。Token和Lexeme的关系就类似丁•而向对象语言屮“类”和“实例”（或“对象”）之间的关系，这个用中文不知该如何解释才好,比如语言中的变量a和b,它们都属于同一种Token：Identifier,而a的lexeme是”a”,b则是”b”,而每个关键字都是一种TokenoToken可以附带有一
3、个值屈性，例如变量当调用词法分析器的GetToken（）时，会返回一个Identifier类型的Token,这个token带有一个属性“a”，属性可以是多样的,例如表示数字的TokenTiJ以带有一个表示数字值的属性，它是整型的。如下代码：intage=23;intcount二50;可以依次提取出8个Token：INT（值为”int”）,ID（值为”age”），ASSIGN（值为”二”）,NUMBER（｛ft为整型数值23）,[NT（值为”int”）,ID（值为”count”）,ASSIGN（值为”二”）
4、，NUMBER（值为50）正则表达式正则表达式可以用来描述字符串模式，例如我们可以用digits来表示NUMBER的token,其中digit表示单个数字（这里说正则表达式并不完全和实现的正则引擎所识别的正则表达式等价，这里只是为了描述问题而已）。然而像C语言的的多行注释，用正则表达式來描述就比较麻烦，此时更倾向于直接用有穷自动机（FiniteAutomaton）来描述，因为用它来描述非常直观且很容易。有穷自动机(FiniteAutomata)有穷口动机也称为有限状态机，状态在输入字符的作用卜•发生迁移，
5、因此，它可以用來识别token,也因此，我们只要画得出FA,之后再用代码实现这个FA,那词法分析器也就差不多弄好了。有穷自动机分确定性(DFA)和非确定性(NFA)两种，如果对于同一个输入，只会有一个确定的状态迁移路线，也就是只有一个确定的“卜•一状态”，那就是DFA,否则就是NFA。因为DFA对于同一个输入只有一个确定的下一状态，所以词法分析器当然优先采用它，那NFA拿来干嘛用呢？NFA用来做描述用时更方便，我们可以非常迅速地画出一个识别token的NFA图，但要想直接画出个DFA那要动不少脑筋。根据止
6、则表达式构建MFA如上所述,NFA更容易画出,那我们就先研究NFA,在定义token时,我们可以用正则表达式来描述它，因为正则表达式干这行很合适，例如一个digits就可以描述数字，多方便。因此，我们需要根据止则表达式画出与Z等价的NFA。而这个算法非常简单，就是Tompson'sconstruction,这个书上写得很清楚了。将NFA转化成DFA(NFA的确定化)对于计算机来说，面对同一个输入，如果有多个下一状态，那计算机就不清楚要转到哪个状态，所以我们期望能从止则表达式得到DFA,而不是NFA,因为这
7、样将來编程实现时比较口然(同一输入有确定的一个下一状态)，而幸运的是，每个NFA都可以转化成DFA。为什么NFA可以转化成DFA?因为FA(FiniteAutomata)中的状态都是我们自己画的，只要FA能正确的识别token,那就ok了，也就是，如果NFA和DFA都可以达到一样的效果：识别token,那其它的我们就不管了。而MFA确定化的木质，就是将原來多个状态改用一个状态來表示，新状态其实是一个状态集，比如"FA中状态si在输入a下可以到达s2和s3,那么，在DFA中，就把s2和S3合起来认为是一个状
8、态。还有一个问题是MFA中的空转换(8输入)，如杲si在苗俞入下可以到达s2,就表示si可以无条件地转移到s2,那si和s2口然可以合并起來作为DFA中的一个状态，于是NFA转DFA的算法也就好理解了。但首先得先定义下空闭包(s-closure):s-closure:状态s的s-closure即s经过£转换可以到达的状态集,s的£-closure永远都会包含s口身。一个状态集的8-closurc即该状态集中各状态的8-clos
