|
|
| Linia 1: |
Linia 1: |
|
| |
|
|
| |
| == Ćwiczenia 3: Dodawanie binarne (małe kroki) ==
| |
|
| |
|
| |
| == Zadania z rozwiązaniami ==
| |
|
| |
|
| |
| ==== Zadanie 1 ====
| |
|
| |
| Rozważmy następujący język wyrażeń (liczby binarne z dodawaniem):
| |
|
| |
| <math>
| |
| e \, ::= \,\,
| |
| \epsilon \,\,|\,\,
| |
| e 0 \,\,|\,\,
| |
| e 1 \,\,|\,\,
| |
| e_1 + e_2
| |
| </math>
| |
|
| |
| <math> \epsilon </math> oznacza słowo puste, czyli np. <math> \epsilon 1 0 1 </math>
| |
| oznacza binarną liczbę 101.
| |
| Napisz semantykę operacyjną obliczającą wartość wyrażeń.
| |
|
| |
|
| |
| ==== Rozwiązanie ====
| |
|
| |
| Składnia wyrażeń pozwala na wygodny dostęp do najmniej znaczącego
| |
| bitu liczby. Spróbujmy zatem zastosować metodę dodawania
| |
| pisemnego:
| |
|
| |
| <math>
| |
| e_1 0 + e_2 0 \,\Longrightarrow\, (e_1 + e_2) 0
| |
| </math>
| |
| <math>
| |
| e_1 0 + e_2 1 \,\Longrightarrow\, (e_1 + e_2) 1
| |
| </math>
| |
| <math>
| |
| e_1 1 + e_2 0 \,\Longrightarrow\, (e_1 + e_2) 1
| |
| </math>
| |
|
| |
| Ale co zrobić z przeniesieniem?
| |
|
| |
| <math>
| |
| e_1 1 + e_2 1 \,\Longrightarrow\, ?
| |
| </math>
| |
|
| |
| Podstawowy pomysł to potraktować przeniesienie jak dodatkowy składnik:
| |
|
| |
| <math>
| |
| e_1 1 + e_2 1 \,\Longrightarrow\, ((e_1 + e_2) + 1) 0
| |
| </math>
| |
|
| |
| Zauważmy, że w składni dopuszcza się dowolne przeplatanie operatora dodawania
| |
| i bitów <math> 0, 1 </math>. Tę dowolność wykorzystaliśmy właśnie w regułach
| |
| powyżej. Gdyby nasz język ograniczyć tylko do składni
| |
|
| |
| <math>
| |
| e \, ::= \,\,
| |
| b \,\,|\,\,
| |
| e_1 + e_2
| |
| </math>
| |
|
| |
| <math>
| |
| b \, ::= \,\,
| |
| \epsilon \,\,|\,\,
| |
| b 0 \,\,|\,\,
| |
| b 1
| |
| </math>
| |
|
| |
| (nazwijmy ją ''składnią ograniczoną'') to powyższe reguły byłyby niepoprawne.
| |
|
| |
| Zanim dopiszemy pozostałe reguły, określmy zbiór konfiguracji jako
| |
| zbiór wyrażeń. Konfiguracje końcowe to wyrażenia bez operatora dodawania
| |
| (liczby binarne). Nasz pomysł jest taki, że tranzycje stopniowo przesuwają
| |
| operator dodawania w lewo, aż się go ostatecznie <pre>''pozbędą''</pre>.
| |
|
| |
|
| |
| ....
| |
|
| |
|
| |
| ==== Zadanie 2 ====
| |
