Sintassi (prima parte)

Giuseppe Morelli

Introduzione

• Abbiamo già visto come la fase di analisi di un compilatore consente di suddividere un programma sorgente in “pezzi” e produce una rappresentazione interna (codice intermedio)

• L’analisi è organizzata attorno alla sintassi del linguaggio in cui il programma sorgente è scritto.– Sintassi: descrive la forma di un programma

– Semantica: descrive cosa il programma fa quando è in esecuzione

• La specifica della sintassi viene fatta secondo la notazione delle Grammatiche Context Free

Grammatiche [Context Free] - definizioni

• Una grammatica descrive naturalmente la struttura gerarchica della maggior parte costrutti dei diversi linguaggi di programmazione; es:– If (expression) statement else statement

• Si tratta della concatenzione di più elementi

• Utilizzando un’altra notazione può essere espressa come

stmt -> if (expr) stmt else stmt

• Una regola così fatta è chiamata produzione

stmt -> if (expr) stmt else stmt

• If , (, ), else sono detti simboli Terminali

• stmt, expr sono sequenze di simboli terminali e sono detti simboli non terminali

• La -> si legge “può avere la forma”

• I simboli non terminali in corsivo

• Lettere in Neretto, non corsivo, digits ed operatori, aritmetici e ralazionali sono terminali

Definizione di grammatica

1. Un insieme di simboli terminali (token)2. Un insieme di non terminali (variabili sintattiche)3. Un insieme di produzioni,dove ognuna consiste

di: 1. Un simbolo non terminale (head or left side)2. Una freccia 3. Una sequenza di simboli terminali e/o non

terminali (body or right side); permette di specificare un costrutto

4. Un simbolo non terminale è designato quale Iniziale (Start symbol)

.. continua

• Una grammatica è specificata attraverso la lista delle sue produzioni.

• La produzione per il simbolo iniziale è posizionata in testa alla lista

• Le produzioni con lo stesso simbolo non terminale come Head (left side) hanno il corpo (body) accorpato ovvero i diversi bodies sono separati dal simbolo | (or)

• NOTA: equivalenza tra token e simboli terminali

Esempio (ricorrente)

• Costruiamo una grammatica in grado di rappresentare l’espressione 9 -5 +2, e simililist -> list + digitlist -> list – digitlist -> digitdigit -> 0|1|2|3|4|5|6|7|8|9

• In pratica stiamo affermando che chiamiamo list due o più digit separati da + o –

• In sintesilist -> list + digit | list – digit | digitdigit -> 0|1|2|3|4|5|6|7|8|9

Derivazione

• Una grammatica deriva una stringa, iniziando con il simbolo iniziale e rimpiazzando ripetutamente un simbolo non terminale con la produzione per lo stesso simbolo.

• L’insieme delle stringhe derivabili a partire del simbolo iniziale si dice il linguaggio definito dalla grammatica.

Esempio

• Si consideri la grammatica:1. list -> list + digit2. list -> list – digit3. list -> digit4. digit -> 0|1|2|3|4|5|6|7|8|9

• La stringa 9-5+2 può essere derivata(dedotta):1. Il 9 è una list (3) poichè 9 è un digit (4)2. 9-5 è una list poiché 9 è list e 5 è digit (2)3. 9-5+2 è una list poiché 9-5 è list e 2 è digit

(1)

Esempio

• Supponiamo di voler scrivere la grammatica e voler riconoscere una chiamata a funzione con relativa lista parametri ( nomefunz(x,y) ).1. Call -> id ( optparams )2. Optparams -> params | E3. Params -> params, params | param4. Param ????? (dipende dal linguaggio …..)

• Note:1. Lista dei parametri può essere vuota2. Params coincide con la definizione di list esempio

precedente (, al posto di + e – e param per digit)

Parsing

• È il nome del problema di prendere una stringa di simboli terminali e mostrare come è possibile derivarla a partire dal simbolo iniziale della grammatica.

• Nel caso la derivazione non possa avvenire permette di segnalare errori di sintassi nella stringa

• Il parsing è propedeutico alla esecuzione del lexer (lessemi --- Token)

• Negli esempi successivi si partirà sempre da stringhe di terminali

Alberi di parsing

• Un albero sintattico permette di illustrare il procedimento di parsing ovvero come si può derivare una stringa del linguaggio a partire dal simbolo iniziale della grammatica

• Sia A un generico simbolo non terminale che ha a produzione A->XYZ, il suo “parse tree” avrà un nodo interno etichettato con A con tre figli etichettati da sinistra a destra con X,Y, e Z ovvero:

A

X Y Z

..continua

• Data una grammatica context free, il suo albero sintattico è un albero con le seguenti caratteristiche:1. La root è etichettata con il simbolo iniziale2. Ogni foglia è etichettata con un simbolo terminale3. Ogni nodo interno è etichettato con un simbolo non-

terminale4. Se A è un non terminale che etichetta un nodo

interno e X1, X2, …. , Xn sono etichette per i figli di detto nodo allora la grammatica deve possedere la produzione A -> X1 X2…. Xn

Esempio

• Esperssione 9-5+2

1. list -> list + digit

2. list -> list – digit3. list -> digit4. digit -> 0|1|2|3|4|5|6|7|8|

9

digit

digit

digitlist

list

list

9 - 5 + 2

Start symbol (1)

9-5 (2) 2 (4)

9 (3)

9 (4)

5 (4)

Yield ()

Stringa derivata o generata

Ambiguità

• Una grammatica si dice ambigua quando un stringa di terminali può essere generata da due o più parse tree.

• Ciò dipende da come vengono scritte le produzioni

• Per la realizzazione dei applicazioni di compilazione è necessario scrivere grammatiche non ambigue, o utilizzare grammatiche ambigue ma con regole addizionali che permetto di risolvere tali ambiguità.

Esempio

1. list -> list + list

2. list -> list – list 3. list -> 0|1|2|3|4|5|6|7|8|9

list

list

list

9 - 5

+

2list

list list

list

list

5 + 2

-

9list

list

9-5+2

Associatività degli operatori

• La proprietà associativa, in presenza di una espressione in cui un operando compare fra due operatori, ci permette di scegliere quale operatore applicare all’operando.

• Quando si dice che l’operatore + è associativo a sinistra significa che in presenza di un operando con due segni + (dx e sx) appartiene all’operatore di sinistra ( 9+5+2 - (9+5)+2 )

• Gli operatori + - * / sono associativi a sinistra• ^p è associativo a destra• Operatore di assegnazione = è associativo a

destra

Esempio

right -> letter = right right -> letterletter -> a | b | …. |z

• Permette di riconoscere stringe del tipo a=b=c e generarle attraverso l’albero:

• Nota sbilanciamento

b=

c

right

right

letter

=

a

letter

letter

right

Precedenza degli operatori

• Si consideri 9+5*2 • 2 interpretazioni possibili (9+5)*2 o 9+(5*2)• L’associatività a sinistra di entrambi non aiuta• Quando sono presenti differenti tipi di operatore

è necessario definire delle regole di precedenza• Un operatore ha precedenza maggio re rispetto

ad un altro quando prende l’operando prima dell’altro

• * ha precedenza maggiore rispetto a + così l’espressione precedente è valutata come 9+(5*2)

Esempio: espressioni aritmetiche

• l’associatività è evidenziata esplicitamenteleft-associative +,- ……(expr)left-associative *,/ ……(term)expr -> expr + term | expr – term | termterm -> term * factor | term / factor | factorfactor –> digit | (expr)• Attraverso i due non terminali vengono

evidenziati i livelli di precedenza (+,- e *,/)

Parse tree di espressioni aritmetiche

expr -> expr + term | expr – term | termterm -> term * factor | term / factor | factorfactor –> digit | (expr)

Deriviamo: 9+5*2

factor

factor

expr term

term

5 * 2+

expr

factor

term

9

Esercizio

• Consideriamo la grammaticaS -> S S + | S S * | a- Mostrare che aa+a* può essere generata dalla

grammatica- Costruire l’albero di parsing

Esercizi

• Quali linguaggi sono generati dalle grammatiche:A. S -> 0 S 1 | 01B. S -> + S S | - S S | aC. S -> S ( S ) S | εD. S -> a S b S | b S a S | εE. S -> a | S + S | S S | S* | ( S )