/ Autore: Ettore Pasquini, sett. 1999

/ Sommario:
/ Obiettivo
/ Analisi di Progetto
Alcune considerazioni sulla grammatica
/ Implementazione e Codifica
1. Estensione del linguaggio e del compilatore
1.1 Analizzatore Sintattico
1.2 Generazione Codice
1.3 Analizzatore lessicale
1.4 Generazione del codice oggetto finale
1.5 Sorgenti
/ Verifica

/ Obiettivo

Si è voluto estendere il compilatore già iniziato (che gestiva espressioni aritmetiche, assegnamenti, salti condizionati, ma senza nessun controllo semantico nell'uso misto di operatori logici ed aritmetici, ed era ispirato dall'articolo di Warren "Logic Programming and Compiler Writing", 1979, in "Software - Practice and Experience", Vol. 10, pp. 97-125, 1980) per gestire anche:
- blocchi di statement;
- cicli while;
- espressioni logiche, con separazione semantica rispetto alle operazioni arimetiche.

/Analisi di progetto

L'uso del Prolog per la realizzazione di un compilatore comporta i seguenti vantaggi e svantaggi:

/ VANTAGGI /

• Semplicità di progettazione, codifica, estensione, e diagnosi del sistema, garantita dall'approccio dichiarativo del linguaggio alla descrizione del sistema.
• Ciò comporta anche una elevata velocità di progetto e stesura del codice di ogni successiva estensione incrementale.
• La semantica dichiarativa coglie sinteticamente (e con chiarezza) gli aspetti essenziali del dominio del discorso, venendo subito al cuore del concetto da implementare (siccome l'esposizione coincide - all'incirca - con la sua implementazione).

• L'uso di un motore non deterministico per la risoluzione di un problema deterministico può risultare molto inefficiente, qualora non si controlli opportunamente l'operato della macchina. Ciò comporta un impegno aggiuntivo (e assolutamente indesiderato) in fase di stesura del codice e durante il debugging, che bilancia "in negativo" (!) la iniziale rapidità di progetto. Inoltre si perde di vista l'approccio puramente dichiarativo.
• Pertanto si può correre il rischio di fare un uso assolutamente spropositato delle risorse (e anzi se ne fa comunque: a che mi serve uno stack di backtracking ? e una macchina così complessa come la Warren-Machine ? La stessa descrizione a clausole è un "di più" non necessario che ha un suo costo, anche se dà molti vantaggi).

Alcune Considerazioni sulla grammatica

Tenendo conto delle estensioni indicate, la grammatica complessivamente è:

SCOPO = <block>

<exp> ::= <exp> <op> <exp> |
( <exp> ) |
<integerconst> |
<ident>

<op> ::= + | - | * | /

<comparison_op> ::= > | < | == | <= | >= | !=

<compare_test> ::= <exp> <comparison_op> <exp>

<logic exp> ::= <logic exp> <logic op> <logic exp> |
<compare_test> |
( <logicexp> ) |
true | false

<logic op> ::= && | || | =>

<block> ::= { <statements> } | { }

<statement> ::= <ident> = <exp> ; |
if (<logic exp>) <statement> else <statement> endif |
while ( <logic exp> ) <statement> |
<emptystatement> |
<block>

<statements> ::= <statement> |
<statement> <statements>

<emptystatement> ::= ;

La grammatica non è LL(1): infatti nella produzioni con testa <logicexp>abbiamo insiemi di starter symbols non disgiunti, a causa della presenza delle '('. Escludendo dalle <logicexp> il fattore <compare_test>, esse diventano in tutto e per tutto analoghe alle espressioni aritmetiche che, come sappiamo, attraverso la fattorizzazione danno origine ad una grammatica LL(1). Quindi senza quel fattore aggiuntivo avremmo, nel complesso, una grammatica LL(1), se fattorizziamo le clausole <statements> e impediamo a <ident> di assumere i valori "while" e "if" (che diventano quindi vere parole riservate: l'analizzatore qualora incontri (ad es.) "while" capisce che la "mossa giusta" è aspettarsi uno statement "while-condition-do". Se in seguito incontra un '=' (perchè quel while era un identificatore, e non uno statement while-do), allora segnalerà errore.).
Tuttavia, grazie alla potenza del backtracking, questo problema non viene avvertito dalla soluzione prolog, dove basta limitarsi a scrivere "cosa è" una <logicexp>.

/ Implementazione e Codifica

1. ESTENSIONE (del linguaggio e del compilatore )

NOTA: per la spiegazione generale del funzionamento del compilatore si veda il sopracitato articolo di Warren.
L'estensione del compilatore avviene di pari passo all'estensione del linguaggio: introdurre nuove produzioni alla grammatica del linguaggio si traduce nell'aggiunta di corrispondenti clausole Prolog per l'analisi sintattica e per la generazione del relativo codice.
In questo caso particolare, si è anche introdotto la separazione semantica tra operatori logici ed aritmetici, che nella versione precedente erano tutti raggruppati insieme allo stesso livello.

1.1 Analizzatore Sintattico

Il riconoscimento delle espressioni logiche è praticamente identico a quello delle espressioni aritmetiche (diverso è il codice generato, tuttavia), e l'aggiunta del ciclo while e dei blocchi avviene in modo autoesplicativo, grazie alle capacità espressive del Prolog. Nella scrittura di queste clausole bisogna cercare di scrivere, per quanto possibile, un riconoscitore deterministico, ossia bisogna eliminare tutti punti di scelta lasciati aperti dalla macchina Prolog, introducendo opportuni "cut".
Da notare che nella gestione delle espressioni logiche mancano le variabili logiche.
L'analisi sintattica parte con la procedura 'scopo(F, Rest, Res)', ossia la scopo della grammatica (il 'block'), e produce una forma intermedia dalla quale si genera il codice macchina. L'aggiunta delle nuove clausole avviene in testa al database già esistente, ottenendo così la garanzia di un funzionamento corretto ed indipendente dalle clausole sottostanti.
L'analisi delle espressioni logiche deve essere nettamente distinta da quella delle espressioni aritmetiche, affinchè la semantica sia corretta. A questo scopo, comunque, basta seguire quanto scritto nelle produzioni della grammatica, implementando come al solito una procedura per ogni produzione.

1.2 Generazione Codice

La procedura che genera il codice è:

gencode( Res, Dic, Code )

dove Res è il risultato dell'analisi sintattica, Dic è il dizionario dei simboli (parzialmente specificato), e Code il codice generato.
Le espressioni logiche sono presenti sia nello statement if-then-else, sia nel ciclo while: la generazione del relativo codice inizia, in entrambi i casi, con l'invocazione della procedura gencondcode. Questa è simile alla gencode relativa alle espressioni aritmetiche, ma con differenti fattori: al posto di identificatori e costanti intere abbiamo termini di confronto (comparetest ->an.sint.; ->gen.cod.) e le costanti true e false. Scriveremo quindi 4 clausole per tale procedura, tre per i diversi fattori (ma il caso di una condizione composta solo da un unico true o false si può riconoscere e gestire, eliminando il test che di fatto non sussiste) e una per il caso generale di espressione logica con diversi termini e fattori.
Vi sono però altre differenze.
Intanto le espressioni logiche si pongono al di sopra delle espressioni aritmetiche, nel senso che queste ultime, insieme agli operatori relazionali, formano termini logici; ciò vuol dire che bisogna convertire il risultato del confronto (un numero intero, positivo o negativo) in un valore logico. Per estrarre tale valore logico si potrebbe usare direttamente il segno del risultato (in complemento a due), ma così facendo bisognerebbe opportunamente invertire gli operandi del confronto a seconda dell'operatore: ad es. se un confronto "a>b" comporta la sottrazione "b-a", il confronto "a<b" deve comportare la sottrazione "a-b", altrimenti il significato del bit di segno non è più lo stesso. Le cose si complicano con i confronti >= e <=. Per risolvere efficacemente il problema bisognerebbe fare riferimento alla macchina fisica, alla presenza di eventuali istruzioni di TEST dei FLAG di sistema (ZERO, NEGATIVE, CARRY, ecc.), nonchè all'implementazione del complemento a due, ecc.: siccome la macchina target è solo un riferimento astratto, si è preferito non considerare questo tipo di problematiche, e non imporre nessuna ipotesi aggiuntiva alla macchina (come l'aggiunta di nuove istruzioni, ad es.). La soluzione infatti può essere software, basta aggiungere al generico codice dell'espressione aritmetica (a-b, nell'esempio di prima) qualche altra istruzione per permettere la comprensione esplicita del risultato logico; in pratica, il termine (a>b) dà luogo a:

<ExprCode>
POP
<JUMPIF> L0
PUSH 1
JUMP L2
L0: PUSH 0
L2:

dove JUMPIF è un'istr. di salto condizionale opportuna (come al solito), a seconda dell'operatore di confronto presente. In tal modo le operazioni logiche lavorano sempre con valori numerici 0 e 1, dal significato chiaro.
L'istruzione POP, posta dopo il codice dell'espressione (una sottrazione), serve a pulire lo stack dai risultati aritmetici.
Quanto allo statement

while( <logic exp> ) <statement>

viene tradotta in:

label1:
<testcode>
<DOcode>
JUMP label1
label2:

dove <testcode> provoca un salto a label2 se il risultato del test è falso. La condizione è dello stesso tipo di quella dell'if, quindi si può richiamare la stessa procedura gencondcode.

1.3 Analizzatore Lessicale

Questo componente è privo di interesse concettuale: esso non deve far altro che estrarre, dal file comunicato in input (od eventualmente dall'input immesso via console), i token della frase da compilare (restituiti come lista). Il file può essere convenientemente letto e trasferito direttamente su una lista di caratteri, per poi essere successivamente analizzato.
Vale forse la pena scrivere che si è voluto costruire un analizzatore in grado di riconoscere ed estrarre token anche se fra questi non vi è nessun separatore. Si vedano alcuni dettagli implementativi qui.

1.4 Generazione del codice oggetto finale

Come noto, il compilatore usa, per la gestione del codice oggetto, una rappresentazione interna nella forma di termini Prolog del tipo:

instr( OPCODE, OPERANDS )

L'uscita della gencode è una disgiunzione di termini siffatti, utile per fissare (nella allocate) l'indirizzo assoluto delle variabili. Tuttavia, l'output vero e proprio può convenientemente essere riscritto nel formato

<opcode-mnemonic> <operands>

che si suppone indipendente dal generico compilatore e dalla sua rappresentazione interna. Questo è l'input che si può dare ad es. al simulatore di Stack machine.

1.5 Sorgenti

Complessivamente, il compilatore è articolato nei seguenti file:

Expgen.pl espressioni logiche
Expc1.pl assegnamento
Expc21.pl espressioni logiche, salti condizionati (il file Expc2.pl è stato riscritto)
Expc3.pl blocchi, ciclo while, statement vuoto.
lexan.pl analizzatore lessicale
front_end.pl main program
esmc.zip tutti i sorgenti (Sicstus Prolog) + esempi + questo documento

/ Verifica

La verifica del corretto funzionamento avviene coprendo con opportuni esempi tutti le forme di frase possibili secondo la grammatica data. Inoltre, vista la modularità con cui è stato costruito il sistema, è risultato conveniente la verifica di un blocco alla volta, alleggerendo così il carico di lavoro complessivo.