RIGAL

Strumento per compilatori

RIGAL è un linguaggio di programmazione per la generazione di compilatori, basato sul riconoscimento sintattico (pattern matching), creato da Mikhail Auguston e Vadim Engelson all’Università di Riga (Lettonia) nel 1987-1988.

Le strutture dati di RIGAL sono atomi, liste ed alberi, con corredo di istruzioni ed operatori per il loro trattamento. RIGAL è formato da una “regola principale (main rule)” all’inizio del sorgente, un vero e proprio modulo procedurale, che richiama le regole (rules) formate da parti dichiarative e procedurali, liberamente frammischiate; questa caratteristica da a RIGAL una notevole flessibilità. Un semplice esempio di struttura è:

#nome_regola	#BETA	#BETA(5 '+' 7);
modello	$A $O := ('+' ! '-') $B
/ implementazione /	/RETURN (.$A $O $B.)/	5 + 7
##	##

Figura 13

Il modello è la parte dichiarativa di RIGAL, se i parametri nel richiamo della regola soddisfano il modello, è eseguita la parte procedurale che eventualmente segue. Nella tabella precedente il modello è formato da tre atomi, contenuti nelle variabili $A, $O e $B, in particolare la regola ha successo se il secondo atomo è il carattere + oppure -.

Sono sotto forma di regole anche alcune funzioni di servizio: #IMPLODE()per concatenare atomi, #LEN(lista_o_albero) per il numero degli elementi di lista_o_albero e predicati per stabilire il tipo di oggetto. La regola particolare #CALL_PAS(n param) fornisce, tuttavia, oltre un centinaio di funzioni non implementate in RIGAL, fra cui scomposizione in elementi di un testo, elaborazioni su stringhe, funzioni numeriche, ecc...) e un abbozzo di interazione con WINDOWS. L’assegnazione ad una variabile di un’altra variabile è solo una copia del puntatore all’oggetto; per evitare inconvenienti si deve usare l’istruzione COPY(variabile), la cui sintassi non rispetta la sintassi prevalente dei comandi (gli argomenti non sono racchiusi fra parentesi es. OPEN handle nomefile).

Le liste possono contenere qualsiasi oggetto di RIGAL e sono costruite tramite (. Obj1 obj2 ... .). Gli alberi sono strutture in cui gli oggetti, di qualsiasi tipo, sono raggiungibili indicandone il cammino mediante il nome associato agli archi (selector) e sono costruiti in modo analogo alle liste: <. Sel1 : Obj1, Sel2 : Obj2 ... .> , qui la virgola che separa i nodi è una piccola incoerenza sintattica.

Manca al linguaggio un modo diretto di eliminare un elemento da una lista, inoltre l’istruzione FORALL per visitare liste ed alberi, non è, per gli alberi, ricorsiva. La dotazione del linguaggio è essenziale, ad esempio al costrutto IF manca la parte ELSE, facilmente sostituibile da ELSIF T (T è la costante TRUE).

I nomi delle variabili sono del tipo $nome_variabile, la variabile $$ è la variabile contenente l’elemento corrente della regola. Tutte le variabili sono locali alla regola in cui sono definite, tuttavia sono accessibili le variabili esterne ad essa tramite il costrutto LAST #nome_regola $nome_variabile.

L’esempio seguente (Figura 14), illustra una semplice regola di riconoscimento di un soggetto implicito (come nel caso del COBOL).

#MAIN

OPEN P ' ';

#FORMULA(Z '>' B 'OR' '=' 17); -- i parametri non formano lista?

LOOP

P <<;

$cmd := #CALL_PAS(1 'immetti istruzione: ');

-- MAIUSCOLO e substring

IF #CALL_PAS(85 #CALL_PAS(87 $cmd 1 3)) = 'FIN' -> BREAK FI;

$lst := #CALL_PAS(36 (.$cmd.)); -- separa in parti

#FRM($lst);

END;

##

#FRM (. (* #FORMULA *) .) ## -- estrae da lista

#FORMULA $T1 $OP1 := #CFR $T2 / P << $T1 $OP1 $T2 / -- a cfr b

(($BOL := ('OR' ! 'AND')

-- c'e' operando?

(($T3 $OP2 := #CFR $T4) ! ($OP2 := #CFR $T4 /$T3 := $T1/))

/ P <]$BOL $T3 $OP2 $T4; /) ! ' ' -- <] accoda output

)

##

#CFR ('<' ! '>' ! '=') /RETURN $/## -- determina operatore e lo restituisce

Z > B OR Z = 17

immetti istruzione: a>b

A > B

immetti istruzione: a>b and = 17

A > B AND A = 17

immetti istruzione: C=1 or D>0

C = 1 OR D > 0

immetti istruzione: fine

End of execution

Figura 14

Qui accanto l’esecuzione del programma.

Nell’esempio è stata utilizzata la regola #CALL_PAS() per convertire in maiuscolo una sottostringa

(#CALL_PAS(85 ...) e #CALL_PAS(87 ...)), e #CALL_PAS(36 ...) per generare una lista dei

componenti di una stringa.

Ci sono meccanismi per il trattamento delle espressioni regolari:

· (obj1 ! obj2 ! ...) valido se l’elemento è uno fra gli objn

in alternativa una regola può avere sottoregole, ad esempio una per ogni objn, separate fra di loro da: ;;

· (* Obj1 *) 0 o più volte il match con Obj1, esempio:

#SIGMA /$S := 0;/ (* $N /$S := $S + $N/ *) /RETURN $S/## -- somma numeri

· (+ Obj1 +) 1 o più volte il match con Obj1

E’ possibile effettuare il match anche con liste ed alberi. Nel listato di Figura 15 ci sono esempi di trattamento di liste ed alberi.

-- Rigal Versione 2.6

-- con suggerimenti di Vadim Engelson

#PRINC

OPEN S ' '; -- apertura output su video

-- sintagma nominale

$SN := <. Articolo: 'Una', Nome : 'vecchia' .>;

-- sintagma verbale

$SV := <. Verbo: 'legge', SN : Nil .>;

$frase := <. Frase: <. SN: $SN, SV: $SV .> .>;

$frase.Frase.SV.SN := <. Articolo: 'la', Nome : 'regola' .>;

#CALL_PAS(13 $frase); -- funzione 13: visualizza struttra albero

$LST := #TOLISTR($frase); -- estraggo lista delle foglie

S << 'Lista da albero:' $LST;

S << 'Cerca in lista: ' #INLIST('regola' $LST); -- cerco elemento in lista

S << 'Cerca in lista: ' #INLIST2($LST 'legge'); -- cerco in lista elemento

S << 'Cerca in lista: ' #INLIST('wxyz' $LST); -- cerco elemento in lista

S << 'Cerca in albero:' #FIND('Una' $frase); -- cerco foglia in albero

S << 'Cerca in albero:' #FIND('regola' $frase); -- cerco foglia in albero

S << 'Cerca in albero:' #FIND('wxyz' $frase); -- cerco foglia in albero

##

#TOLIST $ALB /#TOLISTR($ALB); RETURN $L/ ##

#TOLISTR <* $sel : $res!!:=#TOLISTR *> / RETURN $res /;;

$a / RETURN (. $a .) /

##

#INLIST $TOFND (. (* $ITM /IF $TOFND = $ITM -> $FND := $TOFND FI/ *) .)

/RETURN $FND/

##

#INLIST2 $LST $TOFND / RETURN #INLIST ($TOFND $LST) / ##

#FIND $src <* $sel : $node

/ IF #TREE($node)-> $res:=#FIND($src $node);

IF $res -> RETURN (. $sel .)!.$res FI; -- taglia ed appende il cammino

ELSIF $node=$src -> RETURN (. $sel $node .) -- taglia a livello di foglia

FI / *>

##

Figura 16

─Frase─┬SN─┬Articolo─'Una'

│ └Nome─'vecchia'

└SV─┬Verbo─'legge'

└SN─┬Articolo─'la'

└Nome─'regola'

Lista da albero: Una vecchia legge la regola

Cerca in lista: regola

Cerca in lista: legge

Cerca in lista:

Cerca in albero: Frase SN Articolo Una

Cerca in albero: Frase SV SN Nome regola

Cerca in albero:

End of execution

L’esecuzione del programma diFigura 16 produce l’output qui sopra.

Il listato di Figura 17 è un “compilatore” di FLOWMATIC, adattato e ristretto ad un frammento di programma (v. par. 2.22 FLOW-MATIC); l’output prodotto è un sorgente in PASCAL (v. par. 2.45 PASCAL).

-- Rigal Versione 2.6

#MAIN

$LIST:=#CALL_PAS(2 'flowmat.txt'); -- Lista degli elementi lessicali

$TreeLab := <. .>; -- albero delle etichette

$TreeStm := <. .>; -- albero delle istruzioni, ogni elemento è una lista

$TreeVar := <. 'NumRec' : 'integer; {NumRec = 0 e'' fine file}',

'Ris' : 'longint; {Ris = -1, 0, +1 risultato confronto}'

.>; -- albero delle variabili

$LB := '0'; -- identificatore istruzione

$NumStat := 0; -- numero istruzione

$FLPREV := NULL; -- File precedente (per istruzione read)

$FLIN := (. .); -- lista files di input

OPEN PGM 'FlowMat.pas';

#pgm($LIST);

PGM <] '{Turbo Pascal - Version 5.5';

PGM << 'Copyright (c) 1983, 1989 by Borland International, Inc.}';

PGM << 'Program FLOWMATIC;';

-- parte di Flowmatic "presunta"

PGM << 'type rec=record';

PGM << ' key: array[1..4] of char;';

PGM << ' Cust_code_no: array[1..12] of char;';

PGM << ' crlf: array[1..2] of char;';

PGM << 'end;';

PGM << 'function iff(str1, str2: string): longint;';

PGM << 'begin';

PGM << ' iff := -1;';

PGM << ' if str1 = str2 then iff:=0;';

PGM << ' if str1 > str2 then iff:=1;';

PGM << 'end;';

-- dichiarazione delle variabili

PGM << 'var';

FORALL SELECTORS $VAR BRANCHES $VAR1 IN $TreeVar DO

PGM << $VAR ':' $VAR1 OD;

-- dichiarazioni delle label

PGM << 'Label';

$stm := ' ';

FORALL $LAB IN $TreeLab DO

$stm := #IMPLODE($stm ' ' $LAB ',');

OD;

PGM <] #IMPLODE(#CALL_PAS(87 $stm 1 (#LEN($stm) -1)) ';'); -- substringa

PGM << 'Begin';

$I := 0;

LOOP

IF $I > $NumStat -> BREAK FI;

$LAB := $TreeLab.#IMPLODE('Lab' $I);

IF $LAB <> NULL -> PGM << $LAB FI;

$STM := $TreeStm.#IMPLODE('stm' $I);

FORALL $Item IN $STM DO PGM << ' ' $Item OD; -- 1 istr. per riga

$I := $I + 1;

END;

PGM << 'End.';

##

-- inizio regole

#pgm (. (* /LAST #MAIN $LB := #IMPLODE('stm' LAST #MAIN $NumStat);

LAST #MAIN $NumStat := LAST #MAIN $NumStat + 1; /

#stmt '.' *) .) -- riconosce blocco istruzioni

##

#stmt /#ADDSTM(#IMPLODE('{' $$ '}')); / (* #SCAN *)

##

#SCAN (('JUMP' 'TO') ! ('GO' 'TO') ! 'JUMP' ! 'GO') 'OP' $LAB ('.' ! ',')

/#ADDLAB($LAB);

$SP := NULL;

IF LAST #MAIN $FLPREV <> NULL -> $SP := ' ' FI;

#ADDSTM(#IMPLODE($SP 'Goto Lab' $LAB ';'));

IF LAST #MAIN $FLPREV <> NULL -> #ADDSTM('end;') FI;

LAST #MAIN $FLPREV := NULL;FAIL;

/ ;;

'TRANSFR_ITEM' $IN 'TO' $OUT $FIL1 '.'

/#ADDSTM(#IMPLODE($OUT ' := ' $IN ';'));FAIL/;;

'IF' 'END' 'OF' 'DATA'

/$FL := LAST #MAIN $FLPREV;

#ADDSTM(#IMPLODE('if NumRec = 0 then begin'));

#ADDSTM(#IMPLODE(' FillChar(' $FL ', SizeOf(' $FL '), ''Z'');'));

/;;

'SELECT_LEAST' 'KEY' ';'/FAIL;/;;

'IF' $FLC

/$stm := NULL;

FORALL $FL IN LAST #MAIN $FLIN DO

IF $FLC <> $FL -> $stm := #IMPLODE($stm 'if ' $FLC '.key <= ' $FL '.key then '); FI;OD;

#ADDSTM($stm);FAIL;

/;;

('INPUT' ! 'OUTPUT') (* $FlType := ('CUST_FILE' ! 'MASTER_FILE')

$FILE 'SERVOS' $F1 ',' $F2

/$Unit := #EXPLODE($FILE);

$Unit := $Unit[#LEN($Unit)];

$FlUnit := #IMPLODE('Fl' $Unit);

#ADDVAR($Unit 'Rec;');

#ADDVAR($FlUnit 'File;');

#ADDSTM(#IMPLODE('Assign (' $FlUnit ', ''' $FILE ''');'));

IF $FlType = 'CUST_FILE' ->

#ADDSTM(#IMPLODE('Reset (fl' $Unit ', SizeOf(' $Unit '));'));

LAST #MAIN $FLIN := LAST #MAIN $FLIN!.$Unit;

FI;

IF $FlType = 'MASTER_FILE' ->

#ADDSTM(#IMPLODE('Rewrite (fl' $Unit ', SizeOf(' $Unit '));')); FI;

/ *) ';'/FAIL/;;

'PRESELECTION'

/FORALL $FL IN LAST #MAIN $FLIN DO

#ADDSTM(#IMPLODE('blockread (fl' $FL ', ' $FL ', 1, NumRec);')) OD;FAIL/;;

'WRITE_ITEM' $FL '.'

/#ADDSTM(#IMPLODE('blockwrite (fl' $FL ', ' $FL ', 1);'));FAIL/;;

'READ_ITEM' $FL (';' ! '.')

/LAST #MAIN $FLPREV := $FL;

#ADDSTM(#IMPLODE('blockread (fl' $FL ', ' $FL ', 1, NumRec);'));

/;;

'TEST' $VAR '(' $FL ')' 'AGAINST' $VAR2 ';'

/#ADDSTM(#IMPLODE('ris := iff(' $FL '.' $VAR ', ' #CHR(39) $VAR2 #CHR(39) ');'));FAIL/;;

'IF_EQUAL' /#ADDSTM('if ris = 0 then');FAIL;/;;

'CLOSE_OUT' 'FILE' $FL '.'

/#ADDSTM(#IMPLODE('close (fl' $FL ');'));FAIL;/;;

'STOP' '.'

/#ADDSTM ('exit;');FAIL;/;;

$A /IF $A = '.' -> FAIL FI/

##

#ADDSTM $X

/ $LST := LAST #MAIN $TreeStm.(LAST #MAIN $LB) !. $X;

LAST #MAIN $TreeStm ++:= <. LAST #MAIN $LB : $LST .>;/

##

#ADDLAB $LAB /$L := #IMPLODE('Lab' $LAB);

LAST #MAIN $TreeLab ++:= <. $L : #IMPLODE($L ':') .>/

##

#ADDVAR $VAR $TYPE /LAST #MAIN $TreeVar ++:= <. $VAR : $TYPE .>/##

Figura 17