Appunti di Linguaggi e Modelli Computazionali

Linguaggi e Modelli Computazionali M

Matteo Galletti

Marco Boschi, Marco Rossini e Nicola Severini

A.A. 2017–2018

0 Introduzione 1

1 Linguaggi e macchine astratte 2

1.1 Gerarchia di macchine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1.1 Macchina combinatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.2 Automa a stati finiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.3 Macchine a stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.4 Macchina di Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.4.1 Macchina di Turing universale . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Teoria della computabilità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1 Procedimento di Gödel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.2 Funzioni computabili . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.2.1 Halt di Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.2.2 Linguaggi decidibili . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Linguaggi e grammatiche 7

2.1 Sintassi e semantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Interpreti vs compilatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 Analisi lessicale, sintattica e semantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.4 Grammatica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.4.1 Tipo 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4.2 Tipo 1 – Context dependant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4.3 Tipo 2 – Context free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4.4 Tipo 3 – Regolari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4.5 Gerarchia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Teorema 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Esempio 2.1 – Eliminazione di . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

ε-rule

n n n

Esempio 2.2 – . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

a b c

2.4.5.1 Riconoscere le grammatiche . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Esempio 2.3 – Finto self-embedding . . . . . . . . . . . . . . . . . . . . . . 11

2.4.5.2 Riconoscitori di linguaggi . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5 Grammatiche BNF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5.1 Extended-BNF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.6 Derivazioni canoniche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.7 La stringa vuota . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Teorema 2.2 – Teorema della stringa vuota . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.8 Forme normali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.8.1 Sostituzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Esempio 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.8.2 Raccoglimento a fattor comune . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Esempio 2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.8.3 Eliminazione della ricorsione a sinistra . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Esempio 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.8.4 Il pumping lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

i

2.9 Espressioni regolari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.9.1 Passaggi tra rappresentazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.9.1.1 Dalla grammatica all’espressione regolare . . . . . . . . . . . . . . . . . . 16

2.9.1.2 Dall’espressione regolare alla grammatica . . . . . . . . . . . . . . . . . . 16

Esempio 2.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Riconoscitori a stati finiti 17

Teorema 3.1 – Linguaggio non vuoto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Teorema 3.2 – Linguaggio infinito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1 Mapping tra grammatiche e riconoscitori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Esempio 3.1 – Stati finali multipli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Esempio 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1.1 Considerazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 Implementazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3 Automi non deterministici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3.1 Da automi non deterministici a deterministici . . . . . . . . . . . . . . . . . . . . . . 20

Teorema 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4 Riconoscitori PDA 22

Esempio 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.1 PDA non deterministici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Teorema 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2 PDA deterministici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.2.1 Analisi ricorsiva discendente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Ipotesi 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Esempio 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.3 Grammatiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

LL(k)

Esempio 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.3.1 Starter Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Esempio 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Domanda 4.1 – Perché la stringa vuota fa la differenza? . . . . . . . . . . . . . . . . 27

Esempio 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Domanda 4.2 – Come risolvere? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.3.2 Director symbol set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Domanda 4.3 – Il linguaggio generato da una grammatica è . . . . . . . . . 28

LL(1)?

4.3.3 Il problema della ricorsione sinistra . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Esempio 4.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.4 Oltre l’analisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

LL(k)

5 Dai riconoscitori agli interpreti 29

Domanda 5.1 – Cosa vuol dire dare significato a una frase? . . . . . . . . . . . . . . . . . . . . . . 29

5.1 Analisi lessicale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

Domanda 5.2 – Come gestisco le parole chiave? . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.2 Analisi sintattica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.2.1 Sintassi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.2.2 Semantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Esempio 5.1 – Differenza di semantica . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.2.3 Grammatica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.2.4 Ricorsione sinistra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.3 Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.3.1 Applicazione pratica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

ii

5.4 Valutatore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.4.1 Specificare la semantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.4.1.1 Semantica denotazionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Esempio 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.5 Alberi sintattici astratti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Esempio 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.5.1 Sintassi astratta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.5.2 Implementazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.5.3 Verifica del modello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Esempio 5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Esempio 5.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Esempio 5.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.5.4 Compilatore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.5.5 Valutatore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.5.5.1 Notazione prefissa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Esempio 5.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.5.5.2 Notazione infissa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.5.5.3 Notazione postfissa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Esempio 5.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

6 Stili di interpretazione 38

6.1 Funzione statica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6.1.1 Metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6.2 Soluzione polimorfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6.3 Pattern visitor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

7 L’interprete esteso 40

7.1 Assegnamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

7.1.1 Assegnamento multiplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

7.2 Estensione dell’interprete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

7.2.1 Nuove azioni semantiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

7.3 Verso il compilatore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

8 Riconoscitori LR 43

8.1 Proprietà, potenzialità e limiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

8.2 Funzionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

8.2.1 Analisi top-down vs bottom-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

8.2.2 L’informazione di contesto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Esempio 8.1 – Ricorsione sinistra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

8.3 Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

LR(0)

Esempio 8.2 – Grammatica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

LR(0)

8.3.1 Calcolo dei contesti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

LR(0)

Esempio 8.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

8.3.1.1 Miglioramenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

8.3.2 Condizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

LR(0)

Teorema 8.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

8.3.3 Procedimento operativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

8.3.3.1 LR item 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

8.3.3.2 LR item 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

8.3.3.3 LR item 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

8.3.3.4 Considerazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

8.3.4 Costruzione parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

LR(0)

8.3.5 Controesempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

iii

8.4 Verso l’analisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

LR(1)

8.4.1 Definizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

8.4.2 Considerazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

8.5 Approssimazioni del contesto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

LR(1)

8.5.1 Parser SLR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Esempio 8.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

8.5.1.1 Procedimento operativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

8.5.2 Parser LALR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

9 Processo computazionale iterativo e ricorsivo 55

9.1 Iterazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

9.2 Ricorsione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

9.3 Differenze tra i modelli computazionali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

9.4 Iterazione simulata tramite ricorsione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Esempio 9.1 – Il linguaggio Scala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

9.4.1 Guadagni della TRO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

10 Basi di programmazione funzionale 58

10.1 Funzioni come first-class entities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

10.2 JavaScript come linguaggio funzionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

10.2.1 Funzioni in JavaScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

10.3 Chiusure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

10.3.1 Criteri di chiusura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

10.3.1.1 Catena lessicale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

10.3.1.2 Catena dinamica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

10.3.2 Chiusura nei linguaggi più comuni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

10.4 Modelli computazionali per la valutazione di funzioni . . . . . . . . . . . . . . . . . . . . . . 61

10.4.1 Modello applicativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

Esempio 10.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

10.4.2 Modello call-by-name . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

10.4.2.1 Macro in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

10.4.2.2 Con funzioni first-class entities . . . . . . . . . . . . . . . . . . . . . . . . 63

Esempio 10.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

10.4.2.3 Java e C# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

10.4.2.4 Call-by-name in Scala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

11 Multi-paradigm programming in JavaScript 64

11.1 Le basi del linguaggio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

11.1.1 Architettura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

11.1.2 Tipi di dato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

11.1.2.1 Stringhe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

11.1.2.2 Numeri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

11.1.2.3 Booleani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

11.1.2.4 Altre costanti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

11.1.3 Espressioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

11.1.4 Variabili . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

11.1.4.1 Tipo dinamico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

11.1.5 Istruzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

11.1.6 Strutture di controllo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

11.1.7 Operatori relazionali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

11.2 Il lato funzionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

11.2.1 Funzioni first-class entities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

11.2.2 Function expression vs declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

iv

11.2.3 Funzioni innestate e chiusure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Esempio 11.1 .