使用pyparsing解析正則表達式

Question

我正在嘗試使用pyparsing編寫簡化的正則表達式解析器（除了串聯之外，還支持*和|運算符）。下面是我的語法迄今：

from pyparsing import alphas, Word, Forward 

regular_expression = Forward() 

character = Word(alphas, max=1) 
group  = '(' + regular_expression + ')' 
star  = (character | group) + '*' 

# A 'concat_expression' is any string concat of the above 
# String concat with a 'concat_expression' also produces a 'concat_expression' 
concat_expression = Forward() 
concat_expression << ((character | group | star | concat_expression) + 
         (character | group | star)) 

or_expression = regular_expression + '|' + regular_expression 

regular_expression << or_expression | concat_expression 

我得到無限遞歸當我嘗試解析簡單的表達式（如regular_expression.parseString("a")）。我的連接定義有什麼問題嗎？

僅供參考，我在嘗試改編this語法。

Answer 1

您現在正在查看的問題（無限遞歸）是由於語法中的左遞歸。 pyparsing純粹是從左到右的解析，沒有前瞻（除非你在語法中明確地做）。所以你如果定義一個列表如下：

expr ::= expr | expr 

然後它會只是螺旋下來的污垢。

我認爲其中的一部分是，你的解析器是種類繁多，有很多冗餘的遞歸術語。如果你可以停下來思考你正在解析的內容的定義，甚至可以將它捕獲到一些簡化的BNF中，它應該有助於澄清你的想法。

這是我得到：

• 的表達可以由塊，其中的每一個是一個單獨的字符或表達內（）的，任選接着進行一些重複指示符（'*」或'？'或和{}中的整數等）
• 這些片段可以一起運行
• 這些片段可以用'|'分隔。指示替代

還是有點更正式：

re_item  ::= (character | '(' re_expr ')') [repetition] 
re_item_seq ::= re_item+ 
repetition ::= '*' | '?' 
re_expr  ::= re_item_seq [ '|' re_item_seq ]... 

沒有左遞歸在此解析器，因爲re_expr只能匹配左括號後遞歸進入。

翻譯成pyparsing幾乎是逐字：

from pyparsing import (alphas, Word, Forward, oneOf, OneOrMore, Optional, 
    delimitedList, Group) 

character = Word(alphas, exact=1).setName("character") # <- use 'exact', not 'max' 

regular_expression = Forward() 
group  = Group('(' + regular_expression + ')') 
repetition = oneOf("* ?") 

re_item = Group((character | group) + repetition) | character | group 
re_item_seq = OneOrMore(re_item) 

regular_expression <<= delimitedList(re_item_seq, '|') 

測試了這一點：

regular_expression.runTests(""" 
    a 
    a? 
    sdlfj*(b|c)? 
    """) 

給出：

a 
['a'] 


a? 
[['a', '?']] 
[0]: 
    ['a', '?'] 


sdlfj*(b|c)? 
['s', 'd', 'l', 'f', ['j', '*'], [['(', 'b', 'c', ')'], '?']] 
[0]: 
    s 
[1]: 
    d 
[2]: 
    l 
[3]: 
    f 
[4]: 
    ['j', '*'] 
[5]: 
    [['(', 'b', 'c', ')'], '?'] 
    [0]: 
    ['(', 'b', 'c', ')'] 
    [1]: 
    ? 

TL; DR - 對 「左遞歸」 讀了起來，你也可以訪問這個重新解析的例子（它將re反轉成re可匹配的候選字符串列表）：http://pyparsing.wikispaces.com/file/view/invRegex.py/111533811/invRegex.py