解析正則表達式時，詞法分析器和解析器之間的任務分離

我對於詞法分析器和解析器之間的任務分離有些困惑。解析正則表達式時，詞法分析器和解析器之間的任務分離

我正在嘗試編寫一個採用Perl風格正則表達式並構建語法樹的解析器。我的問題是識別量詞，如{n,m}，這意味着前面的組或字符或字符類應該至少出現n，但不會超過m次。

的要點是，一個不完整的/無效的量詞如{2,5asdf}是不量詞，而是一組的常規字符。

的問題是：給定輸入/a{2,5}/，應該詞法分析器返回托克斯（Tokes）如DELIMITER CHARACTER QUANTIFIER_START NUMBER COMMA NUMBER QUANTIFIER_END DELIMITER END的列表（問題是，該QUANTIFIER_START可能不是一個量詞的「真正」開始，這取決於以下），或是否應該嘗試匹配完整的量詞，並返回QUANTIFIER，這直觀地聽起來更像是解析器的任務？

來源

2013-04-12 Geier

在詞法分析器和解析器分開的情況下使用工具，在練習中通常沒有多少空間可以更改記號。詞法分析器通常獨立於解析器運行，並且如果可能的話，使得輕鬆的上下文敏感（如果可能的話，您可能希望Google爲PEG或無掃描器解析，在lexing和解析之間沒有真正的分離）。

但是，這一切都取決於您使用的工具。我已經創建了一個使用ANTLR的PCRE解析器，如果解析失敗，它使用回溯。因此，如果在解析{2,5a之後無法構造量詞（a無效），則解析器將回溯到"{"並從此char中創建一個LITERAL令牌，然後將繼續。以一點RAM爲代價，我啓用了memoization，導致解析器在大型輸入上仍然表現良好。

它解析X{2,5asdf}爲：

'- ALTERNATIVE 
    |- ELEMENT 
    | '- LITERAL='X' 
    |- ELEMENT 
    | '- LITERAL='{' 
    |- ELEMENT 
    | '- LITERAL='2' 
    |- ELEMENT 
    | '- LITERAL=',' 
    |- ELEMENT 
    | '- LITERAL='5' 
    |- ELEMENT 
    | '- LITERAL='a' 
    |- ELEMENT 
    | '- LITERAL='s' 
    |- ELEMENT 
    | '- LITERAL='d' 
    |- ELEMENT 
    | '- LITERAL='f' 
    '- ELEMENT 
     '- LITERAL='}'

和X{2,5}爲：

'- ALTERNATIVE 
    '- ELEMENT 
     |- LITERAL='X' 
     '- QUANTIFIER 
     |- NUMBER='2' 
     |- NUMBER='5' 
     '- GREEDY

你可以玩的解析器這裏：http://pcreparser.appspot.com/

的ANTLR語法可以在這裏找到：https://github.com/bkiers/PCREParser/blob/master/src/grammar/PCRE.g

來源

2013-04-12 12:55:05

解析正則表達式時，詞法分析器和解析器之間的任務分離

回答

相關問題