2016-10-04 156 views
1

我正在尝试使用pyparsing编写简化的正则表达式解析器(除了串联之外,还支持*|运算符)。下面是我的语法迄今:使用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语法。

回答

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