Grammatiche libere dal contesto

Una grammatica libera del contesto (Context-Free Grammar, CFG) è una quadrupla $G=\lang V, T, \Gamma, S\rang$ in cui:

• $V$ è un insieme finito i cui elementi sono detti simboli non-terminali (o variabili o ancora categorie sintattiche)
• $T$ è un insieme finito i cui elementi sono detti simboli terminali
• $\Gamma$ è l’insieme finito delle regole di produzione, ciascuna delle quali è una coppia $A\rarr \alpha$, dove:
  • $A\in V$ è un simbolo non-terminale, che prende il nome di testa o lato sinistro della (regola di) produzione
  • $\alpha \in (V \cup T)^*$ è una sequenza di terminali e non-terminali, chiamata corpo o lato destro della produzione
• $S\in V$ è il simbolo iniziale della grammatica

Il significato di questi elementi verrà formalizzato più avanti, ma sostanzialmente:

• i simboli non-terminali rappresentano elementi sintattici del linguaggio
• i simboli terminali sono quelli che compaiono concretamente nelle stringhe del lingauggio
• le regoe di produzione indicano come sostituire ciascun simbolo non-terminale con sequenze di altri simboli (terminali e non-terminali) per generare le stringhe del linguaggio
• il simbolo iniziale è il simbolo non-terminale a partire dal quale vengono generate le stringhe del linguaggio

Esempio: linguaggio dei palindromi

Esempio: linguaggio delle espressioni

Backus-Naur form

Nelle applicazioni pratiche delle CFG è tipicamente necessario rappresentarle in forma testuale, mediante una sintassi concreta che sia facilmente manipolabile tramite un editore di testo. Una tale sintassi concreta è la Backus-Naur form, BNF. Essa è sostanzialmente simile alla rappresentazione usata finora, con due principali differenze:

• i simboli non-terminali sono racchiusi tra parentesi angolari, $\texttt{<>}$
• la freccia delle regole di produzione è sostituita dal simbolo $\texttt{::=}$

Ad esempio, la rappresentazione in BNF della grammatica delle espressioni vista prima è: