Linguaggi di programmazione : sintassi e semantica

Introduzione: linguaggi formali e naturali

Nello studio dei linguaggi naturali (italiano, inglese ...) vi sono due componenti fondamentali la sintassi e la semantica . La prima si occupa della forma delle frasi (ossia del come un insieme di simboli elementari può essere messo assieme per ottenere una frase corretta) mentre la semantica si occupa del loro significato (assegna un significato ai simboli ed alle loro concatenazioni). La forma di una frase è: l'insieme delle regole da rispettare per costruirla. Nei linguaggi di programmazione (“artificiali o formali” tipo il Pascal , il C…) esiste la medesima analogia, nel senso che con sintassi si intende: l' insieme delle regole da rispettare per costruire, tutti e soli, i programmi ( 'frasi' ) legali nel linguaggio, mentre la semantica si occupa delle regole, che governano l'attribuzione di un significato ai programmi del linguaggio.

Linguaggi e Grammatiche

Un linguaggio di programmazione e’ un linguaggio artificiale o formale ; implementare un linguaggio, significa rendere una macchina in grado di eseguire i programmi di quel linguaggio, oppure realizzare un traduttore che rende eseguibili su un certo calcolatore i programmi.

Introduciamo adesso alcune definizioni rigorose per descrivere la sintassi di un linguaggio

Definizione

Dato un insieme finito non vuoto V , si definisce Universo linguistico su V e lo indichiamo con V* l’insieme delle sequenze finite di lunghezza arbitraria di elementi di V.

V è detto vocabolario o lessico; gli elementi del vocabolario V sono detti simboli o caratteri terminali. Ad esempio il vocabolario V, può essere costituito dall’insieme delle lettere dell’alfabeto italiano, dove in questo caso i simboli coincidono con le lettere.

V={a, b, c, d, e,……,u, v, z }

Gli elementi dell’ universo linguistico V* vengono detti stringhe o frasi, costruite sul vocabolario V.

Ad esempio il vocabolario del linguaggio C sarà del tipo:

V= { if, else, while, do, ‘0’, ’1’, …’9’, {, }, int, struct,….}

Definizione

Dato un vocabolario V si definisce, come linguaggio L , sull’alfabeto V un qualunque sottoinsieme di V*, cioè L= insieme delle espressioni (frasi) corrette usando gli elementi di V.

Il vocabolario V è finito, V* no; cioè V* ha cardinalità non numerabile; comunque a noi interessano soltanto i sottoinsiemi di V* che sono descrivibili in maniera finita.

* (nel seguito con il simbolo a intendiamo alfa , con B beta , con E eta ,con C gamma e con D delta )

Definiamo adesso una grammatica o sintassi G per descrivere un linguaggio LG, dove con il termine descrivere, intendiamo (riconoscere se una data stringa/frase B Î V* appartiene al linguaggio ).

Definizione

Una grammatica o sintassi G

e‘ definita da una quadrupla: < V, N, S, P >

Dove

V indica un alfabeto di simboli terminali (Vocabolario);

N indica un alfabeto di simboli non terminali;

S indica un assioma o simbolo iniziale o anche simbolo distinto con S Î N tale che V Ç N = Æ;

P indica un insieme finito di regole sintattiche (o Produzioni) del tipo

X ---> a o anche X ::= a , dove X Î N ed a Î ( N U V ) * .

Una produzione si applica ad un simbolo non terminale e produce una combinazione finita di simboli terminali e non terminali.

Se usiamo la convenzione X ::= a i simboli non terminali sono racchiusi da parentesi angolari, per distinguerli dai simboli terminali; esempio <frase>,<cifra>.

Invece usando la convenzione X ---> a i simboli non terminali sono scritti in corsivo ed i terminali tra apici “a”, “b”,……

Usiamo la convenzione di scrivere X---> a1 | a2 | a3 | ... | an , “alfa1 oppure alfa2 oppure alfa3…oppure alfan deriva da X” se in una grammatica, esistono più regole aventi la medesima parte sinistra del tipo

X ---> a1 , X ---> a2 , X ---> a3 ,..., X ---> an .

Esempio G italiana “ ESEMPIO DI GRAMMATICA ITALIANA ”

V italiano = {il, lo, topo, gatto, mangia, sasso, beve }

N italiano = {<frase>, <soggetto>, <complemento oggetto >, <verbo>, <nome>, <articolo> }

S italiano = <frase>

P italiano = { <frase>::= <soggetto> <verbo> < complemento oggetto> }

<verbo>::=mangia | beve " il simbolo | significa oppure"

<complemento oggetto>::= <articolo> <nome> (articolo seguito da un nome)

<nome>::= sasso | gatto | topo }

chiariamo il significato della seguente:

<frase>::= <soggetto> <verbo> < complemento oggetto>

La riga si legge: il non terminale frase è definito come (::=) il non terminale soggetto, seguito dal non terminale verbo, seguito dal non terminale complemento oggetto.

Con la scrittura G ---> LG intendiamo, che ad una grammatica corrisponde un linguaggio (LG = linguaggio generato/riconosciuto dalla G )

Le regole, applicate a partire dal simbolo iniziale su categorie sintattiche permettono di riconoscere che B Î LG (o di non riconoscere!)

Es. il gatto mangia il topo appartiene ad LG italiana mentre lupo il beve sasso non appartiene al linguaggio della grammatica italiana ( Ï LG italiana )

Riconoscimento º Derivazione

Definizione

Data una grammatica G e due stringhe

B , C ( beta e gamma ) Î ( N U V ) * si dice che C deriva direttamente da B in G e si scrive B ---> C

( derivazione diretta “ generazione”) se le stringhe si possono decomporre trovando parti comuni B = E C D e C = E a D

Con E , a , D appartenenti ad ( N U V )* e X appartenente ad N ed esiste una produzione

X ---> a appartenente a P .

Esempio

il <nome><verbo> il topo

-->il gatto <verbo> il topo

avremo che :

E = il

D = <verbo> il topo

X = <nome> e X ® gatto appartenente a P italiano

Le stringhe nella definizione di sopra a , B , D ( alfa beta e delta ) possono anche essere vuote.

Si può definire una catena di derivazione dirette:

B0 --> B1 --> B2--> .... Bn-1 --> Bn

coincidente con B0 ---> n Bn

Definizione

Data una grammatica G e due stringhe B , C Î ( N È V ) * , si dice che C deriva da B e si scrive B ---> * C ,

se $ n >=0 : B --> nC

Definizione

Data una grammatica G, si dice linguaggio generato da G e si indica con LG l’insieme delle frasi di V* derivabili a partire dall’ assioma S;

LG = Linguaggio generato da G ( dove generato = riconoscibile ) = { B appartenti a V* tale che S ---- > *B } = Tutte le stringhe derivabili a partire dall’assioma S .

Definizione

Un linguaggio di programmazione L su un alfabeto V e’ un sottoinsieme di V* : $ una grammatica G : L = LG .

Le stringhe o frasi di un linguaggio di programmazione vengono dette programmi “di tale linguaggio”.

Esempio

LG italiana = { sequenza di elementi Î V italiano

derivabili ( riconoscibili come ) da <frase> }

il gatto	mangia	il topo	Bn
E	C
il gatto	<verbo>	il topo	Bn-1
E D
<articolo>gatto	<verbo>	il topo	.
.	.	.
<articolo><nome>	<verbo>	il topo	.
.	.	.
<soggetto>	<verbo>	il topo	.
.	.
<soggetto> <verbo> <complemento oggetto>			B1
.
<frase>			B0

<frase> ---> * il gatto mangia il topo

invece la <frase> ---> * gatto mangia il il è scorretta

Un modo più agevole consiste nel costruire l’ albero sintattico della stringa da riconoscere:

Forma di Backus-Naur BNF

Il formalismo che abbiamo introdotto nelle definizioni su menzionate è un metalinguaggio (un linguaggio utilizzato per parlare di un altro linguaggio) formale che si chiama BNF o meglio EBNF Exetended Backus Naur Form. In BNF le produzioni vengono indicate solitamente con il simbolo ::= .

Scrivendo X ---> [ a] B intendiamo dire che il simbolo alfa è opzionale, nel senso che può comparire o non comparire ossia

X ---> B | aB , mentre con la scrittura X ---> { a }^n B

Intendiamo dire che da X si può derivare B ,aB, aaB ... ,(aa...a)B con 0, 1, 2, ..., n volte che compare il simbolo a .

Un esempio di metalinguaggio usato correntemente da noi può essere il seguente:

il verbo essere in inglese si dice to be ( stiamo usando come metalinguaggio l’italiano per descrivere un altro linguaggio l’inglese ).

Esempi di sintassi EBNF applicata al linguaggio C

<istruzione if> ::= if < ( espressione logica )>< istruzione>[else <istruzione>]

Il significato di questa sintassi è il seguente:

L' istruzione if consiste della parola chiave if seguita da una espressione logica, fra parentesi tonde, seguita da una istruzione, seguita (dalla parola chiave else seguita da una istruzione che sono opzionali).

Il lessico , ossia l'insieme dei simboli terminali di un linguaggio di programmazione assieme ad un insieme di regole EBNF, ci permette di dare la definizione della sintassi di un linguaggio di programmazione. Il lessico è costituito da un alfabeto finito di parole chiave ( Nel linguaggio C sono if, else , while,{, }, struct ...) da simboli speciali ( :, ; +, *, .....) e da un alfabeto di caratteri e cifre ( 'a' .. 'z', '0'...'9' ) .

<identificatore>::=<lettera>{<lettera-cifra>}^n

ossia un identificatore consiste di una sequenza di lettere e cifre, di cui la prima deve essere una lettera.

< istruz. while >::= while < espressione logica > < istruzione >

< istruz. semplice > ::= < assegnazione > | < input > |<output>....

< istruz. controllo > ::= < istruz. while > | < istruz. if > | <istruz. for >.....

< istruz. non composta > ::= < istruz. semplice > | < istruz. controllo >

< istruzione > ::=

< istruz. non composta > | <istruz. composta>

< istruz. composta > ::= { < istruz. non composte > }

ossia una istruzione composta consiste dalla parola chiave { seguita da un certo numero maggiore uguale a due di istruzioni non composte e terminante con la parola chiave } .

< sequenza istruzioni > ::= { <istruzioni non composte>}

::= < istruz. non composte> |

< istruz. non composte > < sequenza di istruzioni>

Diagrammi sintattici

Sono delle forme grafiche ( grafi di flusso ) per esprimere le regole di una grammatica che coincidono col percorso da seguire, da sinistra a destra, per riconoscere una stringa . I nodi del grafo vengono etichettati con i simboli terminali e non terminali del linguaggio; i nodi sono collegati con archi orientati ; la presenza di un arco da un nodo < n1 > ad un nodo < n2 > significa che il simbolo < n1 > e’ seguito dal simbolo < n2 >. La presenza di piu’ di un arco in uscita od in ingresso ad un nodo significa una alternativa. Per comodita’ si possono introdurre dei nodi fittizi.

Esempio

Esempio : INTERI SENZA SEGNO

Abbiamo che :

V = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

N = { < intero senza segno >, < cifra > , < cifra non 0 > }

S = { intero - senza - segno}

P =

a) < intero - senza - segno > ::=

una cifra non 0 opzionale seguita da una cifra coincide : con una cifra non 0 seguita da una cifra, oppure nel caso non c‘e’ la cifra non 0, con una cifra :

[ < cifra non 0 > ] < cifra > = < cifra non 0 > < cifra > | < cifra >

b) una cifra consiste di una cifra non 0 oppure 0 :

< cifra > ::= < cifra non 0 > | 0