Подтвердить что ты не робот

Генераторы безрасширителя Parser

Пролог: Хотя набор языков, распознаваемых парсерами (контекстно-свободные грамматики), строго больше, чем сканер (обычные грамматики), большинству генераторов парсеров нужен сканер.

(Пожалуйста, не пытайтесь объяснить причины этого, я их хорошо знаю).

Я видел парсеры, для которых не нужен сканер вроде

Существуют определенные преимущества использования сканера:

  • Только одно понятие (контекстно-свободные грамматики) вместо двух
  • Разбор нескольких языков в одном файле (например, HTML/Javascript)
  • Разбирайте языки без зарезервированных ключевых слов (например, PL/1)

Часто "обходные пути" используются как переключение сканера на запрос парсера.

Вопрос: Знаете ли вы какие-либо другие генераторы синтаксического анализатора (любой язык)? Являются ли они практическими в использовании (или чисто академическими)? Существуют ли какие-либо другие подходы, кроме Tomita/GLR?

Ответы:

4b9b3361

ОТВЕТЫ

Ответ 1

Два других:

  • Брайан Форд (Prying Expression Grammars) (PEG) не требует сканера. Эффективный, ленивый "парсер парсер" необязателен. У меня не было ничего, кроме хорошего опыта с версией Lua LPEG, которая компилируется на эффективную машину байт-кода. Практически.

  • YAKKER выглядит очень интригующим, хотя он все еще явно находится в предварительном состоянии. Они используют то, что, по их утверждению, являются эффективным вариантом алгоритма синтаксического анализа Эрли.

Я на самом деле огромный поклонник сканеров без разбора; они упрощают конфигурацию. И типичные генераторы сканеров, мягко говоря, не очень забавны в использовании. Из справочной страницы для Lex:

Астероид, чтобы убить этого динозавра, все еще находится на орбите.

Наконец, у меня нет личного опыта работы с Elkhound, но отчеты из вторых рук, которые я слышу, впечатляют. Я бы сказал, что нет никаких сомнений, но некоторые генераторы-генераторы без сканера очень практичны.

Ответ 2

Генераторы Parser не нуждаются в сканере. Но вы очень сумасшедший, если не используете его.

Парсеры, созданные генераторами парсеров, не заботятся о том, что вы их кормите, если вы называете их токенами.

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

Причина, по которой это безумие, заключается в том, что синтаксический анализ является более сложным, чем лексирование. Вы можете создавать лексеры как конечные конечные машины, которые переводят на машинный код в значительной степени, как "сравнить и перейти к следующему состоянию". Для скорости это действительно сложно победить. Генераторы Parser создают парсеры, которые проводят рекурсивный прогностический анализ спуска (для большинства генераторов LL, таких как ANTLR), или выполняют поиск таблиц путем хэширования, двоичного или линейного поиска и т.д. Таким образом, парсер тратит гораздо больше энергии на токен, чем лексер тратит на характер.

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

Так называемые scannerless анализаторы GLR страдают от этой проблемы с производительностью, по сравнению с анализаторами GLR, которые предназначены для использования токенов.

Моя компания создает инструмент, Инструмент для реинжиниринга программного обеспечения DMS, в котором используется анализатор GLR (и успешно анализирует все обычные langauges, которые вы знаете и много из более четких вы этого не делаете, потому что у него есть парсер GLR). Мы знали о сканерных синтаксических анализаторах и решили не выполнять их из-за разницы в скорости; у нас есть классическая (но чрезвычайно мощная) LEX-подобная подсистема для определения лексических токенов. В одном случае, когда DMS перешел носом к носу против инструмента XT (инструмента со сканерным анализатором GLR), который обрабатывал тот же вход, DMS оказался в 10 раз быстрее, чем XT-пакет. Справедливости ради следует, что эксперимент проводился ad hoc и не повторялся, но поскольку он соответствовал моим подозрениям, я не видел причин повторять его. YMMV. И, конечно, если мы хотим идти без сканера, ну, довольно легко написать грамматик с символьными терминалами, как я уже указывал.

GLR У анализаторов Scannerless есть еще одно очень приятное свойство, которое не имеет большого значения для большинства людей. Вы можете взять две отдельные грамматики для анализатора без сканера и буквально объединить их и все равно получить парсер (часто с большим количеством двусмысленностей). Это очень важно, когда вы строите один язык, встроенный в другой. Если это не то, что вы делаете, это просто академическое любопытство.

И, AFAIK, Elkhound не сканер без пауз. (Я мог ошибаться в этом). (EDIT: 2/10: Похоже, я был неправ. Не первый раз в жизни:)

Ответ 3

boost::spirit::qi не нужен лексер, хотя вы можете использовать boost::spirit::lex в качестве front-end. Из введения boost::spirit::lex:

Фактически, Spirit.Qi позволяет писать парсеров без использования лексера, разбора входной поток символов напрямую, и по большей части это путь Дух использовался с Изобретение.

boost::spirit (исходный) действительно работал так, как вам нужно, но он был перенесен в boost::spirit::classic. spirit::qi, spirit::lex - новый дизайн духа, поэтому я оставил классическую версию:)