Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Lexical Analysis - Finite Automata

Posted on 2007-09-06 22:09 ZelluX 阅读(291) 评论(0)  编辑  收藏 所属分类: Courses

DFA(deterministic finite automaton): 从同一状态出发的边都标记有不同的符号

可以把一个DFA用一个转置矩阵(transition matrix)表示,矩阵的第i行记录状态i向其他状态跳转的情况,edges[i][j]表示状态i时吃掉一个j符号后跳转到edges[i][j]状态。

DFA的一个好处就是可以识别最长的匹配,比如对于IF8这个字符串,可以被识别为一个变量而不是一个关键字加数字。
处理方法是保留最后一次自动机的终结状态Last-Final及其相对应的字符位置Input-Position-at-Last-Final。
每次进入一个终结状态,就更新这两个变量。
遇到死路(dead state, a nonfinal state with no output transitions),通过这两个变量回复到上一个终结状态。

NFA(nondeterministic finite automaton): 从同一状态出发的边可能标记有相同的符号
由于从同一状态出发选择的路径可能有多条,非确定性自动机总是需要进行“猜测”,而且总要做出正确的猜测。


只有注册用户登录后才能发表评论。


网站导航: