python - 构建 Python 列表比较逻辑解析器

Question

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

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 示例，那就太好了。

Answer 1

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

您需要将输入字符串拆分为标记，并将这些标记的列表转换为 syntax tree .在您的情况下，您应该具有以下内容:

• 一个
• ||
• (b&c)
  • b
  • &
  • c

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

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

   OR  /  \ a   AND     / \    b   c

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