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

2024-03-29 00:02:32 发布

您现在位置:Python中文网/ 问答频道 /正文

我已经编写了一个解析器,它正确地接受一个表达式并从中创建一个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。你知道吗


Tags: selftokennode解析器returnif表达式def
2条回答

有一些解析算法,对于一个模棱两可的语法,可以找到所有可能的方法来解析一个给定的字符串:Earley、CYK、Tomita、GLR、GLL。但它们都离现在的递归下降解析器很远。(GLL声称是递归下降式的,但这似乎有点夸张。)

实现这一点的“明显”方法是向解析器接受的语言添加额外的语法规则。我的意思是,首先写下递归解析器接受的语法;目前它只接受表达式的解释。为其他解释添加明确的规则;这定义了歧义。你知道吗

比如:

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

现在“只是”调整解析器以接受这些规则。要做到这一点,您的解析器可能必须在遇到其他方法时实现对解析状态的保存,以便它可以恢复(“回溯”)并尝试其他方法。这包括输入流在备选位置的点。可以通过缓冲输入文本和/或输入标记来实现这一点。你知道吗

michaeldyck列出了各种各样的解析引擎/方法,它们以一种更为常规的方式来实现这一点,但是它们都是从假设语法显式地包含歧义替代项开始的。你知道吗

相关问题 更多 >