向分析器/解释器添加故意歧义

Question

我编写了一个解析器，它正确地获取了一个表达式并从中创建了一个AST。然后我的解释器接受AST，对其进行评估，然后返回一个解决方案。但是，我希望解析器（或解释器）能够解释表达式中的歧义（缺少括号）。

例如，如果我写一个像R∩G - B这样的表达式，我希望看到两个（R∩G） - B和R∩（G - B）的ASTs返回。我在解析表达式时看到了许多消除歧义的解决方案，但我希望能够看到表达式的所有可能解释。

这是我的解析器类的片段：

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

Answer 2

“明显”的方法是在解析器接受的语言中添加额外的语法规则。我的意思是，首先写下你的递归解析器接受的语法;目前它只接受对表达的解释。为其他解释添加明确的规则;这定义了歧义。

就像是：

set_expression = intersection | set_expression '-' intersection;
intersection = term  |  intersection '∩'  intersection_term ;
term = primitive_set | term '∩' primitive_set ;

现在“只是”调整你的解析器以接受这些规则。要做到这一点，你的解析器可能必须实现在遇到替代方案时保存解析状态，以便它可以恢复（“回溯”）并尝试替代方案。这包括替代输入流的点。您可以通过缓冲输入文本和/或输入标记来完成此操作。

Michael Dyck列出了各种解析引擎/方法，这些引擎/方法以更常规的方式执行此操作，但它们都假设您的语法明确包含模糊的替代方法。