|
Rozszerzamy składnię abstrakcyjną wyrażeń arytmetycznych i
logicznych o dodawanie (+) oraz test równości
(=).
|
Zadanie 1 (5p) Rozszerz strukturalną
semantykę operacyjną (małych kroków) podaną na
wykładzie o reguły dla + oraz =, a
następnie na podstawie tak otrzymanej definicji
relacji → i jej zwrotno-przechodniego
domknięcia zaimplementuj ewaluator rozszerzonych
wyrażeń arytmetycznych i logicznych. Zwróć szczególną
uwagę na postacie normalne, które nie są wartościami,
a zatem reprezentują błędy wykonania.
|
Zadanie 2 (5p) Zdefiniuj semantykę naturalną
(dużych kroków) dla rozszerzonych wyrażeń
arytmetycznych i logicznych. W tym celu indukcyjnie
zdefiniuj relację t ⇓ v opisującą pełne
obliczenie termu t do wartości v (a nie
pojedynczy krok ewaluacji). Na podstawie tej definicji
zaimplementuj ewaluator rozszerzonych wyrażeń
arytmetycznych i logicznych.
|
Zadanie 3 (5p) Zbuduj prosty system typów,
który będzie rozróżniał wyrażenia typu Nat
(intuicyjnie -- dobrze zbudowane wyrażenia
arytmetyczne), wyrażenia typu Bool (intuicyjnie
-- dobrze zbudowane wyrażenia logiczne) oraz pozostałe
wyrażenia, które uznasz za źle typowane. Każde
wyrażenie powinno mieć co najwyżej jeden
typ. Zaimplementuj dwie funkcje, z których jedna
będzie sprawdzała czy dane wyrażenie jest danego typu,
a druga będzie znajdowała typ danego wyrażenia.
|
Zadanie 4 (5p) Zaimplementuj parser oraz
obsługę wejścia-wyjścia (czytanie wyrażeń z konsoli
lub pliku, a także pretty-printer) dla rozszerzonego
języka wyrażeń. Zaimplementuj pętlę powtarzającą
operacje:
czytaj, parsuj, sprawdź typ, oblicz, wydrukuj
używając wcześniej napisanych komponentów
(nie ma znaczenia, którego ewaluatora
użyjesz). Oczywiście, sprawdzanie typu powinno być
wykonywane tylko dla wyrażeń, które bezbłędnie przejdą
fazę parsowania (są zgodne ze składnią języka), a
ewaluowane powinny być tylko te wyrażenia, które
bezbłędnie przejdą fazę sprawdzania typu (są dobrze
typowane).
|
|