[cpl] Ultimele sfaturi utile inainte de examen

[Bogdan Nitulescu]

Salut, 

Mai e foarte putin timp inainte de ultimul examen din sesiune, si inainte sa incepem vroiam sa va trimit cateva sfaturi: 

- Nu scrieti foarte mult si nu trebuie sa redati exact informatia din slide-urile de la curs. Examenul va consta doar dintr-un set de exercitii si fiecare subiect este gandit pentru a fi rezolvat intr-un interval limitat de timp. Conteaza ca rezolvarea exercitiilor sa fie corecta si sa fie facuta conform metodelor predate la cursuri. 

- Puteti folosi documentatie pe hartie, insa nu si laptopuri, sau telefoane. 

- Cateva exemple de subiecte tipice si rezolvarile lor. Nu e o lista exhaustiva, pot aparea si alte tipuri de subiecte. 

1. Scrieti o gramatica LR(1) ce recunoaste limbajul seturilor de paranteze ce se inchid corect, de exemplu: 
“” “()” “(())” “()(())(()(()))” 

S → λ 
S → S P 
P → ( S ) 

2. Transformati gramatica LR(1) intr-o gramatica LL(1) 

S → λ 
S → P S 
P → ( S ) 



3. Scrieti, in pseudocod (limbaj la alegere, tip Java sau Python), un program ce citeste un sir de tokeni si, daca sirul face parte din limbajul de mai sus, calculeaza adancimea maxima de paranteze imbricate; altfel arunca o eroare. 




“” → 0 “()” → 1 “(())” → 2 “()(())(()(()))” → 3 




Programul trebuie sa fie un parser descendent recursiv construit pe baza unei gramatici de atribute LL(1) si trebuie sa trateze corect erorile. Conditiile de eroare vor fi verificate pe baza multimilor FIRST si FOLLOW. Aveti la dispozitie o variabila globala la pentru lookahead la, o functie NEXT() ce intoarce urmatorul token din lexer, o functie ERROR() ce arunca o exceptie, si o functie MATCH(). 




Gramatica de atribute: 

S → λ S.n = 0 

S → P S S1.n = max (P.n, S2.n) 

P → ( S ) P.n = S.n + 1 




Multimile FIRST, FOLLOW relevante: 

FOLLOW(S) = { EOF, ')' } 


FIRST (P) = { '(' } 





Pseudocod: 



Depth() { la = NEXT(); r = S(); if (la == EOF) return r; else ERROR(); } 




S() { if (la in [EOF, ')' ] ) return 0; 

else if (la == '(' ) return max ( P(), S() ); 

else ERROR(); } 




P() { MATCH ('('); r = S(); MATCH (')'); return r; } 




MATCH(token) { if (la == token) la = NEXT(); else ERROR(); } 


4.Pentru codul high level urmator, scrieti codul low-level corespunzator intr-un limbaj intermediar de tip “3-address code” cu registri nelimitati 

while ( x > 0) { x = x - ( y + 1 ); } 




L1: 

if x <= 0 goto L2 

V1 = y + 1 

x = x - V1 

goto L1 

L2: 


5. Impartiti codul in basic blocks si desenati graful fluxului de control (CFG) 





B1 	

if x <= 0 goto L2 


B2 	

V1 = y + 1 

x = x - V1 

goto L1 


6. Identificati buclele naturale si scoateti instructiunile invariante in afara buclei 





O bucla, {B1, B2} , B1 header. Instructiunea "V1 = y + 1" este invarianta si va fi mutata in pre-header: 





V1 = y + 1 

L1: 

if x <= 0 goto L2 

x = x - V1 

goto L1 

L2: 


7.O variabila este in viata intr-un punct din program daca exista o posibilitate ca valoarea ei curenta sa fie citita inainte ca aceasta sa fie distrusa printr-o operatie de scriere.Proiectati o analiza a fluxului de date care sa identifice la compilare, variabilele in viata, de exemplu: 
// nicio variabila in viata 
a = 1; // a este in viata 
b = 2; // a si b sunt in viata 
c = a + b; // c este in viata 
return c; 
Descrieti algoritmul folosit pentru analiza: 
- Care este structura de date folosita? Pentru fiecare punct din program, multimea variabilelor in viata in acest punct (reprezentata ca set sau vector de biti) 
- Cum este initializata? Multimea vida 

- Care este directia: ascendenta, descendenta? Descendenta 
- Cum se calculeaza functiile de transfer pentru instructiuni de tipul x = y + z ? In = Out - { x } U { y , z } 
- Cum se calculeaza functiile de transfer la intrarea/iesirea dintr-un basic block? Out(b) = U ( In(s) ) pentru fiecare succesor s al blocului b 



8.Consideram un procesor pe 32 biti ce suporta urmatoarele instructiuni: 
CALL label 
RETURN 
LOAD reg, [reg + constant] 
STORE reg, [reg + constant] 
ADD reg, reg, constant 
Desenati cadrul de stiva si scrieti codul asamblare corespunzator codului C : int f(int x){ return g(x) – 1; } 

Conventia de apel este urmatoarea: 
- parametrii se trimit prin stiva, si rezultatul functiei se intoarce in registrul r0. 

- exista un stack pointer, sp . Nu exista frame pointer. 
- instructiunea CALL scade valoarea sp cu 4 bytes si apoi salveaza in *sp adresa de intoarcere. 
- registrii r0 – r3 sunt volatili. Registrii r4 - r7 sunt nonvolatili 



ADD sp, sp -4 ; prolog: spatiu pentru cadrul de stiva al lui f() 


LOAD r0, [sp + 8] ; se incarca parametrul x 


STORE r0, [sp] ; se pregateste primul parametru pentru g() 
CALL g 


ADD r0, r0, -1 ; return g(x) - 1 
ADD sp, sp, 4 ; epilog 
RETURN 








	

Parametrul x 



	

Adresa de intoarcere 


sp 	

Parametru pentru g 


9.Consideram un procesor ce poate avea in executie, simultan, doua operatii aritmetice. Instructiunile sunt lansate in ordine, nu mai mult de doua la fiecare ciclu, si executia lor dureaza un ciclu. Reordonati instructiunile de mai jos folosind algoritmul list scheduling: 
mov r0,1 (A) 
add r1,r0,1 (B) 
mov r2,2 (C) 
add r2,r2,1 (D) 
- Numarul de cicli necesari pentru executia codului intial : 3 
1: A 
2: B C 
3: D 
- Ce dependente apar intre instructiuni: Dependente de date: (A) → (B), (C) → (D) 
- Noua ordine a instructiunilor dupa planificare: A C B D 
- Numarul de cicli necesari pentru executia codului dupa planificare: 2 
1: A C 
2: B D 
10.Secventa urmatoare de cod contine variabile, v0 – v2, pentru care sunt disponibili registri fizici: r0, r1 Alocati registrii folosind un algoritm bazat pe colorare si scrieti codul rezultat dupa alocare. 
(1) mov v0, 0 
(2) add v1, v0, 1 
(3) cmp v1, v2 
(4) add v1, v1, 1 
(5) store v1, [0x1000] 
- Identificati weburile si adaugati variabile noi daca este cazul: v3 este o variabila nou introdusa 
(1) mov v0, 0 
(2) add v1, v0, 1 
(3) cmp v1, v2 
(4) add v3, v1, 1 
(5) store v3, [0x1000] 
- Identificati care sunt punctele din program unde fiecare variabila este in viata (“live range”). 
- Desenati graful de interferenta intre variabile : 
- Alocati registrii fizici folosind graful de interferenta si scrieti codul rezultat dupa alocare. 
V2: r0 
V0: r1 
V1: r1 
v3: r0 

mov r1, 0 
add r1, r1, 1 
cmp r1, r0 
add r0, r1, 1 
store r0, [0x1000] 


Succes, 
Bogdan Nitulescu 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cursuri.cs.pub.ro/pipermail/cpl/attachments/20180207/e852c206/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 1048117.3873310188
Type: image/png
Size: 4847 bytes
Desc: not available
URL: <http://cursuri.cs.pub.ro/pipermail/cpl/attachments/20180207/e852c206/attachment-0003.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 2632492.684929506
Type: image/png
Size: 1889 bytes
Desc: not available
URL: <http://cursuri.cs.pub.ro/pipermail/cpl/attachments/20180207/e852c206/attachment-0004.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 2724830.2073073727
Type: image/png
Size: 3615 bytes
Desc: not available
URL: <http://cursuri.cs.pub.ro/pipermail/cpl/attachments/20180207/e852c206/attachment-0005.png>