鑑於我已經實現了一個基本的正則表達式匹配器，我該如何實現一個詞法分析器？

Question

我試圖實現一個詞法分析器的樂趣。我已經實現了一個基本的正則表達式匹配器（首先將模式轉換爲NFA，然後轉換爲DFA）。現在我對如何着手毫無頭緒。

我的詞法分析器將採取標記列表及其相應的正則表達式。用來創建詞法分析器的通用算法是什麼？

我想過（或）所有的正則表達式，但我不能確定哪個特定的標記匹配。即使我擴展了我的正則表達式模塊以返回匹配成功時匹配的模式，我如何在匹配器中實現lookahead？

Answer 1

假設你有一個工作正則表達式，regex_match它返回一個布爾值（如果字符串滿足正則表達式，則爲真）。首先，你需要有一個有序的令牌列表（每個有正則表達式）tokens_regex，這個命令很重要，因爲命令將會規定優先級。

一種算法可以是（這並不一定是隻有一個）：

1. 寫過程next_token它接受一個字符串，並返回所述第一令牌，它的值和剩餘的字符串（或 - 如果是非法/忽略字符 - 無，違規字符和剩餘字符串）。 注意：這必須尊重優先權，並且應該找到最長的標記。
2. 編寫一個程序lex遞歸調用next_token。

。

像這樣的東西（用Python編寫的）：

tokens_regex = [ (TOKEN_NAME, TOKEN_REGEX),...] #order describes precedence 

def next_token(remaining_string): 
    for t_name, t_regex in tokens_regex: # check over in order of precedence 
     for i in xrange(len(remaining_string), 0, -1): #check longest possibilities first (there may be a more efficient method). 
      if regex_match(remaining_string[:i], t_regex): 
       return t_name, remaining_string[:i], remaining_string[i:] 
    return None, remaining_string[0], remaining_string[1:] #either an ignore or illegal character 

def lex(string): 
    tokens_so_far = [] 
    remaining_string = string 
    while len(remaining_string) > 0: 
     t_name, t_value, string_remaining = next_token(remaining_string) 
     if t_name is not None: 
      tokens_so_far.append(t_name, t_value) 
     #elif not regex_match(t_value,ignore_regex): 
      #check against ignore regex, if not in it add to an error list/illegal characters 
    return tokens_so_far 

有些東西添加到您的提高詞法分析器：忽略正則表達式，錯誤列表和位置/行號（這些錯誤或令牌）。

玩得開心！祝你好運，解析器:)。

Answer 2

我已經做了幾乎相同的事情。我這樣做的方式是將所有表達式合併到一個非常大的NFA中，並將同一個事件轉換爲一個DFA。這樣做時，可以跟蹤以前在每個對應的原始DFA中接受狀態的狀態及其優先級。

生成的DFA將具有許多正在接受狀態的狀態。您運行此DFA，直到它收到一個沒有相應轉換的字符。如果DFA處於接受狀態，那麼您將查看您的哪個原始NFA具有該接受狀態。具有最高優先級的那個是您要返回的令牌。

這不處理正則表達式lookaheads。無論如何，這些通常不是真正需要詞法分析器的工作。這將是解析器的工作。

這樣的詞法分析器的運行速度與單個正則表達式的速度大致相同，因爲基本上只有一個DFA可以運行。您可以省略完全轉換NFA以獲得更快速的構造算法，但運行速度更慢。該算法基本相同。

我寫的詞法分析器的源代碼是github上的freely available，如果你想看看我是怎麼做到的。