Jak mogę stworzyć własny język programowania i kompilator dla niego [zamknięte]

Jestem dogłębnie programowany i poznałem języki, w tym BASIC, FORTRAN, COBOL, LISP, LOGO, Java, C ++, C, MATLAB, Mathematica, Python, Ruby, Perl, JavaScript, asembler i tak dalej. Nie rozumiem, jak ludzie tworzą języki programowania i opracowują dla nich kompilatory. Nie mogłem również zrozumieć, w jaki sposób ludzie tworzą systemy operacyjne takie jak Windows, Mac, UNIX, DOS i tak dalej. Inną tajemniczą rzeczą dla mnie jest to, jak ludzie tworzą biblioteki takie jak OpenGL, OpenCL, OpenCV, Cocoa, MFC i tak dalej. Ostatnią rzeczą, której nie jestem w stanie zrozumieć, jest sposób, w jaki naukowcy opracowują język asemblera i asemblera dla mikroprocesora. Naprawdę chciałbym nauczyć się tych wszystkich rzeczy i mam 15 lat. Zawsze chciałem być informatykiem, takim jak Babbage, Turing, Shannon lub Dennis Ritchie.

Przeczytałem już książkę Aho Compiler Design i koncepcję Tanenbauma dotyczącą systemu operacyjnego i wszystkie one omawiają tylko koncepcje i kod na wysokim poziomie. Nie zagłębiają się w szczegóły i niuanse oraz jak opracować kompilator lub system operacyjny. Chcę konkretnego zrozumienia, abym mógł sam je stworzyć, a nie tylko zrozumienia, czym jest nić, semafor, proces lub analiza. Zapytałem o to brata. Jest studentem SB w EECS na MIT i nie ma pojęcia, jak stworzyć te wszystkie rzeczy w prawdziwym świecie. Wszystko, co wie, to tylko zrozumienie koncepcji kompilatora i koncepcji systemu operacyjnego, takich jak te, o których wspominaliście (np. Wątek, synchronizacja, współbieżność, zarządzanie pamięcią, analiza leksykalna, generowanie kodu pośredniego i tak dalej)

Zasadniczo twoje pytanie brzmi: „w jaki sposób układy komputerowe, zestawy instrukcji, systemy operacyjne, języki, biblioteki i aplikacje są projektowane i wdrażane?” To wielomiliardowy światowy przemysł zatrudniający miliony ludzi, z których wielu to specjaliści. Być może zechcesz bardziej skoncentrować swoje pytanie.

To powiedziawszy, mogę zrobić crack:

Nie rozumiem, jak ludzie tworzą języki programowania i opracowują dla nich kompilatory.

To mnie zaskakuje, ale wiele osób uważa języki programowania za magiczne. Kiedy spotykam ludzi na przyjęciach, czy coś w tym stylu, jeśli pytają mnie, co robię, mówię im, że projektuję języki programowania oraz wdrażam kompilatory i narzędzia. Zaskakujące jest to, ile razy ludzie - profesjonalni programiści, pamiętajcie - mówią „wow, nigdy o tym nie myślałem, ale tak, ktoś musi to zaprojektować”. To tak, jak myśleli, że języki powstają już w całości uformowane wraz z infrastrukturą narzędziową wokół nich.

Nie tylko się pojawiają. Języki są projektowane jak każdy inny produkt: poprzez ostrożne dokonywanie szeregu kompromisów wśród konkurencyjnych możliwości. Kompilatory i narzędzia są zbudowane jak każdy inny profesjonalny produkt programowy: poprzez rozwiązywanie problemu, pisanie jednego wiersza kodu na raz, a następnie testowanie programu wynikowego.

Projektowanie języka to ogromny temat. Jeśli interesuje Cię projektowanie języka, dobrym miejscem na początek jest zastanowienie się, jakie są braki w języku, który już znasz. Decyzje projektowe często wynikają z rozważenia wady projektowej innego produktu.

Możesz też rozważyć domenę, która Cię interesuje, a następnie zaprojektować język specyficzny dla domeny (DSL), który określa rozwiązania problemów w tej domenie. Wspomniałeś o LOGO; to świetny przykład DSL dla domeny „rysowania linii”. Wyrażenia regularne to DSL dla domeny „znajdź wzorzec w ciągu”. LINQ w C # / VB to DSL dla domeny „filtruj, łącz, sortuj i projektuj dane”. HTML to DSL dla domeny „opisz układ tekstu na stronie” i tak dalej. Istnieje wiele domen, które są podatne na rozwiązania oparte na języku. Jednym z moich ulubionych jest Inform7, który jest DSL dla domeny „tekstowej gry przygodowej”; jest to prawdopodobnie najwyższy poziom poważnego języka programowania, jaki kiedykolwiek widziałem.

Kiedy już naszkicujesz, jak ma wyglądać Twój język, spróbuj dokładnie zapisać, jakie są zasady określania, który program jest legalny i nielegalny. Zazwyczaj będziesz chciał to zrobić na trzech poziomach:

1. leksykalne : jakie są reguły dla słów w języku, jakie znaki są legalne, jak wyglądają liczby i tak dalej.
2. składniowy : jak słowa danego języka łączą się w większe jednostki? W języku C # większe jednostki to takie wyrażenia, instrukcje, metody, klasy i tak dalej.
3. semantyczny : jak rozumiesz, co robi program, biorąc pod uwagę składniowo zgodny program ?

Zapisz te zasady tak dokładnie, jak to możliwe . Jeśli wykonasz dobrą robotę, możesz użyć tego jako podstawy do napisania kompilatora lub interpretera. Spójrz na specyfikację C # lub specyfikację ECMAScript, aby zobaczyć, co mam na myśli; są pełne bardzo precyzyjnych zasad opisujących, co tworzy legalny program i jak dowiedzieć się, co się robi.

Jednym z najlepszych sposobów na rozpoczęcie pisania kompilatora jest napisanie kompilatora wysokiego poziomu na język wysokiego poziomu . Napisz kompilator, który pobiera łańcuchy w twoim języku i wyrzuca łańcuchy w języku C # lub JavaScript lub innym języku, który znasz; pozwól kompilatorowi dla tego języka zająć się ciężkim przekształcaniem go w kod wykonywalny.

Piszę blog na temat projektowania C #, VB, VBScript, JavaScript oraz innych języków i narzędzi; jeśli ten temat Cię interesuje, sprawdź to. http://blogs.msdn.com/ericlippert (historyczny) i http://ericlippert.com (bieżący)

W szczególności ten post może Cię zainteresować; tutaj wymienię większość zadań, które kompilator C # wykonuje dla Ciebie podczas analizy semantycznej. Jak widać, jest wiele kroków. Wielki problem analizy dzielimy na szereg problemów, które możemy rozwiązać indywidualnie.

http://blogs.msdn.com/b/ericlippert/archive/2010/02/04/how-many-passes.aspx

Wreszcie, jeśli szukasz pracy wykonującej te rzeczy, gdy jesteś starszy, zastanów się, czy nie pójść do Microsoftu jako stażysta w college'u i spróbować dostać się do działu programistów. Tak skończyłem dzisiaj swoją pracę!

Można znaleźć Pozwala zbudować kompilator Jack Crenshaw ciekawy wstęp do pisania kompilatorów i asemblerze.

Autor utrzymał to bardzo proste i skoncentrował się na budowaniu rzeczywistej funkcjonalności.

„ Naprawdę chciałbym się tego nauczyć”. Jeśli jesteś poważny długoterminowo:

• Idź na studia, specjalizuj się w inżynierii oprogramowania. Weź każdą klasę kompilatora, którą możesz zdobyć. Osoby prowadzące zajęcia są lepiej wykształcone i mają większe doświadczenie niż ty; dobrze jest wykorzystać ich perspektywy ekspertów do prezentacji informacji w sposób, którego nigdy nie uzyskasz podczas czytania kodu.

• Trzymaj się lekcji matematyki przez liceum i kontynuuj naukę przez wszystkie 4 lata. Skoncentruj się na niestandardowej matematyce: logice, teorii grup, meta-matematyce. Zmusi cię to do abstrakcyjnego myślenia. Umożliwi ci przeczytanie zaawansowanych prac teoretycznych na temat kompilacji i zrozumienie, dlaczego te teorie są interesujące i przydatne. Możesz zignorować te zaawansowane teorie, jeśli na zawsze chcesz pozostać w tyle za najnowszymi osiągnięciami.

• Zbierz / przeczytaj standardowe teksty kompilatora: Aho / Ullman itp. Zawierają one to, co społeczność ogólnie uznaje za fundamentalne. Możesz nie używać wszystkiego z tych książek, ale powinieneś wiedzieć, że istnieje i powinieneś wiedzieć, dlaczego go nie używasz. Myślałem, że Muchnick był świetny, ale dotyczy to dość zaawansowanych tematów.

• Zbuduj kompilator. Zacznij TERAZ, budując zgniłe. To nauczy Cię niektórych problemów. Zbuduj drugi. Powtarzać. To doświadczenie buduje ogromną synergię z nauką książek.

• Naprawdę dobrym miejscem do rozpoczęcia jest poznanie BNF (Backus Naur Form), parserów i generatorów parserów. BNF jest skutecznie uniwersalnie wykorzystywany na obszarach kompilatora i nie możesz realistycznie rozmawiać z innymi typami kompilatorów, jeśli go nie znasz.

Jeśli chcesz mieć świetne pierwsze wprowadzenie do kompilacji, a bezpośrednią wartość BNF nie tylko dla dokumentacji, ale jako języka metalicznego przetwarzanego przez narzędzie, zobacz ten samouczek (nie mój) na temat budowania kompilatorów „meta” (kompilatory budujące kompilatory) na podstawie artykuł z 1964 r. (tak, dobrze przeczytałeś) [„META II - język pisania kompilatora zorientowany na składnię” Val Schorre. (http://doi.acm.org/10.1145/800257.808896)] Ten IMHO jest jednym z najlepszych opracowań na temat comp-sci, jakie kiedykolwiek napisano: uczy budowania kompilatorów na 10 stronach. Nauczyłem się początkowo z tego artykułu.

To, o czym pisałem powyżej, pochodzi z własnego doświadczenia i myślę, że całkiem mi to pomogło. YMMV, ale IMHO, niewiele.

Oto książka / kurs online, który możesz śledzić zatytułowany The Elements of Computing Systems: Building Modern Computer from First Principles .

Za pomocą symulatorów budujesz kompletny system komputerowy od podstaw. Chociaż wielu komentujących stwierdziło, że twoje pytanie jest zbyt ogólne, ta książka faktycznie na nie odpowiada, pozostając bardzo wykonalnym. Kiedy skończysz, będziesz pisać grę w języku wysokiego poziomu (który zaprojektowałeś), który wykorzystuje funkcjonalność twojego własnego systemu operacyjnego, który zostaje skompilowany w języku VM (zaprojektowanym przez ciebie) przez kompilator, który dostaje przetłumaczone na język asemblera (który zaprojektowałeś) przez twojego tłumacza VM, który zostaje skompilowany w kod maszynowy (który zaprojektowałeś) przez asembler, który działa na twoim systemie komputerowym, który składasz z układów zaprojektowanych za pomocą logiki logicznej i prosty język opisu sprzętu.

Rozdziały:

1. Przegląd kursu
2. Logika logiczna
3. Chipy kombinatoryczne
4. Sekwencyjne żetony
5. Język maszyny
6. Architektura komputerowa
7. Monter
8. Maszyna wirtualna I: arytmetyka
9. Virtual Machine II: Control
10. Język programowania
11. Kompilator I: Analiza składni
12. Kompilator II: Generowanie kodu
13. System operacyjny
14. Element listy

Więcej radości z podróży

Zrób krok wstecz. Kompilator to po prostu program, który tłumaczy dokument z jednego języka na dokument w innym języku. Oba języki powinny być dobrze zdefiniowane i specyficzne.

Języki nie muszą być językami programowania. Mogą być dowolnym językiem, którego reguły można zapisać. Prawdopodobnie widziałeś Tłumacza Google ; jest to kompilator, ponieważ może tłumaczyć jeden język (powiedzmy niemiecki) na inny (być może japoński).

Innym przykładem kompilatora jest silnik renderujący HTML. Jego dane wejściowe to plik HTML, a dane wyjściowe to seria instrukcji narysowania pikseli na ekranie.

Kiedy większość ludzi mówi o kompilatorze, zwykle ma na myśli program, który tłumaczy język programowania wysokiego poziomu (taki jak Java, C, Prolog) na język niskiego poziomu (asembler lub kod maszynowy). To może być zniechęcające. Ale nie jest tak źle, gdy spojrzysz na pogląd ogólny, że kompilator to program, który tłumaczy jeden język na inny.

Czy potrafisz napisać program, który odwraca każde słowo w ciągu? Na przykład:

When the cat's away, the mice will play.

staje się

nehW eht s'tac yawa, eht ecim lliw yalp.

To nie jest trudny program do napisania, ale musisz pomyśleć o kilku rzeczach:

• Co to jest „słowo”? Czy potrafisz zdefiniować, które znaki składają się na słowo?
• Gdzie zaczynają się i kończą słowa?
• Czy słowa są oddzielone tylko jedną spacją, czy może być ich więcej lub mniej?
• Czy interpunkcja również musi zostać odwrócona?
• Co z interpunkcją wewnątrz słowa?
• Co dzieje się z dużymi literami?

Odpowiedzi na te pytania pomagają dobrze zdefiniować język. Teraz napisz program. Gratulacje, właśnie napisałeś kompilator.

Co powiesz na to: czy możesz napisać program, który pobiera serię instrukcji rysowania i generuje plik PNG (lub JPEG)? Może coś takiego:

image 100 100
background black
color red
line 20 55 93 105
color green
box 0 0 99 99

Ponownie musisz przemyśleć, aby zdefiniować język:

• Jakie są podstawowe instrukcje?
• Co następuje po słowie „linia”? Co następuje po „kolorze”? Podobnie dla „tła”, „pudełka” itp.
• Co to jest liczba?
• Czy dozwolony jest pusty plik wejściowy?
• Czy wpisywanie słów jest w porządku?
• Czy dozwolone są liczby ujemne?
• Co się stanie, jeśli nie podasz dyrektywy „image”?
• Czy nie można określić koloru?

Oczywiście jest więcej pytań, na które należy odpowiedzieć, ale jeśli potrafisz je dopracować, zdefiniowałeś język. Program, który piszesz, aby wykonać tłumaczenie jest, jak się domyślacie, kompilatorem.

Widzisz, napisanie kompilatora nie jest takie trudne. Kompilatory używane w Javie lub C są tylko większymi wersjami tych dwóch przykładów. Więc idź na całość! Zdefiniuj prosty język i napisz program, aby ten język coś zrobił. Wcześniej czy później będziesz chciał rozszerzyć swój język. Na przykład możesz chcieć dodać zmienne lub wyrażenia arytmetyczne. Twój kompilator stanie się bardziej złożony, ale zrozumiesz wszystko, ponieważ sam to napisałeś. Tak powstają języki i kompilatory.

Jeśli interesuje Cię projektowanie kompilatora, sprawdź Dragon Book (oficjalny tytuł: Compilers: Principles, Techniques and Tools). Jest powszechnie uważany za klasyczną książkę na ten temat.

„Zbudujmy kompilator” zostało już zasugerowane. Istnieje „zmodernizowana” wersja wykorzystująca Haskell zamiast Turbo Pascal: http://alephnullplex.appspot.com/blog/view/2010/01/12/lbach-1-introduction

Trzymając się Haskella, istnieje bardzo pouczający tłumacz, który może podać dalsze pomysły: Napisz sam schemat w 48 godzin

Nie wierz, że w kompilatorze lub systemie operacyjnym jest coś magicznego: nie ma. Pamiętasz programy, które napisałeś, aby policzyć wszystkie samogłoski w ciągu lub dodać liczby do tablicy? Kompilator nie różni się pod względem koncepcji; jest po prostu o wiele większy.

Każdy program ma trzy fazy:

1. poczytaj trochę
2. przetwarzaj te rzeczy: przetłumacz dane wejściowe na dane wyjściowe
3. napisz kilka innych rzeczy - dane wyjściowe

Pomyśl o tym: co jest wprowadzane do kompilatora? Ciąg znaków z pliku źródłowego.

Co jest generowane przez kompilator? Ciąg bajtów reprezentujących instrukcje komputera dla komputera docelowego.

Jaka jest więc faza „kompilacji” kompilatora? Co robi ta faza?

Jeśli weźmiesz pod uwagę, że kompilator - jak każdy inny program - musi uwzględniać te trzy fazy, będziesz miał dobry pomysł na to, jak zbudowany jest kompilator.

Nie jestem ekspertem, ale oto moje dźgnięcie:

Wydaje się, że nie pytasz o napisanie kompilatora, asembler. To nie jest naprawdę magia.

Kradnąc komuś odpowiedź z SO ( https://stackoverflow.com/questions/3826692/how-do-i-translate-assembly-to-binary ), asembler wygląda następująco:

label:  LDA #$00
        JMP label

Następnie uruchom go przez asembler i zamień w coś takiego:

$A9 $00
$4C $10 $00

Tylko wszystko jest zgniecione, tak:

$A9 $00 $4C $10 $00

To naprawdę nie jest magia.

Nie można tego zapisać w Notatniku, ponieważ Notatnik używa ASCII (nie hex). Używałbyś edytora szesnastkowego lub po prostu zapisywałeś bajty programowo. Zapisujesz ten hex w pliku, nadaj mu nazwę „a.exe” lub „a.out”, a następnie powiedz systemowi operacyjnemu, aby go uruchomił.

Oczywiście nowoczesne procesory i systemy operacyjne są naprawdę dość skomplikowane, ale to podstawowa idea.

Jeśli chcesz napisać nowy kompilator, oto jak to zrobić:

1) Napisz interpretowany język, używając czegoś takiego jak przykład kalkulatora w parsowaniu (lub innym dobrym frameworku). To przyspieszy podstawową analizę.

2) Napisz tłumacza. Przetłumacz swój język, powiedzmy, JavaScript. Teraz Twój język będzie działał w przeglądarce.

3) Napisz tłumacza na coś niższego poziomu, na przykład LLVM, C lub Assembly.

Możesz zatrzymać się tutaj, to jest kompilator. To nie jest kompilator optymalizujący, ale nie o to chodziło. Być może będziesz musiał rozważyć napisanie linkera i asemblera, ale czy naprawdę tego chcesz?

4) (Szalony) Napisz optymalizator. Duże zespoły pracują nad tym od dziesięcioleci.

4) (Sane) Zaangażuj się w istniejącą społeczność. GCC, LLVM, PyPy, podstawowy zespół pracujący na dowolnym tłumaczu.

Kilka innych udzieliło doskonałych odpowiedzi. Dodam jeszcze kilka sugestii. Po pierwsze, dobrą książką do tego, co próbujesz zrobić, jest tekst Appel's Modern Compiler Implementation (wybierz C , Java lub Standard ML ). Ta książka poprowadzi cię przez pełną implementację kompilatora prostego języka Tiger do zestawu MIPS, który można uruchomić w emulatorze, wraz z minimalną biblioteką wsparcia środowiska wykonawczego. Dla jednego przejścia przez wszystko, co niezbędne, aby skompilowany język działał, jest to całkiem niezła książka ¹ .

Appel przeprowadzi Cię przez proces kompilacji języka, który jest wstępnie zaprojektowany, ale nie poświęca wiele czasu na to, co oznaczają różne cechy języka ani jak o nich myśleć w kategoriach ich względnych zalet w zakresie projektowania własnego. Pod tym względem języki programowania: koncepcje i konstrukcje są przyzwoite. Pojęcia, techniki i modele programowania komputerowego to także dobra książka do głębokiego myślenia o projektowaniu języka, chociaż dzieje się tak w kontekście jednego języka ( Oz ).

Na koniec wspomniałem, że Appel ma swój tekst w języku C, Java i Standard ML - jeśli poważnie myślisz o budowie kompilatora i językach programowania, zalecam naukę ML i używanie tej wersji Appela. Języki rodziny ML mają silne systemy typów, które są głównie funkcjonalne - funkcje, które będą się różnić od wielu innych języków, więc nauka ich, jeśli jeszcze nie znasz języka funkcjonalnego, poprawi twoje umiejętności językowe. Ponadto ich nastawienie do wzorców i funkcjonalne sposoby myślenia są wyjątkowo dobrze dostosowane do rodzajów manipulacji, które należy często wykonywać w kompilatorze, więc kompilatory napisane w językach opartych na języku ML są zazwyczaj znacznie krótsze i łatwiejsze do zrozumienia niż kompilatory napisane w języku C, Java lub podobne języki. Książka Harperana Standard ML jest całkiem dobrym przewodnikiem na dobry początek; praca nad tym powinna przygotować cię do przyjęcia książki implementacyjnej Standardowego kompilatora ML Appela. Jeśli nauczysz się Standard ML, to będzie bardzo łatwo podnieść OCaml do późniejszej pracy; IMO ma lepsze oprzyrządowanie dla działającego programisty (integruje się bardziej czysto z otaczającym środowiskiem systemu operacyjnego, łatwo tworzy programy wykonywalne i ma spektakularne narzędzia do budowania kompilatora, takie jak ulex i Menhir).

¹ Na dłuższą metę wolę Dragon Book, ponieważ zawiera ona więcej szczegółów na temat rzeczy, o których prawdopodobnie będę się odnosił, takich jak wewnętrzne działanie algorytmów parsera i ma szerszy zakres różnych podejść, ale książka Appela jest bardzo dobra za pierwsze przejście. Zasadniczo Appel uczy jednego sposobu robienia rzeczy przez całą kompilator i prowadzi przez to. Dragon Book opisuje bardziej szczegółowo różne alternatywy projektowe, ale zapewnia znacznie mniej wskazówek, jak uzyskać coś w działaniu.

Edytowano : zamień niepoprawne odniesienie Aho na Sethi, wspomnij o CTMCP.

Musiałem stworzyć kompilator do zajęć na studiach.

Podstawy robienia tego nie są tak skomplikowane, jak mogłoby się wydawać. Pierwszym krokiem jest stworzenie gramatyki. Pomyśl o gramatyce języka angielskiego. W ten sam sposób możesz przeanalizować zdanie, jeśli zawiera ono temat i predykat. Aby uzyskać więcej informacji na ten temat, przeczytaj o gramatyce bezkontekstowej .

Gdy już opanujesz gramatykę (zasady swojego języka), napisanie kompilatora jest tak proste, jak tylko przestrzeganie tych reguł. Kompilatory zwykle tłumaczą się na kod maszynowy, ale jeśli nie chcesz nauczyć się x86, sugeruję przyjrzeć się MIPS lub stworzyć własną maszynę wirtualną.

Kompilatory zazwyczaj składają się z dwóch części, skanera i parsera. Zasadniczo skaner odczytuje kod i dzieli go na tokeny. Analizator składni analizuje strukturę tych tokenów. Następnie kompilator przechodzi przez kilka raczej prostych reguł, aby przekonwertować go na dowolny kod, w którym jest potrzebny (asembler, kod pośredni, taki jak kod bajtowy itp.). Jeśli podzielisz go na coraz mniejsze części, nie będzie to wcale zniechęcające.

Powodzenia!

Książka Petzolda Code to świetne wprowadzenie zarówno do nietechnicznych, jak i technicznych, zaczynając od pierwszych zasad. Jest bardzo czytelny i ma szeroki zasięg, bez zbytniego zagłębiania się.

Teraz, gdy to napisałem, będę musiał go ponownie przeczytać.

Możesz sprawdzić to doskonałe pytanie (i odpowiedzi) na StackOverflow: Nauka pisania kompilatora . Zawiera szeroką listę zasobów.

W tym wątku są doskonałe odpowiedzi, ale chciałem tylko dodać moje, ponieważ ja też kiedyś miałem to samo pytanie. (Chciałbym również zauważyć, że książka zaproponowana przez Joe-Internet jest doskonałym źródłem.)

Pierwsze pytanie dotyczy tego, jak działa komputer? Oto jak: Wejście -> Oblicz -> Wyjście.

Najpierw rozważ część „Obliczanie”. Przyjrzymy się później, jak działa wejście i wyjście.

Komputer zasadniczo składa się z procesora (lub procesora) i pewnej pamięci (lub pamięci RAM). Pamięć jest zbiorem lokalizacji, z których każda może przechowywać skończoną liczbę bitów, a do każdej takiej lokalizacji pamięci może odnosić się liczba, nazywa się to adresem lokalizacji pamięci. Procesor jest gadżetem, który może pobierać dane z pamięci wykonaj niektóre operacje na podstawie danych i zapisz niektóre dane z powrotem do pamięci. W jaki sposób procesor zastanawia się, co czytać i co robić po odczytaniu danych z pamięci?

Aby odpowiedzieć na to pytanie, musimy zrozumieć strukturę procesora. Poniżej znajduje się dość prosty widok. Procesor zasadniczo składa się z dwóch części. Jednym z nich jest zestaw lokalizacji pamięci wbudowanych w procesor, które służą jako pamięć robocza. Są to tak zwane „rejestry”. Drugi to kilka elektronicznych maszyn zbudowanych do wykonywania pewnych operacji z wykorzystaniem danych w rejestrach. Istnieją dwa specjalne rejestry zwane „Licznikiem programów” lub komputerem osobistym i „rejestrem instrukcji” lub ir. Procesor uważa pamięć za podzieloną na trzy części. Pierwsza część to „pamięć programu”, która przechowuje wykonywany program komputerowy. Drugi to „pamięć danych”. Trzeci służy do specjalnych celów, o czym porozmawiamy później. Licznik programów zawiera lokalizację następnej instrukcji do odczytania z pamięci programu. Licznik instrukcji Zawiera liczbę odnoszącą się do aktualnie wykonywanej operacji. Każda operacja, którą może wykonać procesor, jest oznaczona numerem zwanym opcode operacji. Komputer zasadniczo działa w ten sposób, że odczytuje lokalizację pamięci, do której odnosi się Licznik Programów, do Rejestru Instrukcji (i zwiększa Licznik Programów, tak aby wskazywał lokalizację pamięci następnej instrukcji). Następnie odczytuje Rejestr instrukcji i wykonuje żądaną operację. Na przykład instrukcja może polegać na wczytaniu określonej lokalizacji pamięci do rejestru lub zapisaniu w jakimś rejestrze lub wykonaniu pewnych operacji z wykorzystaniem wartości dwóch rejestrów i zapisaniu danych wyjściowych w trzecim rejestrze. Licznik instrukcji Zawiera liczbę odnoszącą się do aktualnie wykonywanej operacji. Każda operacja, którą może wykonać procesor, jest oznaczona numerem zwanym opcode operacji. Komputer zasadniczo działa w ten sposób, że odczytuje lokalizację pamięci, do której odnosi się Licznik Programów, do Rejestru Instrukcji (i zwiększa Licznik Programów, tak aby wskazywał lokalizację pamięci następnej instrukcji). Następnie odczytuje Rejestr instrukcji i wykonuje żądaną operację. Na przykład instrukcja może polegać na wczytaniu określonej lokalizacji pamięci do rejestru lub zapisaniu w jakimś rejestrze lub wykonaniu pewnych operacji z wykorzystaniem wartości dwóch rejestrów i zapisaniu danych wyjściowych w trzecim rejestrze. Licznik instrukcji Zawiera liczbę odnoszącą się do aktualnie wykonywanej operacji. Każda operacja, którą może wykonać procesor, jest oznaczona numerem zwanym opcode operacji. Komputer zasadniczo działa w ten sposób, że odczytuje lokalizację pamięci, do której odnosi się Licznik Programów, do Rejestru Instrukcji (i zwiększa Licznik Programów, tak aby wskazywał lokalizację pamięci następnej instrukcji). Następnie odczytuje Rejestr instrukcji i wykonuje żądaną operację. Na przykład instrukcja może polegać na wczytaniu określonej lokalizacji pamięci do rejestru lub zapisaniu w jakimś rejestrze lub wykonaniu pewnych operacji z wykorzystaniem wartości dwóch rejestrów i zapisaniu danych wyjściowych w trzecim rejestrze. Każda operacja, którą może wykonać procesor, jest oznaczona numerem zwanym opcode operacji. Komputer zasadniczo działa w ten sposób, że odczytuje lokalizację pamięci, do której odnosi się Licznik Programów, do Rejestru Instrukcji (i zwiększa Licznik Programów, tak aby wskazywał lokalizację pamięci następnej instrukcji). Następnie odczytuje Rejestr instrukcji i wykonuje żądaną operację. Na przykład instrukcja może polegać na wczytaniu określonej lokalizacji pamięci do rejestru lub zapisaniu w jakimś rejestrze lub wykonaniu pewnych operacji z wykorzystaniem wartości dwóch rejestrów i zapisaniu danych wyjściowych w trzecim rejestrze. Każda operacja, którą może wykonać procesor, jest oznaczona numerem zwanym opcode operacji. Komputer zasadniczo działa w ten sposób, że odczytuje lokalizację pamięci, do której odnosi się Licznik Programów, do Rejestru Instrukcji (i zwiększa Licznik Programów, tak aby wskazywał lokalizację pamięci następnej instrukcji). Następnie odczytuje Rejestr instrukcji i wykonuje żądaną operację. Na przykład instrukcja może polegać na wczytaniu określonej lokalizacji pamięci do rejestru lub zapisaniu w jakimś rejestrze lub wykonaniu pewnych operacji z wykorzystaniem wartości dwóch rejestrów i zapisaniu danych wyjściowych w trzecim rejestrze. Komputer zasadniczo działa w ten sposób, że odczytuje lokalizację pamięci, do której odnosi się Licznik Programów, do Rejestru Instrukcji (i zwiększa Licznik Programów, tak aby wskazywał lokalizację pamięci następnej instrukcji). Następnie odczytuje Rejestr instrukcji i wykonuje żądaną operację. Na przykład instrukcja może polegać na wczytaniu określonej lokalizacji pamięci do rejestru lub zapisaniu w jakimś rejestrze lub wykonaniu pewnych operacji z wykorzystaniem wartości dwóch rejestrów i zapisaniu danych wyjściowych w trzecim rejestrze. Komputer zasadniczo działa w ten sposób, że odczytuje lokalizację pamięci, do której odnosi się Licznik Programów, do Rejestru Instrukcji (i zwiększa Licznik Programów, tak aby wskazywał lokalizację pamięci następnej instrukcji). Następnie odczytuje Rejestr instrukcji i wykonuje żądaną operację. Na przykład instrukcja może polegać na wczytaniu określonej lokalizacji pamięci do rejestru lub zapisaniu w jakimś rejestrze lub wykonaniu pewnych operacji z wykorzystaniem wartości dwóch rejestrów i zapisaniu danych wyjściowych w trzecim rejestrze.

W jaki sposób komputer wykonuje operacje wejścia / wyjścia? Podam bardzo uproszczoną odpowiedź. Zobacz http://en.wikipedia.org/wiki/Input/output i http://en.wikipedia.org/wiki/Interrupt. po więcej. Wykorzystuje dwie rzeczy, trzecią część pamięci i coś o nazwie Przerwania. Każde urządzenie podłączone do komputera musi mieć możliwość wymiany danych z procesorem. Robi to przy użyciu trzeciej części pamięci wspomnianej wcześniej. Procesor przydziela plasterek pamięci każdemu urządzeniu, a urządzenie i procesor komunikują się za pośrednictwem tego segmentu pamięci. Ale skąd procesor wie, która lokalizacja odnosi się do jakiego urządzenia i kiedy urządzenie musi wymieniać dane? W tym momencie przychodzą przerwania. Przerwanie jest zasadniczo sygnałem dla procesora, aby wstrzymać to, co aktualnie jest i zapisać wszystkie swoje rejestry w znanej lokalizacji, a następnie zacząć robić coś innego. Istnieje wiele przerwań, z których każdy jest oznaczony unikalnym numerem. Dla każdego przerwania jest powiązany z nim specjalny program. Kiedy nastąpi przerwanie, procesor wykonuje program odpowiadający przerwaniu. Teraz, w zależności od systemu BIOS i tego, jak urządzenia sprzętowe są podłączone do płyty głównej komputera, każde urządzenie otrzymuje unikalne przerwanie i kawałek pamięci. Podczas uruchamiania systemu operacyjnego za pomocą biosu określa przerwanie i lokalizację pamięci każdego urządzenia oraz konfiguruje specjalne programy do przerwania, aby poprawnie obsługiwać urządzenia. Kiedy więc urządzenie potrzebuje danych lub chce je przesłać, sygnalizuje przerwanie. Procesor wstrzymuje to, co robi, obsługuje przerwanie, a następnie wraca do tego, co robi. Istnieje wiele rodzajów przerwań, takich jak dysk twardy, klawiatura itp. Ważnym jest timer systemowy, który wywołuje przerwanie w regularnych odstępach czasu. Istnieją również kody, które mogą wyzwalać przerwania, zwane przerwaniami programowymi.

Teraz możemy prawie zrozumieć, jak działa system operacyjny. Podczas rozruchu system operacyjny ustawia przerwanie timera, dzięki czemu kontroluje system operacyjny w regularnych odstępach czasu. Konfiguruje także inne przerwania do obsługi innych urządzeń itp. Teraz, gdy komputer uruchamia kilka programów, a przerwanie timera się zdarza, uzyskuje kontrolę i wykonuje ważne zadania, takie jak zarządzanie procesem, zarządzanie pamięcią itp. Również system operacyjny zwykle zapewnia abstrakcyjny sposób dostępu programów do urządzeń, zamiast pozwalać im na bezpośredni dostęp do urządzeń. Gdy program chce uzyskać dostęp do urządzenia, wywołuje kod dostarczony przez system operacyjny, który następnie komunikuje się z urządzeniem. Istnieje wiele teorii, które dotyczą współbieżności, wątków, blokad, zarządzania pamięcią itp.

Teraz teoretycznie można napisać program bezpośrednio za pomocą opcodes. To się nazywa kod maszynowy. To jest oczywiście bardzo bolesne. Teraz język asemblera dla procesora to nic innego jak mnemonika dla tych kodów, co ułatwia pisanie programów. Prosty asembler to program, który pobiera program napisany w asemblerze i zastępuje mnemoniki odpowiednimi kodami operacyjnymi.

Jak przejść do projektowania procesora i języka asemblera. Aby wiedzieć, że musisz przeczytać kilka książek na temat architektury komputera. (patrz rozdziały 1-7 książki, do których odnosi się joe-internet). Obejmuje to naukę o algebrze boolowskiej, jak budować proste układy kombinatoryczne w celu dodawania, mnożenia itp., Jak budować pamięć i układy sekwencyjne, jak budować mikroprocesor i tak dalej.

Jak teraz pisze się komputerowe języki. Można zacząć od napisania prostego asemblera w kodzie maszynowym. Następnie użyj tego asemblera do napisania kompilatora dla prostego podzbioru C. Następnie użyj tego podzbioru C do napisania bardziej kompletnej wersji C. Na koniec użyj C do napisania bardziej skomplikowanego języka, takiego jak python lub C ++. Oczywiście, aby napisać język, musisz go najpierw zaprojektować (w taki sam sposób jak procesor). Ponownie spójrz na kilka podręczników na ten temat.

I jak napisać OS. Najpierw celujesz w platformę taką jak x86. Następnie wymyślisz, jak to się uruchamia i kiedy zostanie przywołana twoja OS. Typowy komputer startuje w ten sposób. Uruchamia się i bios wykonuje pewne testy. Następnie bios odczytuje pierwszy sektor dysku twardego i ładuje zawartość do określonego miejsca w pamięci. Następnie konfiguruje procesor, aby rozpocząć wykonywanie załadowanych danych. To jest punkt, w którym zostajesz przywołany. Typowy system operacyjny w tym momencie ładuje resztę pamięci. Następnie inicjuje urządzenia i konfiguruje inne rzeczy, a na koniec wita Cię ekranem logowania.

Aby napisać system operacyjny, musisz napisać „boot-loader”. Następnie musisz napisać kod do obsługi przerwań i urządzeń. Następnie musisz napisać cały kod do zarządzania procesami, zarządzania urządzeniami itp. Następnie musisz napisać interfejs API, który pozwala programom działającym w twoim systemie operacyjnym na dostęp do urządzeń i innych zasobów. Na koniec musisz napisać kod, który odczytuje program z dysku, ustawia go jako proces i zaczyna go uruchamiać.

Oczywiście moja odpowiedź jest zdecydowanie uproszczona i prawdopodobnie mało praktyczna. W mojej obronie jestem teraz absolwentem teorii, więc zapomniałem wiele z tych rzeczy. Ale możesz znaleźć w Google wiele takich rzeczy i dowiedzieć się więcej.

Pamiętam pewien moment w mojej karierze programistycznej, kiedy byłem w stanie pomieszania z twoim: sporo czytałem o teorii, książce Smoka, książce Tygrysa (czerwona), ale wciąż nie miałem zbyt wiele wskazówka, jak to wszystko połączyć.

Tym, co go łączyło, było znalezienie konkretnego projektu do wykonania (a następnie odkrycie, że potrzebowałem tylko niewielkiego podzbioru całej teorii).

Java VM zapewniła mi dobry punkt wyjścia: jest koncepcyjnie „procesorem”, ale jest bardzo abstrakcyjna od niechlujnych szczegółów rzeczywistych procesorów. Zapewnia również ważną i często pomijaną część procesu uczenia się: rozbierać rzeczy na części przed ponownym ich złożeniem (tak jak dzieci w dawnych czasach korzystały z odbiorników radiowych).

Graj z dekompilatorem i Hello, światowej klasy w Javie. Przeczytaj specyfikację JVM i spróbuj zrozumieć, co się dzieje. To da ci gruntowny wgląd w to, co robi kompilator .

Następnie baw się z kodem, który tworzy klasę Hello, World. (W efekcie tworzysz kompilator specyficzny dla aplikacji, dla wysoce wyspecjalizowanego języka, w którym możesz tylko powiedzieć Hello, World.)

Spróbuj napisać kod, który będzie w stanie odczytać w Hello, World napisany w innym języku i wypisać tę samą klasę. Zrób to, abyś mógł zmienić ciąg znaków z „Hello, World” na coś innego.

Teraz spróbuj skompilować (w Javie) klasę obliczającą pewne wyrażenie arytmetyczne, takie jak „2 * (3 + 4)”. Rozłóż tę klasę na części, napisz „kompilator zabawek”, który może ją ponownie złożyć.

1) Świetne wykłady wideo z University of Washington:

Budowa kompilatora CSE P 501 - jesień 2009 www.cs.washington.edu/education/courses/csep501/09au/lectures/video.html *

2) SICP http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/ I książka o tej samej nazwie. Jest to faktycznie obowiązkowe dla każdego inżyniera oprogramowania.

3) Także o programowaniu funkcjonalnym, rachunku Haskella, rachunku lambda, semantyce (w tym denotacyjnej) i implementacji kompilatora dla języków funkcjonalnych. Możesz zacząć od 2005-SS-FP.V10.2005-05-24.HDV, jeśli już znasz Haskell. Filmy Uxx są odpowiedziami. Najpierw postępuj zgodnie z filmami Vxx .

http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung

(filmy są w języku angielskim, inne kursy są w języku niemieckim.)

• nowi użytkownicy mogą publikować maksymalnie dwa hiperłącza.

ANTLR jest dobrym punktem wyjścia. Jest to framework do generowania języka, podobny do Lexa i Yacca. Istnieje GUI o nazwie ANTLRWorks, które upraszcza proces.

W świecie .NET istnieje środowisko uruchomieniowe języka dynamicznego, którego można używać do generowania kodu w świecie .NET. Napisałem język wyrażeń o nazwie Zentrum, który generuje kod za pomocą DLR. Pokaże ci, jak parsować i wykonywać wyrażenia o typie statycznym i dynamicznym.

Dla prostego wprowadzenia na temat działania kompilatorów i tworzenia własnego języka programowania poleciłbym nową książkę http://createyourproglang.com, która skupia się bardziej na teorii projektowania języków bez konieczności znajomości wewnętrznych elementów systemu operacyjnego / procesora, tj. Leksykatorów, parserów , tłumacze itp.

Wykorzystuje te same narzędzia, które zostały użyte do stworzenia ostatnio popularnych języków programowania Coffee Script i Fancy .

Jeśli wszystko, co mówisz, jest prawdą, masz profil obiecującego badacza, a konkretne zrozumienie można uzyskać tylko w jeden sposób: studiować. I nie mówię: „ Przeczytaj te wszystkie książki informatyczne wysokiego poziomu (szczególnie te ) napisane przez tego geniusza !”; Mam na myśli: musisz być z ludźmi wysokiego szczebla, aby być informatykiem, takim jak Charles Babbage, Alan Turing, Claude Shannon lub Dennis Ritchie. Nie gardzę samoukami (jestem jednym z nich), ale nie ma wielu takich ludzi jak ty. Naprawdę polecam Symbolic Systems Program (SSP) na Uniwersytecie Stanforda . Jak mówi ich strona internetowa:

Program Symbolic Systems Program (SSP) na Uniwersytecie Stanforda koncentruje się na komputerach i umysłach: sztucznych i naturalnych systemach wykorzystujących symbole do reprezentowania informacji. SSP skupia studentów i wykładowców zainteresowanych różnymi aspektami relacji człowiek-komputer, w tym ...

• kognitywistyka : badanie ludzkiej inteligencji, języków naturalnych i mózgu jako procesów obliczeniowych;
• sztuczna inteligencja : wyposażanie komputerów w zachowania i zrozumienie podobne do ludzkich; i
• interakcja człowiek-komputer : projektowanie oprogramowania komputerowego i interfejsów dobrze współpracujących z użytkownikami.

Mam zamiar zasugerować coś nieco z lewej strony: naucz się języka Python (a może Ruby, ale mam dużo więcej doświadczenia w Pythonie, więc to omówię). I nie tylko zagłębia się w to, ale naprawdę poznaje to na głębokim poziomie.

Sugeruję to z kilku powodów:

1. Python jest wyjątkowo dobrze zaprojektowanym językiem. Chociaż ma kilka brodawek, ma mniej IMHO niż w wielu innych językach. Jeśli jesteś początkującym projektantem języka, dobrze jest wystawić się na jak najwięcej dobrych języków.

2. Standardowa implementacja Pythona (CPython) jest open source i dobrze udokumentowana, co ułatwia zrozumienie, jak działa język pod maską.

3. Python jest skompilowany do prostego kodu bajtowego, który jest łatwiejszy do zrozumienia niż asembler i który działa tak samo na wszystkich platformach, na których działa Python. Dowiesz się więc o kompilacji (ponieważ Python kompiluje kod źródłowy do kodu bajtowego) i interpretacji (ponieważ ten bajtowy kod jest interpretowany na maszynie wirtualnej Python).

4. Python ma wiele proponowanych nowych funkcji, udokumentowanych numerowanymi PEP (Propozycje ulepszeń Pythona). PEP-y, które warto przeczytać, aby zobaczyć, jak projektanci języków rozważali wdrożenie funkcji przed wybraniem sposobu, w jaki to zrobili. (PEP, które są nadal rozważane, są szczególnie interesujące pod tym względem.)

5. Python ma wiele funkcji z różnych paradygmatów programowania, dzięki czemu poznasz różne sposoby podejścia do rozwiązywania problemów i będziesz mieć szerszy zakres narzędzi do rozważenia, w tym w swoim własnym języku.

6. Python sprawia, że ​​rozszerzanie języka na różne sposoby jest bardzo łatwe dzięki dekoratorom, metaklasom, hakom importowym itp., Dzięki czemu możesz grać z nowymi funkcjami językowymi do pewnego stopnia bez opuszczania języka. (Nawiasem mówiąc: bloki kodu są pierwszorzędnymi obiektami w Rubim, więc możesz pisać nowe struktury kontrolne, takie jak pętle! Mam wrażenie, że programiści Ruby niekoniecznie uważają to za rozszerzenie języka, po prostu programujesz w Ruby. Ale to całkiem fajne.)

7. W Pythonie możesz dezasemblować kod bajtowy generowany przez kompilator, a nawet napisać własny kod od zera i zlecić mu wykonanie go przez interpretera (sam to zrobiłem, i było to zadziwiające, ale zabawne).

8. Python ma dobre biblioteki do analizowania. Możesz parsować kod Pythona w abstrakcyjne drzewo składniowe, a następnie manipulować nim za pomocą modułu AST. Moduł PyParsing jest przydatny do analizowania dowolnych języków, takich jak te, które projektujesz. Teoretycznie możesz napisać swój kompilator w języku Python, jeśli chcesz (i może generować dane wyjściowe w języku C, a nawet w Pythonie).

To podejście dochodzeniowe może być dobrze dostosowane do bardziej formalnego podejścia, ponieważ zaczniesz rozpoznawać pojęcia, które studiowałeś w języku, z którym pracujesz, i na odwrót.

Baw się dobrze!

Cóż, myślę, że twoje pytanie może zostać napisane na nowo: „Jakie są podstawowe praktyczne koncepcje informatyki”, a całkowitą odpowiedzią jest oczywiście uzyskanie własnego licencjata z informatyki.

Zasadniczo tworzysz własny kompilator języka programowania, odczytując plik tekstowy, wyodrębniając z niego informacje i wykonując transformacje tekstu na podstawie informacji, które z niego przeczytałeś, dopóki nie przekształcisz go w bajty, które mogą być odczytane przez moduł ładujący (por. Linkers and Loaders firmy Levine). Trywialny kompilator jest po raz pierwszy dość rygorystycznym projektem.

Sercem systemu operacyjnego jest jądro, które zarządza zasobami (np. Alokacją / zwalnianiem pamięci) i przełącza między zadaniami / procesami / programami.

Asembler to transformacja tekst-bajt.

Jeśli jesteś zainteresowany tymi rzeczami, sugerowałbym napisanie asemblera X86 w Linuksie, który obsługuje pewien podzbiór standardowego zestawu X86. Będzie to dość prosty punkt wejścia i zapozna Cię z tymi zagadnieniami. To nie jest projekt dla dzieci i nauczy Cię wielu rzeczy.

Poleciłbym napisać to w C; C to lingua franca dla tego poziomu pracy.

Zobacz książkę Kennetha Loudena „Budowa kompilatora”

http://www.cs.sjsu.edu/~louden/cmptext/

Zapewnia lepsze praktyczne podejście do rozwoju kompilatora.

Ludzie uczą się przez działanie. Tylko niewielka liczba może zobaczyć symbole narysowane na planszy i od razu przejść od teorii do praktyki. Niestety, ci ludzie są często dogmatyczni, fundamentalistyczni i najgłośniejsi.

Miałem szczęście być wystawionym na PDP-8 jako mój pierwszy język asemblera. PDP-8 miał tylko sześć instrukcji, które były tak proste, że łatwo było sobie wyobrazić, że są one implementowane przez kilka dyskretnych komponentów, którymi w rzeczywistości były. Naprawdę usunęło „magię” z komputerów.

Inną bramą do tego samego objawienia jest język asemblera „mix”, którego Knuth używa w swoich przykładach. „Mix” wydaje się dziś archaiczny, ale nadal ma ten DE-mistyfikujący efekt.

Kompilatory i języki programowania (i wszystko, łącznie z budowaniem jednego - takie jak zdefiniowanie gramatyki skończonej i konwersja do asemblera) to bardzo złożone zadanie, które wymaga dużej wiedzy na temat systemów jako całości. Ten typ kursu jest zazwyczaj oferowany jako klasa Comp Sci na 3/4 rok na uniwersytecie.

Gorąco poleciłbym najpierw lepsze zrozumienie systemów operacyjnych i sposobu kompilowania / wykonywania istniejących języków (tj. Natywnie (C / C ++), na maszynie wirtualnej (Java) lub przez interpretera (Python / JavaScript)).

Wydaje mi się, że wykorzystaliśmy książkę Koncepcje systemu operacyjnego Abrahama Silberschatza, Petera B. Galvina, Grega Gagne'a na kursie systemów operacyjnych (w drugim roku). To była doskonała książka, która dokładnie omówiła każdy składnik systemu operacyjnego - trochę drogo, ale warto, a starsze / używane kopie powinny się unosić.

To duży temat, ale zamiast odurzać cię pompatycznym „idź poczytać książkę, dzieciaku”, zamiast tego chętnie dam ci wskazówki, które pomogą ci owinąć wokół niego głowę.

Większość kompilatorów i / lub tłumaczy działa w ten sposób:

Tokenize : zeskanuj tekst kodu i podziel go na listę tokenów.

Ten krok może być trudny, ponieważ nie możesz po prostu podzielić łańcucha na spacje, musisz rozpoznać, że if (bar) foo += "a string";jest to lista 8 tokenów: WORD, OPEN_PAREN, WORD, CLOSE_PAREN, WORD, ASIGNMENT_ADD, STRING_LITERAL, TERMINATOR. Jak widać, po prostu podział kodu źródłowego na spacje nie zadziała, musisz odczytać każdy znak jako sekwencję, więc jeśli napotkasz znak alfanumeryczny, będziesz czytał znaki, dopóki nie trafisz znaku innego niż alfanumeryczny i ciąg znaków właśnie przeczytane to SŁOWO, które później zostanie sklasyfikowane. Możesz sam zdecydować, jak szczegółowy jest twój tokenizer: czy połyka "a string"jako jeden token o nazwie STRING_LITERAL, który będzie później analizowany dalej, czy też zobaczy"a string" jako OPEN_QUOTE, UNPARSED_TEXT, CLOSE_QUOTE lub cokolwiek innego, jest to tylko jedna z wielu opcji, które musisz sam zdecydować podczas kodowania.

Lex : Masz teraz listę tokenów. Prawdopodobnie oznaczyłeś niektóre tokeny niejednoznaczną klasyfikacją, taką jak WORD, ponieważ podczas pierwszego przejścia nie poświęcasz zbyt wiele wysiłku, próbując zrozumieć kontekst każdego ciągu znaków. Więc teraz przeczytaj ponownie swoją listę tokenów źródłowych i przeklasyfikuj każdy z niejasnych tokenów na bardziej szczegółowy typ tokena na podstawie słów kluczowych w twoim języku. Więc masz WORD, np. „If”, a „if” znajduje się na liście specjalnych słów kluczowych o nazwie symbol IF, więc zmieniasz typ symbolu tego tokena z WORD na IF, a także WORD, którego nie ma na liście słów kluczowych , takie jak WORD foo, jest IDENTYFIKATOREM.

Analiza : Teraz if (bar) foo += "a string";zmieniłeś listę leksykalnych tokenów, która wygląda następująco: JEŚLI IDENTYFIKATOR OPEN_PAREN IDENTYFIKATOR ZAMKNIJ_PAREN ASIGN_ADD STRING_LITERAL TERMINATOR. Etap polega na rozpoznaniu sekwencji tokenów jako instrukcji. To jest parsowanie. Robisz to za pomocą gramatyki, takiej jak:

OŚWIADCZENIE: = ASIGN_EXPRESSION | IF_STATEMENT

IF_STATEMENT: = IF, PAREN_EXPRESSION, STATEMENT

ASIGN_EXPRESSION: = IDENTYFIKATOR, ASIGN_OP, WARTOŚĆ

PAREN_EXPRESSSION: = OPEN_PAREN, VALUE, CLOSE_PAREN

WARTOŚĆ: = IDENTYFIKATOR | STRING_LITERAL | PAREN_EXPRESSION

ASIGN_OP: = EQUAL | ASIGN_ADD | ASIGN_SUBTRACT | ASIGN_MULT

Produkcje wykorzystujące „|” między terminami oznacza „dopasuj dowolny z nich”, jeśli są przecinki między terminami, oznacza „dopasuj tę sekwencję terminów”

Jak tego używasz? Zaczynając od pierwszego tokena, spróbuj dopasować swoją sekwencję tokenów do tych produkcji. Najpierw próbujesz dopasować swoją listę tokenów do STATEMENT, więc czytasz regułę dla STATEMENT i mówi ona „STATEMENT jest albo ASIGN_EXPRESSION lub IF_STATEMENT”, więc najpierw spróbuj dopasować ASIGN_EXPRESSION, więc sprawdź regułę gramatyczną dla ASIGN_EXPRESSION i mówi „ASIGN_EXPRESSION jest IDENTYFIKATOREM, po którym następuje ASIGN_OP, a następnie WARTOŚĆ, więc sprawdzasz regułę gramatyczną dla IDENTIFIER i widzisz, że nie ma żadnej gramatyki dla IDENTIFIER, co oznacza, że ​​IDENTYFIKATOR jest„ terminalem ”, co oznacza, że ​​nie wymaga dalszych parsowanie w celu dopasowania, abyś mógł spróbować dopasować go bezpośrednio do tokena, ale pierwszy token źródłowy to JEŻELI, a JEŻELI nie jest taki sam jak IDENTYFIKATOR, więc dopasowanie nie powiodło się. Co teraz? Wróć do reguły STATEMENT i spróbuj dopasować następny termin: IF_STATEMENT. Sprawdzasz IF_STATEMENT, zaczyna się od IF, wyszukujesz IF, IF jest terminalem, porównujesz terminal z pierwszym tokenem, IF dopasowuje token, niesamowite kontynuowanie, następny termin to PAREN_EXPRESSION, odnośnik PAREN_EXPRESSION, to nie jest terminal, jaki jest pierwszy termin, PAREN_EXPRESSION zaczyna się od OPEN_PAREN, wyszukaj OPEN_PAREN, to terminal, dopasuj OPEN_PAREN do następnego tokena, pasuje, ... i tak dalej.

Najłatwiejszym sposobem podejścia do tego kroku jest posiadanie funkcji o nazwie parse (), której przekazujesz token kodu źródłowego, który próbujesz dopasować, i termin gramatyczny, z którym próbujesz go dopasować. Jeśli termin gramatyczny nie jest terminalem, to powracasz: ponownie wywołujesz parse (), przekazując mu ten sam token źródłowy i pierwszy termin tej reguły gramatycznej. Dlatego nazywany jest „parserem zejścia rekurencyjnego”. Funkcja parse () zwraca (lub modyfikuje) twoją bieżącą pozycję w czytaniu tokenów źródłowych, zasadniczo przekazuje ostatni token w dopasowanej sekwencji i kontynuujesz następne wywołanie stamtąd () stamtąd.

Za każdym razem, gdy parse () pasuje do produkcji takiej jak ASIGN_EXPRESSION, tworzysz strukturę reprezentującą ten fragment kodu. Ta struktura zawiera odniesienia do oryginalnych tokenów źródłowych. Zaczynasz budować listę tych struktur. Nazwę tę całą strukturę abstrakcyjnym drzewem składni (AST)

Kompiluj i / lub Wykonaj : Dla niektórych produkcji w twojej gramatyce stworzyłeś funkcje obsługi, które gdyby otrzymały strukturę AST, skompilowałyby lub wykonałyby tę część AST.

Spójrzmy więc na kawałek twojego AST, który ma typ ASIGN_ADD. Więc jako tłumacz masz funkcję ASIGN_ADD_execute (). Ta funkcja jest przekazywana jako element AST, który odpowiada drzewku analizy foo += "a string", więc funkcja ta patrzy na tę strukturę i wie, że pierwszy element w strukturze musi być IDENTYFIKATOREM, a drugi to WARTOŚĆ, więc ASIGN_ADD_execute () przekazuje warunek VALUE do funkcji VALUE_eval (), która zwraca obiekt reprezentujący oszacowaną wartość w pamięci, a następnie ASIGN_ADD_execute () wyszukuje „foo” w tabeli zmiennych i przechowuje odniesienie do wszystkiego, co zostało zwrócone przez eval_value () funkcjonować.

To jest tłumacz. Zamiast tego kompilator miałby funkcje obsługi tłumaczące kod AST na kod bajtowy lub kod maszynowy zamiast go wykonywać.

Kroki od 1 do 3 i niektóre 4 można ułatwić za pomocą narzędzi takich jak Flex i Bison. (aka. Lex i Yacc), ale pisanie tłumacza od zera jest prawdopodobnie najbardziej wzmacniającym ćwiczeniem, jakie może wykonać każdy programista. Wszystkie pozostałe wyzwania programistyczne wydają się trywialne po zdobyciu tego.

Moja rada jest na początek mała: mały język, z niewielką gramatyką, spróbuj parsować i wykonać kilka prostych instrukcji, a następnie stamtąd wyrastaj.

Przeczytaj je i powodzenia!

http://www.iro.umontreal.ca/~felipe/IFT2030-Automne2002/Complements/tinyc.c

http://en.wikipedia.org/wiki/Recursive_descent_parser

Pole komputerowe jest tylko skomplikowane, ponieważ miało czas na ewolucję w wielu kierunkach. Jego sednem są maszyny obliczeniowe.

Moim ulubionym bardzo podstawowym komputerem jest komputer przekaźnikowy Harry'ego Portera . Daje smak działania komputera na poziomie podstawowym. Następnie możesz zacząć doceniać, dlaczego potrzebne są takie języki, jak systemy operacyjne.

Chodzi o to, że trudno jest zrozumieć cokolwiek bez zrozumienia, czego potrzebuje . Powodzenia i nie tylko czytajcie rzeczy. Rób rzeczy.

Wejdź na http://mikeos.berlios.de/

Istnieje naprawdę prosty system operacyjny w zestawie x86.

Ma fajny samouczek, jak napisać prosty system operacyjny od zera.

Inną dobrą książką wprowadzającą jest „Compilerbau” N. Wirtha z 1986 r. (Konstrukcja kompilatora), który ma około 100 stron i wyjaśnia zwięzły, dobrze zaprojektowany kod języka zabawek PL / 0, w tym parser, generator kodu i maszynę wirtualną. Pokazuje także, jak napisać analizator składni, który wczytuje gramatykę do analizy w notacji EBNF. Książka jest w języku niemieckim, ale napisałem streszczenie i przetłumaczyłem kod na Python jako ćwiczenie, patrz http://www.d12k.org/cmplr/w86/intro.html .

Jeśli jesteś zainteresowany zrozumieniem istoty języków programowania, sugeruję, abyś zapoznał się z książką PLAI (http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/), aby zrozumieć pojęcia i ich wdrożenie. Pomoże Ci również w zaprojektowaniu własnego języka.

Jeśli naprawdę interesujesz się kompilatorem, a nigdy wcześniej go nie miałeś, możesz zacząć od zaprojektowania kalkulatora do obliczania formuł arytmetycznych (rodzaj DSL, jak wspomniał Eric). Jest wiele aspektów, które należy wziąć pod uwagę w przypadku tego rodzaju kompilatora:

• Dozwolone liczby
• Dozwoleni operatorzy
• Priorytety operatora
• Sprawdzanie poprawności składni
• Zmienny mechanizm wyszukiwania
• Wykrywanie cyklu
• Optymalizacja

Na przykład masz następujące formuły, Twój kalkulator powinien być w stanie obliczyć wartość x:

a = 1
b = 2
c = a + b
d = (3 + b) * c
x = a - d / b

Na początku nie jest to ekstremalnie trudny kompilator, ale może sprawić, że pomyślisz bardziej o niektórych podstawowych pomysłach na temat tego, czym jest kompilator, a także pomoże ci poprawić umiejętności programowania i kontrolować jakość kodu (jest to idealny problem, który Test Driven Development TDD może mieć zastosowanie do poprawy jakości oprogramowania).