Согласно Хомскому, формальные грамматики делятся на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие всех её правил (продукций) некоторым схемам.

Тип 0 — неограниченные

·        Тип 0.  Произвольные грамматики (грамматики  с фразовой структурой, или без ограничений)

§  На структуру их правил таких грамматик не накладывается никаких ограничений, т.е. правила имеют вид:   

§  Это самый общий тип грамматик. Грамматики, которые относятся только к этому и не могут быть отнесены ни к какому другому типу, являются самыми сложными по структуре.

·        Тип 1– Контекстно-зависимые (КЗ) (неукорачивающие грамматики)

§  Имеют правила вида

§  В КЗ-грамматиках при построении предложений заданного языка один и тот же нетерминальный символ может быть заменен различными терминальными цепочками в зависимости от контекста, в котором он встречается.

§  При построении компиляторов такие грамматики не применяются, поскольку языки программирования имеют более простую структуру и могут быть построены с помощью грамматик других типов.

·        Тип 2 – Контекстно-свободные (КС) грамматики

§  Имеют правила вид   

§   Характерная особенность – в левой части правил всегда один нетерминальный символ, в правой части у них стоит всегда хотя бы один символ.

§  КС-грамматики широко используются при описании синтаксических конструкций языков программирования.

·        Тип 3 – Автоматные (регулярные) грамматики

§  К этому типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные.

§  Леволинейные грамматики могут иметь правила двух видов: 

§  Праволинейные грамматики имеют правила тоже двух видов

§  Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т.д.