ESAME DI LINGUAGGI E TRADUTTORI
7 Maggio 1999 – Parte I (2 ore)
1.
Scrivere
una grammatica che generi ed un automa
che riconosca il linguaggio
L =
{an am bp (bh)+ dr as
ct | s + t > n + m,
r > p, m,r > 0, n,s,t >=0}
Svolgimento:
·
n
+ m = q >0
·
(bh)+
= b* se h ³0
·
poiché r > p
e bpb* si pone p = 0 e dr = d+
L =
{ aq b* d+ as
ct | s + t > q, s + t ³ 0}
L = L1 È L2
L1 (q ³ t)
= {at as1 b*
d+ a+ as1 ct | t ³ 0, s1 > 0}
L2 (q <
t) = {aq b* d+ a* c+ cq
| q > 0}
dove L0 = b* d+ a*
2.
Scrivere
un parser discendente per il linguaggio definito dalla grammatica le cui
produzioni sono di seguito riportate:
Svolgimento:
Le
regole F e G non vengono richiamate da alcuna produzione e perciò possono
essere eliminate.
Insiemi First:
First(S) = {i,j,k}
First(S’) = {a,;}
First(S’’) = {b,c}
First(A) = {i,j,k}
First(A’) = {i,j,k,e}
First(B) = {a,e}
First(C) = {e}
First(C’) = {i,e}
First(D) = {i,j,k,a,h,e}
First(E) = {i,j,k}
First(H) = {b}
First(H’) = {g,e}
Insiemi Follows (quelli
utilizzati per la costruzione della tabella di Parser):
Follows(H’) = Follows(H) = Follows(B) = {h,’;’}
Follows(D) = Follows(S)È { j } = {$,j}
Follows(A’) = Follows(A) = First(S’)ÈG(D) = {a,’;’}È{i,j,k,a,h,’;’,$}
G(X)
= Unione degli insiemi guida che hanno come parte sinistra il non terminale X
|
$ |
b |
c |
g |
i |
j |
k |
h |
a |
; |
* |
S |
|
|
|
|
®AS’ |
®AS’ |
®AS’ |
|
|
|
|
S’ |
|
|
|
|
|
|
|
|
®aS’’ |
®;C*D |
|
S’’ |
|
®H;C*D |
®C |
|
|
|
|
|
|
|
|
A |
|
|
|
|
®iA’ |
®j |
®k |
|
|
|
|
A’ |
®e |
|
|
|
®A (1) |
®A (1) |
®A (1) |
®e |
®e |
®e |
|
B |
|
|
|
|
|
|
|
®e |
®aH |
®e |
|
C |
|
|
®eC’ |
|
|
|
|
|
|
|
|
C’ |
®e |
|
|
|
®iEjC’ |
|
|
|
|
|
®e |
D |
®e |
|
|
|
®Adj |
®Adj (2) |
®ADj |
®Bh |
®Bh |
®Bh |
|
E |
|
|
|
|
® i |
® j |
® k |
|
|
|
|
H |
|
®bH’ |
|
|
|
|
|
|
|
|
|
H’ |
|
|
|
®gH’ |
|
|
|
®e |
|
®e |
|
(1)
sta
ad indicare un conflitto con la regola A’ ® e
(2)
sta
ad indicare un conflitto con la regola D ® e
ESAME DI LINGUAGGI E TRADUTTORI
7 Maggio 1999 – Parte II
(2 ore)
1.
Scrivere
un programma Prolog contiene(M,V) che
riceve una matrice quadrata M di dimensione
n ed una stringa V di dimensione
k, k £ n, e restituisce True se la
stringa V è contenuta nella diagonale principale di M.
2.
Due
matrici di uguali dimensioni sono simili se la somma degli elementi della
diagonale principale di una matrice è uguale alla somma degli elementi della
diagonale principale dell’ altra matrice. Si realizzi un programma
Prolog simili(A,B) che riceva
in ingresso due matrici quadrate di interi, A di dimensione n ´ n e B di dimensioni k ´ k, con k £ n, e verifichi la presenza
all’interno di A di una sottomatrice k ´ k
simile alla matrice B.
Soluzione:
1.
ELEM ([X|_],X,0).
ELEM
([_|L],N,X) :- ELEM (L,X,N1), N is N1+1.
DP([R|M],[X|T],N)
:- ELEM (R,X,N), N1 is N+1, DP(M,T,N1).
DP([],[],_).
PREFIX([],_).
PREFIX([X|L1],[X|L2])
:- PREFIX(L1, L2).
SUBLIST(X,Y) :-
PREFIX(X,Y).
SUBLIST(X,[Y|YS
]) :- SUBLIST(X, YS).
LENGTH([],0).
LENGTH([X|L],N)
:- LENGTH(l,N1), N is N1+1.
CONTIENE(M,V)
:- DP(M,Dp,1), SUBLIST(V,Dp).
lung([], 0).
lung([_|L], N):-lung(L, N1), N is N1+1.
somma([],0).
somma([X|L],S):-somma(L,S1), S is X+S1.
submatr([_|M1],RIGA,COL,DIM,N):-RIGA>1, R1 is RIGA-1,
submatr(M1,R1,COL,DIM,N).
submatr([M|M1],1,COL,DIM,[N|N1]):-subvettore(M,COL,DIM,N),
CNT
is DIM-1, sub1(M1,COL,DIM,CNT,N1).
sub1([M|M1],COL,DIM,CNT,[N|N1]):-CNT>1,subvettore(M,COL,DIM,N),
CNT1
is CNT-1,sub1(M1,COL,DIM,CNT1,N1).
sub1([M|_],COL,DIM,1,[N]):-subvettore(M,COL,DIM,N).
subvettore([_|X1],COL,DIM,L):-COL>1, COL1 is COL-1,
subvettore(X1,COL1,DIM,L).
subvettore([X|X1],1,DIM,[X|Y1]):-DIM>1, DIM1 is DIM-1,
subvettore(X1,1,DIM1,Y1).
subvettore([X|_],1,1,[X]).
sottomatricidimk(M,K,M1):-lung(M,N), sottmatr(M,K,M1,N,1,1).
sottmatr(M,K,M1,_,I,J):-submatr(M,I,J,K,M1).
sottmatr(M,K,M1,N,I,J):- I=<N-K, I1 is I+1,
sottmatr(M,K,M1,N,I1,J).
sottmatr(M,K,M1,N,I,J):-I>N-K, J=<N-K, J1 is J+1,
sottmatr(M,K,M1,N,1,J1).
simili(A,B):-lung(B,K), lung(A,N), K<N, dp(B, DPB, 1),
somma(DPB, S),
sottomatricidimk(A,K,M1),
dp(M1,DPM1,1), somma(DPM1,S).
simili(A,B):-lung(B,K), lung(A,N), K=:=N, dp(B, DPB, 1),
somma(DPB, S),
dp(A,DPA,1),
somma(DPA,S).
ESERCIZIO
3
1.
Scrivere
una macchina di Turing che riconosca il
linguaggio:
2.
Verificare
se la seguente grammatica è LR(1) :
S ® hAB
| BaS
A ® aB | cS
B ® bB
| c
Soluzione:
|
h |
a |
b |
c |
$ |
S |
A |
B |
0 |
s-2 |
|
|
s-4 |
|
1 |
|
5 |
1 |
|
|
|
|
accetta |
|
|
|
2 |
|
s-8 |
|
s-7 |
|
|
6 |
|
3 |
|
|
s-3 |
s-4 |
|
|
|
10 |
4 |
|
B ® c |
|
|
|
|
|
|
5 |
|
s-9 |
|
|
|
|
|
|
6 |
|
|
s-12 |
s-13 |
|
|
|
11 |
7 |
s-21 |
|
s-3 |
s-4 |
|
20 |
|
22 |
8 |
|
|
s-17 |
s-16 |
|
|
|
19 |
9 |
s-2 |
|
s-3 |
s-4 |
|
15 |
|
5 |
10 |
|
B ® bB |
|
|
|
|
|
|
11 |
|
|
|
|
S->hAB |
|
|
|
12 |
|
|
s-12 |
s-13 |
|
|
|
14 |
13 |
|
|
|
|
B ® c |
|
|
|
14 |
|
|
|
|
B ® bB |
|
|
|
15 |
|
|
|
|
S ® BaS |
|
|
|
16 |
|
|
B ® c |
B ® c |
|
|
|
|
17 |
|
|
s-17 |
s-16 |
|
|
|
18 |
18 |
|
|
B ® bB |
B ® bB |
|
|
|
|
19 |
|
|
A ® aB |
A ® aB |
|
|
|
|
20 |
|
|
A ® cS |
A ® cS |
|
|
|
|
21 |
|
s-8 |
|
s-7 |
|
|
23 |
|
22 |
|
s-25 |
|
|
|
|
|
|
23 |
|
|
s-17 |
s-16 |
|
|
|
24 |
24 |
|
|
S->hAB |
S->hAB |
|
|
|
|
25 |
s21 |
|
s-3 |
s-4 |
|
26 |
|
22 |
26 |
|
|
S ® BaS |
S ® BaS |
|
|
|
|
Poiché non ci sono conflitti, la grammatica è
LR(1).