Czy istnieje alternatywa dla flex/bison, która może być używana w 8-bitowych systemach wbudowanych?

Jeśli potrzebujesz łatwego sposobu kodowania parserów, lub jesteś ograniczony przestrzenią, powinieneś ręcznie kodować rekurencyjny Parser opadania; są to zasadniczoLL (1) parsery. Jest to szczególnie skuteczne w przypadku języków, które są tak "proste" jak podstawowe. (Zrobiłem kilka z nich w latach 70-tych!). Dobrą wiadomością jest to, że nie zawierają one żadnego kodu bibliotecznego; tylko to, co piszesz.

Są dość łatwe do zakodowania, jeśli masz już gramatykę. Najpierw trzeba pozbyć się lewych reguł rekurencyjnych (np., X = X Y). Jest to ogólnie dość łatwe do zrobienia, więc pozostawiam to jako ćwiczenie. (Nie musisz tego robić dla reguł tworzenia list; patrz dyskusja poniżej).

Wtedy jeśli masz reguła BNF postaci:

 X = A B C ;

Tworzy podprogram dla każdego elementu w regule (X, A, B, C), który zwraca wartość logiczną mówiąc: "Widziałem odpowiedni konstrukt składniowy". Dla 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 sprawdzający strumień wejściowy dla ciąg znaków, który składa się na terminal. Np. dla liczby sprawdź, czy strumień wejściowy zawiera cyfry i kursor strumienia wejściowego obok cyfr. Jest to szczególnie łatwe, jeśli są parsowanie z bufora (dla BASIC, masz tendencję do uzyskania jednej linii w czasie) po prostu postępuj lub nie postępuj wskaźnik skanowania bufora. Ten kod jest zasadniczo częścią lexer parsera.

Jeśli reguła BNF jest rekurencyjna... nie martw się. Wystarczy zakodować wywołanie rekurencyjne. Obsługuje reguły gramatyczne like:

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 wyborami:

subroutine P()
    if ~(Q())
        {if ~(R()) return false;
         return true;
        }
    return true;
end P;

Czasami napotkasz reguły tworzenia listy. Te zwykle pozostają rekurencyjne, a sprawa jest łatwa do załatwienia. Przykład:

L  =  A |  L A ;

Możesz to zakodować jako:

subroutine L()
    if ~(A()) then return false;
    while (A()) do // loop
    return true;
end L;

Możesz w ten sposób zakodować kilkaset reguł gramatycznych w ciągu dnia lub dwóch. Jest więcej szczegółów do wypełnienia, ale podstawy tutaj powinny wystarczy.

Jeśli jesteś naprawdę Ciasno na przestrzeni, możesz zbudować maszynę Wirtualną, która implementuje te pomysły. To właśnie robiłem w latach 70-tych, kiedy 8K 16 bitowych słów było tym, co można było dostać.

Jeśli nie chcesz kodować tego ręcznie, możesz zautomatyzować go za pomocą metacompilera ( Meta II ), który produkuje zasadniczo to samo. To oszałamiająca zabawa techniczna i naprawdę wymaga całej pracy, nawet dla dużych grammars.

Dostaję wiele próśb o "jak zbudować AST z parserem". Po szczegóły na ten temat, który zasadniczo rozwija tę odpowiedź, zobacz moją drugą odpowiedź SO https://stackoverflow.com/a/25106688/120163

Lipiec 2015:

Jest wielu ludzi, którzy chcą napisać prosty ewaluator wyrażeń. Możesz to zrobić, wykonując te same rzeczy, co sugeruje powyższy link "AST builder"; po prostu rób arytmetykę zamiast budować węzły drzew. Oto ewaluator wyrażenia zrobiony w ten sposób .

Możesz użyć flex/bison na Linuksie z jego natywnym gcc do wygenerowania kodu, który następnie skompilujesz ze swoim gcc AVR dla osadzonego celu.

GCC może kompilować na różnych platformach, ale uruchamiasz flex i bison na platformie, na której uruchamiasz kompilator. Po prostu wypluwają kod C, który kompilator następnie buduje. Przetestuj go, aby zobaczyć, jak duży jest wynikowy plik wykonywalny. Zauważ, że mają biblioteki czasu pracy (libfl.a itd.), że będziesz również musiał krzyżować kompilację do celu.

Spróbuj Boost:: Spirit. Jest to biblioteka tylko nagłówkowa, do której możesz wpaść i zbudować bardzo szybki, czysty parser całkowicie w C++. Przeciążone operatory w C++ są używane zamiast specjalnego pliku gramatycznego.

Zamiast wymyślać koło, spójrz na LUA: www.lua.org . jest to język interpretacyjny przeznaczony do osadzania w innym oprogramowaniu i używany w małych systemach, takich jak systemy wbudowane. Wbudowane drzewo parsowania składni proceduralnej, logika sterowania, matematyka i obsługa zmiennych-nie ma potrzeby wymyślania na nowo czegoś, co tysiące innych już debugowało i używało. I jest rozszerzalny, co oznacza, że możesz dodać do gramatyki, dodając własne funkcje C.