<html><body><div style="font-family: arial, helvetica, sans-serif; font-size: 12pt; color: #000000"><div>Salut,</div><div><br></div><div>Mai e foarte putin timp inainte de ultimul examen din sesiune, si inainte sa incepem vroiam sa va trimit cateva sfaturi:</div><div><br></div><div>- 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.</div><div><br></div><div>- Puteti folosi documentatie pe hartie, insa nu si laptopuri, sau telefoane.</div><div><br></div><div>- Cateva exemple de subiecte tipice si rezolvarile lor. Nu e o lista exhaustiva, pot aparea si alte tipuri de subiecte.<br></div><div><br></div><div><span style="font-size: 10pt; font-family: arial, helvetica, sans-serif;" data-mce-style="font-size: 10pt; font-family: arial, helvetica, sans-serif;">1. Scrieti o gramatica LR(1) ce recunoaste limbajul seturilor de paranteze ce se inchid corect, de exemplu:</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif; font-size: 10pt;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif; font-size: 10pt;">“” “()” “(())” “()(())(()(()))”</span><br><br><span style="font-size: 10pt;" data-mce-style="font-size: 10pt;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;">S → λ</span></em></span><br><span style="font-size: 10pt;" data-mce-style="font-size: 10pt;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;">S → S P</span></em></span><br><span style="font-size: 10pt;" data-mce-style="font-size: 10pt;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;">P → ( S )</span></em></span></div><div><hr><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif; font-size: 10pt;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif; font-size: 10pt;"></span></div><div><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif; font-size: 10pt;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif; font-size: 10pt;"><span style="font-family: arial, helvetica, sans-serif;" data-mce-style="font-family: arial, helvetica, sans-serif;">2. Transformati gramatica LR(1) intr-o gramatica LL(1)</span> <br><br><em>S → λ</em><br><em>S → P S</em><br><em>P → ( S )</em> </span></div><div><hr></div><div><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">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.</span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;">“” → <span face="Trebuchet MS, sans-serif"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">0 “()” → 1 “(())” → 2 “()(())(()(()))” → 3</span></span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">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(). </span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">Gramatica de atribute:</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-size: small; font-family: 'courier new', courier, monaco, monospace, sans-serif;" size="2" data-mce-style="font-size: small; font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span face="Trebuchet MS, sans-serif">S → </span><span face="Trebuchet MS, sans-serif">λ </span><span face="Trebuchet MS, sans-serif">S.n = 0 </span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-size: small; font-family: 'courier new', courier, monaco, monospace, sans-serif;" size="2" data-mce-style="font-size: small; font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span face="Trebuchet MS, sans-serif">S → </span><span face="Trebuchet MS, sans-serif">P S S1.n = max (P.n, S2.n) </span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">P → <span face="Trebuchet MS, sans-serif">( S )</span> P.n = S.n + 1</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">Multimile FIRST, FOLLOW relevante:</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"><span face="Trebuchet MS, sans-serif">FOLLOW(S) = { EOF, ')' }<br></span></span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">FIRST (P) = { '(' }<br></span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">Pseudocod:</span></span></em></p></div><div><br></div><div><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">Depth() { la = NEXT(); r = S(); if (la == EOF) return r; else ERROR(); }</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">S() { if (la in [EOF, ')' ] ) return 0;</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> else if (la == '(' ) return max ( P(), S() );</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> else ERROR(); }</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">P() { MATCH ('('); r = S(); MATCH (')'); return r; }</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">MATCH(token) { if (la == token) la = NEXT(); else ERROR(); }</span></span></em></p><hr><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">4.Pentru codul high level urmator, scrieti codul low-level corespunzator intr-un limbaj intermediar de tip “3-address code” cu registri nelimitati</span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">while ( x > 0) { x = x - ( y + 1 ); }</span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">L1:</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> if x <= 0 goto L2</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> V1 = y + 1</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> x = x - V1</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> goto L1</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">L2:</span></span></em></p><hr><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">5. Impartiti codul in basic blocks si desenati graful fluxului de control (CFG)<br></span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><table width="147" border="1" cellspacing="0" cellpadding="4"><colgroup><col width="17"> <col width="112"> </colgroup><tbody><tr valign="top"><td style="border-top: 1px solid #000000; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding: 0.1cm 0cm 0.1cm 0.1cm;" data-mce-style="border-top: 1px solid #000000; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding: 0.1cm 0cm 0.1cm 0.1cm;" width="17"><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">B1</span></span></em></p></td><td style="border: 1px solid #000000; padding: 0.1cm;" data-mce-style="border: 1px solid #000000; padding: 0.1cm;" width="112"><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">if x <= 0 goto L2</span></span></em></p></td></tr><tr valign="top"><td style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding: 0cm 0cm 0.1cm 0.1cm;" data-mce-style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding: 0cm 0cm 0.1cm 0.1cm;" width="17"><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">B2</span></span></em></p></td><td style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: 1px solid #000000; padding: 0cm 0.1cm 0.1cm 0.1cm;" data-mce-style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: 1px solid #000000; padding: 0cm 0.1cm 0.1cm 0.1cm;" width="112"><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">V1 = y + 1</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">x = x - V1</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">goto L1</span></span></em></p></td></tr></tbody></table><img src="cid:5b5bef6d51d70efbfd3e368fd175f51954fe60e3@zimbra" data-mce-src="cid:5b5bef6d51d70efbfd3e368fd175f51954fe60e3@zimbra"><hr><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">6. Identificati buclele naturale si scoateti instructiunile invariante in afara buclei<br></span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"><em>O bucla, {B1, B2} , B1 header. Instructiunea "V1 = y + 1" este invarianta si va fi mutata in pre-header:</em><br></span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> V1 = y + 1</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">L1:</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> if x <= 0 goto L2</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> x = x - V1</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">goto L1</span></span></em></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> L2:</span></span></em></p><hr><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">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:<br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> // nicio variabila in viata</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> a = 1; // a este in viata</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> b = 2; // a si b sunt in viata</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> c = a + b; // c este in viata</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> return c;</span><br>Descrieti algoritmul folosit pentru analiza:<br>- Care este structura de date folosita? <em>Pentru fiecare punct din program, multimea variabilelor in viata in acest punct (reprezentata ca set sau vector de biti)</em><br>- Cum este initializata? <em>Multimea vida</em></span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">- Care este directia: ascendenta, descendenta? <em>Descendenta</em><br>- Cum se calculeaza functiile de transfer pentru instructiuni de tipul x = y + z ? <em>In = Out - { x } U { y , z }</em><br>- Cum se calculeaza functiile de transfer la intrarea/iesirea dintr-un basic block? <em>Out(b) = U ( In(s) ) pentru fiecare succesor s al blocului b</em><br></span></span></p><hr><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">8.Consideram un procesor pe 32 biti ce suporta urmatoarele instructiuni:<br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> CALL label</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> RETURN</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> LOAD reg, [reg + constant]</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> STORE reg, [reg + constant]</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> ADD reg, reg, constant</span><br>Desenati cadrul de stiva si scrieti codul asamblare corespunzator codului C : <span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> int f(int x){ return g(x) – 1; }</span> </span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">Conventia de apel este urmatoarea:<br>- parametrii se trimit prin stiva, si rezultatul functiei se intoarce in registrul r0. </span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">- exista un stack pointer, sp . Nu exista frame pointer.<br>- instructiunea CALL scade valoarea sp cu 4 bytes si apoi salveaza in *sp adresa de intoarcere.<br>- registrii r0 – r3 sunt volatili. Registrii r4 - r7 sunt nonvolatili<br><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"></span></span></span></p><p style="margin: 0px;" data-mce-style="margin: 0px;"><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"> </span></span></p><em style="font-size: small;" size="2" data-mce-style="font-size: small;"><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">ADD sp, sp -4 ; prolog: spatiu pentru cadrul de stiva al lui f()<br></span></span></em><p style="margin: 0px; font-weight: normal;" data-mce-style="margin: 0px; font-weight: normal;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">LOAD r0, [sp + 8] ; se incarca parametrul x<br></span></span></em></p><p style="margin: 0px; font-weight: normal;" data-mce-style="margin: 0px; font-weight: normal;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">STORE r0, [sp] ; se pregateste primul parametru pentru g()<br> CALL g<br></span></span></em></p><p style="margin: 0px; font-weight: normal;" data-mce-style="margin: 0px; font-weight: normal;"><em><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">ADD r0, r0, -1 ; return g(x) - 1<br>ADD sp, sp, 4 ; epilog<br> RETURN</span></span></em></p><p style="margin: 0px; font-weight: normal;" data-mce-style="margin: 0px; font-weight: normal;"><br></p><p style="margin: 0px; font-weight: normal;" data-mce-style="margin: 0px; font-weight: normal;"><br></p><table width="249" border="1" cellspacing="0" cellpadding="4"><colgroup><col width="21"> <col width="210"> </colgroup><tbody><tr valign="top"><td style="border-top: 1px solid #000000; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding: 0.1cm 0cm 0.1cm 0.1cm;" data-mce-style="border-top: 1px solid #000000; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding: 0.1cm 0cm 0.1cm 0.1cm;" width="21"><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p></td><td style="border: 1px solid #000000; padding: 0.1cm;" data-mce-style="border: 1px solid #000000; padding: 0.1cm;" width="210"><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">Parametrul x</span></span></em></p></td></tr><tr valign="top"><td style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding: 0cm 0cm 0.1cm 0.1cm;" data-mce-style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding: 0cm 0cm 0.1cm 0.1cm;" width="21"><p style="margin: 0px;" data-mce-style="margin: 0px;"><br></p></td><td style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: 1px solid #000000; padding: 0cm 0.1cm 0.1cm 0.1cm;" data-mce-style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: 1px solid #000000; padding: 0cm 0.1cm 0.1cm 0.1cm;" width="210"><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">Adresa de intoarcere</span></span></em></p></td></tr><tr valign="top"><td style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding: 0cm 0cm 0.1cm 0.1cm;" data-mce-style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding: 0cm 0cm 0.1cm 0.1cm;" width="21"><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">sp</span></span></em></p></td><td style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: 1px solid #000000; padding: 0cm 0.1cm 0.1cm 0.1cm;" data-mce-style="border-top: none; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: 1px solid #000000; padding: 0cm 0.1cm 0.1cm 0.1cm;" width="210"><p style="margin: 0px;" data-mce-style="margin: 0px;"><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">Parametru pentru g</span></span></em></p></td></tr></tbody></table><hr><p style="margin: 0px; font-weight: normal;" data-mce-style="margin: 0px; font-weight: normal;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">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:<br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> mov r0,1 (A)</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> add r1,r0,1 (B)</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> mov r2,2 (C)</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> add r2,r2,1 (D)</span><br>- Numarul de cicli necesari pentru executia codului intial : <em>3</em><br><em>1: A</em><br><em>2: B C</em><br><em>3: D</em><br>- Ce dependente apar intre instructiuni: <em>Dependente de date: (A) → (B), (C) → (D)</em> <br>- Noua ordine a instructiunilor dupa planificare: <em>A C B D</em><br>- Numarul de cicli necesari pentru executia codului dupa planificare: <em>2</em><br><em>1: A C </em><br><em>2: B D</em></span></span></p><hr><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">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. <br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> (1) mov v0, 0</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> (2) add v1, v0, 1</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> (3) cmp v1, v2</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> (4) add v1, v1, 1</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> (5) store v1, [0x1000]</span></span></span></div><div><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">- Identificati weburile si adaugati variabile noi daca este cazul:<em> v3 este o variabila nou introdusa</em></span></span></div><div><div><em><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> (1) mov v0, 0</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> (2) add v1, v0, 1</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> (3) cmp v1, v2</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> (4) add v3, v1, 1</span><br><span style="font-family: 'courier new', courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"> (5) store v3, [0x1000]</span></span></span></em></div><div><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">- Identificati care sunt punctele din program unde fiecare variabila este in viata (“live range”). <br></span></span></div></div><div><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"><img src="cid:0cfb1f93536e4fefada5d376f07ed7cdd6389c3b@zimbra" data-mce-src="cid:0cfb1f93536e4fefada5d376f07ed7cdd6389c3b@zimbra"></span></span></div><div><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">- </span></span></span><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">Desenati graful de interferenta intre variabile</span></span><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"></span></span></span>:<span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;"><br></span></span></div><div><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><img src="cid:0c82e44470538424e405d45ef1e7599e06757f46@zimbra" data-mce-src="cid:0c82e44470538424e405d45ef1e7599e06757f46@zimbra"></span></div><div><div><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"><span style="font-size: small;" size="2" data-mce-style="font-size: small;">- Alocati registrii fizici folosind graful de interferenta si scrieti codul rezultat dupa alocare.<br><span style="font-family: "courier new", courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><em>V2: r0</em></span><br><span style="font-family: "courier new", courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><em>V0: r1</em></span><br><span style="font-family: "courier new", courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><em>V1: r1</em></span><br><span style="font-family: "courier new", courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><em>v3: r0</em></span><br><br><span style="font-family: "courier new", courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><em>mov r1, 0</em></span><br><span style="font-family: "courier new", courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><em>add r1, r1, 1</em></span><br><span style="font-family: "courier new", courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><em>cmp r1, r0</em></span><br><span style="font-family: "courier new", courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><em>add r0, r1, 1</em></span><br><span style="font-family: "courier new", courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><em>store r0, [0x1000]</em></span></span></span><span style="font-family: "courier new", courier, monaco, monospace, sans-serif;" data-mce-style="font-family: 'courier new', courier, monaco, monospace, sans-serif;"><em><span face="Trebuchet MS, sans-serif"><span style="font-size: small;" size="2"></span></span></em></span></div></div><div><hr><span style="font-family: Trebuchet\ MS, sans-serif;" face="Trebuchet MS, sans-serif" data-mce-style="font-family: Trebuchet\ MS, sans-serif;"></span><br></div><div>Succes,</div><div>Bogdan Nitulescu</div><div><br></div></div></body></html>