% ################################################
% ### Riconoscitore, visualizzatore e ###
% ### valutatore di espressioni (in Prolog). ###
% ### Di Luigi Antenucci ###
% ### date marzo-maggio'98 ###
% ### per Linguaggi e Traduttori ###
% ################################################
%
%============================================================================
%=== GRAMMATICA DELLE ESPRESSIONI: UNA DESCRIZIONE GENERALE ===
%============================================================================
% Insieme dei simboli terminali: VT={+,-,*,/,=,<,>,0,1..9,a..z}
% Insieme dei simboli NON term.: VN={Exp,Term,Factor,Num,Ident}
% Scopo della grammatica: Exp
% Insieme delle produzioni:
% Exp ::= Exp + Term
% Exp ::= Exp - Term
% Exp ::= Ident = Exp
% Exp ::= Term
% Term ::= Term * Factor
% Term ::= Term / Factor
% Term ::= Factor
% Factor::= < Exp > (nota: uso parentesi "angolate")
% Factor::= Num
% Factor::= Ident
%
% ( Num ::= Digit | Digit Num )
% ( Digit ::= 0|1|2|3|4|5|6|7|8|9 )
% ( Ident ::= Let | Let Ident2 )
% ( Ident2::= Let | Num )
%
% La grammatica presenta ricorsioni a sinistra (E::= E xxx), percio'
% DEVE essere CONVERTITA in una grammatica equivalente ma senza
% ricorsioni sinistre. Un esempio di conversione e':
% A ::= Aß | µ =====> A ::= µR
% R ::= ßR | § (§=str.vuota)
% La grammatica da implementare e' quindi:
%
% Exp ::= Term RExp
% Exp ::= Ident = Exp
% RExp ::= + Term RExp
% RExp ::= - Term RExp
% RExp ::= §
% Term ::= Factor RTerm
% RTerm ::= * Factor RTerm
% RTerm ::= / Factor RTerm
% RTerm ::= §
% Factor::= < Exp > (nota: uso parentesi "angolate")
% Factor::= Num
% Factor::= Ident
%
%****************************************************************************
%*** RICONOSCITORE DELLA GRAMMATICA DELLE ESPRESSIONI ***
%****************************************************************************
% Nota: l'espressione da rappresentare deve essere passata sottoforma di
% lista di operatori, operandi e simboli, cioe' in forma di "token"
% che rappresentano l'espressione (in notazione infissa!).
% Nota ancora: le tonde vanno passate come "<" e ">".
%
% Esempi:
% espressione goal Prolog unificazione resa
% 1+2 e1(X,[1,+,2],[]). X=piu(1,2)
% 1+2+3 e1(X,[1,+,2,+,3],[]). X=piu(piu(1,2),3)
% a+b*c e1(X,[a,+,b,*,c],[]). X=piu(a,per(b,c))
% a*b+c e1(X,[a,*,b,+,c],[]). X=piu(per(a,b),c)
% a*(b+c) e1(X,[a,*,<,b,+,c,>],[]). X=per(a,piu(b,c))
% a=5 e1(X,[a,=,5],[]). X=ass(a,5)
%
% Nota bene: l'unificazione di "X" (resa) e' la rappresentazione interna
% con struttura ad ALBERO dell'espressione!
% piu
% X=piu(piu(1,2),3) equivale a / \
% piu 3
% / \
% 1 2
%
e1(RI, In, Out) :- t1(T, In, Tmp), /* E::= T RE */
re1(RI, T, Tmp, Out).
e1(ass(L,R), In, Out) :- id1(L, In, [=|Tmp]), !, /* E::= ID = E */
e1(R, Tmp, Out).
re1(RI, STATO, [+|In], Out) :- !, /* RE::= + T RE */
t1(T, In, Tmp),
re1(RI, piu(STATO,T), Tmp, Out).
re1(RI, STATO, [-|In], Out) :- !, /* RE::= - T RE */
t1(T, In, Tmp),
re1(RI, men(STATO,T), Tmp, Out).
re1(STATO, STATO, In, In). /* RE::= § */
t1(RI, In, Out) :- f1(F, In, Tmp), /* T::= F RT */
rt1(RI, F, Tmp, Out).
rt1(RI, STATO, [*|In], Out) :- !, /* RT::= * F RT */
f1(F, In, Tmp),
rt1(RI, per(STATO,F), Tmp, Out).
rt1(RI, STATO, [/|In], Out) :- !, /* RT::= / F RT */
f1(F, In, Tmp),
rt1(RI, div(STATO,F), Tmp, Out).
rt1(STATO, STATO, In, In). /* RT::= § */
f1(SUB, [<|Tmp], Out) :- !, /* F::= < E > */
e1(SUB, Tmp, [>|Out]).
f1(NUM, In, Out) :- nn1(NUM, In, Out), !. /* F::= NUM */
f1(ID, In, Out) :- /* non e' un numero */ /* F::= IDENT */
/* (ho "cut" supra) */
id1(ID, In, Out).
nn1(NUM, [NUM|Out], Out) :- number(NUM).
id1(ID, [ID|Out], Out). /* Ogni altra cosa (non numero) */
/* e' un identificatore! */
%****************************************************************************
%*** STAMPA DELLA RAPPRESENTAZIONE INTERNA (A ALBERO) GENERATA ***
%****************************************************************************
% La stampa (visita) puo' essere fatta in vari modi:
% MODO= "pre" ===> visita prefissa
% "in" ====> " " " infissa
% "post" ==> " " " postfissa;
% LOS= "let" ===> stampa operatori con nomi (piu, per,..)
% "sim" ===> " " " " " " " " con simboli (+, *,..)
% I valori predefiniti sono "in" e "sim"!
%
% Nota: per accedere all'INFormazione del nodo corrente si usa "functor(..)"
% mentre per i sottoalberi sinistro/destro si usa "arg(1/2,..)".
%
% Esempio: e(X,[1,+,2,*,5],[]),visita(X,in,sim).
%
visita(RI) :- visita(RI, in, sim). /* Visita la R.I. */
visita(RI, MODO) :- visita(RI, MODO, sim). /* in un certo modo */
visita(RI, MODO, LOS) :- write(MODO),write(': '), /* con lettere o simboli */
visitavera(RI, MODO, LOS),
nl.
visitavera(RI, MODO, LOS) :- functor(RI, INF, N),
visitabis(RI, INF, N, MODO, LOS).
visitabis(RI, INF, 0, MODO, LOS) :- /* Niente tonde: e' un singolo termine */
!, visitasotto(RI, INF, 0, MODO, LOS).
visitabis(RI, INF, 2, MODO, LOS) :- write('('),write(' '), /* Si' tonde */
visitasotto(RI, INF, 2, MODO, LOS),
write(')'),write(' ').
visitasotto( _, INF, 0, _, LOS) :- /* 0=no sottoalberi->singolo operando*/
!, visitanodo(INF, LOS).
visitasotto(RI, INF, 2, pre, LOS) :- !, /* VISITA PREfissa */
visitanodo(INF, LOS),
arg(1, RI, SX), visitavera(SX, pre, LOS),
arg(2, RI, DX), visitavera(DX, pre, LOS),!.
visitasotto(RI, INF, 2, in, LOS) :- !, /* VISITA INfissa */
arg(1, RI, SX), visitavera(SX, in, LOS),
visitanodo(INF, LOS),
arg(2, RI, DX), visitavera(DX, in, LOS),!.
visitasotto(RI, INF, 2, post, LOS) :- !, /* VISITA POSTfissa */
arg(1, RI, SX), visitavera(SX, post,LOS),
arg(2, RI, DX), visitavera(DX, post,LOS),
visitanodo(INF, LOS),!.
visitanodo(piu, sim) :- !,write('+'),write(' '). /* traduzione di */
visitanodo(men, sim) :- !,write('-'),write(' '). /* lettere->simboli */
visitanodo(ass, sim) :- !,write('='),write(' ').
visitanodo(per, sim) :- !,write('*'),write(' ').
visitanodo(div, sim) :- !,write('/'),write(' ').
visitanodo(INF, _) :- write(INF),write(' ').
%****************************************************************************
%*** CALCOLO DELLA RAPPRESENTAZIONE INTERNA (A ALBERO) GENERATA ***
%****************************************************************************
% Viene visitato l'albero e calcolata l'espressione.
% P.S: la visita viene fatta sempre in "post-order" (postfissa), cioe' prima
% "valuto" i sottoalberi (prima il sinistro e poi il destro) e sui loro
% risultati applico l'operatore (data dall'operatore del nodo).
% P.P.S: la "valuta" con il parametro "SXDX" serve nella valutazione per
% decidere se rendere la variabile (sin) cioe' l'l-value oppure il
% valore associato alla variabile (des) cioe' l'r-value.
%
% Esempio: e(X,[1,+,2,*,5],[]),visita(V,X). rende V=11, X=piu(1,per(2,5))
%
valuta(VAL, RI) :- valuta(VAL, RI, des). /* Valuta la R.I. in VAL */
valuta(VAL, RI, SXDX) :- functor(RI, INF, N),
/* "functor"-> INF=info del nodo; N=N—sottoalberi */
valutasotto(VAL, RI, INF, N, SXDX).
valutasotto(VAL, _, INF, 0, SXDX) :- /* 0=no sottoalberi->singolo operando*/
!, valutanodo(VAL, INF, SXDX).
valutasotto(VAL, RI, INF, 2, _) :- !, /* VISITA POSTfissa dei sottoalberi*/
arg(1, RI, SX), valuta(VALSX, SX, sin),
arg(2, RI, DX), valuta(VALDX, DX, des),
/* In VALSX ho l'l-value (simbolo) e */
/* in VALDX ho l'r-value (valore)! */
valutanodo(VAL, INF, VALSX, VALDX).
valutanodo(VAL, piu, ARG1, ARG2) :- !,
valutanodo(ARG1VAL, ARG1, des),
VAL is ARG1VAL + ARG2.
valutanodo(VAL, men, ARG1, ARG2) :- !,
valutanodo(ARG1VAL, ARG1, des),
VAL is ARG1VAL - ARG2.
valutanodo(VAL, per, ARG1, ARG2) :- !,
valutanodo(ARG1VAL, ARG1, des),
VAL is ARG1VAL * ARG2.
valutanodo(VAL, div, ARG1, ARG2) :- !,
valutanodo(ARG1VAL, ARG1, des),
VAL is ARG1VAL / ARG2.
valutanodo( _, ass, LVAL, _ ) :- /* Controllo se variabile e' assegnata */
clause(assegnazione(LVAL,_),_),
/* (se si',la tolgo e la ricreo nuova) */
retract(assegnazione(LVAL,_)),
fail. /* vado alla clausola successiva */
valutanodo(VAL, ass, LVAL, RVAL) :- /* Qui la variabile non e' assegnata! */
/* Assegno il valore alla variabile */
!,
assert(assegnazione(LVAL,RVAL)),
VAL is RVAL. /* Rendo l'r-value! */
valutanodo(VAL, INF, _) :- number(INF), !, /* E' un numero? */
/* Se si', ne rendo il valore */
VAL is INF.
valutanodo(VAL, INF, des) :- /* "des"=voglio l'r-value (il valore). */
/* Accedo al valore del simbolo (se e' */
/* stato definito) e lo rendo in VAL. */
clause(assegnazione(INF,_),_),
!,
assegnazione(INF,VAL), /*Prelevo valore*/
number(VAL).
valutanodo( _, INF, des) :- /* La "clause" sopra e' falsa (ho cut):*/
/* Si e' cercato di accedere al valore */
/* di una variabile che non e' stata */
/* ancora definita: interrompo valutaz.*/
write('errore: simbolo non definito "'),
write(INF),write('" '),
abort. /* valutazione impossibile */
valutanodo(VAL, INF, sin) :- /* "sin"=voglio l'l-value (il simbolo).*/
/* Basta rendere l'informaz. del nodo. */
VAL=INF.
%****************************************************************************
%*** E SE CAMBIO LA NOTAZIONE DELLA LISTA D'INGRESSO? ***
%*** BASTA GENERARE LA STESSA R.I. E POSSO RIUSARE "visita" e "valuta"! ***
%****************************************************************************
% Insieme delle produzioni per le TRE NOTAZIONI:
% Notazione PREfissa (pre) INfissa (in) POSTfissa (post)
% E::= + E E E::= E + T E::= E E +
% E::= - E E E::= E - T E::= E E -
% E::= = ID E E::= ID = E E::= ID E =
% E::= T
% E::= * E E T::= T * F E::= E E *
% E::= / E E T::= T / F E::= E E /
% E::= F T::= F E::= F
% F::= < E >
% F::= NUM F::= NUM F::= NUM
% F::= ID F::= ID F::= ID
% Nota: SOLO la notazione INfissa ha bisogno delle parentesi!
%
% Ma bisogna togliere la RICORSIONE SINISTRA (non dalla prima gramm.)!
% Notazione PREfissa (pre) INfissa (in) POSTfissa (post)
% E::= + E E E ::= T RE E ::= F RE
% E::= - E E E ::= ID = E RE::= §
% E::= = ID E RE::= + T RE RE::= F RO RE
% RE::= - T RE RO::= +
% RE::= § RO::= -
% T ::= F RT RO::= *
% E::= * E E RT::= * F RT RO::= /
% E::= / E E RT::= / F RT RO::= =
% E::= F RT::= § RO::= F RO RO
% F ::= < E >
% F::= NUM F ::= NUM F ::= NUM
% F::= ID F ::= ID F ::= ID
%
% Grammatica: LL(1) LL(2)
%
% Esempi di scrittura:
% notazione espressione in goal Prolog unificazione
% pre + 1 2 e(pre, X,[+,1,2],[]). X=piu(1,2)
% in 1 + 2 e(in, X,[1,+,2],[]). X=piu(1,2)
% post 1 2 + e(post,X,[1,2,+],[]). X=piu(1,2)
% pre * a (+ b c) e(pre, X,[*,a,+,b,c],[]). X=per(a,piu(b,c))
% in a * (b + c) e(in, X,[a,*,<,b,+,c,>],[]). X=per(a,piu(b,c))
% post a (b c +) * e(post,X,[a,b,c,+,*],[]). X=per(a,piu(b,c))
%
% NOTA MOLTO BENE: avendo la stessa espressione in ingresso in
% qualsivoglia notazione (pre-in-post),
% LA RAPPRESENTAZIONE INTERNA (ALBERO) NON CAMBIA!
% Per visualizzare/valutare la R.I. resa si usano le solite "visita"/"valuta"
%
% Per esempi: usare "vvv" per visualizzare tutti i dati sull'espressione.
%
/* Ottimizzo i tempi di scrittura */
vv(VAL,RI) :- visita(RI),valuta(VAL,RI). /* Visita+Valuta(in) */
vv3(VAL,RI) :- visita(RI,pre), /* Visita+Valuta(pre+in+post) */
visita(RI,in),
visita(RI,post),
valuta(VAL,RI).
vvv(VAL,RI) :- write('albero: '),write(RI),nl, /*Albero+Visita+ */
write(' '), visita(RI,pre), /*Valuta(pr+i+po)+Valore */
write(' '),visita(RI,in),
write(' '), visita(RI,post),
valuta(VAL,RI),
write('valore: '),write(VAL),nl.
/*** PREFISSA ***/
e(pre, piu(X,Y), [+|In], Out) :- !, /* E::= + E E */
e(pre, X, In, Tmp),
e(pre, Y, Tmp, Out).
e(pre, men(X,Y), [-|In], Out) :- !, /* E::= - E E */
e(pre, X, In, Tmp),
e(pre, Y, Tmp, Out).
e(pre, ass(L,R), [=|In], Out) :- !, /* E::= = ID E */
In = [L|Tmp],
ident(L),
e(pre, R, Tmp, Out).
e(pre, per(X,Y), [*|In], Out) :- !, /* E::= * E E */
e(pre, X, In, Tmp),
e(pre, Y, Tmp, Out).
e(pre, div(X,Y), [/|In], Out) :- !, /* E::= / E E */
e(pre, X, In, Tmp),
e(pre, Y, Tmp, Out).
e(pre, RI, In, Out) :- f(pre, RI, In, Out). /* E::= F */
/*** INFISSA ***/
e( in, RI, In, Out) :- t( in, T, In, Tmp), /* E::= T RE */
re(in, RI, T, Tmp, Out), !.
e( in, ass(L,R), In, Out) :- In = [L,=|Tmp], /* E::= ID = E */
ident(L),
!,
e( in, R, Tmp, Out).
re(in, RI, STATO, [+|In], Out) :- !, /* RE::= + T RE */
t( in, T, In, Tmp),
re(in, RI, piu(STATO,T), Tmp, Out).
re(in, RI, STATO, [-|In], Out) :- !, /* RE::= - T RE */
t( in, T, In, Tmp),
re(in, RI, men(STATO,T), Tmp, Out).
re(in, STATO, STATO, In, In). /* RE::= § */
t( in, RI, In, Out) :- f( in, F, In, Tmp), /* T::= F RT */
rt(in, RI, F, Tmp, Out).
rt(in, RI, STATO, [*|In], Out) :- !, /* RT::= * F RT */
f( in, F, In, Tmp),
rt(in, RI, per(STATO,F), Tmp, Out).
rt(in, RI, STATO, [/|In], Out) :- !, /* RT::= / F RT */
f( in, F, In, Tmp),
rt(in, RI, div(STATO,F), Tmp, Out).
rt(in, STATO, STATO, In, In). /* RT::= § */
f( in, SUB, [<|Tmp], Out) :- !, /* F::= < E > */
e(in, SUB, Tmp, [>|Out]).
/*** POSTFISSA ***/
e( post, RI, In, Out) :- f( post, F1, In, Tmp), /* E::= F RE */
re(post, RI, F1, Tmp, Out).
re(post, F1, F1, [], []) :- !. /* RE::= § */
re(post, RI, F1, In, Out) :- f( post, F2, In, Tmp1), /* RE::= F RO RE */
ro(post, RITmp, F1, F2, Tmp1, Tmp2),
re(post, RI, RITmp, Tmp2, Out).
ro(post, piu(F1,F2), F1,F2, [+|In], In) :- !. /* RO::= + */
ro(post, men(F1,F2), F1,F2, [-|In], In) :- !. /* RO::= - */
ro(post, per(F1,F2), F1,F2, [*|In], In) :- !. /* RO::= * */
ro(post, div(F1,F2), F1,F2, [/|In], In) :- !. /* RO::= / */
ro(post, ass(F1,F2), F1,F2, [=|In], In) :- ident(F1),!. /* RO::= = */
ro(post, RI, F1,F2, In,Out) :- f( post, F3, In, Tmp1), /* RO::= F RO RO */
ro(post, R23, F2, F3, Tmp1, Tmp2),
ro(post, RI, F1, R23, Tmp2, Out).
/* (COMUNE a tutte e tre) */
f( _, NUM, [NUM|In], In) :- number(NUM), !. /* F::= NUM */
f( _, ID, [ID|In], In) :- ident(ID). /* F::= ID */
ident(ID) :- \+ number(ID), /* F::= NUM */
\+ operatore(ID).
operatore(+).
operatore(-).
operatore(*).
operatore(/).
operatore(=).
%****************************************************************************
% Esempi pronti per essere usati nel SICStus Prolog (file "spcmd.hst"):
% consult('pro-exp/prlg-exp.pl').
% e(in, X,[1,+,2],[]), vvv(V,X).
% e(in, X,[1,+,2,*,3],[]), vvv(V,X).
% e(in, X,[1,*,2,+,3],[]), vvv(V,X).
% e(in, X,[1,*,<,2,+,3,>],[]), vvv(V,X).
% e(in, X,[a,=,5],[]), vvv(V,X).
% e(in, X,[b,=,2],[]), vvv(V,X).
% e(in, X,[a,+,b,*,b],[]), vvv(V,X).
% listing(assegnazione).
% e(pre, X,[+,1,2],[]), vvv(V,X).
% e(in, X,[1,+,2],[]), vvv(V,X).
% e(post,X,[1,2,+],[]), vvv(V,X).
% e(pre, X,[*,2,+,4,8],[]), vvv(V,X).
% e(in, X,[2,*,<,4,+,8,>],[]), vvv(V,X).
% e(post,X,[2,4,8,+,*],[]), vvv(V,X).
% e(pre, X,[*,*,2,3,+,4,5],[]), vvv(V,X).
% e(post,X,[2,3,*,4,5,+,*],[]), vvv(V,X).
% e(pre, X,[=,a,*,2,+,4,8],[]), vvv(V,X).
%******************************* Fine File **********************************