python - 再帰を使用して Python で単純な正規表現言語を実装する

Question

説明はできるだけ簡単にしようと思います。

0のみの正規表現の解決策を提供するように求められました。1 は、0\*何も一致しないか、または0のみの文字列と一致します。

3 つの演算子があります., \*,|

• .r1とr1の2 つの正規表現を組み合わせ、r1は s1 に一致し、r2はs1に一致しますs2, s = s1 + s2

• |または、r1 と r2 を結合すると、r1 が s1 に一致するか、r2 が s2 に一致します。(r1|r2) matches s = s1 + s2

• \*単なるスターケースであり、ロジックはありません。

すべての演算子と 0 と 1 はバイナリ ツリーに格納されます。

完全なリファレンス: http://www.cdf.toronto.edu/~heap/148/F13/Assignments/A2/a2.pdf

私は再帰的な解決策を見つけようとしています。

((1.(0|1)\*).0)例として(任意の文字列が1で始まり0で終わる) マッチを取る100101010:

.右側の は正規表現ツリーのルートで、その左の子と1.(0|1)\*右の子 0 は再帰的に solve match('1.(0|1)\*', 10010101)、右の子0は再帰的に solvematch('0', 0)です。

正しい子の場合は true を返し、

左の部分は再帰的なステップを続けます。

何かのようなもの

def match(rx, s):
    if rx == s:
         // base case when s is 0 or 1
         return True
    else:
         return False
    x = 'some number'
    s1 = s[:x]
    s2 = s[x:]
    if rx.operator == '.':
       return match(rx.left, s1) and match(rx.right, s2)
    elif rx.operator == '|':
       return match(rx.left, s1) or match(rx.right, s2)
    else:
       return solveStar(rx, s)

私は今行き詰まっている2つの部分、最初にサブ正規表現に一致するように文字列を分割する方法、2番目にスター*ケースの解決に混乱しています