Sono un modo di descrivere linguaggi. Permettono di descrivere caratteristiche ricorsive delle stringhe riconosciute. Per questo sono utili per descrivere linguaggi umani e linguaggi di programmazione.
Una grammatica acontestuale consiste in un insieme di regole di sostituzione, anche chiamate produzioni, scritte nel formato . Le variabili (indicate con lettere maiuscole) sono simboli da sostituire, mentre le stringhe sono sequenze di variabili e terminali, altri simboli dell’alfabeto. Una delle variabili è la variabile iniziale, scritta a sinistra nella prima regola.
Esempio di derivazione (sequenza di simboli per ottenere una stringa) di “00#11” nella seguente grammatica:
Si dice che genera ; scritto come: .
N.B.: Più regole e possono essere abbreviate in .
Linguaggi acontestuali
Il linguaggio di una grammatica acontestuale, cioè l’insieme di tutte le stringhe che possono essere generate dalla suddetta grammatica, è detto context free language (linguaggio acontestuale).
I linguaggi regolari sono linguaggi acontestuali.
Definizioni formali
Una grammatica acontestuale è una quadrupla dove:
- sono le variabili. Esse non sono simboli dell’alfabeto,
- è l’alfabeto,
- solo le regole,
- è la variabile iniziale.
Il linguaggio di una grammatica acontestuale è .
La derivazione di una stringa di una grammatica si dice derivazione leftmost se a ogni step la variabile più a sinistra della stringa viene rimpiazzata.
Una stringa si dice derivata ambiguamente in una grammatica acontestuale se ha una o più dericazioni leftmost.
Una grammatica si dice ambigua se genera ambiguamente almeno una stringa.
Esercizi: formalizzare le descrizioni dei seguenti linguaggi in CFG
1.
Stringhe binarie con almeno 3 uno

2.
vuol dire palindroma.
3.
?
Implementazione mia su python
def derive_from(string, grammar, iterations, i=0, path=None):
if path is None:
path = []
if i > iterations:
return
if not any([var in string for var in grammar.keys()]):
print(*path, string, sep=' -> ')
for variable, substitutions in grammar.items():
if variable in string:
for substitution in substitutions:
path.append(string)
derive_from(
string.replace(variable, substitution, 1),
grammar,
iterations,
i+1,
path
)
path.pop()
G = {
'A': ['0A1', 'B'],
'B': ['#']
}
derive_from('A', G, 5)output:
A -> 0A1 -> 00A11 -> 000A111 -> 000B111 -> 000#111
A -> 0A1 -> 00A11 -> 00B11 -> 00#11
A -> 0A1 -> 0B1 -> 0#1
A -> B -> #
Altro esempio
G = {
'START': ['Hi! SENTENCE'],
'SENTENCE': ['I am PERSON', 'I know a PERSON', 'have a nice TIME in PLACE!', 'I really like ACTIVITY in PLACE', 'I really like ACTIVITY in PLACE in the TIME'],
'PLACE': ['Rome', 'Paris'],
'TIME': ['morning', 'evening'],
'PERSON': ['a GENDER who PREFERENCE ACTIVITY in the TIME', 'a GENDER from PLACE who PREFERENCE ACTIVITY in the TIME'],
'PREFERENCE': ['likes', 'hates', 'would like'],
'GENDER': ['boy', 'girl'],
'ACTIVITY': ['running', 'skating', 'singing']
}
derive_from('START', G, 8)
# Esempi output:
# Hi! have a nice time in Paris!
# Hi! I know a girl from Rome who likes singing in the morning
# Hi! I really like skating in Rome