词法分析小结

《词法分析小结》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、精品文档词法分析小结词法分析是编译器工作的第一阶段，它的工作就是从输入中取得token，以作为parser的输入，一般在词法分析阶段都会把一些无用的空白字符以及注释剔除，以降低下一步分析的复杂度，词法分析器一般会提供一个gettoken()这样的方法，parser可以在做语法分析时调用词法分析器的这个方法来得到下一个token，所以词法分析器并不是一次性遍历所有源代码，而是采取这种on-demand的方式：只在parser需要时才工作，并且每次只取一个token。token和lexeme首先，token不等于lexeme

2、。token和lexeme的关系就类似于面向对象语言中“类”和“实例”之间的关系，这个用中文不知该如何解释才好，比如语言中的变量a和b，它们都属于同一种token：identifier，而a的lexeme是”a”，b则是”b”，而每个关键字都是一种token。token可以附带有一个值属性，例如变量a，当调用词法分析器的gettoken()时，会返回一个identifier类型的token，这个token带有一个属性“a”，属性可以是多样的，例如表示数字的token可以带有一个表示数字值的属性，它是整型的。如下代码：in

3、tage=23;intcount=2016全新精品资料-全新公文范文-全程指导写作–独家原创7/7精品文档50;可以依次提取出8个token：int(值为”int”)，id(值为”age”)，assign(值为”=”)，number(值为整型数值23)，int(值为”int”)，id(值为”count”)，assign(值为”=”)，number(值为50)正则表达式正则表达式可以用来描述字符串模式，例如我们可以用digit+来表示number的token，其中digit表示单个数字。然而像c语言的的多行注释，用正则表达

4、式来描述就比较麻烦，此时更倾向于直接用有穷自动机来描述，因为用它来描述非常直观且很容易。有穷自动机(finiteautomata)有穷自动机也称为有限状态机，状态在输入字符的作用下发生迁移，因此，它可以用来识别token，也因此，我们只要画得出fa，之后再用代码实现这个fa，那词法分析器也就差不多弄好了。有穷自动机分确定性和非确定性两种，如果对于同一个输入，只会有一个确定的状态迁移路线，也就是只有一个确定的“下一状态”，那就是dfa，否则就是nfa。2016全新精品资料-全新公文范文-全程指导写作–独家原创7/7精品文档

5、因为dfa对于同一个输入只有一个确定的下一状态，所以词法分析器当然优先采用它，那nfa拿来干嘛用呢？nfa用来做描述用时更方便，我们可以非常迅速地画出一个识别token的nfa图，但要想直接画出个dfa那要动不少脑筋。根据正则表达式构建nfa如上所述，nfa更容易画出，那我们就先研究nfa，在定义token时，我们可以用正则表达式来描述它，因为正则表达式干这行很合适，例如一个digit+就可以描述数字，多方便。因此，我们需要根据正则表达式画出与之等价的nfa。而这个算法非常简单，就是tompson’sconstructi

6、on，这个书上写得很清楚了。将nfa转化成dfa对于计算机来说，面对同一个输入，如果有多个下一状态，那计算机就不清楚要转到哪个状态，所以我们期望能从正则表达式得到dfa，而不是nfa，因为这样将来编程实现时比较自然，而幸运的是，每个nfa都可以转化成dfa。为什么nfa可以转化成dfa？因为fa(finiteautomata)中的状态都是我们自己画的，只要fa能正确的识别token，那就ok了，也就是，如果nfa和dfa都可以达到一样的效果：识别token，那其它的我们就不管了。〖1〗〖2〗〖3〗2016全新精品资料-全

7、新公文范文-全程指导写作–独家原创7/7精品文档而nfa确定化的本质，就是将原来多个状态改用一个状态来表示，新状态其实是一个状态集，比如nfa中状态s1在输入a下可以到达s2和s3，那么，在dfa中，就把s2和s3合起来认为是一个状态。还有一个问题是nfa中的空转换，如果s1在?输入下可以到达s2，就表示s1可以无条件地转移到s2，那s1和s2自然可以合并起来作为dfa中的一个状态，于是nfa转dfa的算法也就好理解了。但首先得先定义下空闭包：?-closure:状态s的?-closure即s经过?转换可以到达的状态集，

8、s的?-closure永远都会包含s自身。一个状态集的?-closure即该状态集中各状态的?-closure的集合。nfa确定化算法(subsetconstruction)：从开始状态开始，计算它的?-closure，得到状态集set1，然后考察set1在某个输入a的作用下会迁移到哪些状态，把这些状态集中到一起，再