posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          Lexical Analysis - Finite Automata

          Posted on 2007-09-06 22:09 ZelluX 閱讀(412) 評論(0)  編輯  收藏 所屬分類: Courses

          DFA(deterministic finite automaton): 從同一狀態(tài)出發(fā)的邊都標記有不同的符號

          可以把一個DFA用一個轉置矩陣(transition matrix)表示,矩陣的第i行記錄狀態(tài)i向其他狀態(tài)跳轉的情況,edges[i][j]表示狀態(tài)i時吃掉一個j符號后跳轉到edges[i][j]狀態(tài)。

          DFA的一個好處就是可以識別最長的匹配,比如對于IF8這個字符串,可以被識別為一個變量而不是一個關鍵字加數字。
          處理方法是保留最后一次自動機的終結狀態(tài)Last-Final及其相對應的字符位置Input-Position-at-Last-Final。
          每次進入一個終結狀態(tài),就更新這兩個變量。
          遇到死路(dead state, a nonfinal state with no output transitions),通過這兩個變量回復到上一個終結狀態(tài)。

          NFA(nondeterministic finite automaton): 從同一狀態(tài)出發(fā)的邊可能標記有相同的符號
          由于從同一狀態(tài)出發(fā)選擇的路徑可能有多條,非確定性自動機總是需要進行“猜測”,而且總要做出正確的猜測。

          主站蜘蛛池模板: 新密市| 博白县| 湘潭县| 手游| 彩票| 抚远县| 金乡县| 胶南市| 古浪县| 界首市| 云阳县| 馆陶县| 和顺县| 柳河县| 颍上县| 金华市| 什邡市| 恩平市| 金门县| 广饶县| 闽侯县| 晋江市| 隆尧县| 社会| 平武县| 崇仁县| 观塘区| 金沙县| 新昌县| 年辖:市辖区| 东城区| 建宁县| 武功县| 新乐市| 淮滨县| 米脂县| 乌兰浩特市| 海南省| 澄江县| 射洪县| 卢龙县|