Jednou z možností, jak popsat formální jazyk, je použití formální gramatiky. Jedná se v podstatě o množinu syntaktických pravidel, kterými lze ověřit, zda nějaké slovo do jazyka popsaného danou gramatikou patří, či nikoliv, a teoreticky také všechna slova vygenerovat, pokud je jejich množina konečná.
Formální gramatika €G€ je čtveřice €(N, T, P, S)€, kde €N€ je konečná množina neterminálních symbolů (neterminálů), €T: T \cap N = \varnothing€ je konečná množina terminálních symbolů (terminálů), €P€ je konečná množina odvozovacích pravidel ve tvaru €(T \cup N)^* N (T \cup N)^* \longrightarrow (T \cup N)^* € a €S \in N€ je počáteční symbol.
Pro zpřehlednění a zkrácení zápisu se pravidla často zapisují v tzv. Backus-Naurově formě, která umožňuje příbuzná pravidla sloučit do jednoho řádku.
Terminály budou pro přehlednost psány malými písmeny, neterminály velkými.
Definujme gramatiku, která generuje jednoduché výroky. Množina terminálů je malý, velký, pes, kocour, běží, leží, spí, množina neterminálů VÝROK, PŘÍVLASTEK, PODMĚT, PŘÍSUDEK a počáteční symbol je VÝROK. Pravidla budou následující:
Nyní zkusíme vygenerovat nějaké výroky. Začneme u počátečního symbolu a postupně aplikejeme některé z možných pravidel:
Definujme gramatiku, která generuje aritmetické výrazy. Množina terminálů je (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, množina neterminálů VÝRAZ, ČÍSLO, ČÍSLICE, OPERÁTOR a počáteční symbol bude VÝRAZ. Pravidla budou následující:
Opět zkusíme vygenerovat nějaké výroky. Začneme u počátečního symbolu a postupně aplikujeme některé z možných pravidel: