Когда использовать Parser Combinator? Когда использовать Parser Generator?

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

Однако я обнаружил, что существуют два несколько разных подхода к написанию парсеров: Генераторы парсеров и Комбинаторы парсеров.

Интересно, что мне не удалось найти какой-либо ресурс, объясняющий, в каких случаях какой подход лучше; Скорее всего , многие ресурсы (и человек) спросил я о предмете не знал другого подхода, только объясняя свой подход , как на подходе , и не говоря уже о другой вообще:

• Знаменитая Dragon книга входит в лексический / сканирование и упоминает (F) Лекс, но не упоминает комбинатор синтаксического анализа на всех.
• Шаблоны языковой реализации в значительной степени опираются на ANTLR Parser Generator, встроенный в Java, и вообще не упоминают Parser Combinators.
• В руководстве Введение в Parsec по Parsec, который является Parser Combinator в Haskell, вообще не упоминаются Генераторы Parser.
• Boost :: spirit , самый известный C ++ Parser Combinator, вообще не упоминает Parser Generators.
• В большом пояснительном сообщении в блоге, которое вы могли бы изобрести Parser Combinators, вообще не упоминаются генераторы Parser.

Простой обзор:

Parser Generator

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

Это означает, что процесс компиляции выполняется в два отдельных этапа. Интересно, что сами генераторы парсеров также являются компиляторами (и многие из них действительно являются хостами ).

Parser Combinator

Parser Combinator описывает простые функции, называемые синтаксическими анализаторами, которые все принимают входные данные в качестве параметра и пытаются извлечь первые символы этого ввода, если они совпадают. Они возвращают кортеж (result, rest_of_input), где он resultможет быть пустым (например, nilили Nothing), если парсер не смог проанализировать что-либо из этого ввода. Примером будет digitпарсер. Конечно, другие синтаксические анализаторы могут использовать синтаксические анализаторы в качестве первых аргументов (последний аргумент все еще остается во входной строке), чтобы объединить их: например, many1попытаться сопоставить другой синтаксический анализатор столько раз, сколько это возможно (но по крайней мере один раз, или он сам потерпит неудачу).

Теперь вы, конечно, можете комбинировать (создавать) digitи many1, скажем, создавать новый парсер integer.

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

Таким образом, могут быть созданы очень сложные лексеры / парсеры. В языках, поддерживающих перегрузку операторов, это также очень похоже на EBNF, даже если оно все еще написано непосредственно на целевом языке (и вы можете использовать все функции целевого языка, которые вам нужны).

Простые различия

Язык:

• Генераторы синтаксического анализатора написаны в комбинации из DSL EBNF-ish и кода, которому эти операторы должны генерировать, когда они совпадают.
• Парсер-комбинаторы пишутся на целевом языке напрямую.

Лексический / Парсинг:

• Генераторы парсеров имеют очень четкое различие между «лексером» (который разбивает строку на токены, которые могут быть помечены, чтобы показать, с каким значением мы имеем дело) и «парсером» (который берет выходной список токенов из лексера и пытается объединить их, образуя абстрактное синтаксическое дерево).
• Parser Combinators не имеют / не нуждаются в этом различении; обычно простые парсеры выполняют работу «лексера», и более высокоуровневые парсеры вызывают эти более простые парсеры, чтобы решить, какой тип AST-узла создать.

Вопрос

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

Какие свойства проблемы указывают на то, что проблему лучше решить с помощью генератора синтаксических анализаторов? Какие свойства проблемы могут указывать на то, что проблему лучше решить, используя Parser Combinator?

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

Некоторые из уже существующих ответов намекали на некоторые из их различий, но они не давали полной картины, и, казалось, были несколько самоуверенными, поэтому этот ответ был написан.

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

Чтобы понять различия между Parser Combinators и Parser Generator, сначала нужно понять разницу между различными видами синтаксического анализа, которые существуют.

анализ

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

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

Грубо говоря, существует четыре основных алгоритма, позволяющих компьютеру анализировать ввод:

• Разбор LL. (Не зависящий от контекста анализ сверху вниз.)
• Разбор LR. (Контекстный, восходящий анализ.)
• PEG + Packrat парсинг.
• Эрли Парсинг.

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

LL и LR могут смотреть только на контекстно-свободные грамматики (то есть контекст вокруг записанных токенов не важен для понимания того, как они используются).

Разбор PEG / Packrat и разбор Earley используется гораздо реже: разбор Earley хорош тем, что он может обрабатывать намного больше грамматик (включая те, которые не обязательно не зависят от контекста), но он менее эффективен (как утверждает дракон) книга (раздел 4.1.1); я не уверен, что эти утверждения все еще точны). Разбор грамматики выражения + синтаксический анализ пакетов - это метод, который относительно эффективен и может обрабатывать больше грамматик, чем как LL, так и LR, но скрывает неоднозначности, как будет быстро упомянуто ниже.

LL (слева направо, крайний левый вывод)

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

Это дерево строится «сверху вниз», что означает, что мы начинаем с корня дерева и проходим правила грамматики так же, как мы проходим через входную строку. Это также можно рассматривать как построение эквивалента 'postfix' для потока токенов 'infix', который читается.

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

LR (слева направо, крайний правый вывод)

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

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

Смотреть вперед

В любой из этих двух систем иногда необходимо взглянуть на большее количество токенов на входе, прежде чем можно будет решить, какой выбор сделать. Это (0), (1), (k)или (*)-syntax вы видите после названия этих двух общих алгоритмов, таких как LR(1) или LL(k). kобычно означает «столько, сколько нужно вашей грамматике», в то время как *обычно означает «этот синтаксический анализатор выполняет обратное отслеживание», который является более мощным / простым в реализации, но имеет гораздо более высокое использование памяти и времени, чем анализатор, который может просто продолжать анализ линейно.

Обратите внимание, что парсеры в стиле LR уже имеют много токенов в стеке, когда они могут решить «смотреть в будущее», поэтому у них уже есть больше информации для отправки. Это означает, что им часто требуется меньше «оглядки», чем синтаксический анализатор в стиле LL для той же грамматики.

LL vs. LR: двусмысленность

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

Однако у парсинга в стиле LL есть проблема: Left Recursion .

Очень естественно написать грамматику вроде:

expr ::= expr '+' expr | term
term ::= integer | float

Но синтаксический анализатор в стиле LL застревает в бесконечном рекурсивном цикле при синтаксическом анализе этой грамматики: при попытке exprпроверить крайнюю левую возможность правила он снова возвращается к этому правилу, не потребляя никакого ввода.

Есть способы решить эту проблему. Самое простое - переписать вашу грамматику, чтобы такой рекурсии больше не было:

expr ::= term expr_rest
expr_rest ::= '+' expr | ϵ
term ::= integer | float

(Здесь ϵ обозначает «пустую строку»)

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

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

В Разделе 2.5 Книги Дракона говорится:

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

У парсеров в стиле LR нет проблемы этой левой рекурсии, поскольку они строят дерево снизу вверх. Тем не менее , мысленный перевод грамматики, подобной выше, в синтаксический анализатор в стиле LR (который часто реализуется как конечный автомат )
очень труден (и подвержен ошибкам), так как часто бывают сотни или тысячи состояний + переходы состояний для рассмотрения. Вот почему парсеры в стиле LR обычно генерируются генератором парсеров, который также известен как «компилятор компилятора».

Как разрешить неясности

Мы видели два метода для разрешения двусмысленности левой рекурсии выше: 1) переписать синтаксис 2) использовать LR-парсер.

Но есть и другие неясности, которые сложнее решить: что, если два разных правила одинаково применимы одновременно?

Некоторые общие примеры:

• арифметические выражения.
• висящее остальное

Парсеры как в LL-стиле, так и в LR-стиле имеют проблемы с этим. Проблемы с разбором арифметических выражений могут быть решены путем введения приоритета операторов. Аналогичным образом можно решить и другие проблемы, такие как Dangling Else, выбрав одно приоритетное поведение и придерживаясь его. (В C / C ++, например, висячее остальное всегда принадлежит ближайшему «если»).

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

Больше информации, которая намного глубже, чем этот пост, в том числе, почему вообще невозможно узнать, не содержит ли ваша грамматика двусмысленности, и последствия этого - замечательная статья блога LL и LR в контексте: зачем разбирать инструменты сложны . Я очень рекомендую это; это очень помогло мне понять все, о чем я сейчас говорю.

50 лет исследований

Но жизнь продолжается. Оказалось, что «нормальным» синтаксическим анализаторам в стиле LR, реализованным в виде автоматов с конечным состоянием, часто нужны тысячи состояний + переходы, что было проблемой в размере программы. Таким образом, были написаны такие варианты, как Simple LR (SLR) и LALR (Look-forward LR), которые сочетают в себе другие методы, чтобы сделать автомат меньше, уменьшая объем дискового пространства и памяти в программах синтаксического анализа.

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

Интересно, что после описания алгоритма обобщенного LR оказалось, что аналогичный подход можно использовать для реализации синтаксических анализаторов обобщенного LL , который аналогично быстро ($ O (n ^ 3) $ временной сложности для неоднозначных грамматик, $ O (n) $ для полностью однозначных грамматик, хотя и с большим количеством бухгалтерии, чем простой (LA) парсер LR, что означает более высокий постоянный коэффициент), но опять же позволяет парсеру записываться в стиле рекурсивного спуска (сверху вниз), который намного более естественен написать и отладить.

Парсер Комбинаторы, Парсер Генераторы

Итак, с этой длинной экспозицией мы сейчас подходим к сути вопроса:

В чем отличие Parser Combinators и Parser Generator, и когда один из них должен использоваться поверх другого?

Это действительно разные виды зверей:

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

Генераторы парсеров были созданы потому, что люди искали создание парсеров, у которых не было проблем, с которыми были парсеры в стиле LL (то есть парсеры в стиле LR), что оказалось очень трудно сделать вручную. К наиболее распространенным относятся Yacc / Bison, которые реализуют (LA) LR).

Интересно, что в наши дни ландшафт несколько запутан:

• Можно написать Parser Combinators, которые работают с алгоритмом GLL , разрешая проблемы неоднозначности, которые были у классических синтаксических анализаторов в стиле LL, и в то же время столь же читабельны / понятны, как и все виды синтаксического анализа сверху вниз.

• Генераторы парсеров также могут быть написаны для парсеров в стиле LL. ANTLR делает именно это и использует другую эвристику (Adaptive LL (*)) для устранения неоднозначностей, которые были у классических синтаксических анализаторов в стиле LL.

В общем, создание генератора синтаксического анализатора LR и отладка вывода генератора синтаксического анализатора в стиле (LA), работающего на вашей грамматике, затруднены из-за перевода исходной грамматики в LR-форму «наизнанку». С другой стороны, такие инструменты , как Yacc / Bison было много лет оптимизаций, и видел много использования в дикой природе, а это значит , что сейчас многие люди считают это как на способ сделать разбор и скептически относятся к новым подходам.

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

Примечание: по теме лексического анализа.

Лексический анализ может использоваться как для Parser Combinators, так и для Parser Generator. Идея состоит в том, чтобы иметь «тупой» синтаксический анализатор, который очень легко реализовать (и, следовательно, быстро), который выполняет первый проход по вашему исходному коду, удаляя, например, повторяющиеся пробелы, комментарии и т. Д. И, возможно, «разбивая» на очень грубо говоря, различные элементы, которые составляют ваш язык.

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

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

Tl; Dr:

Вот блок-схема, которая применима к большинству случаев:

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

Функция, которая заставляет вас хотеть добавить сложность генераторов парсеров, - это сообщения об ошибках. Вам нужны сообщения об ошибках, которые указывают пользователю на строку и столбец, и, надеюсь, также понятны человеку. Требуется много кода, чтобы сделать это правильно, и лучшие генераторы синтаксического анализатора, такие как antlr, могут помочь вам с этим.

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

Сэм Харвелл, один из разработчиков генератора синтаксических анализаторов ANTLR, недавно написал :

Я обнаружил, что [комбинаторы] не соответствуют моим потребностям:

1. ANTLR предоставляет мне инструменты для управления такими вещами, как неоднозначности. Во время разработки существуют инструменты, которые могут показать мне неоднозначные результаты анализа, чтобы я мог устранить эти неоднозначности в грамматике. Во время выполнения я могу использовать неоднозначность, возникающую из-за неполного ввода в IDE, для получения более точных результатов в таких функциях, как завершение кода.
2. На практике я обнаружил, что комбинаторы синтаксического анализа не подходят для достижения моих целей производительности. Часть этого восходит
3. Когда результаты синтаксического анализа используются для таких функций, как выделение контуров, завершение кода и интеллектуальный отступ, легко можно незаметно изменить грамматику, чтобы повлиять на точность этих результатов. ANTLR предоставляет инструменты, которые могут превратить эти несоответствия в ошибки компиляции, даже в тех случаях, когда в противном случае типы будут компилироваться. Я могу с уверенностью создать прототип новой языковой функции, которая влияет на грамматику, зная, что весь дополнительный код, который формирует IDE, с самого начала предоставит полную возможность для новой функции. Мой форк ANTLR 4 (на котором основана цель C #) - единственный известный мне инструмент, который даже пытается предоставить эту функцию.

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

Как упоминает Карл, генераторы синтаксических анализаторов, как правило, лучше сообщают об ошибках. К тому же:

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

С другой стороны, комбинаторы имеют свои преимущества:

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