1

割り当ての一部として (はい、私はそれを言いました。結果として、import reテストすることさえ許可されていません)、特定の正規表現形式をツリーに解析する方法を実装しましたr。

  • r.symbolはノードのタイプです
    ( e= ε、0または1= ターミナル、.= シーケンス、|および*明らかです)
  • r.children(0, 1, 2)子ノードのリストです。

この形式で一致できる唯一の文字は0で1あるため、それらは可能な唯一の端末でもあります。

def match(r, s):
    """
    Return True iff the list of characters `s' matches the
    regular expression stored in `r'.
    """
    if r.symbol == 'e':
        return True
    elif r.symbol in '01':
        return r.symbol == s.pop(0) if len(s) > 0 else False
    elif r.symbol == '.':
        return match(r.children[0], s) and match(r.children[1], s)
    elif r.symbol == '|':
        sl, sr = s.copy(), s.copy()
        kl, kr = match(r.children[0], sl), match(r.children[1], sr)
        if kl or kr:
            s = (sl if kl else sr) if kl != kr else \
                (sl if len(sl) < len(sr) else sr)
            return True
        return False
    elif r.symbol == '*':
        while match(r.children[0], s):
            pass
        return True

私の実装は、文字のリストを取得し、正規表現に一致する場合は左側から文字を 1 つずつポップすることで機能します。これまでのところ、ほとんどのテスト ケースに一致しましたが、失敗する特定の種類の正規表現があります。私はまだ終わっていないことを知っているので、ここに私の質問があります：

  1. *Kleene スターを正しく実装できないようです。whileループを実行することがこれを行うための最良の方法であるようには見えません。
  2. |代替演算子は実際にどのように機能しますか? 私は現在、両方が一致する場合、より長い一致を返すように実装しています。
4

2 に答える 2

0

基本的な操作だけでかなり簡単に実行できるはずなので、有限状態マシンをお勧めします。

基本的な正規表現操作を NFA として実装する方法を示す記事を次に示します。

正規表現

于 2013-10-23T10:07:45.103 に答える