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
lex,yaccibison.