2

Egzamin z Budowy Kompilatorów

Imię i nazwisko: Nr indeksu: ----

1. Uporządkuj podane poniżej fazy kompilacji zgodnie z ich kolejnością wykonywania: a) generowanie kodu pośredniego analiza leksykalna analiza składniowa analiza kontekstowa optymalizacja kodu wynikowego 2. Dla każdej danej gramatyki:

m parser LALR(l) może mieć mniej stanów niż parser Lft(l),

jeśli istnieje parser LR.( 1), to istnieje również parser LALR(1),

parser SLR( 1) może mieć więcej stanów niż parser LR( 1),

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

jeśli nie istnieje parser LR( 1), to nie istnieje również parser SLR(l),

każdemu żetonowi odpowiada para leksem, atrybut,

każdemu leksemowi odpowiada para żeton, atrybut,

do generowania analizatorów leksykalnych służy lex/flex

analizator składniowy to rodzaj automatu skończeniestanowego

analizator leksykalny m.inn. usuwa z programu komentarze 4. W parser ach wstępujących:

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

komórki tablicy parsera zawierają wyłącznie produkcje do rozwinięcia, drzewo wyprowadzenie jest konstruowane w kolejności postfiksowej,

na stosie znajdują się na przemian stany pewnego automatu i symbole, zawartość stosu odpowiada temu, co ma być jeszcze wczytane z wejścia,

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

wystarczy żeby była jednoznaczna, musi zawierać lewostronną rekursję, należy ją poddać lewostronnej faktoryzacji,

|/*J ,| musi być w postaci normalnej Chomsky’ego,

|    | nie może zawierać produkcji postaci A —> e,

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

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

S —> AB{S.a = B.a + A.a},

S —> AB{B.a = i4.s;5.s = B.s}, wyr:    wyr ' + ’ term ■C$$=$l+$3;>;

S —> AB{printf ("7,d", S.a = A.a + B.a); },

b)

c)

d)

e)

3.

fU

E]

tn

m

(EH

m

m

fKD

F-rl

fxn

H

E

f7J~i

b)

c)

d)

e)

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

7. W parserach zstępującycłi:

[2] zawartość stosu wyznacza jednoznacznie to, co zostało wczytane,

| f\J| drzewo wyprowadzenie jest konstruowane od liści do korzenia,

(El na stosie znajdują się naprzemian stany pewnego automatu i symbole nieterminalne,

m komórki tablicy parsera zawierają produkcje do rozwinięcia,

(0 drzewo wyprowadzenie jest konstruowane w kolejności postfiksowej,

8. W rekordzie aktywacji:

SL wskazuje zawsze na poprzedni rekord aktywacji na stosie,

| miejsce na wynik funkcji rezerwuje wywołujący,

m wielkość stosu arytmetycznego może się zmieniać w trakcie wykonywania procedury,

| T | DL jest używany przy zdejmowaniu rekordu aktywacji z wierzchołka stosu,

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

⁹-    0] Przy generowaniu kodu strukturalnych in

strukcji sterujących używa się wyłącznie atrybutów dziedziczonych.

Jedna tzw. „czwórka” może zawierać cztery różne nazwy zmiennych.

|~Y | W generowaniu kodu skaczącego stosuje się technikę łatania dziur.

| ~J~ | W technice łatania dziur, dziury wypełniane są zwykle adresami skoków.

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

10. |T I Optymalizacje kodu lepiej wykonywać na kodzie pośrednim, niż wynikowym.

SD Eliminacja martwego kodu to optymalizacja globalna.

| /v/ | Eliminacja wspólnych podwyrażeń, to optymalizacja pętli.

17*1 Propagacja kopii powoduje, że niektóre instrukcje stają się martwe.

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

6.