Introduction aux grammaires

Au sens littéraire du terme, les grammaires désignent des règles syntaxiques pour la conversation dans les langues naturelles. La linguistique a tenté de définir les grammaires depuis la création de langues naturelles comme l'anglais, le sanskrit, le mandarin, etc.

La théorie des langages formels trouve son applicabilité largement dans les domaines de l'informatique. Noam Chomsky a donné un modèle mathématique de grammaire en 1956 qui est efficace pour écrire des langages informatiques.

Grammaire

Une grammaire G peut être formellement écrit comme un 4-tuple (N, T, S, P) où -

N ou V_N est un ensemble de variables ou de symboles non terminaux.
T ou ∑ est un ensemble de symboles Terminal.
S est une variable spéciale appelée le symbole de départ, S ∈ N
Pest les règles de production pour les terminaux et les non-terminaux. Une règle de production est de la forme α → β, où α et β sont des chaînes sur V _N ∪ Σ et moins un symbole de α appartient à V _N .

Exemple

Grammaire G1 -

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

Ici,

S, A, et B sont des symboles non terminaux;
a et b sont des symboles de borne
S est le symbole de départ, S ∈ N
Productions, P : S → AB, A → a, B → b

Exemple

Grammaire G2 -

(({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})

Ici,

S et A sont des symboles non terminaux.
a et b sont des symboles de borne.
ε est une chaîne vide.
S est le symbole de départ, S ∈ N
Production P : S → aAb, aA → aaAb, A → ε

Dérivations d'une grammaire

Les chaînes peuvent être dérivées d'autres chaînes en utilisant les productions d'une grammaire. Si une grammaireG a une production α → β, on peut dire ça x α y dérive x β y dans G. Cette dérivation s'écrit -

x α y ⇒G x β y