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.

Příklady

Terminály budou pro přehlednost psány malými písmeny, neterminály velkými.

Jednoduché výroky

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í:

1. VÝROK → PŘÍVLASTEK PODMĚT PŘÍSUDEK
2. PŘÍVLASTEK → malý
3. PŘÍVLASTEK → velký
4. PODMĚT → pes
5. PODMĚT → kocour
6. PŘÍSUDEK → běží
7. PŘÍSUDEK → leží
8. PŘÍSUDEK → spí

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:

1. VÝROK
2. PŘÍVLASTEK PODMĚT PŘÍSUDEK (použité pravidlo: 1)
3. malý PODMĚT PŘÍSUDEK (použité pravidlo: 2)
4. malý pes PŘÍSUDEK (použité pravidlo: 4)
5. malý pes spí (použité pravidlo: 8)

Aritmetické výrazy

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í:

1. VÝRAZ → VÝRAZ OPERÁTOR VÝRAZ
2. VÝRAZ → ČÍSLO
3. VÝRAZ → ( VÝRAZ )
4. ČÍSLO → ČÍSLICE ČÍSLO
5. ČÍSLO → ČÍSLICE
6. OPERÁTOR → +
7. OPERÁTOR → -
8. ČÍSLICE → 0
9. ČÍSLICE → 1
10. ČÍSLICE → 2
11. ČÍSLICE → 3
12. ČÍSLICE → 4
13. ČÍSLICE → 5
14. ČÍSLICE → 6
15. ČÍSLICE → 7
16. ČÍSLICE → 8
17. ČÍSLICE → 9

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:

1. VÝRAZ
2. VÝRAZ OPERÁTOR VÝRAZ (použité pravidlo: 1)
3. ( VÝRAZ ) OPERÁTOR VÝRAZ (použité pravidlo: 3)
4. ( VÝRAZ OPERÁTOR VÝRAZ ) OPERÁTOR VÝRAZ (použité pravidlo: 1)
5. ( ČÍSLO OPERÁTOR VÝRAZ ) OPERÁTOR VÝRAZ (použité pravidlo: 2)
6. ( ČÍSLO OPERÁTOR ČÍSLO ) OPERÁTOR VÝRAZ (použité pravidlo: 2)
7. ( ČÍSLO OPERÁTOR ČÍSLO ) OPERÁTOR ČÍSLO (použité pravidlo: 2)
8. ( 5 OPERÁTOR ČÍSLO ) OPERÁTOR ČÍSLO (použité pravidlo: 5)
9. ( 5 OPERÁTOR ČÍSLICE ČÍSLO ) OPERÁTOR ČÍSLO (použité pravidlo: 4)
10. ( 5 OPERÁTOR 1 ČÍSLO ) OPERÁTOR ČÍSLO (použité pravidlo: 9)
11. ( 5 OPERÁTOR 1 ČÍSLICE ) OPERÁTOR ČÍSLO (použité pravidlo: 5)
12. ( 5 OPERÁTOR 14 ) OPERÁTOR ČÍSLO (použité pravidlo: 12)
13. ( 5 OPERÁTOR 14 ) OPERÁTOR ČÍSLICE (použité pravidlo: 5)
14. ( 5 OPERÁTOR 14 ) OPERÁTOR 5 (použité pravidlo: 13)
15. ( 5 + 14 ) OPERÁTOR 5 (použité pravidlo: 6)
16. ( 5 + 14 ) - 5 (použité pravidlo: 7