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