ESAME  DI  LINGUAGGI  E  TRADUTTORI

7 Maggio 1999 – Parte I (2 ore)

 

 

Esercizio 1

 

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

 

 

 

 

TABELLA DI PARSING

 

 

$

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)

 

 

Esercizio 2

 

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).

 

 

  1.  

 

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:

    L = {wuwwu | u,w Î {a,b}+ }

 

 


 

 

 

 

 

 


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).