Pisanie kompilatora we własnym języku

Intuicyjnie wydaje się, że kompilator języka Foonie może być napisany w Foo. Mówiąc dokładniej, pierwszy kompilator dla języka Foonie może być napisany w Foo, ale można napisać każdy kolejny kompilator Foo.

Ale czy to rzeczywiście prawda? Mam pewne niejasne wspomnienia z czytania o języku, którego pierwszy kompilator został napisany „sam”. Czy to możliwe, a jeśli tak, to w jaki sposób?

Nazywa się to „ładowaniem”. Najpierw musisz zbudować kompilator (lub interpreter) dla swojego języka w innym języku (zwykle Java lub C). Gdy to zrobisz, możesz napisać nową wersję kompilatora w języku Foo. Pierwszego kompilatora rozruchowego używasz do kompilacji kompilatora, a następnie kompilowanego kompilatora używasz do kompilacji wszystkiego innego (w tym jego przyszłych wersji).

Większość języków rzeczywiście powstaje w ten sposób, częściowo dlatego, że projektanci języków lubią używać języka, który tworzą, a także dlatego, że nietrywialny kompilator często służy jako przydatny punkt odniesienia dla tego, jak „kompletny” może być język.

Przykładem może być Scala. Pierwszy kompilator został stworzony w Pizza, eksperymentalnym języku Martina Odersky'ego. Od wersji 2.0 kompilator został całkowicie przepisany w Scali. Od tego momentu stary kompilator Pizza może zostać całkowicie odrzucony, ponieważ nowy kompilator Scala może zostać użyty do samodzielnej kompilacji w przyszłych iteracjach.

Pamiętam, jak słuchałem podcastu Software Engineering Radio, w którym Dick Gabriel mówił o bootstrapowaniu oryginalnego interpretera LISP, pisząc wersję LISP na papierze i ręcznie składając ją w kod maszynowy. Od tego momentu pozostałe funkcje LISP były zarówno zapisywane, jak i interpretowane za pomocą LISP.

Dodanie ciekawości do poprzednich odpowiedzi.

Oto cytat z podręcznika Linux From Scratch , na etapie, w którym zaczyna się budowanie kompilatora GCC z jego źródła. (Linux From Scratch to sposób na zainstalowanie Linuksa, który radykalnie różni się od instalacji dystrybucji, ponieważ musisz skompilować naprawdę każdy plik binarny systemu docelowego.)

make bootstrap

Cel „bootstrap” nie tylko kompiluje GCC, ale kompiluje go kilka razy. Używa programów skompilowanych w pierwszej rundzie do kompilacji po raz drugi, a następnie ponownie po raz trzeci. Następnie porównuje te drugą i trzecią kompilację, aby upewnić się, że może się bezproblemowo odtworzyć. Oznacza to również, że została poprawnie skompilowana.

Użycie celu „bootstrap” jest uzasadnione faktem, że kompilator używany do budowania łańcucha narzędzi systemu docelowego może nie mieć tej samej wersji docelowego kompilatora. Postępując w ten sposób, z pewnością uzyska się w systemie docelowym kompilator, który może się skompilować.

Kiedy piszesz swój pierwszy kompilator dla C, piszesz go w innym języku. Teraz masz kompilator dla C w, powiedzmy, asemblerze. W końcu dotrzesz do miejsca, w którym musisz przeanalizować ciągi znaków, a konkretnie sekwencje specjalne. Napisz kod do konwersji \nna znak o kodzie dziesiętnym 10 (i \rdo 13 itd.).

Gdy ten kompilator będzie gotowy, zaczniesz go ponownie implementować w C. Ten proces nazywa się „ ładowaniem ”.

Kod parsujący stanie się:

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

Kiedy to się kompiluje, masz plik binarny, który rozumie „\ n”. Oznacza to, że możesz zmienić kod źródłowy:

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

Gdzie więc informacja, że ​​„\ n” to kod 13? Jest w pliku binarnym! To jest jak DNA: Kompilowanie kodu źródłowego C z tym plikiem binarnym odziedziczy tę informację. Jeśli kompilator się skompiluje, przekaże tę wiedzę swojemu potomstwu. Od tego momentu nie ma możliwości zobaczenia z samego źródła, co zrobi kompilator.

Jeśli chcesz ukryć wirusa w źródle jakiegoś programu, możesz to zrobić w następujący sposób: Pobierz źródło kompilatora, znajdź funkcję, która kompiluje funkcje i zamień ją na tę:

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

Interesującymi częściami są A i B. A jest kodem źródłowym compileFunction włączenia wirusa, prawdopodobnie w jakiś sposób zaszyfrowanym, więc wyszukiwanie wynikowego pliku binarnego nie jest oczywiste. Dzięki temu kompilacja do kompilatora zachowa kod wstrzyknięcia wirusa.

B jest taki sam dla funkcji, którą chcemy zastąpić naszym wirusem. Na przykład może to być funkcja „login” w pliku źródłowym „login.c”, który prawdopodobnie pochodzi z jądra Linuksa. Możemy zastąpić go wersją, która oprócz zwykłego hasła zaakceptuje hasło „joshua” dla konta root.

Jeśli to skompilujesz i rozpowszechnisz jako plik binarny, nie będzie sposobu, aby znaleźć wirusa, patrząc na źródło.

Oryginalne źródło pomysłu: https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95/

Nie możesz napisać kompilatora sam w sobie, ponieważ nie masz nic do skompilowania początkowego kodu źródłowego. Istnieją dwa podejścia do rozwiązania tego.

Najmniej uprzywilejowane to: Napisz minimalny kompilator w asemblerze (fuj) dla minimalnego zestawu języka, a następnie użyj tego kompilatora do zaimplementowania dodatkowych funkcji języka. Buduj swoją drogę, aż będziesz mieć kompilator ze wszystkimi funkcjami językowymi dla siebie. Bolesny proces, który zwykle wykonuje się tylko wtedy, gdy nie masz innego wyboru.

Preferowanym podejściem jest użycie kompilatora krzyżowego. Zmieniasz zaplecze istniejącego kompilatora na innym komputerze, aby utworzyć dane wyjściowe działające na komputerze docelowym. Następnie masz ładny pełny kompilator i pracujesz na maszynie docelowej. Najbardziej popularny jest język C, ponieważ istnieje wiele istniejących kompilatorów, które mają wtykowe zaplecza, które można wymienić.

Mało znanym faktem jest to, że kompilator GNU C ++ ma implementację, która wykorzystuje tylko podzbiór C. Powodem jest to, że zwykle łatwo jest znaleźć kompilator C dla nowej maszyny docelowej, który pozwala na zbudowanie z niego pełnego kompilatora GNU C ++. Teraz uruchomiłeś system kompilatora C ++ na komputerze docelowym.

Ogólnie rzecz biorąc, najpierw musisz mieć działające (jeśli pierwotne) wycięcie kompilatora działające - wtedy możesz zacząć myśleć o uczynieniu go samodzielnym. Jest to faktycznie uważane za ważny kamień milowy w niektórych językach.

Z tego, co pamiętam z „mono”, jest prawdopodobne, że będą musieli dodać kilka rzeczy do refleksji, aby to zadziałało: zespół mono wciąż wskazuje, że niektóre rzeczy po prostu nie są możliwe Reflection.Emit; oczywiście zespół stwardnienia rozsianego może udowodnić, że się mylą.

Ma to kilka prawdziwych zalet: jest to dość dobry test jednostkowy, na początek! I masz tylko jeden język do zmartwienia (tj. Możliwe jest, że ekspert C # może nie znać dużo C ++; ale teraz możesz naprawić kompilator C #). Zastanawiam się jednak, czy nie ma w tym miejscu dumy zawodowej: po prostu chcą , aby była to hosting.

Niezupełnie kompilator, ale ostatnio pracowałem nad systemem, który sam się hostuje; generator kodu służy do generowania generatora kodu ... więc jeśli schemat się zmieni, po prostu uruchamiam go na sobie: nowa wersja. Jeśli występuje błąd, wracam do wcześniejszej wersji i próbuję ponownie. Bardzo wygodny i bardzo łatwy w utrzymaniu.

Aktualizacja 1

Właśnie obejrzałem to wideo Andersa w PDC i (około godziny później) podaje kilka ważniejszych powodów - wszystko o kompilatorze jako usłudze. Dla przypomnienia.

Oto zrzut (właściwie trudny temat do wyszukiwania):

• Pogawędka

• do

Jest to także idea PyPy i Rubiniusa :

(Myślę, że może to dotyczyć również Fortha , ale nie wiem nic o Forthu.)

GNAT, kompilator GNU Ada, wymaga pełnego kompilatora Ada. Może to być uciążliwe podczas przenoszenia go na platformę, na której nie ma łatwo dostępnego pliku binarnego GNAT.

W rzeczywistości większość kompilatorów jest napisana w języku, który kompilują, z powodów wymienionych powyżej.

Pierwszy kompilator bootstrap jest zwykle napisany w C, C ++ lub asemblerze.

Kompilator C # projektu Mono od dłuższego czasu jest „hostowany”, co oznacza, że ​​został napisany w samym języku C #.

Wiem, że kompilator został uruchomiony jako czysty kod C, ale po zaimplementowaniu „podstawowych” funkcji ECMA zaczęli przepisywać kompilator w języku C #.

Nie jestem świadomy zalet pisania kompilatora w tym samym języku, ale jestem pewien, że ma to związek przynajmniej z funkcjami, które sam język może zaoferować (na przykład C nie obsługuje programowania obiektowego) .

Więcej informacji znajdziesz tutaj .

Napisałem SLIC (System języków do implementacji kompilatorów) sam w sobie. Następnie ręcznie skompilowałem go do zestawu. SLIC ma wiele zalet, ponieważ był to jeden kompilator pięciu podjęzyków:

• SYNTAX Parser Programming Language PPL
• GENERATOR LISP 2 oparty na indeksowaniu drzew język generowania kodu PSEUDO
• Sekwencja ISO, kod PSEUDO, język optymalizacji
• PSEUDO Makro, takie jak język asemblera.
• MACHOP Język instrukcji montażu maszyny.

SLIC został zainspirowany CWIC (kompilatorem do pisania i wdrażania kompilatorów). W przeciwieństwie do większości pakietów programistycznych kompilatora, generowanie kodu SLIC i CWIC ze specjalizowanymi, specyficznymi dla domeny, językami. SLIC rozszerza generowanie kodu CWIC, dodając podjęzyki ISO, PSEUDO i MACHOP, oddzielając specyfikę maszyny docelowej od języka generatora przeszukiwania drzew.

Drzewa i listy LISP 2

Kluczowym elementem jest dynamiczny system zarządzania pamięcią oparty na języku LISP 2. Listy są wyrażone w języku zawartym w nawiasach kwadratowych, a ich składniki są oddzielone przecinkami, tj. Trzyelementowa lista [a, b, c].

Drzewa:

     ADD
    /   \
  MPY     3
 /   \
5     x

są reprezentowane przez listy, których pierwszym wpisem jest obiekt węzła:

[ADD,[MPY,5,x],3]

Drzewa są zwykle wyświetlane z osobnym węzłem poprzedzającym gałęzie:

ADD[MPY[5,x],3]

Rozpakowywanie przy użyciu funkcji generatora opartych na LISP 2

Funkcja generatora to nazwany zestaw (unparse) => akcja> pary ...

<NAME>(<unparse>)=><action>;
      (<unparse>)=><action>;
            ...
      (<unparse>)=><action>;

Wyodrębnianie wyrażeń to testy, które pasują do wzorców drzewa i / lub typów obiektów, rozbijając je i przypisując te części zmiennej lokalnej, która ma być przetwarzana przez jej działanie proceduralne. Coś jak przeciążona funkcja przyjmująca różne typy argumentów. Z wyjątkiem próby () => ... próby są przeprowadzane w zakodowanej kolejności. Pierwszy udany rozpakuj wykonanie odpowiedniej akcji. Wyodrębniane wyrażenia to testy dezasemblujące. ADD [x, y] dopasowuje dwugałęziowe drzewo ADD przypisujące swoje gałęzie do lokalnych zmiennych x i y. Akcja może być prostym wyrażeniem lub ograniczonym blokiem kodu .BEGIN ... .END. Użyłbym dzisiaj bloków w stylu c ... Reguły dopasowywania drzewa, [], rozpakowywanie mogą wywoływać generatory przekazujące zwrócone wyniki do działania:

expr_gen(ADD[expr_gen(x),expr_gen(y)])=> x+y;

W szczególności powyższe polecenie expr_gen unparse odpowiada dwóm gałęziom drzewa ADD. W ramach wzorca testowego jeden generator argumentów umieszczony w gałęzi drzewa zostanie wywołany z tą gałęzią. Jego lista argumentów to jednak zmienne lokalne, którym przypisano zwrócone obiekty. Powyżej unseparowania określa, że ​​dwie gałęzie to ADD deasemblacja drzewa, rekurencyjne naciśnięcie każdej gałęzi do wyrażenia_wyj. Powrót lewej gałęzi umieszczony w zmiennych lokalnych x. Podobnie prawa gałąź przekazana do expr_gen wraz z obiektem zwracanym. Powyższe może być częścią ewaluatora wyrażeń liczbowych. Były funkcje skrótów zwane wektorami znajdującymi się powyżej, zamiast ciągu węzłów, wektor węzłów mógł być użyty z wektorem odpowiednich akcji:

expr_gen(#node[expr_gen(x),expr_gen(y)])=> #action;

  node:   ADD, SUB, MPY, DIV;
  action: x+y, x-y, x*y, x/y;

        (NUMBER(x))=> x;
        (SYMBOL(x))=> val:(x);

Powyższy pełniejszy ewaluator wyrażeń przypisuje zwrot z expr_gen lewej gałęzi do x, a prawej gałęzi do y. Odpowiedni wektor akcji wykonany na xiy zwrócił. Ostatnia para operacji parowania => odpowiada obiektom numerycznym i symbolicznym.

Symbol i atrybuty symboli

Symbole mogły mieć nazwane atrybuty. val: (x) dostęp do atrybutu val obiektu symbolu zawartego w x. Uogólniony stos tablicy symboli jest częścią SLIC. Tabela SYMBOL może być popychana i otwierana, zapewniając lokalne symbole funkcji. Nowo utworzony symbol jest katalogowany w górnej tabeli symboli. Wyszukiwanie symboli przeszukuje stos tablicy symboli od górnej tabeli, najpierw do tyłu stosu.

Generowanie kodu niezależnego od maszyny

Język generatora SLIC produkuje obiekty instrukcji PSEUDO, dołączając je do listy kodów sekcji. F.LUSH powoduje uruchomienie listy kodów PSEUDO, usuwając każdą instrukcję PSEUDO z listy i wywołując ją. Po wykonaniu pamięć obiektów PSEUDO zostaje zwolniona. Organy proceduralne działań PSEUDO i GENERATOR są zasadniczo tym samym językiem, z wyjątkiem ich wyników. PSEUDO mają działać jako makra asemblacyjne zapewniające niezależne od maszyny sekwencjonowanie kodu. Zapewniają one oddzielenie określonej maszyny docelowej od języka generatora przeszukiwania drzew. PSEUDO wywołują funkcje MACHOP w celu wygenerowania kodu maszynowego. MACHOP są używane do definiowania pseudooperacji asemblerowych (takich jak dc, definiowanie stałej itp.) Oraz instrukcji maszynowych lub rodziny podobnych instrukcji sformatowanych przy użyciu wpisu wektorowego. Po prostu przekształcają swoje parametry w sekwencję pól bitowych tworzących instrukcję. Wywołania MACHOP mają wyglądać jak asembler i zapewniają formatowanie pól wydruku, gdy asembler jest pokazywany na liście kompilacji. W przykładowym kodzie używam komentowania w stylu c, które można łatwo dodać, ale nie było w oryginalnych językach. MACHOP-y produkują kod do pamięci adresowalnej nieco. Linker SLIC obsługuje dane wyjściowe kompilatora. MACHOP instrukcji trybu użytkownika DEC-10 z użyciem wpisu wektorowego: MACHOP-y produkują kod do pamięci adresowalnej nieco. Linker SLIC obsługuje dane wyjściowe kompilatora. MACHOP instrukcji trybu użytkownika DEC-10 z użyciem wpisu wektorowego: MACHOP-y produkują kod do pamięci adresowalnej nieco. Linker SLIC obsługuje dane wyjściowe kompilatora. MACHOP instrukcji trybu użytkownika DEC-10 z użyciem wpisu wektorowego:

.MACHOP #opnm register,@indirect offset (index): // Instruction's parameters.
.MORG 36, O(18): $/36; // Align to 36 bit boundary print format: 18 bit octal $/36
O(9):  #opcd;          // Op code 9 bit octal print out
 (4):  register;       // 4 bit register field appended print
 (1):  indirect;       // 1 bit appended print
 (4):  index;          // 4 bit index register appended print
O(18): if (#opcd&&3==1) offset // immediate mode use value else
       else offset/36;         // memory address divide by 36
                               // to get word address.
// Vectored entry opcode table:
#opnm := MOVE, MOVEI, MOVEM, MOVES, MOVS, MOVSI, MOVSM, MOVSS,
         MOVN, MOVNI, MOVNM, MOVNS, MOVM, MOVMI, MOVMM, MOVMS,
         IMUL, IMULI, IMULM, IMULB, MUL,  MULI,  MULM,  MULB,
                           ...
         TDO,  TSO,   TDOE,  TSOE,  TDOA, TSOA,  TDON,  TSON;
// corresponding opcode value:
#opcd := 0O200, 0O201, 0O202, 0O203, 0O204, 0O205, 0O206, 0O207,
         0O210, 0O211, 0O212, 0O213, 0O214, 0O215, 0O216, 0O217,
         0O220, 0O221, 0O222, 0O223, 0O224, 0O225, 0O226, 0O227,
                           ...
         0O670, 0O671, 0O672, 0O673, 0O674, 0O675, 0O676, 0O677;

.MORG 36, O (18): $ / 36; wyrównuje lokalizację do 36-bitowej granicy, drukując adres $ / 36 słów 18 bitów ósemkowych. 9-bitowy rejestr opcd, 4-bitowy rejestr, bit pośredni i 4-bitowy rejestr indeksowy są łączone i drukowane tak, jakby były pojedynczym 18-bitowym polem. 18-bitowy adres / 36 lub wartość natychmiastowa jest wyprowadzana i drukowana ósemkowo. Przykład wydruku MOVEI z r1 = 1 i r2 = 2:

400020 201082 000005            MOVEI r1,5(r2)

Dzięki opcji kompilacji kompilatora otrzymujesz wygenerowany kod zestawu na liście kompilacji.

Połącz to ze sobą

Linker SLIC jest dostarczany jako biblioteka, która obsługuje połączenia i rozdzielczości symboli. Formatowanie pliku docelowego ładowania docelowego musi jednak zostać napisane dla komputerów docelowych i połączone z biblioteką biblioteki linkera.

Język generatora jest w stanie zapisywać drzewa do pliku i odczytywać je, umożliwiając implementację kompilatora wielopasmowego.

Krótkie podsumowanie generowania i pochodzenia kodu

Najpierw omówiłem generowanie kodu, aby upewnić się, że SLIC był prawdziwym kompilatorem kompilatorów. SLIC został zainspirowany CWIC (kompilatorem do pisania i wdrażania kompilatorów) opracowanym w Systems Development Corporation pod koniec lat 60. XX wieku. CWIC miał tylko języki SYNTAX i GENERATOR, które wytwarzały kod bajtowy z języka GENERATOR. Kod bajtowy został umieszczony lub umieszczony (bufor używany w dokumentacji CWIC) w buforach pamięci powiązanych z nazwanymi sekcjami i zapisany przez instrukcję .FLUSH. Dokument ACM na CWIC jest dostępny w archiwum ACM.

Pomyślnie wdrażam główny język programowania

Pod koniec lat siedemdziesiątych SLIC został użyty do napisania kompilatora krzyżowego COBOL. Ukończone w około 3 miesiące głównie przez jednego programistę. W razie potrzeby pracowałem trochę z programistą. Inny programista napisał bibliotekę wykonawczą i MACHOP dla docelowego minikomputera TI-990. Ten kompilator COBOL skompilował znacznie więcej wierszy na sekundę niż natywny kompilator COBOL DEC-10 napisany w asemblerze.

Więcej o kompilatorze, niż zwykle mówiono

Dużą część pisania kompilatora od zera stanowi biblioteka czasu wykonywania. Potrzebujesz tabeli symboli. Potrzebujesz danych wejściowych i wyjściowych. Dynamiczne zarządzanie pamięcią itp. Łatwo może być więcej pracy przy pisaniu biblioteki wykonawczej dla kompilatora niż pisaniu kompilatora. Jednak w przypadku SLIC biblioteka uruchomieniowa jest wspólna dla wszystkich kompilatorów opracowanych w SLIC. Uwaga: istnieją dwie biblioteki wykonawcze. Jeden dla docelowej maszyny języka (na przykład COBOL). Druga to biblioteka wykonawcza kompilatorów.

Myślę, że ustaliłem, że nie były to generatory parsera. Więc teraz, z odrobiną zrozumienia zaplecza, mogę wyjaśnić język programowania parsera.

Język programowania analizatora składni

Analizator składni jest pisany przy użyciu wzoru zapisanego w postaci prostych równań.

<name> <formula type operator> <expression> ;

Elementem językowym na najniższym poziomie jest znak. Tokeny powstają z podzbiorów znaków języka. Klasy znaków są używane do nazywania i definiowania tych podzbiorów znaków. Operatorem definiującym klasę znaków jest znak dwukropka (:). Znaki należące do klasy są kodowane po prawej stronie definicji. Znaki do wydruku są ujęte w ciągi pojedyncze liczb pierwszych. Znaki niedrukowalne i specjalne mogą być reprezentowane przez ich liczbę porządkową. Członkowie klasy są oddzieleni alternatywną | operator. Formuła klasowa kończy się średnikiem. Klasy postaci mogą obejmować wcześniej zdefiniowane klasy:

/*  Character Class Formula                                    class_mask */
bin: '0'|'1';                                                // 0b00000010
oct: bin|'2'|'3'|'4'|'5'|'6'|'7';                            // 0b00000110
dgt: oct|'8'|'9';                                            // 0b00001110
hex: dgt|'A'|'B'|'C'|'D'|'E'|'F'|'a'|'b'|'c'|'d'|'e'|'f';    // 0b00011110
upr:  'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|
      'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z';   // 0b00100000
lwr:  'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'|
      'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z';   // 0b01000000
alpha:  upr|lwr;                                             // 0b01100000
alphanum: alpha|dgt;                                         // 0b01101110

Klasa skip 0b00000001 jest predefiniowana, ale może być zbyt ogólna, by zdefiniować skip_class.

Podsumowując: Klasa znaków to lista alternatyw, która może być tylko stałą znaku, porządkiem znaku lub wcześniej zdefiniowaną klasą znaków. Gdy zaimplementowałem klasy znaków: Formuła klasy ma przypisaną maskę bitową klasy. (Pokazane w komentarzach powyżej) Każda formuła klasy posiadająca dowolny znak dosłowny lub porządkowy powoduje przydzielenie bitu klasy. Maska jest tworzona przez uporządkowanie masek klasy zawartych klas wraz z przydzielonym bitem (jeśli istnieje). Tabela klas jest tworzona z klas postaci. Wpis zindeksowany porządkiem postaci zawiera bity wskazujące przynależność do klasy postaci. Testy klasowe odbywają się w toku. Przykład kodu IA-86 z porządkiem postaci w eax ilustruje testowanie klas:

test    byte ptr [eax+_classmap],dgt

Następnie:

jne      <success>

lub

je       <failure>

Przykłady kodów instrukcji IA-86 są używane, ponieważ myślę, że instrukcje IA-86 są dziś bardziej znane. Nazwa klasy obliczana na jej maskę klasy jest nieniszcząca AND z tabelą klas indeksowaną znakami porządkowymi (w eax). Niezerowy wynik wskazuje na przynależność do klasy. (EAX jest zerowany, z wyjątkiem al (8 niskich bitów EAX), które zawiera znak).

Tokeny były nieco inne w tych starych kompilatorach. Słowa kluczowe nie zostały wyjaśnione jako tokeny. Po prostu zostały dopasowane przez cytowane stałe ciągów w języku parsera. Cytowane ciągi znaków zwykle nie są przechowywane. Można stosować modyfikatory. A + utrzymuje ciąg pasujący. (tj. + „-” dopasowuje znak - zachowujący znak po pomyślnym zakończeniu). Operacja (tzn. „E”) wstawia ciąg do tokena. Białe znaki są obsługiwane przez formułę tokenową pomijającą wiodące znaki SKIP_CLASS, aż do pierwszego dopasowania. Zauważ, że jawne dopasowanie znaku skip_class zatrzyma pomijanie, umożliwiając tokenowi rozpoczęcie od znaku skip_class. Formuła tokenu pomija wiodące znaki skip_class pasujące do pojedynczego cudzysłowu lub cudzysłowu. Interesujące jest dopasowanie „znaku w ciągu” cytowanego ciągu:

string .. (''' .ANY ''' | '"' $(-"""" .ANY | """""","""") '"') MAKSTR[];

Pierwsza alternatywa pasuje do dowolnego pojedynczego cudzysłowu. Właściwa alternatywa pasuje do łańcucha podwójnego cudzysłowu, który może zawierać znaki podwójnego cudzysłowu, używając dwóch „znaków razem do reprezentowania jednego” znaku. Ta formuła definiuje ciągi używane we własnej definicji. Wewnętrzna prawa alternatywa „” „$ (-„ ”„ ”.ANY |” „” „” „” „„ ”)„ ”pasuje do podwójnego cudzysłowu. Możemy użyć pojedynczego „cudzysłowu”, aby dopasować znak „podwójnego cudzysłowu”. Jednak w ciągu podwójnego „cudzysłowu”, jeśli chcemy użyć „znaku”, musimy użyć dwóch „znaków”, aby uzyskać jeden. Na przykład w wewnętrznej lewej alternatywie pasującej do dowolnego znaku z wyjątkiem cytatu:

-"""" .ANY

negatywne spojrzenie w przód - „” „” jest używane, gdy po pomyślnym (niepasowaniu do znaku) dopasowuje znak .ANY (który nie może być „znakiem”, ponieważ… ”„ ”wyeliminował tę możliwość). Właściwą alternatywą jest przyjęcie - „” „” „dopasowanie postaci”, a porażka była właściwą alternatywą:

"""""",""""

próbuje dopasować dwa „znaki zastępując je pojedynczym podwójnym” za pomocą „” „” „do wstawienia pojedynczego znaku”. Obie wewnętrzne alternatywy, które nie spełniają znaku zamykającego cudzysłowu, są dopasowywane, a MAKSTR [] wywoływany w celu utworzenia obiektu łańcuchowego. $ sekwencja, pętla zakończona powodzeniem, operator dopasowuje sekwencję. Formuła tokenu pomija wiodące znaki klas pomijania (spacja). Po pierwszym dopasowaniu pomijanie_klasy pomijanie jest wyłączone. Możemy wywoływać funkcje zaprogramowane w innych językach za pomocą []. MAKSTR [], MAKBIN [], MAKOCT [], MAKHEX [], MAKFLOAT [] i MAKINT [] to dostarczona funkcja biblioteczna, która konwertuje dopasowany ciąg tokenów na obiekt tekstowy. Poniższa formuła liczbowa ilustruje dość złożone rozpoznawanie tokenów:

number .. "0B" bin $bin MAKBIN[]        // binary integer
         |"0O" oct $oct MAKOCT[]        // octal integer
         |("0H"|"0X") hex $hex MAKHEX[] // hexadecimal integer
// look for decimal number determining if integer or floating point.
         | ('+'|+'-'|--)                // only - matters
           dgt $dgt                     // integer part
           ( +'.' $dgt                  // fractional part?
              ((+'E'|'e','E')           // exponent  part
               ('+'|+'-'|--)            // Only negative matters
               dgt(dgt(dgt|--)|--)|--)  // 1 2 or 3 digit exponent
             MAKFLOAT[] )               // floating point
           MAKINT[];                    // decimal integer

Powyższa formuła tokenu liczbowego rozpoznaje liczby całkowite i zmiennoprzecinkowe. Alternatywy - zawsze są skuteczne. W obliczeniach można stosować obiekty numeryczne. Obiekty tokena są wypychane na stos analizowania po pomyślnym zakończeniu formuły. Potęga wykładnika w (+ „E” | „e”, „E”) jest interesująca. Zawsze chcemy mieć wielką literę E dla MAKEFLOAT []. Ale zezwalamy na małą literę „e” zastępującą ją za pomocą „E”.

Być może zauważyłeś spójność klasy postaci i formuły tokena. Formuła analizowania kontynuuje dodawanie alternatywnych metod cofania i operatorów budowy drzew. Operatory alternatywne śledzenia wstecznego i wstecznego nie mogą być mieszane na poziomie wyrażenia. Być może nie masz (a | b \ c) miksowania bez cofania się | z alternatywną ścieżką zwrotną. (a \ b \ c), (a | b | c) i ((a | b) \ c) są poprawne. Alternatywa \ cofania się zapisuje stan analizy przed próbą lewej alternatywy, aw przypadku awarii przywraca stan analizy przed próbą wykonania właściwej alternatywy. W szeregu alternatyw pierwsza udana alternatywa zadowala grupę. Dalsze alternatywy nie są podejmowane. Faktoring i grupowanie zapewnia ciągłą analizę składni. Alternatywna ścieżka powrotna tworzy zapisany stan parsowania, zanim spróbuje wykonać lewą alternatywę. Cofanie jest wymagane, gdy analiza może dokonać częściowego dopasowania, a następnie zakończyć się niepowodzeniem:

(a b | c d)\ e

W powyższym przypadku, jeśli błąd zwróci, zostanie podjęta próba alternatywnej płyty CD. Jeśli następnie c zwróci błąd, zostanie podjęta próba alternatywna. Jeśli a powiedzie się i b nie powiedzie się, parsowanie zostanie cofnięte i e spróbuje. Podobnie niepowodzenie c udane ib nie powiodło się, parsowanie jest cofane i podejmowane jest alternatywne e. Cofanie nie jest ograniczone do formuły. Jeśli jakakolwiek formuła parsująca w dowolnym momencie dopasuje częściowo, a następnie się nie powiedzie, parsowanie zostanie zresetowane do górnej ścieżki powrotnej i zastosowana zostanie alternatywa. Błąd kompilacji może wystąpić, jeśli kod wyjściowy wykryje, że utworzono ścieżkę zwrotną. Cofnięcie jest ustawiane przed rozpoczęciem kompilacji. Niepowodzenie powrotu lub powrotu do niego jest awarią kompilatora. Podkłady są ułożone w stos. Możemy użyć negatywnego - i pozytywnego? zerkaj / patrz przed siebie, aby przetestować bez przyspieszania analizy. test ciągów to rzut oka, który wymaga jedynie zapisania i zresetowania stanu wejściowego. Spojrzenie w przyszłość byłoby parsowaniem wyrażenia, które dokonuje częściowego dopasowania przed niepowodzeniem. Spojrzenie w przyszłość jest realizowane za pomocą śledzenia wstecznego.

Język analizatora składni nie jest ani analizatorem składni LL, ani LR. Ale język programowania do pisania rekurencyjnego parsera, w którym programujesz budowę drzewa:

:<node name> creates a node object and pushes it onto the node stack.
..           Token formula create token objects and push them onto 
             the parse stack.
!<number>    pops the top node object and top <number> of parstack 
             entries into a list representation of the tree. The 
             tree then pushed onto the parse stack.
+[ ... ]+    creates a list of the parse stack entries created 
             between them:
              '(' +[argument $(',' argument]+ ')'
             could parse an argument list. into a list.

Często stosowanym przykładem analizującym jest wyrażenie arytmetyczne:

Exp = Term $(('+':ADD|'-':SUB) Term!2); 
Term = Factor $(('*':MPY|'/':DIV) Factor!2);
Factor = ( number
         | id  ( '(' +[Exp $(',' Exp)]+ ')' :FUN!2
               | --)
         | '(' Exp ')" )
         (^' Factor:XPO!2 |--);

Exp i Term za pomocą pętli tworzy drzewo leworęczne. Współczynnik użycia prawej rekurencji tworzy drzewo praworęczne:

d^(x+5)^3-a+b*c => ADD[SUB[EXP[EXP[d,ADD[x,5]],3],a],MPY[b,c]]

              ADD
             /   \
          SUB     MPY
         /   \   /   \
      EXP     a b     c
     /   \
    d     EXP     
         /   \
      ADD     3
     /   \
    x     5

Oto trochę kompilatora cc, zaktualizowanej wersji SLIC z komentarzami w stylu c. Typy funkcji (gramatyka, token, klasa znaków, generator, PSEUDO lub MACHOP są określane na podstawie ich początkowej składni zgodnie z ich identyfikatorem. Za pomocą tych odgórnych parserów zaczynasz od formuły definiującej program:

program = $((declaration            // A program is a sequence of
                                    // declarations terminated by
            |.EOF .STOP)            // End Of File finish & stop compile
           \                        // Backtrack: .EOF failed or
                                    // declaration long-failed.
             (ERRORX["?Error?"]     // report unknown error
                                    // flagging furthest parse point.
              $(-';' (.ANY          // find a ';'. skiping .ANY
                     | .STOP))      // character: .ANY fails on end of file
                                    // so .STOP ends the compile.
                                    // (-';') failing breaks loop.
              ';'));                // Match ';' and continue

declaration =  "#" directive                // Compiler directive.
             | comment                      // skips comment text
             | global        DECLAR[*1]     // Global linkage
             |(id                           // functions starting with an id:
                ( formula    PARSER[*1]     // Parsing formula
                | sequencer  GENERATOR[*1]  // Code generator
                | optimizer  ISO[*1]        // Optimizer
                | pseudo_op  PRODUCTION[*1] // Pseudo instruction
                | emitor_op  MACHOP[*1]     // Machine instruction
                )        // All the above start with an identifier
              \ (ERRORX["Syntax error."]
                 garbol);                    // skip over error.

// Zwróć uwagę na fakt, że identyfikator jest uwzględniany, a następnie łączony podczas tworzenia drzewa.

formula =   ("==" syntax  :BCKTRAK   // backtrack grammar formula
            |'='  syntax  :SYNTAX    // grammar formula.
            |':'  chclass :CLASS     // character class define
            |".." token   :TOKEN     // token formula
              )';' !2                // Combine node name with id 
                                     // parsed in calling declaration 
                                     // formula and tree produced
                                     // by the called syntax, token
                                     // or character class formula.
                $(-(.NL |"/*") (.ANY|.STOP)); Comment ; to line separator?

chclass = +[ letter $('|' letter) ]+;// a simple list of character codes
                                     // except 
letter  = char | number | id;        // when including another class

syntax  = seq ('|' alt1|'\' alt2 |--);

alt1    = seq:ALT!2 ('|' alt1|--);  Non-backtrack alternative sequence.

alt2    = seq:BKTK!2 ('\' alt2|--); backtrack alternative sequence

seq     = +[oper $oper]+;

oper    = test | action | '(' syntax ')' | comment; 

test    = string | id ('[' (arg_list| ,NILL) ']':GENCALL!2|.EMPTY);

action  = ':' id:NODE!1
        | '!' number:MAKTREE!1
        | "+["  seq "]+" :MAKLST!1;

//     C style comments
comment  = "//" $(-.NL .ANY)
         | "/*" $(-"*/" .ANY) "*/";

Warto zauważyć, jak język analizatora składni obsługuje komentowanie i odzyskiwanie po błędzie.

Myślę, że odpowiedziałem na pytanie. Po napisaniu dużej części następcy SLIC, język cc sam w sobie tutaj. Na razie nie ma dla niego kompilatora. Ale mogę ręcznie skompilować go do kodu asemblera, nagich funkcji asm c lub c ++.

Tak, możesz napisać kompilator dla języka w tym języku. Nie, nie potrzebujesz pierwszego kompilatora, aby ten język mógł się uruchomić.

To, czego potrzebujesz do bootstrap, to implementacja języka. Może to być kompilator lub tłumacz.

Historycznie języki były zwykle uważane za języki interpretowane lub kompilowane. Tłumacze pisemni napisano tylko dla pierwszego, a kompilatory napisano tylko dla drugiego. Zwykle więc, jeśli kompilator miałby zostać napisany dla języka, pierwszy kompilator byłby napisany w innym języku, aby go załadować, a następnie, opcjonalnie, kompilator zostałby napisany ponownie dla języka tematu. Ale zamiast tego jest napisanie tłumacza w innym języku.

To nie tylko teoretyczne. Tak się składa, że ​​robię to teraz sam. Pracuję nad kompilatorem dla języka Salmon, który sam opracowałem. Najpierw stworzyłem kompilator Salmon w C, a teraz piszę kompilator w Salmon, dzięki czemu mogę uruchomić kompilator Salmon bez konieczności tworzenia kompilatora dla Salmon w innym języku.

Może możesz napisać BNF opisujący BNF.