Хомская иерархия и LL (*) парсеры

Question

Я хочу разобрать язык программирования. Я много читал о формальных языках и иерархии Хомского и ANTLR. Но я не смог найти информацию о том, как соотнести языки ANTLR v3 как синтаксический анализатор рекурсивного спуска LL (*), принимающий иерархию chomsky.

Как типы Хомского смешиваются с LL (*)? Любая информация (онлайн, книги, документы) с благодарностью.

Редактировать: Как синтаксические / семантические предикаты и обратный просмотр карты ANTLR в это?

Answer 1

Иерархия Хомского в основном:

1. Обычные языки
2. Грамматики без контекста
3. Контекстно-зависимые грамматики
4. Рекурсивно перечислимые (полные по Тьюрингу) грамматики

LL Грамматики (и парсеры) являются подмножеством контекстно-свободных грамматик. Они используются потому, что обычные языки слишком слабы для целей программирования, а также потому, что общим не зависящим от контекста парсером является O (n ^ 3), который слишком медлен для анализа программы. Действительно, расширение синтаксического анализатора с помощью вспомогательных функций делает его сильнее. Запись в Википедии о синтаксических анализаторах LL объясняет некоторые из них. Книга Дракона считается ведущим учебником по компиляторам и может объяснить далее.

Answer 2

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

Обратите внимание, что если мы говорим о LL (*), это означает ANTLR v3, а не 2.