Une grammaire définit la syntaxe d'un langage. Etant donné un "alphabet" de lexèmes (c'est à dire de mots du langage), une grammaire décrit les façons de construire des phrases du langage (c'est à dire les suites de symboles qui vont être reconnues par la grammaire).
On distingue 4 grands types de grammaires:
-Les grammaires sans contrainte (où chaque phrase est composée d'un seul et unique mot)
-Les grammaires contextuelles (chaque phrase est composée d'une partie centrale encadrée de 2 mots, avec la partie centrale qui est elle-même une phrase)
-Les grammaires hors-contexte (il existe plusieurs types de décomposition d'une même phrase à une étape donnée)
-Les grammaires régulières (la partie droite ou gauche d'une phrase est elle-même une phrase).
Il existe de nombreux cours en ligne sur les grammaires. Voir en particulier:
http://www.iut-nantes.univ-nantes.fr/~habrias/spec2/grammaire.html
http://fastnet.univ-brest.fr/~gire/COURS/COMPIL_IUP/node39.html
Par exemple, la syntaxe du Pascal ou de Delphi, ainsi que de la plupart des langages de programmation sont des grammaires hors-contexte, voire même ambigües. Par exemple, si on considère la suite d'instructions:
if a then
if b then
Procedure1
else
Procedure 2;
Cette phrase de langage peut être décomposée de 2 façons différentes par la grammaire du Pascal:
if a then begin
if b then
Procedure1
else
Procedure 2;
end
ou aussi:
if a then begin
if b then
Procedure1
end else
Procedure 2;
Evidemment, dans les 2 cas le code ne fonctionnera pas de la même manière. C'est pourquoi la syntaxe du Pascal ne peut pas être décrite à l'aide d'une seule grammaire formelle au sens strict, on a besoin d'établir des règles de priorité (ici, le premier if est prioritaire dans la décomposition, c'est à dire que les compilateurs Pascal vont comprendre la première décomposition en cas d'ambiguité).
Voir aussi Analyse lexicale, Parser...