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

          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這個字符串,可以被識別為一個變量而不是一個關鍵字加數(shù)字。
          處理方法是保留最后一次自動機的終結狀態(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ā)選擇的路徑可能有多條,非確定性自動機總是需要進行“猜測”,而且總要做出正確的猜測。

          主站蜘蛛池模板: 南涧| 彰化县| 临西县| 荔波县| 岳阳市| 安陆市| 广河县| 平远县| 许昌市| 故城县| 衡山县| 博乐市| 安溪县| 龙南县| 彭山县| 米脂县| 竹北市| 库尔勒市| 广德县| 颍上县| 彭山县| 南城县| 桦南县| 西宁市| 喜德县| 沅江市| 兰溪市| 乌兰县| 云梦县| 馆陶县| 泸定县| 淳安县| 昭通市| 阜城县| 阳山县| 桐梓县| 昌平区| 木兰县| 晋宁县| 天峻县| 青河县|