Pisanie kompilatora kompilatora - wgląd w użytkowanie i funkcje

Jest to część serii pytań, które koncentrują się na siostrzanym projekcie Abstraction Project, którego celem jest wyodrębnienie pojęć używanych w projektowaniu języka w formie ram. Projekt siostrzany nazywa się OILexer, który ma na celu skonstruowanie analizatora składni z plików gramatycznych, bez użycia wstrzykiwania kodu do dopasowań.

Niektóre inne strony związane z tymi pytaniami, związane z typowaniem strukturalnym, można wyświetlić tutaj , a łatwość użycia - tutaj . Meta-temat związany z zapytaniem dotyczącym frameworka i odpowiedniego miejsca do opublikowania można znaleźć tutaj .

Przechodzę do punktu, w którym zaczynam rozpakowywać drzewo parsowania z danej gramatyki, a następnie parser Recursive Descent, który używa DFA do rozpoznawania ścieżek do przodu (podobnie do LL (*) ANTLR 4), więc ja pomyślałem, że otworzę to, aby uzyskać wgląd.

Jakie funkcje są idealne w kompilatorze analizatora składni?

Jak na razie tutaj jest krótki przegląd tego, co zostało wdrożone:

1. Szablony
2. Spójrz w przyszłość, wiedząc, co jest ważne w danym momencie.
3. Reguła „Deliteralizacja” bierze literały w ramach reguł i ustala, z którego tokena pochodzą.
4. Niedeterministyczne automaty
5. Automaty deterministyczne
6. Prosta leksykalna maszyna stanów do rozpoznawania tokenów
7. Metody automatyzacji tokenów:
   • Skanowanie - przydatne w przypadku komentarzy: Komentarz: = "/ *" Skanowanie („* /”);
   • Odejmij - przydatne dla identyfikatorów: Identyfikator: = Odejmij (IdentifierBody, Słowa kluczowe);
     • Zapewnia, że ​​identyfikator nie akceptuje słów kluczowych.
   • Kodowanie - koduje automatyzację jako liczbę serii X podstawowych przejść N.
     • UnicodeEscape: = "\\ u" BaseEncode (IdentifierCharNoEscape, 16, 4);
       • Powoduje, że Unicode ucieka w systemie szesnastkowym, z 4 przejściami szesnastkowymi. Różnica między tym a: [0-9A-Fa-f] {4} to wynikowa automatyzacja z Encode ogranicza dozwolony zestaw wartości szesnastkowych do zakresu IdentifierCharNoEscape. Więc jeśli podasz go, wersja kodująca nie zaakceptuje wartości. Takie rzeczy mają poważne zastrzeżenie: używaj oszczędnie. Powstała automatyzacja może być dość złożona.

To, co nie jest zaimplementowane, to generowanie CST, muszę dostosować deterministyczne automatyzacje, aby przenieść odpowiedni kontekst, aby to zadziałało.

Dla wszystkich zainteresowanych przesłałem dość wydrukowaną oryginalną formę projektu T * y♯ . Każdy plik powinien zawierać link do każdego innego pliku, zacząłem linkować w poszczególnych regułach, aby ich przestrzegać, ale zajęłoby to zbyt długo (łatwiej byłoby zautomatyzować!)

Jeśli potrzebujesz więcej kontekstu, opublikuj odpowiednio.

Edytuj 5-14-2013 : Napisałem kod do tworzenia wykresów GraphViz dla automatów stanów w danym języku. Oto wykres GraphViz z AssemblyPart . Członkowie powiązani w opisie języka powinni mieć nazwę pliku nazwa_pliku.txt w swoim folderze względnym z wykresem dla tej reguły. Część opisu języka zmieniła się od czasu opublikowania przykładu, wynika to z uproszczenia gramatyki. Oto interesujący obraz graphviz .

To doskonałe pytanie.

Ostatnio pracuję nad wieloma analizami, a IMHO niektóre z kluczowych funkcji to:

• programowy interfejs API - dzięki czemu można go używać z poziomu języka programowania, najlepiej po prostu importując bibliotekę. Może mieć również interfejs GUI lub BNF, ale kluczem jest programowy, ponieważ możesz ponownie użyć narzędzi, IDE, analizy statycznej, testowania, funkcji abstrakcji języka, znajomości programisty, generatora dokumentacji, procesu kompilacji, itp. Ponadto możesz interaktywnie grać z małymi parserami, co znacznie zmniejsza krzywą uczenia się. Te powody umieszczają go na szczycie mojej listy „ważnych funkcji”.

• raportowanie błędów, jak wspomniano @ guysherman. Kiedy zostanie znaleziony błąd, chcę wiedzieć, gdzie był błąd i co się działo, gdy się pojawił. Niestety nie udało mi się znaleźć dobrych zasobów do wyjaśnienia, w jaki sposób generować przyzwoite błędy, gdy pojawia się gra wsteczna. (Chociaż uwaga @ komentarz Sk-logic poniżej).

• częściowe wyniki. Gdy parsowanie się nie powiedzie, chcę być w stanie zobaczyć, co zostało pomyślnie przeanalizowane z części danych wejściowych, która była przed lokalizacją błędu.

• abstrakcja. Nigdy nie możesz zbudować wystarczającej liczby funkcji, a użytkownik zawsze będzie potrzebował więcej, więc próba ustalenia z góry wszystkich możliwych funkcji jest skazana na niepowodzenie. Czy to masz na myśli szablony?

• Zgadzam się z twoim numerem 2 (przewidywanie z wyprzedzeniem). Myślę, że to pomaga generować dobre raporty błędów. Czy przydaje się do czegoś innego?

• obsługa budowania drzewa parsowania podczas analizy, być może:

  • konkretne drzewo składniowe, dla którego struktura drzewa odpowiada bezpośrednio gramatyce i zawiera informacje o układzie do zgłaszania błędów w późniejszych fazach. W takim przypadku klient nie powinien nic robić , aby uzyskać odpowiednią strukturę drzewa - powinno to zależeć bezpośrednio od gramatyki.
  • abstrakcyjne drzewo składniowe. W takim przypadku użytkownik może manipulować dowolnym drzewem parsowania

• jakiś rodzaj logowania. Nie jestem tego pewien; może pokazać ślad reguł, które wypróbował parser, lub śledzić niepotrzebne tokeny, takie jak białe znaki lub komentarze, w przypadku, gdy (na przykład) chcesz użyć tokenów do wygenerowania dokumentacji HTML.

• umiejętność radzenia sobie z językami kontekstowymi. Nie jestem pewien, jak ważny jest ten język - w praktyce wydaje się, że łatwiej jest przeanalizować nadzbiór języka z gramatyką bezkontekstową, a następnie sprawdzić ograniczenia kontekstowe w kolejnych późniejszych przejściach.

• niestandardowe komunikaty o błędach, dzięki czemu mogę dostroić raporty o błędach w określonych sytuacjach i być może szybciej zrozumieć i naprawić problemy.

Z drugiej strony nie uważam, aby korekcja błędów była szczególnie ważna - chociaż nie jestem na bieżąco z aktualnymi postępami. Zauważyłem problemy, ponieważ potencjalne poprawki dostarczane przez narzędzia są: 1) zbyt liczne i 2) nie odpowiadają faktycznym popełnionym błędom, a więc nie są aż tak pomocne. Mam nadzieję, że ta sytuacja ulegnie poprawie (a może już to zrobiło).

Nie mam doświadczenia w projektowaniu języka, ale kiedyś pisałem parser, kiedy tworzyłem i IDE dla silnika gry.

Moim zdaniem ważne dla ostatecznych użytkowników końcowych są komunikaty o błędach, które mają sens. Wiem, że nie jest to szczególnie wstrząsające ziemią, ale podążając za nim wstecz, jednym z kluczowych implikacji tego jest to, że musisz być w stanie unikać fałszywych trafień. Skąd pochodzą fałszywe alarmy? Pochodzą z analizatora składni przewracającego się przy pierwszym błędzie i nigdy do końca się nie regenerują. C / C ++ jest znany z tego (choć nowsze kompilatory są nieco mądrzejsze).

Czego więc potrzebujesz? Myślę, że zamiast po prostu wiedzieć, co jest / nie jest ważne w danym momencie, musisz wiedzieć, jak wziąć to, co jest nieważne i wprowadzić minimalną zmianę, aby było prawidłowe - abyś mógł dalej analizować bez generowania fałszywych błędów związanych do twojego rekurencyjnego zejścia, który jest zdezorientowany. Możliwość zbudowania analizatora składni, który może generować te informacje, zapewnia nie tylko bardzo wydajny analizator składni, ale także otwiera fantastyczne funkcje oprogramowania, które go analizuje.

Zdaję sobie sprawę, że mogę sugerować coś naprawdę trudnego lub głupio oczywistego, przepraszam, jeśli tak jest. Jeśli nie tego szukasz, chętnie usunę moją odpowiedź.

Gramatyka nie może mieć ograniczeń takich jak „nie pozostawiaj reguł rekurencyjnych”. To niedorzeczne, że narzędzia powszechnie stosowane obecnie mają to i mogą zrozumieć tylko ssanie gramatyki LL - prawie 50 lat po tym, jak yacc zrobił to dobrze.

Przykład prawidłowej rekurencji (przy użyciu składni yacc):

list: 
      elem                  { $$ = singleton($1); }
    | elem ',' list         { $$ = cons($1, $2);  }
    ;

Przykład dla lewej rekurencji (przy użyciu yacc synatx):

funapp:
    term                    { $$ = $1; }
    | funapp term           { $$ = application($1, $2); }
    ;

Teraz może to być „refaktoryzowane” do czegoś innego, ale w obu przypadkach konkretny rodzaj rekurencji jest po prostu „właściwym” sposobem na napisanie tego, ponieważ (w języku przykładowym) listy są rekurencyjne, podczas gdy aplikacja funkcji jest rekurencyjna .

Od zaawansowanych narzędzi można oczekiwać, że wspierają naturalny sposób zapisywania rzeczy, zamiast wymagać „refaktoryzacji” wszystkiego, co ma być rekurencyjne w lewo / w prawo od narzędzia nałożonego na jedno.