|
|
| Linia 1: |
Linia 1: |
| == Semantyka bezpośrednia instrukcji. Konstrukcje iteracyjne. ==
| |
| === Zadanie 1 ===
| |
|
| |
|
| Zdefiniuj semantykę denotacyjną następującego języka:
| |
|
| |
| <math>
| |
| n \, ::= \,\, 0 \,\,|\,\, 1 \,\,|\,\, \ldots
| |
| </math>
| |
|
| |
| <math>
| |
| x \, ::= \,\, \ldots \, (identyfikatory) \, \ldots
| |
| </math>
| |
|
| |
| <math>
| |
| e \, ::= \,\,
| |
| n \,\,|\,\,
| |
| x \,\,|\,\,
| |
| e_1 + e_2 \,\,|\,\,
| |
| </math>
| |
|
| |
| <math>
| |
| b \, ::= \,\,
| |
| e_1 = e_2 \,\,|\,\,
| |
| \mathbf{not}\, b \,\,|\,\,
| |
| b_1\, \mathbf{or}\, b_2 \,\,|\,\,
| |
| </math>
| |
|
| |
| <math>
| |
| 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{repeat}\, i \,\mathbf{until}\, b \,\,|\,\,
| |
| </math>
| |
|
| |
| Pętla <math> \mathbf{repeat}\, i \,\mathbf{until}\, b </math> polega na wykonaniu instrukcji ''i'', a następnie wyliczeniu warunku logicznego ''b''. Jeśli warunek jest prawdziwy wykonanie pętli kończy się, w przeciwnym razie powracamy do wykonania instrukcji ''i''.
| |
|
| |
| === Zadanie 2 ===
| |
| Rozszerzmy język z poprzedniego zadania o instrukcję:
| |
|
| |
| <math>
| |
| i \, ::= \mathbf{for}\, x\, :=\, e_1\, \mathbf{to}\, e_2\, \mathbf{do}\, i
| |
| </math>
| |
|
| |
| Wykonanie takiej pętli polega na:
| |
| # Wyliczeniu wartości <math>n</math> wyrażenia <math>e_1</math>.
| |
| # Przypisaniu wartości <math>n</math> na zmienną <math>x</math>.
| |
| # Wyliczeniu wartości <math>m</math> wyrażenia <math>e_2</math>.
| |
| # Jeśli <math>x > m</math>, to pętla kończy się.
| |
| # W przeciwnym razie:
| |
| #* Wykonujemy instrukcję <math> i </math>.
| |
| #* Zwiększamy zmienną <math>x</math> o 1.
| |
| #* Powracamy do punktu 3.
| |
| Zauważmy, że wyrażenie <math>e_1</math> jest tu wyliczane tylko raz, ale <math>e_2</math> oblicza się przy każdym obrocie pętli.
| |
|
| |
| === Zadanie 3 ===
| |
| Zmieńmy semantykę instrukcji for z poprzedniego zadania tak, aby
| |
| oba wyrażenia obliczały się tylko raz. Tym razem wyliczenie pętli polega na:
| |
| # Wyliczeniu wartości <math>n</math> wyrażenia <math>e_1</math>.
| |
| # Przypisaniu wartości <math>n</math> na zmienną <math>x</math>.
| |
| # Wyliczeniu wartości <math>m</math> wyrażenia <math>e_2</math>.
| |
| # Jeśli <math>x > m</math>, to pętla kończy się.
| |
| # W przeciwnym razie:
| |
| #* Wykonujemy instrukcję <math>i</math>.
| |
| #* Zwiększamy zmienną <math>x</math> o 1.
| |
| #* Powracamy do punktu 4.
| |
|
| |
| === Zadanie 4 ===
| |
| O pętli for można jednak myśleć jeszcze inaczej. Można wymagać, aby wszelkie zmiany wartości zmiennej sterującej <math>x</math> wewnątrz wykonania pętli nie miały wpływu na liczbę iteracji tej pętli. Przykładowo przy semantyce z poprzedniego zadania pętla:
| |
| '''for''' x := 1 '''to''' 10 '''do'''
| |
| x := x + 1;
| |
| y := y + x;
| |
| wykonuje się pięć razy, a zmienna y jest zwiększana łącznie o 2+4+6+8+10. Jeśli uznamy, że zmiany zmiennej x wewnątrz pętli nie wpływają na liczbę iteracji, to pętla wykona się 10 razy, a zmienna y zostanie zwiększona o 2+3+4+5+6+7+8+9+10+11. Zdefiniuj taką semantykę.
| |
|
| |
| === Zadanie 5 ===
| |
| W języku C pętla '''for''' ma następującą postać:
| |
| <math>
| |
| i \, ::= \mathbf{for}\, (i_1;\, b;\, i_2)\, i_3
| |
| </math>
| |
|
| |
| Jej wykonanie polega na:
| |
| # Wykonaniu instrukcji <math>i_1</math>.
| |
| # Wyliczeniu wartości wyrażenia <math>b</math>.
| |
| # Jeśli wyrażenie wylicza się do fałszu, to pętla kończy się.
| |
| # W przeciwnym razie:
| |
| #* Wykonujemy instrukcję <math> i_3 </math>.
| |
| #* Wykonujemy instrukcję <math> i_2 </math>.
| |
| #* Powracamy do punktu 2.
| |
