Какой самый мощный вид парсера?

28

В качестве стороннего проекта я пишу язык с использованием Python. Я начал с использования клона flex / bison под названием Ply, но столкнулся с трудностями, которые я могу выразить с помощью этого стиля грамматики, и мне не интересно взламывать свой язык из-за несоответствия импеданса с инструмент. Поэтому я не против писать свои собственные.

Так какой же самый мощный тип парсера? Цитаты к статьям (а также более вводные статьи) приветствуются.

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

Пол Биггар
источник
1
Понижено: не исследовательский уровень.
Уоррен Шуди
3
@Warren: я проверил FAQ, прежде чем спрашивать - это не является обязательным требованием.
Пол Биггар
1
На самом деле есть два часто задаваемых вопроса, один для общего сайта и один для CStheory. Теория CS показывает, что вопросы, на которые можно ответить, например, читая Википедию, не по теме; см. "Какие вопросы слишком простые?" в meta.cstheory.stackexchange.com/questions/225/… .
Уоррен Шуди
1
@Warren: это часто задаваемые вопросы, которые я прочитал. Я читал википедию, но я чувствовал, что это действительно нужно для понимания.
Пол Биггар
1
Вы имеете в виду парсеры в производстве или теоретические, то есть те, которые охватывают грамматические типы, отличные от CFG?
Рафаэль

Ответы:

33

Грамматика обычно определяется как грамматика без контекста - точное определение дается на странице Википедии, но она работает так же, как и в PLY, которая основана на Bison , который, в свою очередь, основан на yacc .

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

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

O(n3|G|)n|G|

Второй алгоритм - алгоритм Эрли . Этот алгоритм также способен анализировать любую грамматику без контекста. Хотя алгоритму требуется времени для разбора неоднозначного языка, ему требуется только O ( n 2 ) времени для разбора однозначного языка. Кроме того, он, очевидно, работает в линейном времени для большинства грамматик LR и особенно хорошо работает с леворекурсивными грамматиками.O(n3)O(n2)

Здесь вы можете найти статью, в которой обсуждается практическая реализация (адаптация) алгоритма Эрли. Они заключают: «Учитывая универсальность анализа Эрли по сравнению с анализом LALR (1) ((что примерно так и делает PLY)), и учитывая, что даже PEP ((их реализация алгоритма Эрли)) худшее время не будет заметно со стороны пользователь, это отличный результат ".

Последний тип парсера - это парсер GLR . Это обобщенная версия синтаксического анализа LR, способная анализировать любой язык без контекста.

Зрелой реализацией GLR является ASF + SDF . Bison также может генерировать синтаксический анализатор GLR, хотя его реализация немного отличается от «стандартного» алгоритма GLR. Элкхаунд Алгоритм представляет собой гибридный алгоритм РВО / LALR. Он использует LALR, когда это возможно, и GLR, когда это необходимо, чтобы быть быстрым и способным анализировать любую грамматику.

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

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

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

Алекс тен Бринк
источник
1
Отличный ответ !! Любые мысли о том, как вписываются PEG?
Пол Биггар
2
PEG «отличаются» от CFG: есть CFG, которые не являются PEG, и наоборот. Я отсылаю вас сюда: stackoverflow.com/questions/1857022/… .
Алекс тен Бринк
Это также может представлять интерес: blogs.ethz.ch/copton/2009/07/08/parsing-expression-grammars .
Алекс тен Бринк
1
На самом деле, наиболее распространенные генераторы синтаксических анализаторов (yacc, Antlr, bison) допускают не-CF концепции с помощью предикатов или произвольного кода, который проверяет, можно ли применить одно правило, соответственно. решающий приоритет. Это может быть использовано для реализации статической семантики в основном, так как основной синтаксис остается по существу свободным от контекста.
Рафаэль
1
Рекурсивные языки - это как раз те языки, которые можно разрешить, всегда останавливая машины Тьюринга. Поэтому любой контекстно-зависимый язык также является рекурсивным, но поскольку контекстно-зависимые языки разрешимы в экспоненциальном времени, существуют рекурсивные языки, не зависящие от контекста. Неограниченные грамматики еще более мощны: проблема остановки может быть описана неограниченной грамматикой, но не является рекурсивным языком.
Алекс тен Бринк
15

В документе ICFP 2010 в этом году, Total Parser Combinators , описывается библиотека терминальных комбинаторов , которая может быть завершена доказуемым образом, а также устанавливается, что в этой библиотеке «комбинаторы синтаксических анализаторов настолько выразительны, насколько это возможно», учитывая, что синтаксический анализатор гарантированно прекратит работу. К сожалению, я не помню объяснения, которое автор дал для того, что означает «настолько выразительный, насколько это возможно», но оно, безусловно, имеет отношение к вашему вопросу о «власти».

Роб Симмонс
источник
1
У меня есть машина, которая не загрязняет окружающую среду, на самом деле она тоже не движется ... Итак, вопрос в том, какой язык анализируется этой библиотекой? Не значит, что эта работа не интересна, конечно.
Бабу
2

Если вы хотите выйти за рамки контекстно-свободных грамматик для синтаксического анализа языков программирования, но по-прежнему выполнять синтаксический анализ за полиномиальное время, вы можете прибегнуть к синтаксическому анализу грамматик выражений или логических грамматик - последние также доступны в вариантах LL и LR (см. Здесь ). В теории формального языка изучаются также мощные, но распознаваемые по линейному времени языки Черча-Россера , но я не знаю ни одного реализованного генератора синтаксических анализаторов для них.

В обработке естественного языка вкусы различны, например, они имеют дело с неоднозначностью (также: присущая неоднозначность), и свободный порядок слов играет очень важную роль. Здесь ключевые слова слегка контекстно-зависимые языки и перезапуск автоматов могут помочь вам начать чтение.

Герман Грубер
источник
1
Учитывая способ, которым был задан вопрос, и жалобу на то, что CF слишком стеснительный, ваш ответ явно лучший. Так и идет ...
Бабу
0

Инструменты генератора парсеров:

ANTLR очень хорошо. Кроме того, вы можете взглянуть на JavaCC


источник
Я не специалист по компьютерам (несмотря на то, что говорит моя степень;), так что мои слова здесь могут немного весить. Я согласен с Sazzad - ANTLR - очень мощный инструмент. Он очень полный, и мне еще не удалось найти каких-либо проблем с генератором синтаксического анализатора (LL (k), если я правильно помню). С другой стороны, мне еще предстоит реализовать компилятор для несколько сложной грамматики ...
Йорген Сигвардссон
5
Я думаю, что вы упускаете суть вопроса, и, возможно, весь сайт. Речь идет о теории разбора, а не о реализациях и инструментах.
Пол Биггар