Semantyka i weryfikacja programów/Ćwiczenia 9

From Studia Informatyczne

Spis treści

Procedury i funkcje. Przekazywanie parametrów.

Zadanie 1

Zdefiniuj semantykę denotacyjną następującego języka:

n \, ::= \,\, 0 \,\,|\,\, 1 \,\,|\,\, \ldots

x \, ::= \,\, \ldots \, (identyfikatory) \, \ldots

e \,  ::=  \,\,           n   \,\,|\,\,         x   \,\,|\,\,         e_1 + e_2

b \,  ::=  \,\,           e_1 = e_2   \,\,|\,\,         \mathbf{not}\, b    \,\,|\,\,         b_1\, \mathbf{or}\, b_2

i \, ::= \,\,          x := e     \,\,|\,\,          i_1; i_2   \,\,|\,\,          \mathbf{if}\, b \,\mathbf{then}\, i_1 \,\mathbf{else}\, i_2 \,\,|\,\,          \mathbf{skip} \,\,|\,\,          \mathbf{while}\, b \,\mathbf{do}\, i \,\,|\,\,          \mathbf{call}\, P (x) \,\,|\,\,          \mathbf{begin}\, d; i\,\mathbf{end}

d \, ::= \,\,          \mathbf{var}\, x := e     \,\,|\,\,          d_1; d_2   \,\,|\,\,          \mathbf{proc}\, P (x); i\, \mathbf{endproc}

Deklaracja \mathbf{var}\, x := e wprowadza zmienną x i nadaje jej wartość obliczonego wyrażenia e. Deklaracja \mathbf{proc}\, P (x); i\, \mathbf{endproc} wprowadza procedurę o nazwie P z jednym parametrem x przekazywanym przez zmienną. Treścią procedury jest instrukcja i.

Instrukcja bloku \mathbf{begin}\, d; i\,\mathbf{end} polega na wykonaniu instrukcji i po uprzednim wzbogaceniu środowiska deklaracją d. Wszystkie zmienne i procedury wprowadzone przez d są lokalne w bloku. Instrukcja \mathbf{call}\, P (x) to wywołanie procedury P.

Zadanie 2

Jaką wartość ma zmienna z przy semantyce z poprzedniego zadania po wykonaniu następującej instrukcji:

begin
  var
    y := 1;
    proc P (x); x := y endproc;
    begin
      var y := 2;
      var z := 0;
      call P(z);
    end
 end
    

Zadanie 3

Wyjaśnij różnicę między wiązaniami statycznymi a dynamicznymi. Zmień semantykę języka z zadania 1 tak, aby uzyskać dynamiczne wiązania identyfikatorów.

Zadanie 4

Czy semantyka z zadania 1 umożliwia pisanie procedur rekurencyjnych? A semantyka z zadania 3? Jak należy zmienić semantykę, aby procedury rekurencyjne były możliwe?

Zadanie 5

Przypuśćmy, że składnia wywołania procedury z zadania 1 przyjmuje teraz postać:

i \, ::= \,\,          \mathbf{call}\, P (e)

Pozostałe elementy nie zmieniają się. Przekazywanie parametrów odbywa się teraz jednak przez wartość. Opisz semantykę takiego języka. Zadbaj o możliwość definiowania procedur rekurencyjnych i statyczne wiązania zmiennych globalnych.