Разбор произвольных контекстно-свободных грамматик, в основном коротких фрагментов

Я хочу разобрать определенные пользователем доменные языки. Эти языки обычно близки к математическим обозначениям (я не разбираю естественный язык). Пользователи определяют свои DSL в нотации BNF, например так:

expr ::= LiteralInteger
       | ( expr )
       | expr + expr
       | expr * expr

Подобные входные данные 1 + ( 2 * 3 )должны быть приняты, в то время как подобные входные данные 1 +должны быть отклонены как неправильные, а подобные входные данные 1 + 2 * 3должны быть отклонены как неоднозначные.

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

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

Как правило, я буду вызывать анализатор на относительно короткие входные данные, со случайным более длинным вводом. Таким образом, асимптотически более быстрый алгоритм может быть не лучшим выбором. Я хотел бы оптимизировать распределение около 80% входов длиной менее 20 символов, 19% между 20 и 50 символами и 1% редко более длинных входов. Скорость для неверных вводов не является главной проблемой. Кроме того, я ожидаю модификацию DSL примерно через каждые 1000-100000 входов; Я могу потратить пару секунд на предварительную обработку грамматики, а не пару минут.

Какой алгоритм (ы) разбора я должен исследовать, учитывая мои типичные размеры ввода? Должны ли сообщения об ошибках быть фактором моего выбора, или я должен сосредоточиться на разборе однозначных входных данных и, возможно, запустить совершенно отдельный, более медленный синтаксический анализатор для обеспечения обратной связи об ошибках?

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

Вероятно, идеальным алгоритмом для ваших нужд является синтаксический анализ LL или GLL. Это очень новый алгоритм (статья была опубликована в 2010 году). В каком-то смысле, это алгоритм Эрли, дополненный структурированным графом стеком (GSS) и использующий LL (1).

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

Алгоритм имеет ряд явных преимуществ, связанных с вашими потребностями, по сравнению с другими общими алгоритмами синтаксического анализа (о которых я знаю). Во-первых, реализация очень проста: я думаю, что только Earley легче реализовать. Во-вторых, производительность довольно хорошая: фактически она становится такой же быстрой, как LL (1) на грамматиках, которые являются LL (1). В-третьих, восстановить анализ очень просто, а также проверить, существует ли более одного возможного анализа.

Основное преимущество GLL состоит в том, что он основан на LL (1) и поэтому очень прост для понимания и отладки при реализации, при разработке грамматик, а также при разборе входных данных. Кроме того, это также облегчает обработку ошибок: вы точно знаете, где возможны разборы и как они могли продолжаться. Вы можете легко указать возможные разборы в точке ошибки и, скажем, последние 3 точки, где разборы застряли. Вместо этого вы можете выбрать вариант восстановления после ошибки и пометить обработку, над которой работал наиболее удаленный анализ, как «завершенную» для этого анализа, и посмотреть, можно ли продолжить анализ после этого (скажем, кто-то забыл скобки). Вы могли бы даже сделать это, скажем, для 5 разборов, которые получили самый дальний результат.

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

Моя компания (Semantic Designs) очень успешно использовала синтаксические анализаторы GLR для выполнения именно того, что предлагает OP при синтаксическом анализе как специфичных для предметной области языков, так и "классических" языков программирования с помощью нашего DMS Software Reengineering Toolkit. Это поддерживает преобразования программ «источник-источник», используемые для крупномасштабной реструктуризации программ / обратного проектирования / генерации прямого кода. Это включает в себя автоматическое исправление синтаксических ошибок довольно практичным способом. Используя GLR в качестве основы и некоторые другие изменения (семантические предикаты, ввод с набором токенов, а не просто ввод токенов, ...) нам удалось создать парсеры для примерно 40 языков.

Столь же важная, как и возможность разбора экземпляров на всех языках, GLR также оказалась чрезвычайно полезной при разборе правил перезаписи от источника к источнику . Это фрагменты программы с гораздо меньшим контекстом, чем у полной программы, и, как правило, они имеют большую неопределенность. Мы используем специальные аннотации (например, настаивая на том, что фраза соответствует определенной нетерминальной грамматике), чтобы помочь разрешить эти неоднозначности во время / после синтаксического анализа правил. Организовывая механизм синтаксического анализа GLR и инструменты вокруг него, мы получаем «парсеры» для правил перезаписи «бесплатно», когда у нас есть парсер для его языка. Механизм DMS имеет встроенное средство применения правил перезаписи, которое затем можно использовать для применения этих правил для выполнения желаемых изменений кода.

Вероятно, наш самый впечатляющий результат - это возможность проанализировать полный C ++ 14 , несмотря на все неоднозначности, используя в качестве основы контекстно-свободную грамматику. Я отмечаю, что все классические компиляторы C ++ (GCC, Clang) отказались от возможности делать это и использовать рукописные парсеры (что, IMHO, делает их намного сложнее поддерживать, но тогда они не моя проблема). Мы использовали этот механизм для внесения значительных изменений в архитектуру больших систем C ++.

С точки зрения производительности наши GLR-парсеры работают довольно быстро: десятки тысяч строк в секунду. Это намного ниже уровня техники, но мы не предпринимали серьезных попыток оптимизировать это, и некоторые из узких мест находятся в обработке потока символов (полный Unicode). Чтобы создать такие парсеры, мы предварительно обрабатываем контекстно-свободные грамматики с использованием чего-то, очень близкого к генератору парсера LR (1); обычно это выполняется на современной рабочей станции за десять секунд на больших грамматиках размера C ++. Удивительно, но для очень сложных языков, таких как современные COBOL и C ++, генерация лексеров, оказывается, занимает около минуты; некоторые из DFA, определенных для Unicode, становятся довольно волосатыми. Я просто сделал Ruby (с полной подграммой для его невероятных регулярных выражений) в качестве упражнения для пальцев; DMS может обработать свой лексер и грамматику вместе примерно за 8 секунд.

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

Из того, что вы говорите, я думаю, что CYK не такой уж плохой выбор. Вероятно, вам не нужно много выигрывать, добавляя прогнозируемость (LL или LR), и на самом деле это может привести к издержкам за счет различения вычислений, которые следует объединять, а не различать (особенно в случае LR). Они также могут иметь соответствующую стоимость в размере создаваемого леса анализа (что может играть роль в ошибках неоднозначности). На самом деле, хотя я не уверен, как формально сравнивать адекватность более сложных алгоритмов, я знаю, что CYK дает хороший обмен вычислениями.

Теперь я не верю, что существует много литературы по общим синтаксическим анализаторам CF для неоднозначных грамматик, которые должны принимать только однозначный ввод. Я не припоминаю, чтобы кто-то видел, возможно, потому что даже для технических документов или даже языков программирования синтаксическая неоднозначность приемлема, если ее можно разрешить другими способами (например, неоднозначность в выражениях ADA).

Мне действительно интересно, почему вы хотите изменить свой алгоритм, а не придерживаться того, что у вас есть. Это может помочь мне понять, какие перемены могут вам помочь. Это проблема скорости, это представление разборов, или это обнаружение и восстановление ошибок?

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

Вы упоминаете ограничения по времени обработки вашей DSL-грамматики, но не даете подсказки относительно ее размера (что не означает, что я мог бы ответить цифрами, которые вы сделали).

Некоторая обработка ошибок может быть интегрирована в эти общие алгоритмы CF простыми способами. Но мне нужно понять, какую обработку ошибок вы ожидаете получить более позитивно. Не могли бы вы привести несколько примеров?

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