Ноль-или-больше / один-или-больше модификаторов и возврат

Question

Я добавил ноль-или-больше и один-или-больше модификаторов в мой синтаксический анализатор PEG , что довольно просто, поскольку в PEG так мало возвратов. Более ранние итерации никогда не пересматриваются, поэтому достаточно простого цикла while.

Однако в других контекстах модификаторы «ноль или более» и «один или более» требуют возврата назад. Например, возьмем следующее регулярное выражение:

(aa|aaa)+

Это выражение должно иметь жадное совпадение со строкой из семи a: есть несколько способов сложить 2 и 3, чтобы получить 7. Но для этого необходимо пересмотреть более ранние итерации. Например, если выражение соответствует трем a в первый раз и трем a во второй раз, остается только один a, который не может быть сопоставлен. Возвратите последние три a и сопоставьте два a вместо этого, и пять a соответствуют. Тогда последние два a также могут быть сопоставлены (то есть 3 + 2 + 2 = 7).

К счастью, регулярное выражение завершает поиск, как только оно соответствует строке. Но как насчет парсера EBNF ? Если грамматика неоднозначна, синтаксический анализатор должен использовать обратную трассировку, чтобы найти все возможные синтаксические деревья ! Если у нас есть производство

( "aa" | "aaa" )*

и строка из семи a, полностью возвращающий парсер вернул бы все возможные способы выражения 7 через 2 и 3. И это только для семи a: соответствует немного более длинной строке, и N -дное дерево возможностей вырастает еще один уровень . Рассмотрим N = 6:

S : ( T )*
  ;

T : A
  | B
  | C
  | D
  | E
  | F
  ;

Страшный комбинаторный взрыв!

Может ли это действительно иметь место, хотя? Нет ли ограничений на модификаторы «ноль или более» и «один или более» в EBNF? Реализация их, как описано, будет намного больше работы, чем простой цикл while() анализатора PEG, поэтому я должен задаться вопросом ...

Answer 1

да;Откат может дать вам много результатов.я являюсь автором lepl, рекурсивного приличного парсера, который с радостью откатится назад и создаст «лес разбора» всех возможных AST.и нет никакого ограничения в EBNF (который является просто языком спецификации и не привязан к какой-либо конкретной реализации синтаксического анализатора).

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

Есть два (эквивалентных) способа сделать это - либо «скомпилировать» регулярное выражение (выяснить, что было бы выражением, если бы параллельная работа была явной), либо жонглировать параллельными совпадениями во время выполнения.подход компиляции переводит регулярное выражение в DFA (детерминированный конечный автомат).точнее, NFA (недетерминированный ...) в некоторой степени похож на графическую версию регулярного выражения и, вероятно, представляет собой работу регулярных выражений;сопоставление с NFA требует обратного отслеживания, но вы можете перевести NFA в DFA, который этого не делает.

однако, выполнение этого во время выполнения легче понять (и, как правило, более полезно на практике) и объясняетсяв трех потрясающих статьях, которые вы действительно должны прочитать, если хотите лучше понять это: http://swtch.com/~rsc/regexp/regexp3.html и ссылки в начале этого.

Я не могу подчеркнуть это достаточно -вам нужно прочитать эти статьи ...

ps неопределенно связаны - вы можете сделать возврат более эффективным, кэшируя результаты, которые вам могут понадобиться позже (когда вы в конечном итоге получите тот же текст и выражение по другому маршруту)).это называется «синтаксический анализ пакетов» применительно к рекурсивному приличному синтаксическому анализу (хотя, если честно, отдельного имени не стоит - на самом деле он просто использует кэш).кэширование позволяет избежать экспоненциального времени выполнения - где-то есть статья norvig (парень из Google, но она была написана гораздо раньше), в которой объясняется, что: http://acl.ldc.upenn.edu/J/J91/J91-1004.pdf