Как определить переменные Паскаля в PetitParser

Question

Вот (упрощенный) раздел EBNF, который я пытаюсь реализовать в PetitParser:

variable :: component / identifier
component :: indexed / field
indexed :: variable , $[ , blah , $]
field :: variable , $. , identifier

Что я сделал, чтобы добавить все эти произведения (кроме identifier) как ивары моего подкласса PPCompositeParser и определите соответствующие методы следующим образом:

variable
  ^component / self identifier

component
  ^indexed / field

identifier
  ^(#letter asParser, (#word asParser) star) flatten

indexed
  ^variable , $[ asParser, #digit asParser, $] asParser

field
  ^variable , $. asParser, self identifier

start
  ^variable

Наконец, я создал новый экземпляр моего парсера и отправил ему сообщение parse: 'a.b[0]',

Проблема: я получаю переполнение стека.

Answer 1

Проблема в том, что ваша грамматика остается рекурсивной. PetitParser использует жадный алгоритм сверху вниз для разбора входной строки. Если вы выполните шаги, вы увидите, что это идет от start затем variable -> component -> indexed -> variable, Это становится циклом, который выполняется бесконечно, не потребляя никакого ввода, и является причиной переполнения стека (это практическая левая рекурсивность).

Хитрость для разрешения ситуации - переписать синтаксический анализатор, добавив промежуточные шаги, чтобы избежать повторения влево. Основная идея заключается в том, что переписанная версия будет использовать как минимум один символ в каждом цикле. Давайте начнем с того, что немного упростим анализатор, рефакторинг нерекурсивных частей "indexed" и "field" и перенесем их на дно.

variable
  ^component, self identifier

component
  ^indexed / field

indexed
  ^variable, subscript

field
  ^variable, fieldName

start
  ^variable


subscript
    ^$[ asParser, #digit asParser, $] asParser

fieldName
    ^$. asParser, self identifier

identifier
  ^(#letter asParser, (#word asParser) star) flatten

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

variable
    ^self identifier, variable'

теперь variable' на самом деле относится к чему-то с использованным идентификатором, и мы можем безопасно переместить отрывок слева от indexed а также field справа в variable':

variable'
    component', variable' / nil asParser

component'
    ^indexed' / field'

indexed'
    ^subscript

field'
    ^fieldName

Я написал этот ответ без проверки кода, но все должно быть в порядке. Парсер может быть еще более упрощен, я оставлю это в качестве упражнения;).

Для получения дополнительной информации об устранении левой рекурсии вы можете посмотреть на устранение левой рекурсии

Answer 2

Грамматика имеет левую рекурсию: variable -> component -> indexed -> variable, PetitParser использует грамматики синтаксического анализа (PEG), которые не могут обрабатывать левую рекурсию. Парсер PEG всегда выбирает левый вариант, пока не найдет совпадение. В этом случае он не найдет совпадение из-за левой рекурсии. Чтобы это сработало, нужно сначала устранить левую рекурсию. Устранение всех левых рекурсий может быть более сложным, поскольку вы также получите один через field после устранения первого. Например, вы можете написать грамматику следующим образом, чтобы сделать левую рекурсию более очевидной:

variable = (variable , $[ , blah , $]) | (variable , $. , identifier) | identifier

Если у вас есть левая рекурсия, например:

A  -> A a |  b

вы можете устранить это как (e - пустой парсер)

A  -> b A'
A' -> a A' | e

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