Формальная грамматика

• Основы формальных грамматик

  • Формальные грамматики – это математические модели для описания языков. 
  • Они основаны на работах Ноама Хомского и классифицируются по типам. 

• Иерархия Хомского

  • Иерархия Хомского включает типы грамматик, которые различаются по степени строгости правил. 
  • Контекстно-свободные и обычные грамматики являются наиболее часто используемыми типами. 

• Контекстно-свободные грамматики

  • Контекстно-свободные грамматики имеют левую часть с одним нетерминальным символом. 
  • Они могут быть распознаны в линейное время с помощью алгоритмов, таких как распознаватель Эрли. 

• Обычные грамматики

  • Обычные грамматики имеют левую часть с одним нетерминальным символом и правую часть с одним конечным символом или пустой строкой. 
  • Они могут быть распознаны за линейное время с помощью конечных автоматов. 

• Другие формы порождающих грамматик

  • Существуют расширенные формы грамматик, такие как смежные с деревьями, аффинные и атрибутивные грамматики, которые повышают выразительность или облегчают анализ. 
  • Рекурсивные и аналитические грамматики также являются важными расширениями. 

• Примеры формализмов аналитической грамматики

  • Примеры включают язык синтаксического анализа сверху вниз, связующие грамматики и грамматики синтаксического анализа выражений.