🚀 go-pugleaf

W dniu piątek, 21 kwietnia 2017 18:01:23 UTC+2 użytkownik (fir) napisał:

> jak ja ostatnio pisalem prosty kompilator "wyrazen z jednym rowna sie i z czterema operatorami (+-*/) plus nawiasy" to to wcale nie do konca przypominalo 'petle z ifami lub ze switchem')

też ostatnio rozwijam kompilator na potrzeby pracy magisterskiej,
ale kompilacja to jednak coś innego, niż parsowanie. w ogólnym
przypadku celem parsowania jest zbudowanie drzewa rozbioru składni,
choć oczywiście jeżeli format instrukcji jest prosty, często może
wcale nie być nawet takiej potrzeby (co ma znaczenie, jak ktoś
pracuje w językach takich jak C czy Pascal, gdzie obsługa drzew
jest raczej uciążliwa). Jeżeli masz już drzewo rozbioru składni,
to stworzenie interpretera dla języka jest raczej łatwym zadaniem.

Dla amatorów Lispa parsowanie jest zasadniczo umiarkowanie ciekawym
zagadnieniem, natomiast kompilacja -- jak najbardziej. Najbardziej
podstawowa technika kompilacji to konwersja do postaci, w której
funkcje przekazują kontynutacje ("Continuation-Passing Style").

Na przykład, wyrażenie (+ (* x y) (/ z w))
w postaci przekazującej kontynuacje miałoby postać

(pass* x y
  (lambda (xy)
    (pass/ z w
       (lambda (zw)
         (pass+ xy zw return)))))

gdzie pass+, pass/ i pass* to CPS-owe odpowiedniki działań arytmetycznych,
a "return" to "nadrzędna kontynuacja" (np. koniec programu, albo
powrót do wywołującej funkcji). Słowo kluczowe "lambda" ma takie samo
znaczenie, jak w języku Scheme czy w lambda-rachunku, i podobne
jak "function" w JavaScripcie.

Program w takiej postaci można już dość łatwo przekształcić
do pseudo-asemblera:

xy := x * y
zw := z / w
result := xy + zw
return

albo czegoś w tym rodzaju. Dalszy etap nosi w literaturze nazwę
"register allocation" (i używa się do tego np. metod kolorowania
grafów), a chodzi w nim o to, żeby tym zmiennym przechowującym
wyniki pośrednie przypisać konkretne rejestry procesora (żeby zmniejszyć
liczbę dostępów do pamięci)

lista źródeł, na których się opieram, jest dostępna tutaj:

https://www.quora.com/How-do-people-develop-lisps/answer/Panicz-Godek