1

Egzamin z Budowy Kompilatorów

>'9

Imię i nazwisko: Nr indeksu: ____

£]

CE

1. Uporządkuj podane poniżej fazy kompilacji zgodnie z ich kolejnością wykonywania:

a)	analiza kontekstowa	E
b)	generowanie kodu wynikowego	1_!—1
e)	analiza składniowa	1 0^1
d)	analiza leksykalna	E
e)	optymalizacja kodu pośredniego	E

2. W parserach zstępujących:

| zawartość stosu odpowiada temu, co ma być ' jeszcze wczytane z wejścia,

komórki tablicy parsera zawierają akcje shift i reduce,

("f | drzewo wyprowadzenie jest konstruowane od korzenia do liści,

CD na stosie mogą znajdować się terminale i nieterminale,

| ~j* | drzewo wyprowadzenie jest konstruowane w kolejności prefiksowej,

3- g] do generowania analizatorów leksykalnych służy yacc/bison

m każdemu leksemowi odpowiada para żeton, atrybut,

ipn każdemu atrybutowi odpowiada para leksem, żeton,

EJ analizator leksykalny to rodzaj automatu skon czeniestanowegc

| analizator leksykalny dzieli tekst programu na terminale i nieterminale 4. Dla każdej danej gramatyki:

[fi parser LALR.(l) może mieć więcej stanów niż parser LR{ 1).

[(J | jeśli istnieje parser LR.( 1), to istnieje również parser SLR( 1),

[ ^jy| parser SLR.( 1) może mieć mniej stanów niż parser LR( 1),

33 jeśli nie istnieje parser Lft(l), to nie istnieje

również parser LALR(l),

m jeśli nie istnieje parser LL( 1), to może istnieć parser LR.( 1),

5.    Żeby gramatyka była typu LL( 1), to:

m musi być jednoznaczna,

m nie może zawierać lewostronnej rekursji,

fpJI musi się w niej dać wyprowadzić słowo puste

e.

EJ musi zawierać produkcję postaci A —» £,

| należy ją poddać lewostronnej faktoryzacji,

6.    Dopasuj podane fragmenty i formalizmy (tak, żeby każdy miał swój odpowiednik):

a)    S —» {A.a = 4;}A{S.s = A.s;},

b)    5 -> AB{B.a = A.s; S.s = B.s},

C.) wyr: wyr * + * term {$$=$l+$3;>;

d)    S —r AB{S.u = B a + A.a},

e)    S —» AS{printf ("7.d", S.a = A.a + B a); },

10.

gramatyka L-atrybutywna, specyfikacja dla yacc-a, definicje sterowane składnią, gramatyka S-atrybutywna, schemat translacji sterowanej składnią,

7. W parserach wstępujących:

| Al | drzewo wyprowadzenie jest konstruowane od korzenia do liści,

komórki tablicy parsera zawierają m.inn. akcje shift i reduce,

drzewo wyprowadzenie jest konstruowane w kolejności postfiksowej, na stosie znajdują się wyłącznie symbole terminalne i nieterminalne zawartość stosu odpowiada temu, co ma być jeszcze wczytane z wejścia,

8. W rekordzie aktywacji:

CS DL wskazuje zawsze na poprzedni rekord aktywacji na stosie,

wielkość stosu arytmetycznego nie zmienia się w trakcie wykonywania procedury, miejsce na wynik funkcji rezerwuje wywoływany,

rejestr bazowy (BP) wskazuje na umówione miejsce w rekordzie aktywacji na wierzchołku stosu,

SL jest używany przy zdejmowaniu rekordu aktywacji z wierzchołka stosu,

Techniki łatania dziur i generowanie kodu skaczącego wykluczają się nawzajem.

W technice łatania dziur, dziury wypełniane są zwykle adresami zmiennych.

Jedna tzw. „czwórka” może zawierać do trzech różnych nazw zmiennych.

Przy generowaniu kodu strukturalnych instrukcji sterujących używa się atrybutów.

W kodzie skaczącym pośrednie wartości logiczne są pamiętane na stosie.

Optymalizacje kodu lepiej wykonywać na kodzie wynikowym, niż pośrednim.

Przy optymalizowaniu pętli przesuwa się kod z wnętrza pętli do jej przedsionka.

Propagacja kopii powoduje, że niektóre martwe instrukcje „ożywają”.

Eliminacja martwego kodu to optymalizacja lokalna.

Analiza przepływu danych ma miejsce po analizie przepływu sterowania.

ffrl

E

m

E

E

Ę

O

a

E

fFH

E

S

m

E

173

m

E3

m

m