Хомская иерархия и LL(*) парсеры
Я хочу разобрать язык программирования. Я много читал о формальных языках и иерархии Хомского и ANTLR. Но я не смог найти информацию о том, как соотнести языки ANTLR v3 как синтаксический анализатор рекурсивного спуска LL(*), принимающий иерархию chomsky.
Как типы Хомского смешиваются с LL(*)? Любая информация (онлайн, книги, документы) с благодарностью.
Редактировать: Как синтаксические / семантические предикаты и возврат ANTLR-карты в это?
2 ответа
Хомская иерархия в основном:
- Обычные языки
- Контекстно-свободные грамматики
- Контекстно-зависимые грамматики
- Рекурсивно перечислимые (полные по Тьюрингу) грамматики
Грамматики LL (и парсеры) являются подмножеством контекстно-свободных грамматик. Они используются потому, что обычные языки слишком слабы для целей программирования, а также потому, что общим не зависящим от контекста парсером является O(n^3), который слишком медлен для анализа программы. Действительно, расширение синтаксического анализатора с помощью вспомогательных функций делает его сильнее. Запись в Википедии о парсерах LL объясняет некоторые из них. "Книга Дракона" считается ведущим учебником по компиляторам и может объяснить более подробно.
LL(*) - это подмножество контекстно-свободных языков. Однако другой вопрос заключается в том, что может анализировать antlr с учетом предикатов и обратного отслеживания, что расширяет его возможности.
Обратите внимание, что если мы говорим о LL(*), это означает, что ANTLR v3, а не 2.