●
LR1 riflesso
3.3 Grammatiche, linguaggi context-free
Le grammatiche formali sono un metodo di costruzione delle stringhe del
linguaggio basato sul concetto di riscrittura.
1914
Axel Thue studia i primi problemi di riscrittura.
1943
Emil Post definisce sistemi di produzione
1947
A.A. Markov definisce algoritmi basati su regole di riscrittura.
1956
N. Chomsky introduce le grammatiche formali nell'ambito degli studi
sul linguaggio naturale.
1960
J.W.Backus e P. Naur introducono la BNF per descrivere la sintassi del
linguaggio Algol.
Le Grammatiche di Chomsky
Def. Una grammatica formale G = è caratterizzata da:
●
VT(Σ) alfabeto finito di simboli detti terminali,
●
VN alfabeto di simboli non terminali
●
P, detto insieme di produzioni, è una relazione binaria finita su (VT U
VN)*VN(VT U VN)* x (VT U VN)*
<α,β> ∈ P si indica con α → β
●
S ∈ VN è detto assioma.
Le grammatiche di Chomsky costituiscono un metalinguaggio poiché ogni
grammatica descrive un linguaggio.
Def. Il linguaggio generato da una grammatica è l'insieme delle stringhe di
terminali ottenibili con una sequenza finita di passi di riscrittura consistenti
nell'applicazione delle regole di produzione.
50