Формальные грамматики – это математическая модель синтаксиса языков,естественных и искусственных, используемая, в частности, для синтаксического анализа. Впервые грамматики были строго сформулированы в конце 50-х гг. XX века, и в таком виде они и вошли в стандартные курсы информатики. Современное состояние дел в этой области будет представлено на предлагаемых лекциях. Будут описаны основные известные разновидности грамматик, отличающихся как по своим выразительным возможностям, так и по сложности алгоритмов синтаксического анализа. Эти разновидности будут соотнесены с основными классами вычислительной сложности.