2

好吧，我正在尝试编写一个简单的解析器，给出以下内容：

d = {
    'a': [1,2,3,4],
    'b': [2,3,4,5],
    'c': [2,4,6,7]
}

以及以下两个功能：

def _and(l1, l2):
    return [i for i in l1 if i in l2]

def _or(l1, l2):
    return list(set(l1+l2))

我正在尝试接收一个字符串（例如"a||(b&c)"）并将其解析为以下内容：

_or(d['a'],_and(d['b'],d['c']))

我以前从未写过解析器，所以我有点迷茫。解析器应该支持OR,AND和括号。有人能指出我正确的方向吗？如果有人知道的话，Python 中的类似示例会很棒。

4

1 回答 1

2

我将概述您应该如何考虑解决此问题。

您需要将输入字符串拆分为标记并将这些标记的列表转换为语法树。在你的情况下，你应该有一些类似的东西：

  • a
  • ||
  • (b&c)
    • b
    • &
    • c

您可能需要对括号内的组件应用相同的解析技术b&c，以将其拆分为标记（如图所示）。因此，这个解析过程很可能是递归的，以便处理任意嵌套的括号。现有的工具可能会对此有所帮助，例如ANTLR。

从这里，您将希望根据运算符优先级创建语法树。在这种情况下，您的表达式可以用以下树来说明：

   或者
  / \
 一个   与
     / \
    b    c

然后，您可以递归地遍历这棵树，并根据其子节点执行每个节点的“操作”。显然，这说起来容易做起来难。我采用的一种方法是创建一个Node类，其实例用于形成树。每个都Node可以有一个evaluate返回其结果的方法。对于叶子a,b和c，结果很简单d['a'],d['b']和d['c']。对于OR和AND，结果基于您定义的函数_and和_or。

于 2013-07-29T14:40:42.947 回答