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