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 VN 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
Exemple
Considérons la grammaire -
G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})
Certaines des chaînes qui peuvent être dérivées sont -
S ⇒ aA b en utilisant la production S → aAb
⇒ a aA bb en utilisant la production aA → aAb
⇒ aaa A bbb utilisant la production aA → aAb
⇒ aaabbb en utilisant la production A → ε