Добавление правила к грамматору Treesitter LR1 изменяет приоритет

Question

Я пытаюсь установить правильный приоритет операторов в грамматике Treesitter. Treesitter - это генератор парсера LR1.

У меня простая художественная грамматика, которая частично выглядит так:

              multiply_expression: $ => prec.left(2, seq(
            $._expression,
            '*',
            $._expression,
        )),

        addition_expression: $ => prec.left(1, seq(
            $._expression,
            '+',
            $._expression,
        )),

Это работает правильно. действительно получает более высокий приоритет, чем.

Однако приоритет меняется, когда я добавляю промежуточное правило:

              _partial_multi: $ => seq(
            $._expression,
            '*',
        ),

        multiply_expression: $ => prec.left(2, seq(
            $._partial_multi,
            $._expression,
        )),

я переехал $.expression, '*'к своему собственному правилу. На мой взгляд, это эквивалентный грамматик, и я не ожидаю никаких изменений. Однако с этим изменением приоритет больше не является правильным. addition_expression, который остался неизменным, кажется, имеет более высокий приоритет, чем multiply_expression.

Почему добавление дополнительного шага меняет приоритет? Есть ли название для этой проблемы или где я могу найти дополнительную информацию? Есть ли правила, которым нужно следовать, или способы думать об этом при написании грамматики или решении проблем с приоритетом?

Answer 1

Вот ваша полная грамматика для воспроизводимости:

      module.exports = grammar({
  name: 'github_example',

  conflicts: $ => [],

  rules: {
    source_file: $ => $._expression,

    _expression: $ => choice(
      $.number,
      $.multiply_expression,
      $.addition_expression
    ),

    number: $ => /\d+/,

    _partial_multi: $ => seq(
        $._expression,
        '*',
    ),

    multiply_expression: $ => prec.left(2, seq(
        $._partial_multi,
        $._expression,
    )),

    addition_expression: $ => prec.left(1, seq(
        $._expression,
        '+',
        $._expression,
    )),
  }
});

Вы можете решить эту проблему, добавив приоритет к _partial_multi правило и удаление левоассоциативного приоритета из multiply_expression правило:

         _partial_multi: $ => prec(2, seq(
        $._expression,
        '*',
    )),

    multiply_expression: $ => seq(
        $._partial_multi,
        $._expression,
    ),

Что вы сделали здесь, так это сделали умножение правоассоциативным оператором приоритета 2. Именно так вы определяете левую или правую ассоциативность в грамматиках, которые не раскрывают его как примитив. Вы можете сделать умножение левоассоциативным, записав его следующим образом:

          _partial_multi: $ => prec(2, seq(
        '*',
        $._expression,
    )),

    multiply_expression: $ => seq(
        $._expression,
        $._partial_multi,
    ),

На самом деле вы наткнулись на кое-что весьма интересное, а именно на то, что вам не нужны явные языковые конструкции для определения приоритета и ассоциативности в грамматике! Они просто «синтаксический сахар», облегчающий чтение и запись грамматики. См. Эту страницу для получения дополнительной информации о том, как указать приоритет и ассоциативность путем декомпозиции правил. Вы можете видеть, что указание приоритета и ассоциативности исключительно с помощью грамматических конструкций сбивает с толку и почти означает обратное чтение того, чего вы ожидаете, если вы не думаете об этом! Как вы также обнаружили, смешение этих двух подходов (указание приоритета и ассоциативности с помощью языковых конструкций и грамматических конструкций) может привести к путанице. Лучше придерживаться одного или другого.