Metody realizacji języków programowania/MRJP Przykładowy zestaw zadań egzaminacyjnych

Przykładowy zestaw zadań egzaminacyjnych

Egzaminatorom proponujemy wybór:

• jednego zadania z grupy pierwszej

• jednego zadania z grupy drugiej

• jednego zadania z grupy trzeciej

• dwóch zadań z grupy czwartej

oraz, jeśli uznamy za konieczne sprawdzenie przygotowania w zakresie analizy leksykalnej i składniowej:

• dwóch zadań z grupy zadań dodatkowych

Grupa pierwsza

Zadanie 1.1

Poniżej znajduje się gramatyka pewnego języka programowania. Jej symbolem początkowym jest E.

Symbole nieterminalne gramatyki reprezentują wyrażenia – sposób ich obliczania opisano przy każdej produkcji. Terminal num oznacza liczbę całkowitą.

E -> E == F

wartością jest E dzielone przez F gdy F różne od 0, wpp. 0

E -> E =# E ##

wartość to wynik odejmowania pierwszego E od drugiego

E -> ε

wartość 1

E -> num F

w pętli oblicza F dopóki jest różne od num. Wartością jest liczba obrotów pętli

F -> F num

wartość num. Wyrażenie F obliczamy, ale ignorujemy wynik

F -> G G G

oblicza G od ostatniego do pierwszego, pozostawia wartość środkowego

G -> E ===

wartość bezwzględna E

G -> E #== G G

jeśli E jest różne od zera, wartością jest iloczyn obu G, wpp. ich suma

Zaprojektuj generator kodu maszyny wirtualnej NMW dla kompilatora tego języka, podając sposób tłumaczenia każdej konstrukcji języka.

Zadanie 1.2

Poniżej znajduje się gramatyka pewnego języka programowania. Jej symbolem początkowym jest E.

Symbole nieterminalne gramatyki reprezentują wyrażenia – sposób ich obliczania opisano przy każdej produkcji. Terminal num oznacza liczbę całkowitą.

E -> E -+ E *

jeśli wartości obu E są równe, to wartość taka, jak E, wpp. 0

E -> * F G + F

jeśli oba F są równe, to wartość taka jak G, wpp. G nie liczymy, wartością jest 1

E -> * F G ---

jeśli F jest ujemne, wartością jest -G , wpp. G

F -> F **

0 gdy F parzyste, 1 gdy nieparzyste

F -> G num

num razy liczy G; wartością jest średnia arytmetyczna wartości wszystkich G, lub 0, gdy num to 0

G -> G E

jeśli G jest różne od 0, to wartością jest E/G, wpp. wartością jest E

G -> G -* E

wartość G liczy, ale ignoruje; wartością wyrażenia jest E

G -> ε

wartość 1

Zaprojektuj generator kodu maszyny wirtualnej NMW dla kompilatora tego języka, podając sposób tłumaczenia każdej konstrukcji języka.

Zadanie 1.3

Poniżej znajduje się gramatyka pewnego języka programowania. Jej symbolem początkowym jest E.

Symbole nieterminalne gramatyki reprezentują wyrażenia – sposób ich obliczania opisano przy każdej produkcji. Terminal num oznacza liczbę całkowitą.

E -> ab E G bbb

w pętli liczy E i G dopóki są równe; pozostawia wartość większego z nich

E -> F G bcc

jeśli G to 0, wartością jest 0, wpp. jest nią liczba o wartości bezwzględnej takiej jak G i znaku (ujemna lub nieujemna) takim, jak F

E -> ε

wartość 5

F -> F bcc F G

wartością jest 1, jeśli wśród wartości wyrażeń F, F i G jest przynajmniej jedna 1, a 0 wpp.; wyrażenia składowe (F, F i G) liczone są w sposób pełny

F -> ba G

wartością jest sześcian wartości G

F -> ba E a E a

wartością jest iloczyn sumy i różnicy obu E

G -> G E bb

liczy G a E nie; wartość jest o 1 większa od wartości G

G -> num

wartość num

Zaprojektuj generator kodu maszyny wirtualnej NMW dla kompilatora tego języka, podając sposób tłumaczenia każdej konstrukcji języka.

Grupa druga

Zadanie 2.1

Dany jest język programowania, w którym:

• program składa się z funkcji, które można zagnieżdżać i wywoływać rekurencyjnie

• zasady widoczności zmiennych i parametrów w funkcjach zagnieżdżonych są takie, jak w Pascalu

• wszystkie dane (zmienne, parametry, wynik funkcji) są typu integer

• parametry funkcji mogą być przekazywane przez wartość lub przez zmienną

• funkcje znają liczbę argumentów, z którymi są wywoływane

• argumenty operacji arytmetycznych oraz parametry funkcji obliczane są od lewej do prawej

Zakładając, że maszyną docelową jest Nasza Maszyna Wirtualna, zaprojektuj protokół wywołania i powrotu z funkcji tak, by:

• rekord aktywacji zawierał (w kolejności wg malejących adresów): (a) wynik (b) parametry (c) SL (d) ślad (e) zmienne (f) DL

• rejestr FP, pełniący rolę wskaźnika aktualnego rekordu aktywacji, przechowywał adres pola zawierającego SL

Napisz pełne (wraz z prologiem i epilogiem) tłumaczenie funkcji F3 z poniższego fragmentu programu na kod NMW:

function F1(a:integer; var b:integer):integer;
  function F2(var c:integer):integer; var d:integer;
    function F3(e,f:integer):integer;
      begin b:=d/e; return F3(a-F2(f),c) end {F3};
  begin ... end {F2};
begin ... end {F1};

W kodzie wynikowym można się odwoływać do adresu funkcji pisząc #nazwa.

Zadanie 2.2

Dany jest język programowania, w którym:

• program składa się z funkcji, które można zagnieżdżać i wywoływać rekurencyjnie

• zasady widoczności zmiennych i parametrów w funkcjach zagnieżdżonych są takie, jak w Pascalu

• wszystkie dane (zmienne, parametry, wynik funkcji) są typu integer

• parametry funkcji mogą być przekazywane przez wartość lub przez zmienną

• funkcje znają liczbę argumentów, z którymi są wywoływane

• argumenty operacji arytmetycznych oraz parametry funkcji obliczane są od lewej do prawej

Zakładając, że maszyną docelową jest Nasza Maszyna Wirtualna, zaprojektuj protokół wywołania i powrotu z funkcji tak, by:

• rekord aktywacji zawierał (w kolejności wg malejących adresów): (a) wynik (b) ślad (c) DL (d) parametry (e) SL (f) zmienne

• rejestr FP, pełniący rolę wskaźnika aktualnego rekordu aktywacji, przechowywał adres pola zawierającego SL

Napisz pełne (wraz z prologiem i epilogiem) tłumaczenie funkcji F3 z poniższego fragmentu programu na kod NMW:

function F1(var a:integer):integer; var b:integer;
  function F2(c:integer; var d:integer):integer;
    function F3(e:integer; var f:integer):integer; var g:integer;
      begin d:=a*g+f; return F2(b-F3(f,e),d) end {F3};
  begin ... end {F2};
begin ... end {F1};

W kodzie wynikowym można się odwoływać do adresu funkcji pisząc #nazwa.

Zadanie 2.3

Dany jest język programowania, w którym:

• program składa się z funkcji, które można zagnieżdżać i wywoływać rekurencyjnie

• zasady widoczności zmiennych i parametrów w funkcjach zagnieżdżonych są takie, jak w Pascalu

• wszystkie dane (zmienne, parametry, wynik funkcji) są typu integer

• parametry funkcji mogą być przekazywane przez wartość lub przez zmienną

• funkcje znają liczbę argumentów, z którymi są wywoływane

• argumenty operacji arytmetycznych oraz parametry funkcji obliczane są od lewej do prawej

Zakładając, że maszyną docelową jest Nasza Maszyna Wirtualna, zaprojektuj protokół wywołania i powrotu z funkcji tak, by:

• rekord aktywacji zawierał (w kolejności wg malejących adresów): (a) wynik (b) SL (c) parametry (d) DL (e) zmienne (f) ślad

• rejestr FP, pełniący rolę wskaźnika aktualnego rekordu aktywacji, przechowywał adres pola zawierającego DL

Napisz pełne (wraz z prologiem i epilogiem) tłumaczenie funkcji F3 z poniższego fragmentu programu na kod NMW:

function F1(var a:integer):integer; var b:integer;
  function F2(c:integer; var d:integer):integer;
    function F3(e:integer):integer; var f:integer
      begin d:=a-e; return F2(b*F3(c),f) end {F3};
  begin ... end {F2};
begin ... end {F1};

W kodzie wynikowym można się odwoływać do adresu funkcji pisząc #nazwa.

Grupa trzecia

Zadanie 3.1

Dla treści procedury p (bez prologu i epilogu) narysuj graf przepływu sterowania z węzłami w postaci bloków bazowych złożonych z czwórek i „zoptymalizuj” go, nazywając każde z wykonanych przekształceń. Wskaż też optymalizacje, których nie da się wykonać, np. ze względu na możliwość istnienia aliasów.

Tłumacząc na czwórki odwołania do elementów tablicy przyjmij, że wartość typu integer zajmuje 4 komórki pamięci.

var x:array [0..n] of integer; a:integer;
procedure p(b:integer); var c,d,e:integer;
begin
  c:=x[a];
  d:=b;
  b:=a;
  e:=3;
  repeat
    x[c]:=b*4;
    c:=c+d*4
  until x[a]=e;
  a:=e*e
end;

Zadanie 3.2

Dla treści procedury p (bez prologu i epilogu) narysuj graf przepływu sterowania z węzłami w postaci bloków bazowych złożonych z czwórek i „zoptymalizuj” go, nazywając każde z wykonanych przekształceń. Wskaż też optymalizacje, których nie da się wykonać, np. ze względu na możliwość istnienia aliasów.

Tłumacząc na czwórki odwołania do elementów tablicy przyjmij, że wartość typu integer zajmuje 4 komórki pamięci.

var a:array [0..n] of integer; b:integer;
procedure p(x:integer; var y:integer); var z,v:integer;
begin
  y:=a[b];
  z:=a[b];
  v:=5;
  while b*4<a[v*x] do begin
    a[z]:=x*x;
    z:=z+v*2
  end;
  b:=x*x
end;

Zadanie 3.3

Dla treści procedury p (bez prologu i epilogu) narysuj graf przepływu sterowania z węzłami w postaci bloków bazowych złożonych z czwórek i „zoptymalizuj” go, nazywając każde z wykonanych przekształceń. Wskaż też optymalizacje, których nie da się wykonać, np. ze względu na możliwość istnienia aliasów.

Tłumacząc na czwórki odwołania do elementów tablicy przyjmij, że wartość typu integer zajmuje 4 komórki pamięci.

var t:array [0..n] of integer; u:integer;
procedure p(var a:integer); var b,c,d:integer;
begin
  b:=u;
  c:=t[b];
  d:=5;
  a:=7;
  while t[d]<d do begin
    d:=d+b;
    t[c]:=c*b
  end;
  a:=7
end;

Zadanie 3.4

Poniższy program realizuje sortowanie metodą Shella.

• zapisz zaznaczony fragment programu (od "zacznij tu" do "skończ tu") w kodzie czwórkowym

• zoptymalizuj program: omów krótko zastosowane techniki optymalizacji, wskaż miejsca, gdzie stosowane były te techniki i napisz czytelnie ostateczną, zoptymalizowana wersję

Uwagi - każdy element tablic zajmuje 4 bajty. Nie zapomnij pomnożyć indeksu przez 4 przy odwoływaniu się do tablic a oraz incs w kodzie czwórkowym.

shellsort(itemType a[], int l, int r)
{
    int i, j, k, h; itemType v;
    int incs[16] = { 1391376, 463792, 198768, 86961, 33936,
                     13776, 4592, 1968, 861, 336,
                     112, 48, 21, 7, 3, 1 };
    // Zacznij tu
    for ( k = 0; k < 16; k++)
      for (h = incs[k], i = l+h; i <= r; i++)
        {
          v = a[i]; j = i;
          while (j > h && a[j-h] > v)
            { a[j] = a[j-h]; j -= h; }
          a[j] = v;
        }
    // Skończ tu
}

Zadanie 3.5

Rozważ następujący fragment kodu w C

int i,j;
int A[50,100];
int B[50], y[50];
int X[100];

for (i=50; --i>=0;){
  Y[i]= B[i];
  for (j = 100; --j>=0;)
    Y[i] += A[i,j] * X[j];
}

• Narysuj graf przepływu. (Przyjmij, że A[i,j] oznacza *(A + 4*(100*i +j)) .

• Znajdź wyrażenia niezmienne w pętli (niezmienniki pętli) i wynieś je przed pętle.

• Użyj zmiennych indukcyjnych i dokonaj redukcji w mocy (tylko w wewnętrznej pętli!).

Grupa czwarta

Zadanie 4.1

W składni języka mamy następujące produkcje:

Instr -> do  { InstrList }  until Bexpr
Expr -> Bexpr ? Expr1 : Expr2
Bexpr -> Bexpr1 xor Bexpr2

Gdzie:

Instr

instrukcja

InstrList

lista instrukcji

Expr

wyrażenie arytmetyczne

Bexpr

wyrażenie Boolowskie

Semantyka jest standardowa:

• instrList ma być powtarzana aż do momentu gdy Bexpr przyjmie wartość „prawda” (sprawdzanie po każdym wykonaniu listy instrukcji),

• jeśli wyrażenie logiczne przyjmuje wartość „prawda”, to obliczane jest pierwsze wyrażenie Expr1, a jeśli przyjmuje wartość „fałsz” to drugie Expr2; wynik całości to wynik obliczonego wyrażenia,

• wartością wyrażenia boolowskiego jest xor wartości wyrażeń logicznych po prawej stronie produkcji.

Uzupełnij gramatykę o reguły semantyczne opisujące generator kodu czwórkowego.

Zadanie 4.2

Dana jest gramatyka:

• Deklaracje -> const DeklaracjeStalych ;

• DeklaracjeStalych -> DeklaracjaStalej ; DeklaracjeStalych |DeklaracjaStalej

• DeklaracjaStalej -> identyfikator = Wyrazenie

• Wyrazenie -> Wyrazenie + WyrazenieProste | WyrazenieProste

• WyrazenieProste -> ( Wyrazenie )| identyfikator | liczba

Przyjmujemy, że słowo wyprowadzalne z nieterminala Deklaracje jest poprawne, jeśli w każdej wyprowadzonej z niego deklaracji stałej, identyfikatory występujące w wyrażeniu po prawej stronie równości są identyfikatoryami zadeklarowanych wcześniej stałych. Dodatkowo wymagamy, by każda zadeklarowana stała miała jedną deklarację.

Dopisz do podanej gramatyki reguły atrybutowania liczące wartość atrybutu Deklaracje.ok mówiącego, czy deklaracje są poprawne.

Zadanie 4.3

Dana jest gramatyka G1:

S  -> E
E  -> V := E | F
V  -> id | if E then V else V end
F  -> id | if E then E else E end | num

oraz gramatyka G2:

S  -> E
E  -> F := E | F
F  -> id | if E then E else E end | num

Dopisując reguły atrybutowania do gramatyki G2 zbuduj gramatykę atrybutywną, która na atrybucie S.poprawne umieści wartość logiczną mówiącą, czy wyprowadzone słowo należy do języka generowanego przez gramatykę G1.

Grupa piąta (zadań dodatkowych)

Zadanie 5.1

Pewna gramatyka G posiada trzy symbole nieterminalne S (startowy), A i B oraz trzy symbole terminalne x,y i $. W G są następujące produkcje:

• S -> w1
• A -> w2
• A -> w3
• B -> w4
• B -> w5

gdzie w1...w5 są słowami o długościach 2, 3, 1, 3 oraz 0 odpowiednio.

Dana jest tablica sterująca analizatora składniowego LR dla gramatyki G:

$\left[\begin{array}{rrrrrr}Lp& & Akcje& & & Goto\\ & x& y& \mathrm{\$}& A& B& S\\ 1.& S2& S9& R5& 8& 10\\ 2.& S3& R5& & & 4\\ 3.& S3& R5& & & 6\\ 4.& & S5\\ 5.& & & R4\\ 6.& & S7\\ 7.& & R4\\ 8.& & & acc\\ 9.& S11\\ 10.& & & R3\\ 11.& S12\\ 12.& & & R2\end{array}\right]$

Podzadania (każdą odpowiedź uzasadnij):

• Zasymuluj działanie automatu na słowach yxy$ oraz xxxyyy$. Czy te słowa należą do L(G)?

• Jakie produkcje występują w G?

• Czy L(G) jest regularny?

• Czy gramatyka G należy do: LL(1), LR(0), SLR, LR(1),LALR,LR(k) dla k>1?

Zadanie 5.2

Podaj wyrażenie regularne definiujące język składający się z liczb całkowitych, nieujemnych, podzielnych przez dwa. Jedyną liczbą rozpoczynającą sie od 0 jest zero.

Zadanie 5.3

Podaj gramatykę bezkontekstową akceptującą liczby naturalne podzielne przez 3. Dopuszczamy zera na początku liczby i ciąg pusty.

Zadanie 5.4

Rozważ następujące zbiory First i Follow:

First(S) = {b, epsilon} First(T) = {b, epsilon} Follow(S) = {a, $} Follow(T) = {a, b, $}

Podaj najprostszą gramatykę G (minimum produkcji i krótkie prawe strony ) odpowiadającą tym zbiorom.

Zadanie 5.5

• Podaj prosty przykład gramatyki jednoznacznej z konfliktem shift/reduce w metodzie SLR
• Podaj przykład gramatyki jednoznacznej z konfliktem reduce/reduce w metodzie SLR

Zadanie 5.6

Która z poniższych gramatyk jest LL(1) ?

Litery są nieterminalami, cyfry terminalami. Uzasadnij odpowiedzi (krótko)

S -> 0 | 12 | 345

S -> 0 | T1
T -> 1 | S0

S ->  0 | 1T | T0
T -> epsilon | 2

Zadanie 5.7

Pewna gramatyka G posiada dwa symbole nieterminalne S (startowy) i T oraz trzy symbole terminalne a, b i $. Gramatyka G zawiera trzy produkcje

S  -> w0		length(w0) = 2
T  -> w1		length(w1) = 2
T  -> w2  		length(w2) = 3

Dana jest tablica sterująca analizatora składniowego LR dla gramatyki G.

$\left|\begin{array}{rrrrr}Lp& Ak& cje& Go& to\\ & a& b|\mathrm{\$}& S& T\\ 0.& & s3& & 1\\ 1.& s2& & acc\\ 2.& r1& & r1\\ 3.& & s4& s4\\ 4.& & s5& s5\\ 5.& r2& & r2\end{array}\right|$

• Zasymuluj działanie automatu dla słów: bbaa$ oraz bbbaa$. Czy te słowa należą do L(G)?

• Odgadnij produkcje w gramatyce G. Uzasadnij odpowiedź.

• Czy gramatyka G należy do: LL(1), LR(0), SLR, LR(1), LR(k) k>1? Uzasadnij!