Разбор правоассоциативного оператора (показатели степени) - PullRequest
Новая
       24

Разбор правоассоциативного оператора (показатели степени)

0 голосов
/ 31 августа 2018

Я пишу лексер / парсер / интерпретатор для моего собственного языка и до сих пор все работало. Я следовал за примерами в блоге Руслана Спивака ( Github ссылка на каждую статью).

Я хотел расширить мою языковую грамматику до того, что написано в статьях, чтобы включить больше операторов, таких как сравнения (<, >= и т. Д.), А также экспоненты (** или ^ в моем языке) , У меня есть эта грамматика: 

expression        : exponent ((ADD | SUB) exponent)*
exponent          : term ((POWER) term)*
# this one is right-associative (powers **)

term              : comparison ((MUL | DIV) comparison)*
comparison        : factor ((EQUAl   | L_EQUAL | LESS
                             N_EQUAL | G_EQUAL | GREATER) factor)*
# these are all binary operations



factor            : NUM | STR        | variable
                        | ADD factor | SUB factor
                        | LPAREN expr RPAREN
# different types of 'base' types like integers
# also contains parenthesised expressions which are evalutaed first

Что касается разбора токенов, я использую тот же метод, что и в блоге Руслана. Вот тот, который будет анализировать строку exponent, которая обрабатывает сложение и вычитание, несмотря на ее имя, поскольку грамматика говорит, что выражения анализируются как exponent_expr (+ / -) exponent_expr

def exponent(self):
    node = self.term()
    while self.current_token.type in (ADD, SUB):
        token = self.current_token

        if token.type == ADD:
            self.consume_token(ADD)
        elif token.type == SUB:
            self.consume_token(SUB)

        node = BinaryOperation(left_node=node,
                               operator=token,
                               right_node=self.term())

    return node

Теперь это очень хорошо разбирает левоассоциативные токены (поскольку поток токенов естественным образом идет слева направо), но я застрял в том, как анализировать экспоненциально правые показатели. Посмотрите на этот ожидаемый вход / выход для справки: 

>>> 2 ** 3 ** 2
# should be parsed as...
>>> 2 ** (3 ** 2)
# which is...
>>> 2 ** 9
# which returns...
512

# Mine, at the moment, parses it as...
>>> (2 ** 3) ** 2
# which is...
>>> 8 ** 2
# which returns...
64

Чтобы решить эту проблему, я попытался переключить левый и правый узлы BinaryOperation() конструктора, чтобы сделать текущий узел правым, а новый - левым, но это просто делает 2**5 синтаксическим анализом как 5**2, что дает мне 25 вместо ожидаемого 32.

Какие-нибудь подходы, которые я мог бы попробовать?

1 Ответ

0 голосов
/ 31 августа 2018

Тот факт, что ваша exponent функция фактически анализирует expression s, должен был быть красным флагом. На самом деле вам нужна функция expression, которая анализирует выражения, и функция exponent, которая анализирует возведения в степень.

Вы также перепутали приоритеты возведения в степень и умножения (и других операций), потому что 2 * x ** 4 не означает (2 * x) ** 4 (что будет 16x⁴), а скорее 2 * (x ** 4). Точно так же, x * 3 < 17 не означает x * (3 < 17), именно так ваша грамматика будет анализировать его.

Обычно приоритеты для арифметики выглядят примерно так: 

 comparison     <, <=, ==, ... ( lowest precedence)
 additive       +, -
 multiplicative *, /, %
 unary          +, -
 exponentiation **
 atoms          numbers, variables, parenthesized expressions, etc.

(Если бы у вас были постфиксные операторы, такие как вызовы функций, они находились бы между возведением в степень и атомами.)

Как только вы переработаете свою грамматику в этой форме, анализатор экспонент будет выглядеть примерно так: 

def exponent(self):
    node = self.term()
    while self.current_token.type is POWER:
        self.consume_token(ADD)
        node = BinaryOperation(left_node=node,
                               operator=token,
                               right_node=self.exponent())
    return node

Рекурсивный вызов в конце производит правильную ассоциативность. В этом случае рекурсия допустима, поскольку левый операнд и оператор уже заняты. Таким образом, рекурсивный вызов не может создать бесконечный цикл.

...