0

我目前正在尝试使用 Python SLY 模块为命题逻辑构建解析器。SLY 是 lex 和 yacc 的 Python 实现。

https://sly.readthedocs.io/en/latest/sly.html#introduction

文档说，“SLY 没有提供用于构造抽象语法树的特殊函数。但是，这种构造很容易自己完成。” 这就是我想要做的。在他们的示例代码中，他们建议通过为树节点定义自己的数据结构并在语法规则中使用它来执行此操作。

class BinOp(Expr):
    def __init__(self, op, left, right)
        self.op = op
        self.left = left
        self.right = right

class Number(Expr):
    def __init__(self, value):
        self.value = value

@_('expr PLUS expr',
   'expr MINUS expr',
   'expr TIMES expr',
   'expr DIVIDE expr')
def expr(self, p):
    return BinOp(p[1], p.expr0, p.expr1)

@_('LPAREN expr RPAREN')
def expr(self, p):
    return p.expr

我的问题是，对于我解析命题逻辑的应用程序，虽然这种解析方式可以正确检查语法并表示解析的逻辑表达式的含义，但解析器会将 AST 构造为二叉树。因此，如果我让它解析以下两个表达式：

  1. pvqvr
  2. pv(qvr)

生成的 AST 看起来是一样的（具有正确的关联性）。

对于我项目的不同部分，将合取和析取运算视为 n 元而不是二进制对我来说很重要。以上面的第一个表达式为例，析取运算同时应用于三个操作数 p、q 和 r。我需要能够通过查看 AST 本身来区分上面的两个示例表达式。下图显示了我要追求的差异

            v                  v
         /  |  \              / \
         p  q  r             p   v
                                / \
                                q r

从理论上讲，LR 解析是否可以创建具有两个以上子节点的 AST？如果是这样，SLY 框架是否足够强大，让我能够做到这一点，还是我需要创建自己的解析器？如果 LR 解析无法创建这样的树，我应该考虑其他算法吗？创建树后我没有做任何进一步的编译，我只需要形成表示命题逻辑表达式的树，如上所示。

如果这是一个愚蠢的问题，请提前道歉，我刚刚在 2020 年春季学期学习了编程语言和翻译，并且随着世界上正在发生的一切，学习体验相当混乱。我将不胜感激任何建议。非常感谢！

4

1 回答 1

3

当然你可以做到。毕竟，它只是在玩弄数据结构。但是，在解析时覆盖所有情况是很棘手的（尽管当然不是不可能），因此在解析完成后转换树可能更容易（也更有效）。

关键问题是，当您解析时expr OR expr，可能有一个或两个expr非终端已经是OR节点，需要合并其列表。所以你可能会从这样的事情开始：

class BinOp(Expr):
    def __init__(self, op, left, right)
        if left.op == op:
             left_ops = left.operands
        else:
             left_ops = (left,)
        if right.op == op:
             right_ops = right.operands
        else:
             right_ops = (right,)
        self.op = op
        self.operands = left_ops + right_ops

@_('expr OR expr',
   'expr AND expr')
def expr(self, p):
    return BinOp(p[1], p.expr0, p.expr1)

那可行。但这是我的怀疑（因为它发生在我身上，一遍又一遍地有不同的变化）：在某些时候你会想要应用德摩根定律（也许不是一致的，但在某些情况下），所以你最终会转向一些否定连词节点变成析取和/或连词中的否定析取节点。在你这样做之后，你会想要再次压缩新的析取（或合取节点），因为否则你新创建的节点可能会违反合取/析取运算符的操作数不能是合取/析取（分别）的约束。当你爬过应用 deMorgan 的树时，你最终可能会进行各种翻转，这需要更多的压缩通道......

所以我的预感是，如果您首先解析（通常会自然生成二叉树）然后以适当的顺序进行各种转换，您会发现自己的重复代码更少，控制流程更清晰。

尽管如此，肯定有语法自然产生多价节点而不是二元节点。经典的是参数列表，但任何列表结构都会产生相同的效果。不过，这里的列表（可能）不是展平括号子表达式的结果。它只是响应一个语法，例如：

    @_('expr')
    def exprlist(self, p):
        return [p.expr]

    @_('exprlist "," expr')
    def exprlist(self, p):
        p.exprlist.append(p.expr)
        return p.exprlist

    @_('ID "(" exprlist ")" ')
    def expr(self, p):
        return ('call', p.ID, p.exprlist)
        # Or, if you want a truly multivalent node:
        # return ('call', p.ID) + tuple(p.exprlist)

如果你给它 EBNF 产品，SLY 可以自动做那种事情，所以这可能只是有点有趣。

于 2020-07-19T20:36:01.257 回答