Парсеры-генераторы без сканера
Пролог: Хотя набор языков, распознанных синтаксическими анализаторами (контекстно-свободные грамматики), строго больше, чем тот из сканеров (регулярные грамматики), большинству парсеров-генераторов нужен сканер.
(Не пытайтесь объяснить причины позади него, я знаю их вполне хорошо).
Я видел синтаксические анализаторы, которые не требуют сканера как
Существуют определенные преимущества использования никакого сканера:
- Всего одно понятие (контекстно-свободные грамматики) вместо два
- Проанализируйте несколько языков в одном файле (как HTML/Javascript)
- Языки синтаксического анализа без зарезервированных слов (как МН/1)
Часто, "обходные решения" используются как переключение сканера по запросу синтаксического анализатора.
Вопрос: Вы знаете какие-либо другие парсеры-генераторы без сканера (какой-либо язык)? Это практично используемый (или чисто академический)? Есть ли какие-либо другие подходы, чем Tomita/GLR?
Ответы:
- повышение:: дух:: qi AraK
- Грамматики, разбирающие выражение (LPEG для Lua) Norman Ramsey
- Yakker Norman Ramsey
- MBase SK-логика
- Waxeye Trevor Robinson
4 ответа
Два других:
Грамматики синтаксического анализа Брайана Форда (PEG) не требуют сканера. Эффективный и ленивый "синтаксический анализатор пакетов" не обязателен. У меня был только хороший опыт работы с версией Lua LPEG , которая компилируется в эффективную машину с байт-кодом. Вполне практично.
YAKKER выглядит очень интригующе, хотя явно все еще находится в стадии предварительного выпуска. Они используют то, что они называют эффективным вариантом алгоритма синтаксического анализа Эрли.
На самом деле я большой поклонник безсканирующих парсеров; они значительно упрощают настройку. А типичные генераторы сканеров, мягко говоря, не доставляют особого удовольствия. Из справочной страницы Лекса:
Астероид, убивающий этого динозавра, все еще находится на орбите.
Наконец, у меня нет личного опыта с Elkhound, но сообщения из вторых рук, которые я слышу, впечатляют. Я бы сказал, что нет никаких сомнений в том, что некоторые генераторы парсеров без сканирования очень практичны.
Генераторы парсеров не нуждаются в сканер. Но вы в значительной степени сошли с ума, если не пользуетесь им.
Синтаксические анализаторы, созданные генераторами синтаксических анализаторов, не заботятся о том, чем вы их кормите, пока вы называете их токенами.
Чтобы создать генератор синтаксического анализатора без сканера, просто определите свою грамматику до уровня символа и передавайте отдельные символы синтаксическому анализатору как токены.
Причина, по которой это безумие, заключается в том, что синтаксический анализ - более сложная деятельность, чем лексирование. Вы можете создавать лексеры как конечные автоматы, которые переводятся в машинный код во многом как «сравнивать и переходить к следующему состоянию». По скорости это действительно сложно превзойти. Генераторы синтаксического анализатора создают синтаксические анализаторы, которые выполняют прогнозный синтаксический анализ рекурсивного спуска (для большинства генераторов LL, таких как ANTLR) или выполняют поиск в таблицах с помощью хеширования, двоичного или линейного поиска и т. Д.Таким образом, синтаксический анализатор тратит на токен намного больше энергии, чем лексер тратит на символ.
Если вы скармливаете символы синтаксическому анализатору в качестве токенов, он будет тратить на символ соответственно больше энергии, чем эквивалентный лексер. Если вы обрабатываете много входного текста, это в конечном итоге будет иметь значение, независимо от того, делаете ли вы это для миллиардов небольших входных потоков или нескольких действительно больших.
Так называемые анализаторы GLR без сканирования страдают от этой проблемы с производительностью по сравнению с анализаторами GLR, которые предназначены для использования токенов.
Моя компания создает инструмент, DMS Software Reengineering Toolkit , который использует синтаксический анализатор GLR (и успешно анализирует все распространенные языки, которые вы знаете, и множество необычных языков, которых вы не знаете, потому что у него есть GLR парсер). Мы знали о парсерах без сканирования и решили не использовать их из-за разницы в скорости; у нас есть классическая (но чрезвычайно мощная) LEX-подобная подсистема для определения лексических токенов. В одном случае, когда DMS выступила лицом к лицу с инструментом на основе XT (инструмент с бессканерным анализатором GLR), обрабатывающим тот же ввод, DMS оказался в 10 раз быстрее, чем пакет XT. Честно говоря, проведенный эксперимент был спонтанным и не повторялся, но поскольку он соответствовал моим подозрениям, я не видел причин повторять его. YMMV. И, конечно, если мы хотим отказаться от сканера, то, как я уже отмечал, довольно легко написать грамматик с символьными терминалами.
Бессканерные синтаксические анализаторы GLR имеют еще одно очень приятное свойство, которое не имеет значения для большинства людей.Вы можете взять две отдельные грамматики для синтаксического анализатора без сканирования и буквально объединить их, и все же получить синтаксический анализатор (часто с множеством двусмысленностей). Это очень важно, когда вы создаете один язык, встроенный в другой. Если это не то, что вы делаете, это просто академическое любопытство.
И, AFAIK, Элкхаунд не лишен сканера. (Я могу ошибаться в этом). (РЕДАКТИРОВАТЬ: 2/10: Похоже, я был неправ. Не в первый раз в моей жизни :)
boost :: spirit :: qi не нужен лексер, хотя вы можете использовать boost :: spirit :: lex как интерфейс. Из введения boost :: spirit :: lex :
Фактически, Spirit.Qi позволяет писать парсеры без использования лексера, анализируя ввод поток символов напрямую, и по большей части именно так Spirit использовался с момента его изобретения .
boost :: spirit (исходный) действительно работал так, как вы хотели, но он был перемещен в boost :: spirit :: classic . spirit :: qi , spirit :: lex - это новый дизайн Spirit, поэтому я оставил классическую версию:)
Простите за некропост. Вы можете попробовать это - встраиваемую реализацию PEG / Packrat для .NET: