Metody realizacji języków programowania 2007, ćwiczenia

Zajęcia

Konsultacje

Konsultacje przed egzaminem (NEW!)

Zadania z zeszłego roku z egzaminu - warto rozwiązać! (NEW!)

Zad 1

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

1. Nie należy rozwijać pętli zewnętrznej (po k) (tzn nie trzeba 16 razy pisać wnętrza pętli aby wyeliminować kilka instrukcji skoku).
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
}

Zad 2

• Instr ::= do { InstrList } until Bexpr
• Expr ::= Bexpr ? Expr1 : Expr2
• Bexpr ::= Bexpr1 xor Bexpr2

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

• instrList ma być wykonywana aż do momentu gdy Bexpr wyliczy się do prawdy (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ą jest xor wartości wyrażeń logicznych po prawej stronie produkcji.

Zad 3

1. S ::= w1
2. A ::= w2
3. A ::= w3
4. B ::= w4
5. B ::= w5

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
   1. LL(1)
   2. LR(0)
   3. SLR,
   4. LR(1)
   5. LALR
   6. LR(k), dla k>1?

Zad 4

• Deklaracje ::= const DeklaracjeStalych ;
• DeklaracjeStalych ::= DeklaracjeStalych ; DeklaracjaStalej
  | DeklaracjaStalej
• DeklaracjaStalej ::= identyfikator = Wyrazenie
• Wyrazenie ::= Wyrazenie + WyrazenieProste
  | WyrazenieProste
• WyrazenieProste ::= ( Wyrazenie )
  | identyfikator
  | liczba

2. kolokwium

program p 
   var x: integer;
   var z: integer
   procedure q (var x: integer; y : integer) 
      procedure r (y : integer)
      begin
         z := x + y;
         x := 1;
         y := 4;
      end
   begin
      x := 5;
      r(x);
   end;
begin
   x := 2;
   z := 3;
   q(x, z);
   print x + z;
end.
   

• Jaki będzie wynik działania tego programu?
• Skompiluj program do kodu maszyny stosowej z ćwiczeń (patrz ważniak).

Zasoby

Gramatyki LL(1)

Zadania z 1 kolokwium z zeszlego roku

• A → A x B | B
• B → B y C | C
• C → z A z | x

1. Czy gramatykę G można sprowadzić do postaci LL(1) ? Jeśli tak, to zrób to i na podstawie przekształconej gramatyki napisz procedury parsera metodą zejść rekurencyjnych.
2. Czy można zbudować parser LR(0) dla gramatyki G ? Czy można zbudować parser SLR dla gramatyki G ? Czy można zbudować parser LR(1) dla gramatyki G ?