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

10

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 .

Alexander Morou
źródło
8
Tekst na ścianie. Nie bierz tego źle, doceniam dokładnie wyjaśniony problem. W tym przypadku jest to po prostu trochę zbyt szczegółowe. Z tego, co zebrałem, pytasz, jakie funkcje powinny być zawarte w parserze gramatyki lub jak zrobić go bez rozpoczynania od zera? Edytuj, aby odpowiedzieć na następujące pytania (nie musisz przepisywać, po prostu dołącz do końca w podsumowaniu): Na czym polega Twój problem? Jakie ograniczenia wiążą Cię w możliwych rozwiązaniach twojego problemu (musi być szybki, musi być LL * itd.)?
Neil
1
Proszę o wgląd w zestaw funkcji. Nacisk kładziony jest na łatwość użycia. Trudność polega na uzyskaniu kogoś, kto nie zna projektu, wglądu w projekt, aby byli poinformowani o jego ukierunkowaniu. Nie pytam „jak to zrobić”, pytam o użyteczność. Doceniamy sugestie dotyczące przycięcia pytania.
Allen Clark Copeland Jr
1
Dla mnie nie jest oczywiste, o co chodzi w tym projekcie. Na przykład od czasów yacc widzieliśmy wiele generatorów parserów. Czym różni się Twój OILexer? Co nowego
Ingo
1
Celem tego projektu jest uproszczenie generowania parsera. Podobne tak, jak YACC / Bison i FLEX / LEX. Główną różnicą jest unikanie złożoności związanej z tymi programami. Utrzymanie prostoty i konkretności jest głównym celem. Właśnie dlatego stworzyłem format pozbawiony nieparzystych przekrojów, ale raczej celem jest upodobnienie go do zwykłego programowania: specyficznego tylko dla rozwoju języka. Tokeny definiuje się za pomocą „: =” po nazwie, reguły definiuje się za pomocą :: = po nazwie. Szablony używają „<” i „>” jako argumentów, po których następuje „:: =”, ponieważ dzielą one składnię reguł.
Allen Clark Copeland Jr
3
To piekielne skupienie na analizie składni wydaje się niewłaściwe; jest to dobrze rozwiązany problem i prawie nie wgłębia się w to, czego potrzebujesz do przetwarzania języków programowania. Google za mój esej na temat „życia po analizie”.
Ira Baxter,

Odpowiedzi:

5

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).


źródło
Zredagowałem treść pytania, aby umieścić link do PrecedenceHelper w pocisku o treści „Szablony”. Umożliwia krotki tablic parametrów, więc jeśli masz cztery parametry, każda tablica parametrów, szablon musi być używany w zestawach czterech argumentów.
Allen Clark Copeland Jr
Głównym powodem, dla którego chcesz zbudować plik CST, jest ogólny układ analizowanego pliku. Jeśli chcesz wydrukować dokument, najlepszym rozwiązaniem jest użycie CST, ponieważ ich nazwa AST oznacza brak informacji do obsługi nieparzystych odstępów, które mógłby przechwycić CST. Przekształcenie CST jest zwykle dość łatwe, jeśli jest to dobry CST.
Allen Clark Copeland Jr
Zredagowałem pytanie ponownie na temat wbudowanych funkcji dostępnych do użycia.
Allen Clark Copeland Jr
Wydaje mi się, że nie spisałem się dobrze, wyrażając swoje zdanie na temat szablonów / funkcji: miałem na myśli to, że ponieważ nigdy nie możesz mieć wystarczająco dużo, system nie powinien próbować ich rozgryzać z wyprzedzeniem: użytkownik musi mieć możliwość tworzenia jego własny.
1
Znalazłem jedno podejście szczególnie przydatne do zgłaszania błędów z nieskończonym nawracaniem (Packrat): każda reguła produkcyjna jest opatrzona adnotacjami o błędach (sformułowana jako „bla-bla-blah oczekuje”), a po awarii taka wiadomość jest przechowywana w strumieniu w ten sam sposób jako zapamiętane tokeny. Jeśli wszystkich awarii nie da się naprawić (parsowanie zostało zakończone przed osiągnięciem końca strumienia), najbardziej odpowiedni jest komunikat o błędzie znajdujący się po prawej stronie (lub zbiór takich komunikatów). Jest to najłatwiejsza rzecz do zrobienia, oczywiście istnieją sposoby na jej udoskonalenie za pomocą większej liczby adnotacji.
SK-logic
5

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ź.

ludzik
źródło
To jest jedna rzecz, którą planuję zrobić. Aby pomóc w mojej wiedzy na temat domeny, mój przyjaciel zasugerował ręczne napisanie rzeczywistego parsera, aby poczuć automatyzację. Jedną rzecz zdałem sobie sprawę dość szybko: parsery są złożone i są rzeczy, które robimy ręcznie, co upraszcza proces. Reguły i szablony mają tę samą składnię; jednak istnieją elementy języka, które są poprawne w szablonach, ale nie w regułach, istnieją stany wewnętrzne, które obsługują to zadanie. Co przyszło mi do głowy do głowy: reguły powinny umożliwiać określenie pomocy ścieżek, aby ułatwić dzielenie się regułami podrzędnymi.
Allen Clark Copeland Jr
... powinno to być dość łatwe do przeniesienia do automatyki, ale wymagałoby od automatyki warunków zależnych od stanu. Popracuję nad tym i skontaktuję się z tobą. ANTLR używa automatyzacji stanu skończonego do obsługi cykli powiedzmy: „T” *, gdzie, jak użyję go do obsługi większości procesu parsowania, ponieważ redukcje powinny być czystsze niż w stanach, gdy reguła zawiera ponad 800 odmian (spowoduje to wzdęcie szybko jako kod spaghetti w standardowej formie if / else.)
Allen Clark Copeland Jr
0

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.

Ingo
źródło
Tak, miło jest nie mieć takich arbitralnych ograniczeń. Jaki jest jednak przykład lewostronnej rekurencji, której nie można zastąpić operatorem powtarzania (takim jak wyrażenia regularne *lub +kwantyfikatory)? Przyznaję, że moja wiedza w tej dziedzinie jest ograniczona, ale nigdy nie spotkałem się z lewostronną rekurencją, której nie da się przekształcić w powtórzenie. Znalazłem też bardziej przejrzystą wersję powtórzeń (chociaż to tylko osobiste preferencje).
1
@MattFenwick Zobacz moją edycję. Zwróć uwagę, jak bezpośredni kierunek składni prowadzi do prostych i naturalnych działań semantycznych (np.) W celu utworzenia drzewa składni. Choć z powtarzaniem, (który nie jest dostępny w yacc, btw), myślę, że często trzeba sprawdzić, czy masz pustą listę, pojedyncza, itp
Ingo
Dziękuję za odpowiedź. Myślę, że teraz lepiej zrozumieć - Wolałbym napisać te przykłady, jak list = sepBy1(',', elem)i funapp = term{+}(i oczywiście sepBy1i +będą realizowane w zakresie lewej / prawej rekursji i produkować standardowe drzew składniowych). Więc nie chodzi o to, że myślę, że rekurencja w lewo i w prawo jest zła, tylko o to, że czuję, że są na niskim poziomie i chcieliby użyć abstrakcji na wyższym poziomie, jeśli to możliwe, aby wyjaśnić sprawę. Dzięki jeszcze raz!
1
Nie ma za co @MattFenwick. Ale może to kwestia gustu. Dla mnie rekurencja jest (przynajmniej w kontekście języków, które są z natury rekurencyjne lub całkowicie nieciekawe), bardziej naturalnym sposobem myślenia o tym. Drzewo jest również rekurencyjną strukturą danych, więc nie widzę potrzeby powrotu do iteracji w celu symulacji rekurencji. Ale oczywiście preferencje są różne.
Ingo