Architettura degli Elaboratori Architettura degli Elaboratori

(1)

1 Architetture degli Elaboratori

Corso di Corso di

Architettura degli Elaboratori Architettura degli Elaboratori

Reverse Polish Notation:

Jan Lukasiewicz [1878-1956], Donald Knuth [1962]

Matteo Baldoni

Dipartimento di Informatica Università degli Studi di Torino C.so Svizzera, 185 – I-10149 Torino [email protected] http://www.di.unito.it/ ~baldoni

Reverse Polish Notation Reverse Polish Notation

Problema: data una espressione (A + B) / (C – D) scrivere un algoritmo per calcolarne il valore

Questo problema è di fondamentale importanta per la realizzazione di un qualsiasi llinguaggio ad alto livello È più facile utilizzando per le espressioni la RPN:

A B + C D - /

La struttura dati pila (stack) gioca un ruolo fondamentale

La pila (stack) La pila (stack)

La pila è una sequenza di elementi di un certo tipo in cui è possibile

aggiungere o togliere elementi soltanto ad un estremo (la “testa”) della sequenza

LIFO: Last In First Out, ultimo arrivato, primo servito

Testa

La pila (stack) La pila (stack)

La pila puo` essere vista come un caso speciale di lista in cui

l’ultimo elemento inserito è anche il primo ad essere rimosso

non è possibile accedere ad alcun elemento che non sia quello in testa

Applicazione importante:

gestione dell’esecuzione di procedure ricorsive

(2)

Operazioni sulle pile Operazioni sulle pile

creaPila: crea una nuova pila vuota

pilaVuota: test, restituisce true se la pila è vuota, false altrimenti

leggiPila (top): restituisce l’elemento in testa alla pila

fuoriPila (pop): elimina l’elemento in testa alla pila

inPila (push): inserisce un elemento in testa alla pila

Operazioni sulle pile Operazioni sulle pile

creaPila(Pila)

creaLista(Pila)

codaVuota(Pila)

return vuoto(Pila)

leggiPila(Pila) p ← primo(Pila) elem ← leggi(p, Pila) return elem

fuoriPila(Pila) p ← primo(Pila) elem ← leggi(p, Pila) cancella(p, Pila) return elem

inPila(elem, Pila) p ← primo(Pila) inserisci(elem, p, Pila)

Espressioni aritmetiche Espressioni aritmetiche

Le parentesi sono fondamentali per una corretta interpretazioni delle regole di priorita` tra gli operatori additivi e moltiplicativi

3 * 3 + 2: quale è il risultato? 11 oppure 15?

Dipende se * ha maggiore priorita` di + oppure no

* ha maggiore priorita` di +

uso le parentesi per far si che si sommi prima di

!

Albero sintattico Albero sintattico

Albero sintattico

i nodi interni rappresentano gli operatori

le foglie gli operandi la gerarchia permette di memorizzare le relazioni di priorita` tra I vari operatori

le parentesi sono inutili

" "

" # #

#

(3)

Albero: previsita Albero: previsita

$&% '

% (

% )

% *

% +

% ,

% -

% .

% $/% $$

PREVISITA(p, Tree) // Esamina p

if not foglia(p, Tree) then begin v ← primoFiglio(p, Tree)

while not fineFratelli(v, T) do begin PREVISITA(v, Tree)

v ← succFratello(v, Tree) end

end

$

' * $ / $$

, -

+

)

( .

Albero: invisita Albero: invisita

$

' * $/ $$

, -

+

)

( .

INVISITA(p, Tree) if foglia(p, Tree) then //Esamina p else begin

v ← primoFiglio(p, Tree) INVISITA(v, Tree) // Esamina p

v ← succFratello(v, Tree)

while not fineFratelli(v, T) do begin INVISITA(v, Tree)

end

0 1 $

(

% '

% )% $&% +

% *

% .

% -

% $/% $$% ,

Albero: postvisita Albero: postvisita

$

' * $ / $$

, -

+

)

( .

(

% )

% '

% +

% *

% .

% $/% $$&% -

% ,% $

POSTVISITA(p, Tree)

if not foglia(p, Tree) then begin v ← primoFiglio(p, Tree)

while not fineFratelli(v, T) do begin PREVISITA(v, Tree)

// Esamina p end

Albero sintattico Albero sintattico

La notazione postfissa è data dalla visita dell’albero sintattico con una postvisita

La visita postfissa può essere realizzata appogiandosi ad uno stack

La notazione postfissa mantiene l'ordine degli operandi

dell'espressione originale Ma come utilizzare

l’espressione così ottenuta?

Come calcolarne il valore espresso?

(4)

Macchina a stack Macchina a stack

2 Per il calcolo di

un’espressione in notazione polacca postfissa si fa uso di una macchina a pila

2 Si legge l’espressione polacca da sinistra verso destra

2 Per ogni valore numerico si effettua un’operazione di push in una pila di tale valore

2 Per ogni operatore si esegue l’operazione espressa sui due prima valori estratti con la pop e si fa la push del risultato

2 il top finale è il valore dell’espressione

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

(5)

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

8 9

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

8 9

9

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

8 9

9 8 9

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

8 9

9 8 9 88 9

(6)

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

8 9

9 8 9 :8 9

8; 9

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

8 9

9 8 9 :8 9

8; 9 8: 9

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

8 9

9 8 9 88 9

:< 9 88 9 =

9

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

8 9

9 8 9 88 9

:< 9 88 9 =

9

(7)

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

8 9

9 8 9 :8 9

8; 9 8: 9 =

9 :

Esecuzione Esecuzione

3 3 4 5 6 3 7 4 5 6 5 4 6

8

8 9

9 8 9 :8 9

8; 9 8: 9 =

9 :

Uno stack per la conversione Uno stack per la conversione

> Si inserisce un $ sullo stack

> I numeri sono copiati in output

> Le parentesi sinistre sono inserite nello stack

> Se il simbolo analizzato è una parentesi destra si estraggono e inviano in output tutti i simboli sino ad una parentesi sinistra, parentesi destra e sinistra si eliminano

> Se il simbolo analizzato ha priorità più alta di quello sul top il simbolo è inserito nello stack

> Se ha priorità più bassa si estrae il simbolo sul top e lo si invia in output

> Se il simbolo analizzato è $ si estraggono e inviano in output tutti i simboli sullo stack

?

Esecuzione Esecuzione

@A B @A C DE CA B @F C DEE B D G

H

(8)

Esecuzione Esecuzione

@A B @A

C DE CA B @F C DEE B D G

H H

Esecuzione Esecuzione

H H I

Esecuzione Esecuzione

@A B @A

H H I

H

Esecuzione Esecuzione

H H I

H

(9)

Esecuzione Esecuzione

@A B @A

H H I I

H H

Esecuzione Esecuzione

H H I I

H

Esecuzione Esecuzione

@A B @A

H H I I J

H H

H

Esecuzione Esecuzione

H H I I J K

H

H H

(10)

Esecuzione Esecuzione

@A B @A

H H I I J K L

H H

H H H

Esecuzione Esecuzione

H H I I J K L I

H

H H H

Esecuzione Esecuzione

@A B @A

H H I I J K L I

H H

H H H

H

Esecuzione Esecuzione

H H I I J K L I

H

H H H

H

(11)

Esecuzione Esecuzione

@A B @A

H H I I J K L I M

H H

H H H

H

Esecuzione Esecuzione

H H I I J K L I M

H

H H H

H

Esecuzione Esecuzione

@A B @A

H H I I J K L I M J

H H

H H H

H

Esecuzione Esecuzione

H H I I J K L I M J K L K

H

H H H

H

H H

(12)

Esecuzione Esecuzione

@A B @A

H H I I J K L I M J K L K

H H

H H H

H

H H H

Esecuzione Esecuzione

H H I I J K L I M J K L K J

H

H H H

H

H H H

Esecuzione Esecuzione

@A B @A

H H I I J K L I M J K L K J L

H H

H H H

H

H H H H