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

Przykładowy zestaw zadań egzaminacyjnych

Zadanie 1

W składni języka mamy następujące produkcje (terminale są podkreślone):

• a) Instr -> do { InstrList } until Bexpr
• b) Expr -> Bexpr ? Expr1 : Expr2
• c) Bexpr -> Bexpr1 xor Bexpr2

Gdzie: Instr - instrukcja, InstrList - lista instrukcji, Expr - wyrażenie arytmetyczne, Bexpr - wyrażenie Boolowskie.

Semantyka jest standardowa:

• a) instrList ma być powtarzana aż do momentu gdy Bexpr przyjmie wartość „prawda” (sprawdzanie po każdym wykonaniu listy instrukcji),
• b) 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,

• c) 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 2

Poniższy program realizuje sortowanie metodą Shella.

• a) zapisz zaznaczony fragment programu (od "zacznij tu" do "skończ tu") w kodzie czwórkowym
• b) zoptymalizuj program: omów krótko zastosowane techniki optymalizacji, wskaż miejsca, gdzie stosowane były te techniki i napisz czytelnie ostateczną, zoptymalizowana wersję.

Uwagi:

• 1. Nie należy rozwijać pętli zewnętrznej (po k).
• 2. 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

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:

• 1: S -> w1
• 2: A -> w2
• 3: A -> w3
• 4: B -> w4
• 5: 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):

• 1.Zasymuluj działanie automatu na słowach yxy$ oraz xxxyyy$. Czy te słowa należą do L(G)?
• 2.Jakie produkcje występują w G?
• 3.Czy L(G) jest regularny?
• 4.Czy gramatyka G należy do
• a)LL(1)
• b)LR(0)
• c)SLR,
• d)LR(1)
• e)LALR
• f)LR(k), dla k>1?

Zadanie 4

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.

---

Może przyda Ci się następujący:

Zestaw zadań z egzaminu w r.2005

MRJP Instytut Informatyki UW

Metody Realizacji Języków Programowania

Egzamin 13 czerwca 2005 Książki i notatki zamknięte! Telefony wyłączone! Życzymy powodzenia!

Przeczytaj uważnie treść zadań. Zrozumienie jest podstawą sukcesu. Napisz odpowiedź w miejscu przewidzianym na nią. Oceniamy CZYTELNOŚĆ (w obu znaczeniach tego słowa, pisząc niejasno, nieczytelnie ryzykujesz!) i POPRAWNOŚĆ odpowiedzi.

 Imię i nazwisko:  			   indeks: 

   Oświadczam, że podczas tego egzaminu nie korzystałem(-ałam) z
   obcej pomocy ani nie udzielałem(-ałam) jej nikomu

                                Podpis
			  arkusz bez podpisu nie będzie oceniany.
                                                                                                     

$\left|\begin{array}{rrrrrrrrr}Nr& 1& 2& 3& 4& 5& 6& \mathrm{\Sigma }& Uwagi\\ Max& 10& 15& 21& 20& 15& 19& 100\\ Ocena\\ \end{array}\right|.$

1. a) 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.

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

2.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.

3.a) Podaj prosty przykład gramatyki jednoznacznej z konfliktem shift/reduce w metodzie SLR

   b) podaj przykład gramatyki jednoznacznej z konfliktem reduce/reduce w metodzie SLR

c)która z poniższych gramatyk jest LL(1). Litery są nieterminalami, cyfry terminalami. Uzasadnij odpowiedzi (krótko)

c1)   S -> 0 | 12 | 345

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

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

-

4. 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.

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];

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

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

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

6. Pewna gramatyka G posiada dwa symbole nieterminalne S (startowy) i T oraz trzy symbole terminalne a, b i $. Gramatyka G zawiera trzy produkcje 0. S -> w0 length(w0) = 2 1. T -> w1 length(w1) = 2 2. T -> w2 length(w2) = 3 Dana jest tablica sterująca analizatora składniowego LR dla gramatyki G $\left|\begin{array}{rrrrrrrrr}Nr& 1& 2& 3& 4& 5& 6& \mathrm{\Sigma }& Uwagi\\ Max& 10& 15& 21& 20& 15& 19& 100\\ Ocena\\ \end{array}\right|.$ Akcje Goto Stany a b $ S T 0

s3

1 1 s2

accept

2 r1

r1

3

s4 s4

4

s5 s5

5 r2

r2

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

b) Odgadnij produkcje w gramatyce G. Uzasadnij odpowiedź.

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