Как в древовидной грамматике неассоциативно сопоставить список значений без разделителей?

Question

Например, рассмотрим следующую грамматику:

      source_file: $ => $._expression,

_expression: $ => choice(
  $.identifier,
  $.operator
),

identifier: $ => /\w*[A-Za-z]\w*/,

operator: $ => seq(
  repeat1(seq($._expression, '\\X')),
  $._expression
)

Итак, если у меня есть строка ввода a \X b \X c \X d, Я хочу, чтобы он соответствовал как:

      (source_file
  (operator
    (identifier)
    (identifier)
    (identifier)
    (identifier)))

Однако единственный способ добиться такого поведения - это сделать следующее:

      operator: $ => choice(
  $._operator_2,
  $._operator_3,
  ...
),

_operator_2: $ => prec(1, seq(
  $._expression, '\\X', $._expression)
),

_operator_3: $ => prec(2, seq(
  $._expression, '\\X', $._expression, '\\X', $._expression)
),

...

Поэтому мне нужно жестко закодировать все длины выражений с приоритетом, увеличивающимся по мере увеличения длины, и я не могу понять, как написать всеобъемлющий _operator_nправило. Как мне этого добиться? Какая-то комбинация указания конфликта и присвоения динамического приоритета?

Answer 1

Я понимаю, что этот вопрос немного устарел на данный момент, но я наткнулся на него, когда сам учился, и это показалось интересным вызовом.

Судя по предоставленным ожидаемым результатам, цель выражения состоит в том, чтобы использовать все выражения, разделенные токенами. Грамматика неоднозначна, потому что она определяет само выражение как одно из выражений, которые могут быть использованы выражением. В результате синтаксический анализатор не может понять, как он должен группировать последовательность выражений.

Вы можете убедитьчтобы сгенерировать допустимый синтаксический анализатор, применяя приоритет и ассоциативность, но лучшее, что вы можете сделать с этим, — это заставить синтаксический анализатор разбить последовательность на ряд выражений, где каждое выражение имеет не более одной лексемы оператора. Правило является видимым узлом, поэтому вместо ожидаемого результата вы получите что-то вроде следующего (для правоассоциативного оператора):

      (source_file
  (operator
    (operator
      (operator
        (identifier)
        (identifier))
      (identifier))
    (identifier)))

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

Таким образом, кажется, что простейшим решением неоднозначности является разделение выражений на два типа: выражение и все остальные «неоператорные» выражения. Затем вы можете определитьвыражение, чтобы оно повторяло только выражения, не являющиеся операторами. В моем тестировании следующие правила грамматики дадут ожидаемый результат.

      source_file: $ => $._expression,

_expression: $ => choice(
  $.operator,
  $._non_operator_expression,
),

_non_operator_expression: $ => choice(
  $.identifier,
  // [maybe others]
),

operator: $ => seq(
  repeat1(seq($._non_operator_expression, '\\X')),
  $._non_operator_expression,
)

Answer 2

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

конфликты - массив массивов имён правил. Каждый внутренний массив представляет собой набор правил, участвующих в конфликте LR(1), который должен существовать в грамматике. Когда эти конфликты возникают во время выполнения, Tree-sitter будет использовать алгоритм GLR для изучения всех возможных интерпретаций. Если несколько синтаксических анализов завершились успешно, Tree-sitter выберет поддерево, соответствующее правило которого имеет наивысший общий динамический приоритет.

Рассмотрим следующую последовательность токенов:

      a \X b \X c

Ясно, что есть несколько возможных интерпретаций этой строки, например та, которую вы хотите:

      (source_file
  (operator
    (identifier a)
    (identifier b)
    (identifier c)
  )
)

или левоассоциативный:

      (source_file
  (operator
    (operator
      (identifier a)
      (identifier b)
    )
    (identifier c)
  )
)

или правоассоциативный:

      (source_file
  (operator
    (identifier a)
    (operator
      (identifier b)
      (identifier c)
    )
  )
)

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

Таким образом, при отсутствии дальнейшего направления tree-sitter правильно распознает это как локальный конфликт LR(1), что означает, что он не может определить, какая интерпретация верна, только с одним токеном просмотра вперед при чтении токена строки по токену. На самом деле это полная нелокальная двусмысленность, и поэтому, чтобы решить эту проблему, мы можем сказать tree-sitter переключиться с алгоритма синтаксического анализа LR на GLR, используя поле конфликтов:

      conflicts: $ => [
  [$.operator, $.operator]
]

Алгоритм GLR недетерминированно отслеживает все возможные интерпретации синтаксического анализа, а затем (как указано в документации по конфликтам выше) использует интерпретацию с наивысшим общим динамическим приоритетом . Итак, все, что нам нужно сделать, это умно использовать аннотация, позволяющая сидящему на дереве распознать желаемую интерпретацию, имеет наивысший балл! Как мы это делаем?

Это довольно сложно, но, глядя на приведенную выше интерпретацию, мы видим, что хотим минимизировать количество правил операторов в синтаксическом анализе. Итак, мы можем добавить штраф (отрицательное число) к динамическому приоритету оператора!

      operator: $ => prec.dynamic(-1, seq(
  repeat1(seq($._expression, '\\X')),
  $._expression
))

Оно работает! К сожалению, с этим решением мы открыли ящик Пандоры: добавление любых дополнительных инфиксных операторов к языку становится очень сложным, потому что вы должны обрабатывать как их статический приоритет друг относительно друга, так и их динамический приоритет в сочетании с этим оператором. Возможно, было бы проще просто указать оператор как стандартный левоассоциативный оператор с высоким приоритетом для синтаксического анализа, а затем обработать это выравнивание на семантическом уровне.