Deel 1: gesloten boek1) Beschouw de taal L = {a
mb
nc
p}, met m, p en n natuurlijke getallen en m > p.
a) Kan je een reguliere expressie opstellen voor deze taal? Waarom wel/niet?
b) Geef een niet-ambigue grammatica voor deze taal.
c) Veronderstel dat er in de plaats zou staan: m != p. Hoe kan de grammatica uit b) aangepast worden om deze nieuwe taal te herkennen?
2) Gegeven de productieregels
E' -> E
E -> e
E -> PEpE
P -> epsilon
Veronderstel hierbij dat p het plusteken voorstelt en e een getal. Gegeven is de transitietabel van de bijhorende LR-parser en een JFLAP-figuur van de bijhorende DFA (met in elke toestand de LR-items erbij geplaatst). Maw. dit komt rechtstreeks uit de slides over het gebruik van dat "pos"-symbool in yacc dat dient als artificieel symbool om de inputpositie van uw lexer in op te slaan bij reductie.
a) Waarvoor kan deze grammatica gebruikt worden buiten het herkennen van aritmetische zinnen? (Hint: waarvoor dient het symbool P?)
Met andere woorden, hij wilt gewoon horen da ge weet dat het gaat om dat positie-geval.b) Kan je aan de figuur van de DFA zien of deze grammatica ambigu is? Waarom wel/niet? Geef de eerste 5 toestanden die de parser doorloopt bij input "epe".
c) Hoe zou je het shift/reduce-conflict oplossen? I.e. geef de nodige aanpassingen die moeten gebeuren aan de "e"-kolom in de transitietabel. (dus niet een andere grammatica gebruiken ofzo, ge moet wel degelijk de shift/reduce-conflicten oplossen).
d) Geef nu de 5 eerste toestanden die de parser doorloopt voor input "epe".
3) Semantische analyse
void transDec(S_table venv, S_table tenv, A_dec d){
switch(d->kind){
...
case A_functionDec:
S_beginScope(venv);
A_fundec f = d->u.function.head;
Ty_ty resultTy = S_look(tenv, f->result);
Ty_tyList formalTys = makeFormalTyList(tenv, f->params);
S_enter(venv, f->name, E_funEntry(formalTys, resultTy));
{A_fieldList l; Ty_tyList t;
for(l=f->params, t=formalTys; l; l=l->tail, t=t->tail)
S_enter(venv, l->head->name, E_VarEntry(t->head));
}
transExp(venv, tenv, d->u.function.body);
S_endScope(venv);
break;
...
}
}
a) Wat is de bedoeling van dit codefragment? Verwijs in uw antwoord naar regelnummers.
b) De regel met S_beginScope staat niet op de juiste plaats. Waar moet deze regel komen en waarom?
c) Hoe worden typedeclaraties binnen de functie afgehandeld?
4) Loops
a) Wat is een reduceerbare graaf? Geef een voorbeeld van een niet-reduceerbare graaf.
b) Hoe worden lussen gedetecteerd in een controlegraaf?
c) Pas dit toe op de volgende graaf. Bepaal de dominatorboom en geef voor elke lus de bijhorende back-edge en verzameling van knopen.
Nodes: 1 tem. 7
Gerichte paden:
1 -> 2 -> 3 -> 5 -> 6 -> 7
2 -> 4 -> 5
6 -> 8 -> 5
6 -> 1
5 -> 2
2 -> 1
5) Liveness-analyse en registerallocatie
a) Geef het algoritme om liveness te berekenen in een flow-graaf.
b) Geef een schema van de verschillende fasen in het registerallocatie-algoritme, inclusief feedback-loops tussen de fasen.
c) Wat is freezen en waarvoor wordt het gebruikt?
6) Lusoptimalisaties
Gegeven volgende lus:
for i := 1 to N
for j := 1 to N
for k := 1 to N
A[i, k+2] = i + j + k;
a) Geef de affiene index-expressie van de geheugenreferentie in matrixvorm.
b) Wat is de hergebruiksafstand van de geheugenreferenties A[i, k+2]?
c) Welke optimalisatie zou je hier voorstellen en waarom? Pas deze toe.
Deel 2: open boek7) SSA
Gegeven volgende flow-graaf + de effectieve graaf (i.e. met blokken code).
Nodes: 1 tem. 7
Paden:
1 -> 2 -> 3 -> 4 -> 5 -> 7
3 -> 5
2 -> 6 -> 7
7 -> 2
a) Bepaal de dominantiegrens van node 3
b) Stel de dominatorboom op
c) Voeg phi's toe waar nodig volgens het SSA-algoritme (in de graaf met de code in uiteraard, die weet'k wel ni meer).
Als er iets niet werkt, just let it know.
. Komt sterk overeen met de C cyclus, aangezien C en 0 makkelijk binden
