Pisanie kompilatora

kamcio1 · Dołączył: 14 Lip 2011 Posty: 113

Witam, czy zna ktoś jakiś dobry generator kompilatorów i wie jak go użyć?
Niecierpliwie czekam na informacje.

nwxxeh · Dołączył: 21 Kwi 2007 Posty: 763 Skąd: Nieocenzurowano

Generator kompilatorów? - Nie ma takiego...

Musisz sam napisać kompilator...

izaw · Dołączył: 12 Wrz 2008 Posty: 2003 Skąd: Łódź

Uważasz, że jesteś w stanie napisać jakiś sensowny, na pewno nie dobry, kompilator?

Muszę cię rozczarować. Nie masz umiejętności.

Zacznij od napisania parsera analizującego treść pliku tekstowego. Oczywiście możesz użycz gotowej biblioteki. Pomocą będzie wujek Google.

Hashedone · Dołączył: 23 Sie 2008 Posty: 853

Nie ma czegoś takiego jak generator kompilatora. Jednak wbrew temu co tu się mówi, wcale nie jest to aż taka trudna sprawa. W najprostszej sytuacji potrzebujesz trzech rzeczy: lekser, parser i generator bytekodu (czy nawet kodu maszynowego). Leksery i parsery można pisać na różne sposoby: dość staromodny to lex/flex + yacc/bison (są z tym pewne problemy niestety, szczególnie na windowsie), które tłumaczą kod w specjalnym języku na kod C/C++. Są nowoczesne odpowiedniki, np ANT* (pod * kryje się ciąg znaków którego nie pamiętam) - ten generuje domyślnie kod Java, ale również można go zmusić do generowania C++. Można też użyć po prostu biblioteki do tego przeznaczonej - w C++ może to być boost::spirit.
Pozostaje kwestia generowania bytecodu. Dawniej potrzeba było faktycznie tłumaczyć na kod assembly i przepuścić wszystko jeszcze przez assembler. Dzisiaj są już takie narzędzia jak LLVM - mają wygodny interfejs do pisania generatorów kodu. Do tego dostarcza narzędzia do pisania JITów, debuggerów i masy innych rzeczy. Polecam wygooglować.
===EDIT===
Dostałem olśnienia. ANT* = ANTLR

izaw · Dołączył: 12 Wrz 2008 Posty: 2003 Skąd: Łódź

Niby tak. Tylko to będzie bardzo ułomne. Optymalizacje dokonywane przez współczesne kompilatory przerastają możliwości przeciętnego kodera, nie mówiąc o początkującym. Zatem tak, ale jako ćwiczenie.

BTW. Sam napisałem kompilator i interpreter dla... Brainfuck'a.

Hashedone · Dołączył: 23 Sie 2008 Posty: 853

O jakiej optymalizacji ty mówisz? Wiesz co to jest LLVM? Generator i kompilator kodu SSA. Optymalizacje na kodzie HLL są zwykle minimalne i trywialne. Wszystkie ważne optymalizacje dzisiejsze kompilatory wykonują na poziomie kodu SSA (lub innego niskopoziomowego). LLVM daje nam out of the box między innymi redukcję nieużywanych zmiennych, optymalizację rekursji ogonowej, rozwiązywanie pętli, inlining funkcji, redukcja powtarzającego się kodu, oraz masę innych, mniej typowych optymalizacji. Do tego możliwość w prosty sposób tworzenia własnych "optimization passów" właściwych dla bardzo konkretnego języka. Jeśli pisanie kompilatora pociągało by za sobą każdorazową implementację takich podstawowych a jednocześnie bardzo trudnych rzeczy, języki nie powstawały by w takim tempie. A napisać interpreter dla brainfucka rozgarnięty średniopoczątkujący programista powinien w przeciągu <30min (bo w przypadku takiego języka jakiekolwiek optymalizacje to rzecz nadmiarowa).

kamcio1 · Dołączył: 14 Lip 2011 Posty: 113

Cieszę się, że wyrażacie swoje opinie, ale, bardziej interesuje mnie, jak napisać kompilator. Znalazłem co prawda, trochę na ten temat, ale pomijając, że po angielsku, to wyglądało to na trochę... skomplikowane. Myślę, że użytkownik Hashedone powinien jeszcze coś napisać.

Hashedone · Dołączył: 23 Sie 2008 Posty: 853

Ale co? Chętnie odpowiem na pytania na ile wiem, być może rzucę linkiem. Pisanie kompilatora to po prostu pisanie programu który tłumaczy jeden język formalny na inny. Tym innym zwykle jest język assembly, lub dowolny IR który łatwo się na Assembly tłumaczy. Jeśli wybierzemy sobie jako cel Assembly, to faktycznie trzeba samemu napisać masę rzeczy, choćby optymalizacje (o ile constant propagation można sobie napisać dość łatwo, o tyle optymalizacja rekursji ogonowej, albo analiza martwgo kodu to zadania nietrywialne). Możesz też znaleźć sobie jakiś wygodny IR, np. GENERIC/GIMPLE (IR gcc), albo co ja zaproponowałem IR llvm. To drugie jest o tyle wygodniejsze, że llvm dostarcza potężną bibliotekę masakrycznie ułatwiającą generowanie kodu (IRBuilder <> załatwia prawie wszystko, przede wszystkim łatwe wstawianie branch'ów, całkowicie pozwala ominąć ręczne wstawianie węzłów phi), do tego jest spora baza materiałów na stronie llvm. Polecam zajrzeć, a najlepiej przyjżeć się tutorialowi pokazującemu pisanie kompletnego języka: http://llvm.org/docs/tutorial/
Przy czym jeśli w ten sposób pisać lexery/parsery, to można się faktycznie pochlastać, zanim to będzie działało (a jeszcze bardziej jak będzie się chciało dodać nową składnię). O pisaniu parserów powstało już sporo tekstów - do googlowania hasła lex/flex, yacc/bison, ANTLR, boost::spirit, no i oczywiście bardziej podstawowe - trza poczytać o językach formalnych, gramatykach bezkontekstowych.

===EDIT===
Żeby nie było że twierdzę, że pisanie kompilatora to rzecz trywialna, bo to faktycznie by była herezja. Dochodzą takie rzeczy jak obsługa typów (jeśli język jest statycznie typowany to pół biedy, ale i tak nic oczywistego - szczególnie jeśli chcemy implementować polimorfizm czy to w sensie OOP jak w Javie/C++, czy funkcyjnym jak w OCamlu), rozwiązywanie problemu kolizji nazw, rozłącznej kompilacji, trzeba napisać jakąś bibliotekę standardową, trzeba zrobić coś z wyjątkami lecącymi z procesora/systemu (choćby dzielenie przez 0, Ctrl + C), ogólnie dostarczyć mechanizm obsługi błędów, żeby język był dzisiaj użyteczny to do tego jakaś forma callbacków/delegatów (czy to w formie wskaźników na funkcję, czy traktowania funkcji jako normalny typ), pewnie jakaś forma przeładowania/definiowania operatorów (chyba że ktoś uważa, że fajnie wygląda kod w Javie, jeśli np. używamy biblioteki do obliczeń naukowych i musimy wykonać sporo działań matematycznych na niej) i masa innych problemów, które aktualnie mi nie przychodzą do głowy. Jednak jeśli ktoś już na poważnie myśli o stworzeniu języka programowania, to myślę że część, jeśli nie wiekszość z nich jest w stanie ogarnąć przede wszystkim czytając jak to robią inni.

lethern · Dołączył: 09 Paź 2007 Posty: 729 Skąd: Bstok/Lublin

Są generatory parserów, poczytaj o tym na Wikipedii to może się odnajdziesz z tym (+są linki)

usercontrol · Dołączył: 05 Lip 2005 Posty: 2077 Skąd: Poznań

Aho Alfred V., Sethi Ravi, Ullman Jeffrey D. "Kompilatory. Reguły, metody i narzędzia", WNT.