向解析器/Interp添加有意的歧义

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声称是递归下降式的，但这似乎有点夸张。）