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. 我似乎无法*正确实现 Kleene 星。看起来while循环并不是最好的方法。
  2. |替代运算符实际上是如何工作的？我目前已经实现了它，如果两者都匹配，那么它会返回更长的匹配。
4

2 回答 2

0

我建议使用有限状态机，因为它应该很容易通过基本操作来完成。

这是一篇文章，展示了如何将基本的正则表达式操作实现为 NFA：

常用表达

于 2013-10-23T10:07:45.103 回答
0

当然可以直接这样做，但是很难争论正确性。常见的方法是首先将正则表达式转换为有限状态机（以您喜欢的任何表示形式），然后在该有限状态机上模拟输入。

于 2013-10-23T04:12:23.910 回答