Сравнение генераторов парсеров

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

• 1 Регулярные языки
• 2 Детерминированные контекстно-свободные языки
• 3 Анализ грамматик выражений, детерминированные логические грамматики
• 4 Общие контекстно-свободные, конъюнктивные или логические языки
• 5 Контекст- чувствительные грамматики
• 6 См. также
• 7 Примечания
• 8 Ссылки
• 9 Внешние ссылки

Обычные языки - это категория языков (иногда называемая Тип Хомского 3 ), которому может соответствовать конечный автомат (более конкретно, детерминированный конечный автомат или недетерминированный конечный автомат ), построенный из регулярного выражения . В частности, обычный язык может сопоставлять такие конструкции, как «A следует за B», «Либо A, либо B», «A, за которым следует ноль или более экземпляров B», но не может сопоставлять конструкции, которые требуют согласованности между несмежными элементами, например как «несколько экземпляров A, за которыми следует такое же количество экземпляров B», а также не могут выражать концепцию рекурсивной «вложенности» («за каждым A в конечном итоге следует соответствующий B»). Классическим примером проблемы, которую не может решить обычная грамматика, является вопрос о том, содержит ли данная строка правильно вложенные скобки. (Обычно это обрабатывается грамматикой Хомского типа 2, также называемой контекстно-свободной грамматикой.)

Контекстно-свободные языки - это категория языков (иногда называемый Тип 2 Хомского ), которому может соответствовать последовательность правил замены, каждое из которых по существу отображает каждый нетерминальный элемент на последовательность конечных элементов и / или других нетерминальных элементов. Грамматики этого типа могут соответствовать чему угодно, чему может соответствовать обычная грамматика, и, кроме того, могут обрабатывать концепцию рекурсивного "вложения" ("за каждым A в конечном итоге следует соответствующее B"), например вопрос о том, содержит ли данная строка правильно вложенные скобки. Однако правила контекстно-свободных грамматик являются чисто локальными и поэтому не могут обрабатывать вопросы, требующие нелокального анализа, такие как «Существует ли объявление для каждой переменной, которая используется в функции?». Для этого технически потребуется более сложная грамматика, такая как грамматика Хомского типа 1, также называемая контекстно-зависимой грамматикой. Однако генераторы парсеров для контекстно-свободных грамматик часто поддерживают возможность написанного пользователем кода вводить ограниченное количество контекстной чувствительности. (Например, обнаружив объявление переменной, написанный пользователем код может сохранить имя и тип переменной во внешней структуре данных, чтобы их можно было проверить на соответствие более поздним ссылкам на переменные, обнаруженным анализатором.)

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

В этой таблице сравниваются генераторы синтаксического анализатора с грамматиками синтаксического анализа, детерминированными логическими грамматиками.

В этой таблице сравниваются языки-генераторы синтаксического анализатора с общей контекстно-свободной грамматикой, конъюнктивной грамматикой или логическая грамматика.

В этой таблице сравнивается генераторы парсеров с контекстно-зависимыми грамматиками.

• Компилятор-компилятор
• Список систем преобразования программ

1. ^Bison 1.19 fork

• Каталог средств построения компиляторов
• Генераторы синтаксического анализатора с открытым исходным кодом на Java