Добавление преднамеренной неоднозначности к анализатору / интерпретатору - PullRequest
Новая
       28

Добавление преднамеренной неоднозначности к анализатору / интерпретатору

1 голос
/ 01 апреля 2019

Я написал парсер, который правильно берет выражение и создает из него AST. Мой интерпретатор затем берет этот AST, оценивает его и затем возвращает решение. Однако я бы хотел, чтобы синтаксический анализатор (или интерпретатор) учитывал неоднозначность (отсутствие скобок) в выражении.

Например, если я напишу что-то вроде R ∩ G - B в качестве выражения, я бы хотел, чтобы AST возвращались как для (R ∩ G) - B, так и для R G (G - B). Я видел много решений для устранения двусмысленности при синтаксическом анализе выражения, но я хотел бы видеть все возможные интерпретации выражения.

Вот фрагмент из моего класса парсера: 

    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()

При моей текущей настройке парсер возвращает AST только для R ∩ (G - B).

Ответы [ 2 ]

1 голос
/ 03 апреля 2019

Существуют алгоритмы синтаксического анализа, которые для неоднозначной грамматики найдут все возможные способы анализа заданной строки: Earley, CYK, Tomita, GLR, GLL. Но они все довольно далеки от парсера рекурсивного спуска, который у вас есть сейчас. (GLL утверждает, что он похож на рекурсивный спуск, но это кажется немного натянутым.)

0 голосов
/ 03 апреля 2019

«Очевидный» способ сделать это - добавить дополнительные грамматические правила к языку, принимаемому вашим анализатором. Под этим я подразумеваю сначала записать грамматику, которую принимает ваш рекурсивный парсер; в настоящее время он принимает только на интерпретацию выражений. Добавить явное правило для других интерпретаций; это определяет неоднозначности.

Что-то вроде: 

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

Теперь "просто" настройте ваш парсер так, чтобы он принимал эти правила. Для этого вашему синтаксическому анализатору, вероятно, придется реализовать сохранение состояния синтаксического анализа, когда он встречает альтернативу, чтобы он мог восстановить («возврат») и попробовать альтернативные варианты. Это включает в себя точку входного потока в альтернативе. Вы можете сделать это путем буферизации входного текста и / или входных токенов.

Майкл Дейк перечислил множество механизмов / подходов для синтаксического анализа, которые делают это более регулярно, но все они исходят из предположения, что ваша грамматика явно включает неоднозначные альтернативы.

...