Progetto Laboratorio Programmazione
Parte 2: Analizzatore sintattico di espressioni

Stefano Guerrini

A.A. 2000/01

Come abbiamo già visto, l'obiettivo del progetto è arrivare a determinare il valore assegnato ad ogni variabile in una sequenza come quella in Figura 1. Nella prima parte del progetto è stato realizzato l'analizzatore lessicale. La seconda parte riguarda l'analisi sintattica.

Figura 1: Esempio di sequenza di assegnazioni

alfa = 32;
beta = -41;
x    = alfa * beta;
y    = alfa * beta + beta / x * alfa + beta.

L'analizzatore lessicale decompone l'input in una sequenza di token invece che in una sequenza di caratteri. L'analisi sintattica stabilisce se tale sequenza di token è ``corretta''.

Parsing e alberi sintattici

L'analisi sintattica è anche detta parsing¹ ed il modulo che la esegue si chiama parser.

Il parser, oltre a verificare che l'input non contiene sequenze di token illegali (come ad esempio potrebbe essere una espressione del tipo a + b c, dato che tra b e c manca l'operatore aritmetico), deve individuare la struttura sintattica corrispondente alla sequenza di token analizzati. La struttura sintattica del linguaggio è descritta dalla sua grammatica.

La grammatica per le sequenze di assegnazioni che prenderemo in esame è riportata in Figura 2.

Figura 2: Grammatica per le sequenze di espressioni

Senza voler essere troppo formali, dato che la spiegazione del significato preciso di grammatica è argomento di altri corsi, proviamo a capire come interpretare Figura 2.

Per prima cosa, osserviamo che la grammatica è composta da una sequenza di regole simili a delle assegnazioni. Ad esempio, la prima regola è

$$\begin{eqnarray*} \langle\mbox{sequenza}\rangle & \rightarrow & \langle\mbox{as... ...quenza}\rangle \mid \langle\mbox{assegnazione}\rangle \texttt{.} \end{eqnarray*}$$

In ogni regola, a sinistra della freccia abbiamo un (simbolo) non-terminale (i non-terminali sono riconoscibili per il fatto che il loro nome è racchiuso tra parentesi angolose). La parte destra della regola è una espressione ottenuta combinando token del linguaggio (anche detti simboli terminali della grammatica), non-teminali, l'operatore $\mid$ e altri operatori come ad esempio le parentesi quadre.

I non-terminali sono una sorta di variabili e denotano un'intera classe di possibili sequenze di input. Ogni regola della grammatica descrive la struttura del non-terminale alla sinistra della freccia. Per ogni terminale ci possono essere più regole, per tale motivo, nella notazione dell'esempio la barra verticale $\mid$ separa regole che possono essere usate alternativamente.

Cerchiamo di chiarire quanto detto con un esempio. Si riprenda la prima regola della grammatica. La regola descrive il non-terminale $\langle\mbox{sequenza}\rangle$. A destra della freccia, separate dalla barra verticale, appaiono le due espressioni

$$\begin{eqnarray*} (1)&& \langle\mbox{assegnazione}\rangle \texttt{;} \langle\mb... ...}\rangle \\ (2)&& \langle\mbox{assegnazione}\rangle \texttt{.} \end{eqnarray*}$$

Come interpretarle? Entrambe forniscono una possibile struttura di un elemento che appartiene alla classe $\langle\mbox{sequenza}\rangle$, con la quale vogliamo denotare la struttura delle sequenza di espressioni sintatticamente corrette. In altre parole, per decomporre una sequenza di espressioni e stabilire se è corretta si deve vedere se questa rientra in una delle seguenti possibilità:

1. la sequenza si compone di una parte che ha la struttura di un elemento della classe $\langle\mbox{assegnazione}\rangle$ seguita dal terminale (dal token) $\texttt{;}$ e da un'altra parte la cui struttura è nella classe di $\langle\mbox{sequenza}\rangle$.
2. la sequenza si compone di un elemento della classe $\langle\mbox{assegnazione}\rangle$ seguito dal terminale (dal token) $\texttt{.}$

Come si può notare, la descrizione di $\langle\mbox{sequenza}\rangle$ fa riferimento ad altri simboli non-terminali. In particolare, per capire se l'esempio in Figura 1 è corretto, bisogna utilizzare la regola di $\langle\mbox{assegnazione}\rangle$ per determinare quale parte dell'esempio è un'assegnazione (nel nostro caso alfa = 32) e verificare qual è il terminale che la segue. Infatti, dall'osservazione dei due casi di $\langle\mbox{sequenza}\rangle$ è facile vedere che se il terminale che segue l'assegnazione è un $\texttt{;}$ allora si deve applicare il primo caso, se è un $\texttt{.}$ si deve applicare il secondo.

La definizione di $\langle\mbox{sequenza}\rangle$ è ricorsiva: dopo aver verificato che la prima riga dell'esempio di Figura 1 è un elemento di $\langle\mbox{assegnazione}\rangle$ seguito da $\texttt{;}$, occorre verificare che quanto rimane è un elemento della classe $\langle\mbox{sequenza}\rangle$. Quindi, possiamo dire che

la regola di $\langle\mbox{sequenza}\rangle$ descrive una sorta di procedura ricorsiva per l'individuazione degli elementi della corrispondente classe in cui il primo caso è quello ricorsivo, mentre il secondo è quello base.

Per determinare qual è la parte di sequenza che corrisponde ad un elemento di tipo $\langle\mbox{assegnazione}\rangle$ si procede in modo analogo. Nel caso di $\langle\mbox{assegnazione}\rangle$ si ha una sola possibilità: occorre trovare una sequenza che si compone di un $\texttt{identificatore}$ seguito da un $\texttt{=}$ e da una sequenza della classe $\langle\mbox{espressione}\rangle$. I primi due elemnti sono dei token e quindi vengono immediatamente determinati; invece, per capire quale parte della sequenza di input corrisponde ad una espressione occorre applicare le regole di $\langle\mbox{espressione}\rangle$.

Proviamo a vedere il dettaglio dell'applicazione delle regole ai casi nell'esempio. L'espressione alla destra della prima assegnazione è formata dal solo numero 32. Dall'analisi delle regole della grammatica, osserviamo che ogni espressione comicia con un elemnto della classe $\langle\mbox{termine}\rangle$, che a sua volta comincia sempre con un elemento della classe $\langle\mbox{fattore}\rangle$ e che il numero 32, essendo un naturale, è un elemento di tale classe. Ora, andiamo ad osservare il token che segue 32, si tratta di un ;. Siccome non è un operatore moltiplicativo ($\texttt{*}$ o $\texttt{/}$), la regola che si applica è quella che indica che un fattore è un caso particolare di termine, quindi 32 è un termine. Analogamente, dato che 32 non è seguito da un operatore additivo, la regola da applicare è quella che dice che un termine è un caso particolare di espressione per concludere che 32 è l'espressione cercata.

NB. Abbiamo appena visto che un naturale è un caso particolare di termine. Ciò è dovuto al fatto che una delle regole per $\langle\mbox{termine}\rangle$ è $[\texttt{-} \mid \texttt{+}]\texttt{naturale}$. Tale regola va letta nel seguente modo: un naturale, eventualmente preceduto dal segno $\texttt{+}$ o dal segno $\texttt{-}$, è un termine. Infatti, le parentesi quadre denotano una parte opzionale (nel nostro caso la parte $\texttt{-} \mid \texttt{+}$), mentre l'operatore $\mid$ denota l'alternativa tra due possibilita (nel nostro caso, la scelta tra $\texttt{-}$ e $\texttt{+}$). In altre parole, la suddetta regola è un modo compatto di scrivere:

$$\texttt{-} \texttt{naturale}\mid \texttt{+} \texttt{naturale}\mid \texttt{naturale}$$

Passiamo ora ad analizzare un caso meno banale, ovvero, all'analisi dell'ultima espressione dell'esempio in Figura 1. L'espressione da analizzare è alfa * beta + beta / x * alfa + beta.In base alle regole di $\langle\mbox{espressione}\rangle$, si deve trovare il primo termine dell'espressione. In base alla definizione di $\langle\mbox{termine}\rangle$, ciò richiede di trovare il primo fattore del termine. Otteniamo cosìl'identificatore alfa, dato che un identificatore è un caso particolare di fattore. Ora, il token che segue questo fattore è un $\texttt{*}$, ovvero un operatore moltiplicativo. Pertanto, si deve applicare la regola di $\langle\mbox{termine}\rangle$ che dice che un termine può avere una struttura del tipo

$$\langle\mbox{fattore}\rangle \langle\mbox{operatore moltiplicativo}\rangle \langle\mbox{termine}\rangle$$

e si passa alla ricercare del termine che segue alfa *. Procedendo in questa maniera, si trova che il successivo termine è l'identificatore beta (il termine non si può estendere oltre dato che beta non è seguito da un operatore moltiplicativo). In conclusione, il più lungo elemento di $\langle\mbox{termine}\rangle$ che si può costruire all'inizio dell'espressione è alfa * beta. Ora, dato che questo termine è seguito dall'operatore additivo $\texttt{+}$, la regola di $\langle\mbox{espressione}\rangle$ che si applica è quella ricorsiva

$$\langle\mbox{termine}\rangle \langle\mbox{operatore additivo}\rangle \langle\mbox{espressione}\rangle$$

Quindi, resta da vedere se la parte di espressione rimanente beta / x * alfa + beta, è una espressione e il modo in cui si decompone in termini e fattori. Procedendo in modo analogo a quanto visto prima, si trova che tale sotto espresione si decompone nel fattore beta / x * alfa seguito dall'operatore additivo + e dalla espressione beta.

La struttura della precedente decomposizione può essere riassunta in una struttura ad albero, il cosiddetto albero sintattico. L'albero sintattico dell'ultima assegnazione dell'esempio in Figura 1 è riportato in Figura 3.

Figura 3: Albero sintattico

Parsing a discesa ricorsiva

Quanto visto nel paragrafo precedente suggerisce la seguente implementazione per il parser:

per ogni non-terminale, si scrive una procedura (ricorsiva) che richiama le procedure dei non-terminali della regola che si sta applicando.

Rimane da specificare meglio cosa le singole procedure devono produrre come risultato.

Rappresentazione delle espressioni

La rappresentazione che si vuole ottenere per le espressioni è un albero in cui i nodi interni corrispondono agli operatori delle espressioni e le cui foglie sono interi o variabili.

Figura 4: Rappresentazione ad albero di alfa * beta + beta / x * alfa + beta.

Ad esempio, l'albero corrispondente a

alfa * beta + beta / x * alfa + beta

è ripotato in Figura 4. Si osservi che tale albero è in realtà una forma ``compatta'' dell'albero sintattico dell'espressione (nell'albero sintattico i terminali sono sempre foglie dell'albero). In particolare, si osservi che la definizione della grammatica forza anche l'ordine in cui sui associano gli operandi. Ad esempio, la precedente espressione è la somma dei termini

alfa * beta
beta / x * alfa
beta

La grammatica di Figura 2 decompone le espressioni in un termine ed una espressione composti mediante un operatore additivo, decomposizione che è correttamente rappresentata dall'albero di Figura 4, che corrisponde ad un'implicito uso di parentesi per racchiudere il secondo e il terzo termine (e analogamente per beta / x * alfa), ovvero è equivalente a

alfa * beta + (beta / (x * alfa) + beta)

Per forzare il termine di Figura 5 occorre invece racchiudere esplicitamente tra parentesi il primo e secondo temine. Ovvero, l'albero di Figura 5 corrisponde al termine

(alfa * beta + beta / x * alfa) + beta

Figura 5: Albero dell'espressione (alfa * beta + beta / x * alfa) + beta.

Una possibile definizione per la struttura dati che implementa l'albero delle espressioni è la seguente:

type PuntNodoExp = ^NodoExp;
     NodoExp = record of
                  tipo : integer;
                  op1, op2 : PuntNodoExp;
                  id : string;
                  val : integer;
               end;

Si tratta di una semplice estensione del record dei token. Infatti, nel campo tipo si può utilizzare lo stesso codice usato per i token per distinguere se il nodo è quello di un opertaore o quello di un terminale (identificatore o numero intero). Rispetto al record per i token sono stati aggiunti i due campi op1, op2 nei quali memorizzare i puntatori agli alberi degli operandi nel caso in cui il nodo è quello di un operatore.

Per la scrittura delle procedure associate ai non-terminali che costruiscono l'abero, si consiglia la seguente assunzione:

ogni funzione associata ad un non-terminale riceve come parametro di input il primo token che la funzione deve analizzare e lascia in tale parametro il token immediatamente successivo alla parte di input corrispondente al non-terminale analizzato dalla funzione.

Come ulteriore aiuto, si riporta qui di seguito quello che potrebbe essere il codice della funzione ParseEspressione (all'interno di ParseEspressione si usa una funzione boolena IsOpAdd(tk.tipo) che ritorna true se l'argomento è un operatore additivo e false altrimenti).

function ParseEspressione(var tk: token): PuntoNodoExp;
var pnd, aux: PuntoNodoExp;
begin
  pnd := ParseTermine(tk); { costruisci l'albero del primo termine }
  if (pnd <> nil) then
  begin
    if IsOpAdd(tk.tipo) then
    begin  { applico la regola ricorsiva }
      new(aux);  { crea il nodo dell'operatore }
      aux^.tipo := tk.tipo;
      aux^.sin := pnd; { operando sinistro }
      nexttoken(tk); { avanza al prossimo token }
      aux^.des := ParseEpsressione(tk); { operando destro }
      if aux^.des = nil then
      begin { gestione errore }
        ...;
        pnd := nil
      end
      else { non sono stati trovati errori }
        pnd := aux
    end
  end;
  ParseEspressione := pnd
end;

Si è volutamente lasciato non specificato il codice relativo alla gestione dell'errore. Su questa parte, almeno per quanto riguarda la parte obbligatoria del progetto, non vengono fatte particolari richieste (la parte obbligatoria verrà verificata solo su input corretti). Ad ogni modo, una possibile scelta implementativa è quella di far sìche, nel caso in cui la funzione associata ad un non-terminale non riesce a costruire il corrispondente albero a causa di un errore nell'input, la funzione ritorna il valore nil (questa è la strada seguita nell'esempio).

Rappresentazione della sequenza di assegnazioni

Il parser deve costruire l'albero di ogni espressione nella sequenza di input ed associarlo alla corrispondente .

L'output del parser dovrà essere (nel caso di sequenza sintatticamente corretta) una lista di coppie variabile/albero dell'espressione. Una possibile struttura di dati per tale lista è la seguente:

type ListaAssegnazioni = ^Assegnazione;
     Assegnazione = record of
                       id : string;
                       exp : PuntNodoExp;
                       next : ListaAssegnazione;
                    end;

Seguendo la strada di una funzione per ogni non-terminale, è ragionevole che le funzioni ParseSequenza e ParseAssegnazionie ritornino un puntatore di tipo ListaAssegnazioni.

Input-output del parser

Il file di input del parser è lo stesso dell'analizzatore lessicale. Ovvero, la sequenza di assegnazioni deve essere letta da un file di nome dati.txt che si trova nella stessa directory del programma in esecuzione.

Come output, il parser deve stampare la sequenza di assegnazioni di input trasformando le espressioni in notazione prefissa.

Ad esempio, l'output corrispondente all'esempio in Figura 1 è:

alfa = 32;
beta = -41;
x    = * alfa beta;
y    = + * alfa beta + / beta * x alfa beta.

Si osservi che la scrittura dell'espressione in notazione prefissa può essere ottenuta per mezzo di una semplice visita in preordine dell'albero dell'espressione: stampa l'operatore del nodo, l'albero sinistro e quindi l'albero destro, fino ad arrivare alle foglie.

NB. Si noti che esiste una corrispondenza biunivoca tra albero delle espressioni e notazione prefissa e che nella notazione prefissa non c'è bisogno di parentesi.

About this document ...

Progetto Laboratorio Programmazione
Parte 2: Analizzatore sintattico di espressioni

This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.42)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -nonavigation syntan.tex

The translation was initiated by Stefano Guerrini on 2001-06-21

Footnotes

...parsing¹

to parse: to resolve (as a sentence) into component parts of speech and describe them grammatically. (Primo significato come verbo transitivo riportato sul Merrian-Webster Collegiate Dictionary.)