Как определить переменные Паскаля в PetitParser
Хотя я недавно стал конвертером в dplyr для большинства этих типов операций, пакет sqldf по-прежнему очень хорош (и IMHO более читабельным) для некоторых вещей.
Вот пример того, как можно ответить на этот вопрос с помощью sqldf
x <- data.frame(Category=factor(c("First", "First", "First", "Second",
"Third", "Third", "Second")),
Frequency=c(10,15,5,2,14,20,3))
sqldf("select
Category
,sum(Frequency) as Frequency
from x
group by
Category")
## Category Frequency
## 1 First 30
## 2 Second 5
## 3 Third 34
2 ответа
Проблема в том, что ваша грамматика оставлена рекурсивной . 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
Я написал этот ответ, фактически не проверяя код, но должен быть в порядке. Синтаксический анализатор может быть еще более упрощен, я оставляю это как упражнение;).
Для получения дополнительной информации об устранении левой рекурсии вы можете взглянуть на устранение левой рекурсии
Грамматика имеет левую рекурсию: 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
Вам нужно будет применить это дважды, чтобы избавиться от рекурсии. В качестве альтернативы вы можете выбрать упрощение грамматики, если вы не хотите анализировать все возможные комбинации идентификаторов.