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

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

0 голосов
/ 16 января 2019

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

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

Я добавил все эти произведения (кроме identifier) в качестве ivars моего подкласса 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]'.

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

Ответы [ 2 ]

0 голосов
/ 16 января 2019

Проблема в том, что ваша грамматика рекурсивна .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

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

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

0 голосов
/ 16 января 2019

Грамматика имеет левую рекурсию: 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

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

...