System konstrukcji kompilatorów - GENTLE

Spis treści:

  1. Wprowadzenie
  2. Specyfikacja
  3. Uruchamianie
  4. Przykłady
  5. Materiały

1.Wprowadzenie

System konstrukcji kompilatorów GENTLE został zaprojektowany w 1989 roku. Aktualnie jest dostępny w dwóch edycjach: GENTLE97(1997) i GENTLE21(2001) i ciągle jest rozwijany wedlug rosnących zapotrzebowan użytkowników. GENTLE wspiera wysokopoziomowy opis kompilatorów i uwalnia uzytkownika od zajmowania sie szczegółami implementacji. Dostarcza jednolitego szkieletu do specyfikacji komponentow kompilatora. Umożliwiaja rozpoznawanie języka, definicję drzewa abstrakcyjnej składni, transformację opartą na dopasowywaniu wzorców i wiele innych. Tłumaczy wysokopoziomowy opis kompilatora na wydajny i przenosny kod C, Lex i Yacc.
Specyfikacja napisana w GENTLE może być automatycznie zamieniona na kod C, a nawet mozliwe jest częściowe napisanie kompilatora w GENTLE i C.To wszystko powoduje że praca z GENTLE jest bardzo efektywna, a wręcz przyjemna.

Poniższy schemat obrazuje sposób tworzenia kolejnych składowych modułów oraz użycie Lex'a, Yacc'a, Reflexa (część składowa GENTLE'a) oraz kompilatora C. Wiecej informacji na ten temat można znaleźć w 3. Uruchamianie

2.Specyfikacja


2.1 Konkretna składnia

Gentle może generować zwykłe parsery wyrażeń. Poszczególne produkcje mogą także zwracać pewne wartości, więc napisanie prostego kalkulatora jest bardzo łatwe:

'root' expression(-> X) print(X)
	
'nonterm' expression(-> INT)
	'rule' expression(-> X): expr2(-> X)
	'rule' expression(-> X+Y): expression(-> X) "+" expr2(-> Y)
	'rule' expression(-> X-Y): expression(-> X) "-" expr2(-> Y)

'nonterm' expr2(-> INT)
	'rule' expr2(-> X): expr3(-> X)
	'rule' expr2(-> X*Y): expr2(-> X) "*" expr3(-> Y)
	'rule' expr2(-> X/Y): expr2(-> X) "/" expr3(-> Y)

'nonterm' expr3(-> INT)
	'rule' expr3(-> X): Number(-> X)
	'rule' expr3(-> - X): "-" expr3(-> X)
	'rule' expr3(-> + X): "+" expr3(-> X)
	'rule' expr3(-> X): "(" expression(-> X) ")"

'token' Number(-> INT)

Jak widać jest to zwykły opis gramatyki, zawierający nieterminale i terminale, a także operacje na wartościach zwracanych przez nie.
Symbolem początkowym gramatyki zawsze jest 'root', który w tym przypadku wywołuje parsowanie wyrażenia expression, które powinno zwrócić zmienną X, a następnie jej wypisanie.

Nieterminale definiuje się za pomocą 'nonterm', ustalając ich nazwę i typ zwracany (Akurat tutaj wszystko jest typu INT). natomiast produkcje dla tych nieterminali oznacza się za pomocą 'rule', po którym występuje nieterminal będący lewą stroną produkcji, wraz ze zwracaną wartościa, która jest otrzymywana z wartości tokenów lub nieterminali po prawej stronie. Wszystkie występujące w przykładzie X i Y to zmienne lokalne.

Symbol terminalny może wystąpić po prawej stronie produkcji jako wyrażenie w cudzysłowach lub jako token. Linia

'token' Number(-> INT)

wprowadza token Number, który jest zdefiniowany poza kodem programu jako ciąg cyfr. Typem tego tokenu jest liczba calkowita INT.

Dla poprawnych wyrażeń arytmetycznych program ten wypisuje jego obliczoną wartość. Dla niepoprawnego wejścia oflagowuje pierwszy niepoprawny token.

Jeśliby usunąc z programu funkcję print(X), a także pousuwać wszystkie fragmenty typu (->X),(->Y) itd. (oczywiście oprócz tego przy deklaracji tokenu), to program ten byłby zwykłym parserem wyrażeń arytmetycznych.


2.2 Składnia abstrakcyjna

Powyższy kalkulator był zapisany za pomocą prostej składni "konkretnej". Jednakże przy tworzeniu kompilatorów zazwyczaj korzysta się ze składni abstrakcyjnej. Ten sam program zapisany za jej pomocą wyglada nastepująco:

'type' Expr
	plus(Expr, Expr)
	minus(Expr, Expr)
	mult(Expr, Expr)
	div(Expr, Expr)
	neg(Expr)
	num(INT)

'root' expression(-> X) print(X)

'nonterm' expression(-> Expr)
	'rule' expression(-> X): expr2(-> X)
	'rule' expression(-> plus(X,Y)): expression(-> X) "+" expr2(-> Y)
	'rule' expression(-> minus(X,Y)): expression(-> X) "-" expr2(-> Y)

'nonterm' expr2(-> Expr)
	'rule' expr2(-> X): expr3(-> X)
	'rule' expr2(-> mult(X,Y)): expr2(-> X) "*" expr3(-> Y)
	'rule' expr2(-> div(X,Y)): expr2(-> X) "/" expr3(-> Y)

'nonterm' expr3(-> Expr)
	'rule' expr3(-> num(X)): Number(-> X)
	'rule' expr3(-> neg(X)): "-" expr3(-> X)
	'rule' expr3(-> X): "+" expr3(-> X)
	'rule' expr3(-> X): "(" expression(-> X) ")"

'token' Number(-> INT)

Jak widać wiele się tu nie zmieniło, z tym że produkcje zamiast wyliczonych wartości typu INT zwracają obiekty typu Exprzdefiniowanego za pomocą słowa 'type', po którym nastepuje nazwa nowego typu i spis wartości, jakie może przyjąć. Powyższy program dla wyrażenia 10+20*30 wypisze plus(num(10)), mult(num(20), num(30)), czyli składnię abstrakcyjną tego wyrażenia.
Można teraz dopisać odpowiednią funkcję, która przetworzy tą składnię we właściwy wynik. Wystarczy dodać w programie następującą akcję:

'action' eval (Expr -> INT)
	'rule' eval(plus(X1, X2) -> N1+N2): eval(X1 -> N1) eval(X2 -> N2)
	'rule' eval(minus(X1, X2) -> N1-N2): eval(X1 -> N1) eval(X2 -> N2)
	'rule' eval(mult(X1, X2) -> N1*N2): eval(X1 -> N1) eval(X2 -> N2)
	'rule' eval(div(X1, X2) -> N1 / N2): eval(X1 -> N1) eval(X2 -> N2)
	'rule' eval(neg(X) -> -N): eval(X -> N)
	'rule' eval(num(N) -> N)

i zmodyfikować linię, zawierającą 'root' aby miała postać:

'root' expression(-> X) eval(X -> N) print(N)

żeby kalkulator działał jak należy.
Akcje, czyli procedury, definiuje się za pomocą slowa 'action'. Deklaracja akcji w tym przypadku zawiera jej nazwę, a nastepnie listę typów argumentów i typ wyrażenia zwracanego. Następnie w kodzie powinny sie znależć jakieś reguły (definiowane dość podobnie jak produkcje przy pisaniu parsera - słowo 'rule'), pokazujące jak zależnie od wartości wywołania tworzona jest wartość zwracana. Przykładowo:

rule' eval(plus(X1, X2) -> N1+N2): eval(X1 -> N1) eval(X2 -> N2)

najpierw sprawdza czy argument wywołania akcji eval (w nawiasie, po lewej stronie znaku ->) jest typu plus(X1,X2), gdzie X1 i X2 są dowolnymi zmiennymi. Następnie wykonywane są akcje eval(X1 -> N1) i eval(X2 -> N2). Jeżeli obydwie zakończą się sukcesem, zwracając jakieś wartości N1 i N2 to obliczany jest wynik zwracany przez akcję eval (czyli N1+N2).


2.3 Specyfikacja GENTLE

Specyfikacja w GENTLE'u to lista deklaracji, które mogą wprowadzać:

typy danych np.

'type' Expr
	plus(Expr, Expr)
	neg(Expr)
	num(INT)

predykaty np.

'action' eval (Expr -> INT)
	'rule' eval(plus(X1, X2) -> N1+N2): eval(X1 -> N1) eval(X2 -> N2)
	'rule' eval(minus(X1, X2) -> N1-N2): eval(X1 -> N1) eval(X2 -> N2)
	'rule' eval(num(N) -> N)

zmienne globalne np.

'var' CurLoopContext: LoopContext

lub globalne tablice np.

'table' Label (Address: INT)

Deklaracje mogą mieć dowolną kolejność!

Poza tym zawsze musi wystapić definicja 'root' zawierająca wywołania jakichś predykatów, które wygenerowany program wykonuje.

W kodzie mogą też pojawić sie komentarze dwóch rodzajów:

-- komentarz do końca linii

/* komentarz przez 
kilka linii */

2.3.1 Dane

Dane mogą należeć do któregoś ze zdefiniowanych typów, lub do typów podstawowych, z których definiuje się te bardziej złożone. Podstawowymi typami danych są INT i STRING, a także zwykła stała np. czerwony, natomiast złożone mogą wyglądać tak:

wymienienie kilku podstawowych danych np.

type Color
	czerwony
	zielony
	biały

złożenie kilku typów danych posiadające nazwę np.

'type' Signal
	signal (Color, Color)

definicja rekursywna np.

'type' ColorList
	list (Color, ColorList)
	nil

poszczególne pola w definicji mogą mieć także nazwy np.

list(Head: Color, Tail: ColorList)

Zmienne nie muszą być deklarowane, ale są silnie typizowane i ich typ znacząco wpływa min. na wybór właściwej zasady 'rule'.


2.3.2 Definiowanie predykatów

Predykat jest deklarowany przez podanie jego identyfikatora i jego zasad na przykład:

'action' length (ColorList -> INT)		--oblicza długość listy typu Colorlist
	'rule' length (list(Head, Tail) -> N+1) : length(Tail -> N)
	'rule' length (nil -> 0)

Identyfikator jest postaci:

Kategoria Nazwa ( Typy wejściowe -> Typy wyjściowe )

Nazwy poszczególnych typów wymienia się po przecinkach. Jeżeli brak jest typów wyjściowych, to strzałkę się pomija.
Parametry mogą posiadać nazwy pomocne w dokumentowaniu np.

'action' length (L: ColorList -> N: INT)

Kategoria jest jedną spośród: 'nonterm', 'token', 'action', 'condition', 'choice', 'sweep'. Różnią się one między sobą strategią wyboru odpowiedniej zasady. I tak:

'nonterm' i 'token' wykorzystywane są do przedstawiania gramatyk bezkontekstowych i są ewaluowane za pomocą parsingu LR.

W przypadku 'condition' i 'action' zasady wykonywane sa jedna po drugiej i gdy jakaś zostanie spełniona, to predykat tez jest spełniony. natomiast gdy żadna zasada nie jest spełniona, to 'condition' zawodzi, natomiast 'action' zwraca błąd, co pomaga przy debuggowaniu programu.

W przypadku 'choice' zasada wybierana jest tak, żeby suma kosztów wszystkich wykorzystanych zasad była minimalna. należy wyspecyfikować koszty.


2.3.3 Wywoływanie predykatów

Jeżeli został zdefiniowany predykat, który oznacza Imie ojca dla Osoby, to możemy napisać tata(O -> X) aby zapytać o to. Jeżeli w definicji predykatu były następujące zasady:

	'rule' tata (jim -> steven)
	'rule' tata (julia -> brian)

to wywołanie tata (julia -> X) podstawi pod stworzoną zmienną lokalną X słowo brian. Predykaty mogą mieć argumenty wejściowe i wyjściowe. I tak na przykład:

tata(X -> steven) 

podstawi pod zmienną X słowo jim przy tak zdefiniowanych zasadach. Natomiast tata(jim -> brian) zawiedzie, nie zwróci nic.
Predykaty moga także mieć swoje ciała wpisywane po znaku ":".

'rule' tata(jack -> X): tata(jane -> X)

W tym przypadku wywołanie tata(jack->X) zwróci to samo co zwróciłoby wywołanie tata(jane->X).
Możemy też napisać

'rule' dziadek(X -> Z): tata(X -> Y) tata(Y -> Z)

co bedzie szukało takiej zmiennej Z, żeby oba predykaty w ciele były spełnione.

W przypadku istnienia kilku pasujących zasad dobierana jest pierwsza. Jeżeli w miare obliczania dalszej cześci ciała funkcji coś zawiedzie, to mogą byc dobierane kolejne wartości. Jest możliwość skorzystania ze słowa Other aby otrzymać na przykład:

'rule' kind(a -> vowl)
'rule' kind(e -> vowl)
'rule' kind(i -> vowl)
'rule' kind(o -> vowl)
'rule' kind(u -> vowl)
'rule' kind(Other -> consonant)

co chyba nie wymaga tłumaczenia.


2.3.4 Predefiniowane predykaty

Następujące predykaty moga byc używane bez deklarowania: eq, ne, gt, ge, lt, le, print, where, @ .

Spośród nich 6 pierwszych oznacza relacje, a dwa pierwsze są zadeklarowane dla każdego typu. Z kolei cztery kolejne można wywoływać dla zmiennych INT i STRING. Predykaty te oznaczają kolejno: równy, różny, większy niż, większy lub równy, mniejszy niż, mniejszy lub równy. Predykaty te moga być spełnione lub zawodzić, co nie wymaga tłumaczenia.

print jest zdefiniowany jako 'action' print(T). Działa dla każdych danych wejściowych i wypisuje ich wartość.

where jest zdefiniowany jako:

'action' where(T -> T)
	'rule' where(X -> X)

Działa dla każdych danych, zwracając na wyjściu dane z wejścia.

Natomiast predykat @ jest zdefiniowany jako 'action' @(-> POS) i zwraca pozycję terminala lub nieterminala, w ciele którego został wywołany. Tutaj na przykład pod zmienną P zostaje wpisana pozycja Expression.

'rule' Statement: "IF" Expression @(->P) "THEN" Statement

3.Uruchamianie

Aby kompilacja naszego programu była możliwa potrzebujemy plików ze specyfikacją wszystkich tokenów. Zapisujemy je w katalogu Reflex'a, który jest tworzony w czasie instalcji GENTLE'a. Pliki te mają postać: nazwa_tokenu.t a ich specyfikacja jest taka sama jak specyfikacja LEX'a. Oczywiście najważniejszym elementem jest example.g napisany w GENTLE.

Przykładowy Makefile:

PROG = example

all : ${PROG}
$GENTLE ${PROG}.g
$REFLEX
lex gen.l
yacc gen.y
gcc -o ${PROG} ${PROG}.c lex.yy.c y.tab.c $LIB/errmsg.o $LIB/main.o $GRTS

$GENTLE jest ścieżką dostępu do programu GENTLE, a $GRTS do środowiska w pliku grts.o, $REFLEX to ścieżka do programu reflex, $LIB do biblioteki użytkownika.

$GENTLE example.g

Tłumaczy example.g na kilka plików: example.c oraz pliki gen.* które zostją później wykorzystane przez pozostałe programy.

$REFLEX

Pobiera wygenerowane pliki gen.lit i gen.ltk, oraz pliki ze specyfikacją tokenów i łączy je do pliku gen.l, który w następnym poleceniu zostaje przetlumaczony przez LEX'a:

lex gen.l

i powstaje plik lex.yy.c z kodem skanera.

yacc gen.y

Tlumaczy gen.y do y.tab.c. Teraz możemy dokonać kompilacji:

gcc -o ${PROG} ${PROG}.c lex.yy.c y.tab.c $LIB/errmsg.o $LIB/main.o $GRTS

$LIB/errmsg.o i $LIB/main.o są modułami z bilbioteki użytkownika. Dostarczają procedury obsługi błędów i funkcję main() która zawiera kod wygenerowany przez kompilator GENTLE'a (użytkownik może zdefiniować własne według potrzeb).

Poniższy rysunek dokładnie przedstawia kolejne etapy tworzenia wynikowego pliku, jest to fragment z tutoriala znajdujacego się na stronie (1)źródła

4.Przykłady

Prosty program obliczajacy pochodna z wyrazen arytmetycznych zawierajacych takze zmienna x:
'type' Expr
	plus(Expr, Expr)
	minus(Expr, Expr)
	mult(Expr, Expr)
	div(Expr, Expr)
	neg(Expr)
	num(INT)
	x

'root' expression(-> X) deriv(X -> D) print(D)

'nonterm' expression(-> Expr)
	'rule' expression(-> X): expr2(-> X)
	'rule' expression(-> plus(X,Y)): expression(-> X) "+" expr2(-> Y)
	'rule' expression(-> minus(X,Y)): expression(-> X) "-" expr2(-> Y)

'nonterm' expr2(-> Expr)
	'rule' expr2(-> X): expr3(-> X)
	'rule' expr2(-> mult(X,Y)): expr2(-> X) "*" expr3(-> Y)
	'rule' expr2(-> div(X,Y)): expr2(-> X) "/" expr3(-> Y)

'nonterm' expr3(-> Expr)
	'rule' expr3(-> num(X)): Number(-> X)
	'rule' expr3(-> neg(X)): "-" expr3(-> X)
	'rule' expr3(-> X): "+" expr3(-> X)
	'rule' expr3(-> X): "(" expression(-> X) ")"
	'rule' expr3(-> X): "X"

'token' Number(-> INT)

'action' deriv (Expr -> Expr)
	'rule' deriv(mult (U,V) -> plus(mult(Ud,V), mult(U,Vd))):
		deriv(U -> Ud)
		deriv(V -> Vd)
	'rule' deriv(div(U,V) -> div(minus(mult(Ud,V),mult(U,Vd)),mult(V,V))):
		deriv(U -> Ud)
		deriv(V -> Vd)
	'rule' deriv(plus(U,V) -> plus(Ud, Vd)):
		deriv(U -> Ud)
		deriv(V -> Vd)
	'rule' deriv(minus(U,V) -> minus(Ud, Vd)):
		deriv(U -> Ud)
		deriv(V -> Vd)
	'rule' deriv(num(N) -> num(0))
	'rule' deriv(x -> num(1))



5.Materiały

Więcej informacji można znaleźć w: