Формальная грамматика
-
Основы формальных грамматик
- Формальные грамматики — это математические модели для описания языков.
- Они основаны на работах Ноама Хомского и классифицируются по типам.
-
Иерархия Хомского
- Иерархия Хомского включает типы грамматик, которые различаются по степени строгости правил.
- Контекстно-свободные и обычные грамматики являются наиболее часто используемыми типами.
-
Контекстно-свободные грамматики
- Контекстно-свободные грамматики имеют левую часть с одним нетерминальным символом.
- Они могут быть распознаны в линейное время с помощью алгоритмов, таких как распознаватель Эрли.
-
Обычные грамматики
- Обычные грамматики имеют левую часть с одним нетерминальным символом и правую часть с одним конечным символом или пустой строкой.
- Они могут быть распознаны за линейное время с помощью конечных автоматов.
-
Другие формы порождающих грамматик
- Существуют расширенные формы грамматик, такие как смежные с деревьями, аффинные и атрибутивные грамматики, которые повышают выразительность или облегчают анализ.
- Рекурсивные и аналитические грамматики также являются важными расширениями.
-
Примеры формализмов аналитической грамматики
- Примеры включают язык синтаксического анализа сверху вниз, связующие грамматики и грамматики синтаксического анализа выражений.