python - 故意为解析器/解释器添加歧义

Question

我编写了一个解析器，它正确地接受一个表达式并从中创建一个 AST。然后我的解释器接受那个 AST，对其求值，然后返回一个解决方案。但是，我希望解析器(或解释器)能够解释表达式中的歧义(缺少括号)。

例如，如果我将类似 R ∩ G - B 的内容写为表达式，我希望看到返回 (R ∩ G) - B 和 R ∩ (G - B) 的 AST。我见过许多在解析表达式时消除歧义的解决方案，但我希望能够看到表达式的所有可能解释。

这是我的解析器类的一个片段:

    def eat(self, token_type):
        if self.current_token.type == token_type:
            self.current_token = self.lexer.get_next_token()
        else:
            self.error()

    def factor(self):
        token = self.current_token

        if token.type in (COLOR, EMPTY_S, UNIVERSE_OP):
            self.eat(token.type)
            return Num(token)
        elif token.type == L_PAREN:
            self.eat(L_PAREN)
            node = self.expr()
            self.eat(R_PAREN)
            return node

    def term(self):
        node = self.factor()

        while self.current_token.type is COMPLIMENT:
            token = self.current_token
            self.eat(COMPLIMENT)

            node = BinOp(left = node, op = token, right = self.expr())

        return node

    def expr(self):
        node = self.term()

        while self.current_token.type in (UNION, INTERSECT, MINUS, SUBSET, EQUALS):
            token = self.current_token

            if token.type == UNION:
                self.eat(UNION)
            elif token.type == INTERSECT:
                self.eat(INTERSECT)
            elif token.type == MINUS:
                self.eat(MINUS)
            elif token.type == SUBSET:
                self.eat(SUBSET)
            elif token.type == EQUALS:
                self.eat(EQUALS)

            else:
                self.error()

            node = BinOp(left = node, op = token, right = self.expr())

        return node

    def parse(self):
        return self.expr()

在我当前的设置下，解析器只会为 R ∩ (G - B) 返回一个 AST。

Answer 1

对于有歧义的语法，有一些解析算法会找到所有可能的方法来解析给定的字符串:Earley、CYK、Tomita、GLR、GLL。但是它们与您现在拥有的递归下降解析器相去甚远。 (GLL 声称类似于递归下降，但这似乎有点牵强。)