Metody realizacji języków programowania/MRJP Przykładowy zestaw zadań egzaminacyjnych: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 4 wersji utworzonych przez 2 użytkowników)
Linia 1: Linia 1:
 
= Przykładowy zestaw zadań egzaminacyjnych =
 
= Przykładowy zestaw zadań egzaminacyjnych =
  
Na egzaminie proponujemy wybór:
+
Egzaminatorom proponujemy wybór:
  
 
* jednego zadania z grupy pierwszej
 
* jednego zadania z grupy pierwszej
Linia 17: Linia 17:
 
== Grupa pierwsza ==
 
== Grupa pierwsza ==
  
=== Zadanie ===
+
=== Zadanie 1.1 ===
  
 
Poniżej znajduje się gramatyka pewnego języka programowania. Jej symbolem początkowym jest E.
 
Poniżej znajduje się gramatyka pewnego języka programowania. Jej symbolem początkowym jest E.
Linia 41: Linia 41:
 
Zaprojektuj generator kodu maszyny wirtualnej NMW dla kompilatora tego języka, podając sposób tłumaczenia każdej konstrukcji języka.
 
Zaprojektuj generator kodu maszyny wirtualnej NMW dla kompilatora tego języka, podając sposób tłumaczenia każdej konstrukcji języka.
  
=== Zadanie ===
+
=== Zadanie 1.2 ===
  
 
Poniżej znajduje się gramatyka pewnego języka programowania. Jej symbolem początkowym jest E.
 
Poniżej znajduje się gramatyka pewnego języka programowania. Jej symbolem początkowym jest E.
Linia 65: Linia 65:
 
Zaprojektuj generator kodu maszyny wirtualnej NMW dla kompilatora tego języka, podając sposób tłumaczenia każdej konstrukcji języka.
 
Zaprojektuj generator kodu maszyny wirtualnej NMW dla kompilatora tego języka, podając sposób tłumaczenia każdej konstrukcji języka.
  
=== Zadanie ===
+
=== Zadanie 1.3 ===
  
 
Poniżej znajduje się gramatyka pewnego języka programowania. Jej symbolem początkowym jest E.
 
Poniżej znajduje się gramatyka pewnego języka programowania. Jej symbolem początkowym jest E.
Linia 91: Linia 91:
 
== Grupa druga ==
 
== Grupa druga ==
  
=== Zadanie ===
+
=== Zadanie 2.1 ===
  
 
Dany jest język programowania, w którym:
 
Dany jest język programowania, w którym:
Linia 124: Linia 124:
 
W kodzie wynikowym można się odwoływać do adresu funkcji pisząc #nazwa.
 
W kodzie wynikowym można się odwoływać do adresu funkcji pisząc #nazwa.
  
=== Zadanie ===
+
=== Zadanie 2.2 ===
  
 
Dany jest język programowania, w którym:
 
Dany jest język programowania, w którym:
Linia 157: Linia 157:
 
W kodzie wynikowym można się odwoływać do adresu funkcji pisząc #nazwa.
 
W kodzie wynikowym można się odwoływać do adresu funkcji pisząc #nazwa.
  
=== Zadanie ===
+
=== Zadanie 2.3 ===
  
 
Dany jest język programowania, w którym:
 
Dany jest język programowania, w którym:
Linia 192: Linia 192:
 
== Grupa trzecia ==
 
== Grupa trzecia ==
  
=== Zadanie ===
+
=== 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.
 
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.
Linia 212: Linia 212:
 
  '''end''';
 
  '''end''';
  
=== Zadanie ===
+
=== 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.
 
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.
Linia 231: Linia 231:
 
  '''end''';
 
  '''end''';
  
=== Zadanie ===
+
=== 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.
 
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.
Linia 251: Linia 251:
 
  '''end''';
 
  '''end''';
  
=== Zadanie ===
+
=== Zadanie 3.4 ===
  
 
Poniższy program realizuje sortowanie metodą Shella.
 
Poniższy program realizuje sortowanie metodą Shella.
Linia 278: Linia 278:
 
     // Skończ tu
 
     // 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 ==
 
== Grupa czwarta ==
  
=== Zadanie ===
+
=== Zadanie 4.1 ===
  
 
W składni języka mamy następujące produkcje:
 
W składni języka mamy następujące produkcje:
Linia 309: Linia 330:
 
Uzupełnij gramatykę o reguły semantyczne opisujące generator kodu czwórkowego.
 
Uzupełnij gramatykę o reguły semantyczne opisujące generator kodu czwórkowego.
  
=== Zadanie ===
+
=== Zadanie 4.2 ===
  
 
Dana jest gramatyka:
 
Dana jest gramatyka:
Linia 327: Linia 348:
 
Dopisz do podanej gramatyki reguły atrybutowania liczące wartość atrybutu ''Deklaracje.ok'' mówiącego, czy deklaracje są poprawne.
 
Dopisz do podanej gramatyki reguły atrybutowania liczące wartość atrybutu ''Deklaracje.ok'' mówiącego, czy deklaracje są poprawne.
  
=== Zadanie ===
+
=== Zadanie 4.3 ===
  
 
Dana jest gramatyka G1:
 
Dana jest gramatyka G1:
Linia 347: Linia 368:
 
gramatykę G1.
 
gramatykę G1.
  
=== Zadanie ===
+
== Grupa piąta (zadań dodatkowych) ==
  
Rozważ następujący fragment kodu w C
+
=== Zadanie 5.1 ===
 
 
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 zadań dodatkowych ==
 
 
 
=== Zadanie ===
 
  
 
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:
 
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:
Linia 415: Linia 415:
 
* Czy gramatyka G należy do: LL(1), LR(0), SLR, LR(1),LALR,LR(k)  dla k>1?
 
* Czy gramatyka G należy do: LL(1), LR(0), SLR, LR(1),LALR,LR(k)  dla k>1?
  
=== Zadanie ===
+
=== 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.
 
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 ===
+
=== Zadanie 5.3 ===
  
 
Podaj gramatykę bezkontekstową akceptującą liczby naturalne podzielne przez 3.  Dopuszczamy zera na początku liczby i ciąg pusty.
 
Podaj gramatykę bezkontekstową akceptującą liczby naturalne podzielne przez 3.  Dopuszczamy zera na początku liczby i ciąg pusty.
  
=== Zadanie ===
+
=== Zadanie 5.4 ===
  
 
Rozważ następujące zbiory First i Follow:
 
Rozważ następujące zbiory First i Follow:
Linia 434: Linia 434:
 
Podaj najprostszą gramatykę G (minimum produkcji i krótkie prawe strony ) odpowiadającą tym zbiorom.
 
Podaj najprostszą gramatykę G (minimum produkcji i krótkie prawe strony ) odpowiadającą tym zbiorom.
  
=== Zadanie ===
+
=== Zadanie 5.5 ===
  
 
* Podaj prosty przykład gramatyki jednoznacznej z konfliktem shift/reduce w metodzie SLR
 
* 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
 
* Podaj przykład gramatyki jednoznacznej z konfliktem reduce/reduce w metodzie SLR
  
=== Zadanie ===
+
=== Zadanie 5.6 ===
  
 
Która z poniższych gramatyk jest LL(1) ?
 
Która z poniższych gramatyk jest LL(1) ?
Linia 446: Linia 446:
  
 
  S -> 0 | 12 | 345
 
  S -> 0 | 12 | 345
           
+
 
 
  S -> 0 | T1
 
  S -> 0 | T1
 
  T -> 1 | S0
 
  T -> 1 | S0
Linia 453: Linia 453:
 
  T -> epsilon | 2
 
  T -> epsilon | 2
  
=== Zadanie ===
+
=== 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
 
Pewna gramatyka G posiada dwa symbole nieterminalne S (startowy) i T oraz trzy symbole terminalne a, b i $.  Gramatyka G zawiera trzy produkcje

Aktualna wersja na dzień 13:39, 2 paź 2006

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:

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.

  • 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!