Formalnie gramatykę G określamy jako:
G= <V, T, P, S >
gdzie:
V- zbiór symboli terminalnych- skończony niepusty zbiór symboli zwany także alfabetem końcowym (zasadniczym ) gramatyki G. alfabet końcowy jest to zbiór elementów pierwotnych, z których budowane są słowa generowane przez gramatykę.
T- zbiór symboli nieterminalnych- skończony niepusty zbiór symboli zwany także alfabetem pomocniczym. Alfabet pomocniczy jest to zbiór symboli, którymi oznacza się klasy lub słowa złożone z elementów pierwotnych, czyli inaczej jest to słownik typów syntaktycznych.
P- lista produkcji- są to reguły gramatyki, czyli skończony zbiór reguł
S- głowa- symbol początkowy. Jest to wyróżniony symbol pomocniczy oznaczający klasę tych wszystkich obiektów językowych, dla których opisu przeznaczona jest gramatyka.
W teorii Chomskiego wyróżnia się cztery typy gramatyk. Gramatyki te wyodrębnia się przez nakładanie kolejno coraz silniejszych ograniczeń na układ reguł P:
- gramatyka klasy 0 - charakteryzuje się tym , że wszystkie produkcje mają postać: u→w, u∈V*\ {ε}, w ∈V*,
- gramatyka klasy 1- zwana kontekstową, nazywa się gramatykę charakteryzującą się tym, że wszystkie produkcje mają postać: uAw → ubw, u,w∈V*, A∈S , b∈V*\ {ε},
- gramatyka typu 2- zwana gramatyką bezkontekstową, która w układzie reguł P dopuszcza jedynie reguły postaci A→b, A∈S , b∈V*\ {ε},
- gramatyka klasy 3- (regularna), która w układzie reguł P dopuszcza reguły postaci A→bB (gramatyki prawostronnie regularne) albo A→Bb (gramatyki lewostronnie regularne), A∈S, B∈S∪ {ε}, b∈T*\ {ε}.