Piszę mały interpreter dla prostego języka BASIC, jako ćwiczenie na mikrokontrolerze AVR w C przy użyciu łańcucha narzędzi avr-gcc. Zastanawiam się jednak, czy istnieją jakieś narzędzia open source, które pomogłyby mi w pisaniu leksera i parsera.
Gdybym napisał to, aby działał na moim Linuksie, mógłbym użyć flex / bison. Teraz, gdy ograniczyłem się do platformy 8-bitowej, muszę to wszystko zrobić ręcznie, czy nie?
Odpowiedzi:
Zaimplementowałem parser dla prostego języka poleceń przeznaczonego dla ATmega328p . Ten układ ma 32 KB ROM i tylko 2 KB RAM. Pamięć RAM jest zdecydowanie ważniejszym ograniczeniem - jeśli nie jesteś jeszcze przywiązany do konkretnego chipa, wybierz taki, który ma jak najwięcej pamięci RAM. To znacznie ułatwi ci życie.
Na początku rozważałem użycie flex / bison. Zdecydowałem się na tę opcję z dwóch głównych powodów:
Po odrzuceniu Flex & Bison zacząłem szukać innych narzędzi do generowania. Oto kilka, które rozważałem:
Możesz również rzucić okiem na porównanie Wikipedii .
Ostatecznie skończyło się na ręcznym kodowaniu zarówno leksera, jak i parsera.
Do analizowania użyłem rekurencyjnego parsera zstępującego. Myślę, że Ira Baxter wykonał już odpowiednią robotę, omawiając ten temat, i jest wiele samouczków online.
Dla mojego leksera napisałem wyrażenia regularne dla wszystkich moich terminali, sporządziłem diagram równoważnej maszyny stanów i zaimplementowałem ją jako jedną gigantyczną funkcję, używając gotodo przeskakiwania między stanami. To było żmudne, ale wyniki działały świetnie. Nawiasem mówiąc, gotojest to świetne narzędzie do implementowania maszyn stanu - wszystkie twoje stany mogą mieć wyraźne etykiety tuż obok odpowiedniego kodu, nie ma wywołania funkcji ani narzutu zmiennych stanu i jest to tak szybkie, jak to tylko możliwe. C naprawdę nie ma lepszej konstrukcji do budowania maszyn statycznych.
Coś do przemyślenia: leksery to tak naprawdę tylko specjalizacja parserów. Największą różnicą jest to, że zwykłe gramatyki są zwykle wystarczające do analizy leksykalnej, podczas gdy większość języków programowania ma (głównie) gramatyki bezkontekstowe. Więc naprawdę nic nie powstrzymuje cię przed zaimplementowaniem leksera jako rekurencyjnego parsera zstępującego lub użyciem generatora parsera do napisania leksera. Zwykle nie jest to tak wygodne, jak korzystanie z bardziej specjalistycznego narzędzia.
Jeśli chcesz mieć łatwy sposób kodowania parserów lub masz mało miejsca, powinieneś ręcznie zakodować rekursywny parser zstępujący; są to zasadniczo parsery LL (1). Jest to szczególnie efektywne w przypadku języków, które są tak „proste” jak Basic. (Kilka z nich zrobiłem w latach 70-tych!). Dobra wiadomość jest taka, że nie zawierają one żadnego kodu biblioteki; po prostu to, co piszesz.
Są dość łatwe do zakodowania, jeśli masz już gramatykę. Najpierw musisz pozbyć się lewych reguł rekurencyjnych (np. X = XY). Generalnie jest to dość łatwe, więc zostawiam to jako ćwiczenie. (Nie musisz tego robić w przypadku reguł tworzenia list; zobacz dyskusję poniżej).
Następnie, jeśli masz regułę BNF w postaci:
X = A B C ;
utwórz podprogram dla każdego elementu w regule (X, A, B, C), który zwraca wartość logiczną mówiącą „Widziałem odpowiednią konstrukcję składniową”. W przypadku X kod:
subroutine X()
if ~(A()) return false;
if ~(B()) { error(); return false; }
if ~(C()) { error(); return false; }
// insert semantic action here: generate code, do the work, ....
return true;
end X;
Podobnie dla A, B, C.
Jeśli token jest terminalem, napisz kod, który sprawdza strumień wejściowy pod kątem ciągu znaków tworzących terminal. Np. W przypadku liczby sprawdź, czy strumień wejściowy zawiera cyfry i przesuń kursor strumienia wejściowego poza cyfry. Jest to szczególnie łatwe, jeśli przetwarzasz bufor (w przypadku BASIC-a masz tendencję do pobierania jednej linii na raz), po prostu zwiększając lub nie przesuwając do przodu wskaźnika skanowania bufora. Ten kod jest zasadniczo częścią leksera parsera.
Jeśli twoja reguła BNF jest rekurencyjna ... nie martw się. Po prostu zakoduj wywołanie rekurencyjne. Obsługuje reguły gramatyczne, takie jak:
T = '(' T ')' ;
Można to zakodować jako:
subroutine T()
if ~(left_paren()) return false;
if ~(T()) { error(); return false; }
if ~(right_paren()) { error(); return false; }
// insert semantic action here: generate code, do the work, ....
return true;
end T;
Jeśli masz regułę BNF z alternatywą:
P = Q | R ;
następnie kod P z alternatywnymi opcjami:
subroutine P()
if ~(Q())
{if ~(R()) return false;
return true;
}
return true;
end P;
Czasami napotkasz reguły tworzenia list. Zwykle są one rekurencyjne i ten przypadek jest łatwy do obsłużenia. Podstawową ideą jest użycie raczej iteracji niż rekurencji, co pozwala uniknąć nieskończonej rekurencji, którą można uzyskać robiąc to w „oczywisty” sposób. Przykład:
L = A | L A ;
Możesz to zakodować za pomocą iteracji jako:
subroutine L()
if ~(A()) then return false;
while (A()) do { /* loop */ }
return true;
end L;
W ten sposób możesz zakodować kilkaset reguł gramatycznych w dzień lub dwa. Jest więcej szczegółów do uzupełnienia, ale podstawy tutaj powinny być więcej niż wystarczające.
Jeśli masz naprawdę mało miejsca, możesz zbudować maszynę wirtualną, która wdroży te pomysły. To właśnie robiłem w latach 70., kiedy można było uzyskać 8-bitowe 16-bitowe słowa.
Jeśli nie chcesz tego kodować ręcznie, możesz zautomatyzować to za pomocą metakompilatora ( Meta II ), który generuje zasadniczo to samo. To niesamowita techniczna zabawa, która naprawdę pochłania całą pracę, nawet w przypadku dużych gramatyk.
Sierpień 2014:
Otrzymuję wiele próśb „jak zbudować AST z parserem”. Aby uzyskać szczegółowe informacje, które zasadniczo rozwijają tę odpowiedź, zobacz moją inną odpowiedź SO https://stackoverflow.com/a/25106688/120163
Lipiec 2015:
Jest wielu ludzi, którzy chcą napisać prostą ocenę wyrażeń. Możesz to zrobić, wykonując te same czynności, które sugeruje powyższy link „Kreator AST”; po prostu wykonuj arytmetykę zamiast budować węzły drzewa. Oto ewaluator wyrażeń wykonany w ten sposób .
GCC może kompilować krzyżowo na różne platformy, ale uruchamiasz flex i bison na platformie, na której uruchamiasz kompilator. Po prostu wypluwają kod C, który następnie kompiluje kompilator. Przetestuj, aby zobaczyć, jak duży jest wynikowy plik wykonywalny. Zauważ, że mają biblioteki uruchomieniowe ( libfl.aitp.), Które będziesz musiał również skompilować krzyżowo do celu.
Wypróbuj Boost :: Spirit. Jest to biblioteka zawierająca tylko nagłówki, do której możesz wrzucić i zbudować bardzo szybki, czysty parser całkowicie w C ++. Przeciążone operatory w C ++ są używane zamiast specjalnego pliku gramatyki.
Zamiast wymyślać koło na nowo, spójrz na LUA: www.lua.org . Jest to język interpretacyjny, który ma być osadzony w innym oprogramowaniu i używany w małych systemach, takich jak systemy wbudowane. Wbudowane drzewo parsowania składni proceduralnej, logika sterowania, obsługa matematyki i zmiennych - nie ma potrzeby ponownego odkrywania czegoś, co tysiące innych już debugowało i wykorzystywało. Jest rozszerzalny, co oznacza, że możesz wzbogacać gramatykę, dodając własne funkcje C.