Gramatyka G opisuje automat sterujący LR:
A -> P A | ε
P -> goto(n,n,n) | shift(n,n,n) | reduce(n,n,n) | accept(n,n)
gdzie n jest liczbą oznaczającą oznaczającą numer stanu, produkcji lub symbolu. Ciągi terminali n oddzielonych przecinkiem w produkcjach P oznaczają najpierw stan/stany, później ewentualnie produkcję, a na końcu symbol. Np. shift(1,2,6) oznacza operację shift w stanie 1 z przesunięciem symbolu 6 i przejściem do stanu 2.
Napisz na podstawie gramatyki G gramatykę atrybutywną, która ustawi atrybut sr dla A na true wtw gdy nie ma konfliktu shift/reduce. Załóż, że terminal n posiada atrybut v, reprezentujący jego wartość liczbową.
Rozważmy język programów opisany poniższą gramatyką, składających się z sekwencji deklaracji D poprzedzających pojedyncze wyrażenie W
P -> D;W
D -> D;D | id : T
T -> char | int | array [n] of T
W -> c | n | id | W mod W | W[W]
W gramatyce tej c oznacza stałą znakową, n - stałą liczbową.
1. Zapisz reguły sprawdzania typów dla tego języka (np. w postaci gramatyki atrybutywnej)
2. Rozszerz język o wskaźniki i reguły typowania dla nich
3. Używając zaprojektowanych wcześniej reguł wyznacz typy wyrażeń w następujących fragmentach programu:
a) c : char; i : int; c mod i mod 3
b) p : ^int; a: array[10] of int; a[p^]
4. Rozszerz język o typy postaci list of T (lista elementów typu T), wyrażenie konstruujące listę z głowy i ogona i wyrażenie nil reprezentujące listę pustą (która moze reprezentować listę pustą elementów dowolnego typu).
W pewnym języku programowania występuje typ real reprezentujący
liczby oraz mac(m,n) reprezentujący macierze wymiaru m * n o
wyrazach typu real. Napisz gramatykę atrybutywną dla produkcji mnożenia
(E -> E1 * E2) opisującą analizę typów (obliczone typy umieszczaj w
atrybucie E.typ).
Program w języku EZ2 składa się z ciągu definicji funkcji. Funkcje opisuje gramatyka
definicja-funkcji ::= identyfikator '(' wyrażenie ')' '=' wyrażenie
wyrażenie ::= wyrażenie operacja-arytmetyczna wyrażenie
| identyfikator
| stała-całkowita
| identyfikator '(' wyrażenie ')'
| 'let' identyfikator '=' wyrażenie 'in' wyrażeniePrzedostatnia produkcja oznacza wywołanie funkcji. Ostatnia oznacza deklarację i nadanie
wartości zmiennej lokalnej, która może przesłaniać zadeklarowane wcześniej zmienne, jak i
nazwy funkcji.
Zasięgiem deklaracji po 'let' jest wyrażenie po 'in'.
Funkcje mogą być rekurencyjne (także wzajemnie) i ich definicje mogą występować w dowolnej
kolejności (tzn. dowolna permutacja poprawnego ciągu definicji funkcji daje poprawny ciąg
definicji funkcji).
Programy w EZ2 operują wyłącznie na liczbach całkowitych.
Efektem działania programu w EZ2 jest wypisanie wyniku main(0)
a) Opisz zwięźle warunki poprawności kontekstowej programu EZ2, których spełnienie jest
niezbędne aby wykonanie programu było możliwe.
b) Opisz interfejs tablicy symboli dla EZ2
c) Uwzględniając powyższe, napisz fragment programu sprawdzający poprawność kontekstową
wyrażeń.
Dany jest język wyrażeń o gramatyce:
S → E E → * E E → & E E → E := E E → id
Identyfikatory występujące w wyrażeniach reprezentują zmienne typu prostego T.
Gwiazdka jest operatorem dereferencji (wyłuskania), który stosujemy do wskaźnika, by otrzymać wartość przezeń wskazywaną. Wyrazenie *E jest poprawne, jeśli E jest wskaźnikiem.
Ampersand (&) jest operatorem pobrania adresu, który daje wskaźnik do wartości wyrażenia, do którego ten operator stosujemy. Wyrażenie &E jest poprawne nawet, jesli E nie jest zmienną. W takiej sytuacji dostaniemy wskaźnik do zmiennej tymczasowej, przechowującej obliczoną wartość E.
Przypisanie E:=E jest poprawne, jeśli typy obu wyrażeń są równe, a lewa strona przypisania jest zmienną lub dereferencją wskaźnika.
Zbuduj, w oparciu o powyższą gramatykę bezkontekstową, gramatykę atrybutywną z regułami atrybutowania, ktore umieszczą na atrybucie S.ok wartość logiczną mowiącą, czy wyrażenie wyprowadzone z S jest poprawne.
W pewnym języku programowania występuje typ int reprezentujący liczby całkowite oraz typ list(t) reprezentujący listy o elementach typu t. Wszystkie elementy danej listy muszą być tego samego typu, aby lista była poprawna.
Do tworzenia list służy stała nil (pusta lista) i operator cons budujący listę, argumentami sa głowa i ogon listy. Operatory car i cdr daja odpowiedni głowę i ogon swojego argumentu.
Przykładowo: x = cons(1,cons(0,nil)) tworzy listę zawierającą dwa elementy: 1 i 0,car(x) = 1, cdr(x) = cons(0,nil).
Uzupełnij poniższą gramatykę o opis analizy typów (obliczone typy wyrażeń umieszczaj w atrybucie E.typ):
E → 0 | 1 | E+E | nil | cons(E,E) | car(E) | cdr(E)
.
Rozważmy język, którego składnię opisuje gramatyka w formie EBNF:
Program ::= {Funkcja}
Funkcja ::= id({id:Typ[,]})[:Typ] = Wyrażenie
Wyrażenie ::= num | id {Wyrażenie}
Typ ::= int | Typ -> TypPrzykład poprawnego programu:
main() = f 42 f(r:int):int = s p q r s (a:int->(int->int)->int, d:int->int->int, c:int):int = a c (d c) p(x:int, y:int->int) = x q(x:int, y:int) = x
Zaproponuj system typów dla tego języka.