《词法分析小结精选》由会员分享，可在线阅读，更多相关《词法分析小结精选（7页珍藏版）》请在金锄头文库上搜索。
1、精品文档 2016全新精品资料-全新公文范文-全程指导写作 独家原创 1 / 7词法分析小结词法分析是编译器工作的第一阶段，它的工作就是从 输入中取得token，以作为parser的输入，一般在词法分 析阶段都会把一些无用的空白字符以及注释剔除，以降低 下一步分析的复杂度，词法分析器一般会提供一个 gettoken这样的方法，parser可以在做语法分析时调用词 法分析器的这个方法来得到下一个token，所以词法分析器 并不是一次性遍历所有源代码，而是采取这种on-demand 的方式：只在parser需要时才工作，并且每次只取一个 token。token和lexeme首先，token不等于l
2、exeme。token和lexeme的关 系就类似于面向对象语言中“类”和“实例”之间的关系， 这个用中文不知该如何解释才好，比如语言中的变量a和 b，它们都属于同一种token：identifier，而a的lexeme 是”a” ，b则是”b” ，而每个关键字都是一种 token。token可以附带有一个值属性，例如变量a，当调 用词法分析器的gettoken时，会返回一个identifier类 型的token，这个token带有一个属性“a” ，属性可以是多 样的，例如表示数字的token可以带有一个表示数字值的 属性，它是整型的。如下代码：精品文档 2016全新精品资料-全新公文范文-全
3、程指导写作 独家原创 2 / 7int age =3;int count =0;可以依次提取出8个 token：int，id，assign，number，int，id，assign，nu mber正则表达式正则表达式可以用来描述字符串模式，例如我们可 以用digit+来表示number的token，其中digit表示单个 数字。然而像c语言的的多行注释，用正则表达式来描述 就比较麻烦，此时更倾向于直接用有穷自动机来描述，因 为用它来描述非常直观且很容易。有穷自动机有穷自动机也称为有限状态机，状态在输入字符的 作用下发生迁移，因此，它可以用来识别token，也因此， 我们只要画得出fa，之后再用
4、代码实现这个fa，那词法分 析器也就差不多弄好了。有穷自动机分确定性和非确定性两种，如果对于同 一个输入，只会有一个确定的状态迁移路线，也就是只有 一个确定的“下一状态” ，那就是dfa，否则就是nfa。因为dfa对于同一个输入只有一个确定的下一状态， 所以词法分析器当然优先采用它，那nfa拿来干嘛用呢？精品文档 2016全新精品资料-全新公文范文-全程指导写作 独家原创 3 / 7 nfa用来做描述用时更方便，我们可以非常迅速地画出一个 识别token的nfa图，但要想直接画出个dfa那要动不少 脑筋。根据正则表达式构建nfa如上所述，nfa更容易画出，那我们就先研究nfa， 在定义toke
5、n时，我们可以用正则表达式来描述它，因为 正则表达式干这行很合适，例如一个digit+就可以描述数 字，多方便。因此，我们需要根据正则表达式画出与之等 价的nfa。而这个算法非常简单，就是tompsons construction，这个书上写得很清楚了。将nfa转化成dfa对于计算机来说，面对同一个输入，如果有多个下 一状态，那计算机就不清楚要转到哪个状态，所以我们期 望能从正则表达式得到dfa，而不是nfa，因为这样将来编 程实现时比较自然，而幸运的是，每个nfa都可以转化成 dfa。为什么nfa可以转化成dfa？因为fa中的状态都是我 们自己画的，只要fa能正确的识别token，那就ok了
6、，也 就是，如果nfa和dfa都可以达到一样的效果：识别 token，那其它的我们就不管了。而nfa确定化的本质，就是将原来多个状态改用一 个状态来表示，新状态其实是一个状态集，比如nfa中状 态s1在输入a下可以到达s2和s3，那么，在dfa中，就精品文档 2016全新精品资料-全新公文范文-全程指导写作 独家原创 4 / 7 把s2和s3合起来认为是一个状态。还有一个问题是nfa 中的空转换，如果s1在?输入下可以到达s2，就表示s1可 以无条件地转移到s2，那s1和s2自然可以合并起来作为 dfa中的一个状态，于是nfa转dfa的算法也就好理解了。 但首先得先定义下空闭包：?-closu
7、re: 状态s的?-closure即s经过?转换可以 到达的状态集，s的?-closure永远都会包含s自身。一个 状态集的?-closure即该状态集中各状态的?-closure的集 合。nfa确定化算法：从开始状态开始，计算它的?-closure，得到状态集 set1，然后考察set1在某个输入a的作用下会迁移到哪些 状态，把这些状态集中到一起，再求这个集合的?- closure，得到set2，这样我们就可以画两个圈，一个标上 set1，另一个标上set2，然后画条从set1到set2的线把 这两圆连起来，在线上标上a，这样dfa的一部分就画好了， 然后我们再考察set1在其它输入下可以达
8、到的状态集的?- closure，同样画圈连线，以此类推，最后的时候，把包含 了原nfa中终结状态的dfa状态标记为终结状态。最小化dfa状态数由一个正则表达式，可以构建出一个等价的nfa，然 后nfa又可以确定化成dfa，似乎到此事情搞完了，但事实精品文档 2016全新精品资料-全新公文范文-全程指导写作 独家原创 5 / 7 证明，最终构成的这dfa似乎有些复杂，有些状态好像很 冗余，呃，是的，dfa是可以最小化的。最小化dfa状态数算法的思想是，在开始时，假设 是最完美的情况，整个dfa只有两个状态，一个终结状态， 一个开始，当然，这是假设，不是真的，所以这个算法， 就是在这个完美的假设
9、下，对假设进一步考察，如果发现 有些状态不能合并，那就分出来吧，这样重复考察，直到 发现没有状态会不能合并时，就做完了，此时不也正是最 优解么。嗯，就是这个，所以一开始，我们把所有非终结状 态用一个袋子包起来，看成是一个状态，把所有终结状态 也用另一袋子包起来，也看成是一个状态，注意，别把原 dfa中各状态间的连线给扯断了。然后，我们抽出其中一个 袋子，考察其中的各个状态，我们准备好所有的可能输入， 然后逐个拿出来测试，如果该袋子中的所有状态在某个输 入a下达到的状态正好都在这个袋子中，那就说明，这个 袋子中的这些状态“在目前看来”是可以合并的，也就是 说，如果在所有的可能输入的作用下，袋子中
10、的状态达到 的新状态正好也都是这个袋子中的状态，那它们就可以合 并。而如果，在某个输入a下，袋子中的一部分状态会转 移到同一袋子中的其它状态，而有几个叛徒，假设是s1和 s2，竟然在输入a下会迁移到其它袋子中的状态，那就说精品文档 2016全新精品资料-全新公文范文-全程指导写作 独家原创 6 / 7 明s1和s2是不可以和其它转移到同一袋子中的状态合并 的，于是，我们就把s1和s2装成一个新袋子，从原袋子 中分出来，当然，现在还是假设s1和s2可以合并，所以 才把它们装一起，究竟真的可不可以合并呆会还要再考察。 考察完输入a，还要接着考察其它的可能输入。如果在考察 完一个袋子后，发现所有状态
11、在a输入下都可以转移到本 袋子中的状态，那么最后的dfa它们就被合并成一个状态， 并且在a输入下，它有一个到自身的状态迁移。实现词法分析器对于一个token，比如用来表示数字的 token：num，我们可以用正则表达式描述它，然后画出 nfa，再将nfa转化成dfa，再最小化dfa的状态，但是我 们的词法分析器是不是分析一个token，所以我们要把所有 类型的token的dfa合并成一个dfa，这样，这个dfa也就 可以识别语言的所有token了，如果在某一连串的输入下， dfa达不到终结状态，那就说明源代码有错误了。我用c#实现了一个用于compiler construction: prin
12、ciples and practice中tiny语言的词法分析器， tiny语言有关键字：if, then, else, end, repeat, until, read, write，有操作符+，-，*，/，=， 上面 这张图和编译原理及实践中的一样，其中的带中括号 的输入说明这个输入是lookahead的，在匹配成功后是要精品文档 2016全新精品资料-全新公文范文-全程指导写作 独家原创 7 / 7 重新放回输入流中的，比如识别num时，如果发现个非 digit的，那就说明识别到了一个number，但是最后识别 的那个非digit字符是要放回输入流的，因为它要留着下 一次识别。其中从start到done的那个other，指所有非 white space，非，非letter，非digit，也非:的字符， 它有可能是合法的+, *, /这些，也可能是不合法的其它输 入，如#号。因此，done这个状态只是说本次gettoken已 经结束，状态机是有可能因为不合法的输入而进入done状 态的。究竟从start到done是因为合法的，如+号导致的， 还是由不合法的如#号导致的，将在代码中实现判断，但可 以肯定的是，不管是+号还是#号作用于start状态，都会 进入done状态。
