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に取り込むことができれば、あなたの考えを明確にするのに役立ちます。ここで

は、私が得たものです：

• 式は*」「必要に応じて、いくつかの繰り返しインジケータ（続く、s」は単一の文字または（）内の式で、それぞれが、作品の構成することができますまたは '？'の整数や{}の整数など）
• これらの要素は隣り合わせに実行することができます
• これらの要素は '|'代替

以上正式に少しを示すために：re_exprのみ開きカッコにマッチした後に再帰することができますので、このパーサには左再帰は、ありません

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

。 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 - "左再帰" をよく読んで、また、このreparsingの例を見てください。これは、reを候補文字列のリストに変換して返します。http://pyparsing.wikispaces.com/file/view/invRegex.py/111533811/invRegex.py