sono scritte utilizzando linguaggi compilati, mentre i linguaggi interpretati
vengono utilizzati quasi esclusivamente per scopi particolari o in fase di prova.
3.1 Introduzione sulla teoria dei linguaggi formali
La teoria dei linguaggi formali studia gli insiemi di stringhe, cioè i linguaggi
formali, e le loro proprietà seguendo vari approcci.
●
Approccio generativo:un linguaggio viene definito come l'insieme di
tutte e sole le stringhe che vengono prodotte da una grammatica
generativa, da un sistema di Lyndenmayer o da qualche altro sistema di
riscrittura.
Esempi:
Grammatiche di Chomsky
Forma di Backus Naur(BNF)
Linguaggi di marcatura(HTML,XML)
●
Approccio riconoscitivo: un linguaggio viene definito come l'insieme di
tutte e sole le stringhe che vengono accettate da un automa.
Esempi:
Automi a stati finiti – Analizzatori lessicali(scanner)
Automi a pila – Analizzatori sintattici(parser)
●
Approccio algebrico:un linguaggio viene definito attraverso sue
proprietà algebriche, in particolare proprietà riconducibili alla teoria dei
semigruppi e alle algebre di Kleene.
Esempio:
Espressioni regolari(vedi anche Lex o Luthorj)
●
Approccio trasformazionale: un linguaggio viene definito come
ottenuto sottoponendo a una data trasformazione un altro linguaggio,
46