Jak utworzyć analizator składni AST, który dopuszcza błędy składni?

Question

Po pierwsze, co przeczytać na temat analizowania i budowania AST?

Jak utworzyć parser dla języka (takiego jak SQL), który zbuduje AST i pozwoli na błędy składni?

Na przykład dla "3 + 4 * 5":

+ 
/\ 
3 * 
/\ 
    4 5 

I "3 + 4 * +" z powodu błędu składni, parser będzie odgadnąć, że użytkownik rozumie:

+ 
/\ 
3 * 
/\ 
    4 + 
    /\ 
    ? ? 

Od czego zacząć?

SQL:

SELECT_________________ 
/   \   \ 
    .   FROM  JOIN 
/\   |  / \ 
a city_name people address ON 
           | 
           =______________ 
          /    \ 
           .____    . 
          / \   /\ 
          p address_id  a id 

Answer 1

Standardowa odpowiedź na pytanie, jak zbudować parser (które budują ASTs) jest czytać standardowe teksty na kompilacji. Kompilator "Dragon" Aho i Ullmana jest dość klasyczny. Jeśli nie masz cierpliwości, aby uzyskać najlepsze materiały referencyjne, będziesz miał więcej problemów, ponieważ dostarczają teorii i badają subtelności. Ale here is my answer dla osób w pośpiechu, budowanie parserów rekurencyjnych.

Można budować parsery z wbudowanym odzyskiwaniem po błędzie. Jest wiele artykułów na ten temat, gorący temat w latach osiemdziesiątych. Sprawdź Google Scholar, poluj na "naprawę błędów składni". Podstawową ideą jest to, że parser, napotykając błąd parsowania, przechodzi do jakiegoś znanego beacona (";" ogranicznik instrukcji jest dość popularny w językach podobnych do języka C, dlatego zostałeś poproszony o komentarz, jeśli twój język terminatory instrukcji) lub proponuje różne usuwanie lub wstawianie strumienia wejściowego w celu wspięcia się w punkcie błędu składni. Sama różnorodność takich programów jest zaskakująca. Kluczową ideą jest zazwyczaj uwzględnienie jak największej liczby punktów informacyjnych o numerze . Jedna z najbardziej intrygujących pomysłów, jakie kiedykolwiek widziałem, zawierała parsery, z których jeden prowadził N tokenów przed sobą, szukał min lądowych składni, a drugi parser naprawiał błędy karmy na podstawie dostępnych tokenów N, zanim napotkał błąd składni. Dzięki temu drugi parser może działać inaczej, zanim dojdzie do błędu składni. Jeśli tego nie zrobisz, większość analizatorów wyrzuci lewy kontekst i straci zdolność do naprawy. (Nigdy nie wprowadziły taki system.)

wybór rzeczy do wstawienia często mogą pochodzić z informacji wykorzystywanych do budowania parser (często Pierwszy i Śledź zestawy) w pierwszej kolejności. Jest to względnie łatwe w przypadku parserów L (AL) R, ponieważ tabele parse zawierają niezbędne informacje i są dostępne dla analizatora składni w punkcie, w którym napotkał błąd. Jeśli chcesz zrozumieć, jak to zrobić, musisz zrozumieć teorię (oops, znowu jest ta książka kompilatora), jak konstruuje się parsery. (Z powodzeniem wdrożyłem ten program kilka razy).

Bez względu na to, co robisz, naprawa błędów składniowych niewiele nie pomaga, ponieważ jest prawie niemożliwe, aby zgadnąć, co pisarz parsowanego dokumentu faktycznie zamierzał. Sugeruje to, że fantazyjne schematy nie będą naprawdę pomocne. Trzymam się prostych; ludzie są zadowoleni, gdy otrzymają raport o błędach i pewną półobjętą kontynuację parsowania.

Prawdziwym problemem z toczeniem własnego parsera dla prawdziwego języka jest to, że prawdziwe języki są nieprzyjemnymi bałaganem; ludzie budujący prawdziwe implementacje robią to źle i zamarzają w kamieniu ze względu na istniejące podstawy kodu, albo nalegają na zginanie/ulepszanie języka (standardy są dla żon, gadżety są dla marketingu), ponieważ jest cool. Spodziewaj się poświęcić wiele czasu na ponowną kalibrację, która według ciebie jest gramatyczna, wbrew prawdzie prawdziwego kodu. Zasadniczo, jeśli chcesz mieć działający parser, lepiej zdobyć taki, który ma zapis, a nie samodzielnie.

Lekcja dla większości ludzi, którzy są piekielnie zgięci, aby zbudować parser, nie jest, jest to, że jeśli chcą wszystko, co przydatne z wyników analizy lub drzewa, będą potrzebowali o wiele więcej podstawowych maszyn niż tylko parser. Sprawdź mój bio za "Life After Parsing".

Answer 2

Są dwie rzeczy parser mógłby zrobić:

1. zgłosić błąd i mieć użytkownik spróbuj ponownie.
2. Napraw błąd i kontynuuj.

Ogólnie rzecz biorąc pierwszy jest łatwiejszy (i bezpieczniejszy). Nie zawsze może być wystarczająco dużo informacji, aby parser mógł wywnioskować intencję, gdy składnia jest błędna. W zależności od okoliczności może być niebezpieczne wykonywanie naprawy, która sprawia, że ​​dane wejściowe są poprawne pod względem składni, ale semantycznie niepoprawne.

Napisałem kilka zwiniętych ręcznie parserów recursive dla małych języków. Podczas pisania kodu w celu wyraźnego interpretowania reguł gramatycznych (w przeciwieństwie do korzystania z parser-generatora), można łatwo wykryć błędy, ponieważ następny token nie pasuje do reguły produkcji. Wygenerowane parsery mają tendencję do wypowiadania uproszczonego "oczekiwanego $ (TOKEN_TYPE) tutaj", co nie zawsze jest użyteczne dla użytkownika. W przypadku ręcznego analizatora składni często łatwiej jest podać bardziej szczegółowy komunikat diagnostyczny, ale może to być czasochłonne, aby uwzględnić każdy przypadek.

Jeśli Twoim celem jest zgłoszenie problemu, ale kontynuowanie analizowania (aby można było sprawdzić, czy występują dodatkowe problemy), możesz umieścić specjalny węzeł AST w drzewie w punkcie błędu. Dzięki temu drzewo nie rozpada się.

Następnie należy ponownie zsynchronizować do pewnego punktu poza błędem, aby kontynuować przetwarzanie. Jak wspomniała Ira Baxter w swojej odpowiedzi, możesz szukać tokenu, takiego jak ";", który oddziela zdania. Prawidłowe tokeny do odszukania zależą od języka, który analizujesz. Inną możliwością jest odgadnięcie, co oznacza użytkownik (np. Wyciągnięcie dodatkowego tokena lub innego tokena w momencie wykrycia błędu), a następnie kontynuowanie. Jeśli napotkasz inny błąd składni w ciągu kilku następnych tokenów, możesz wycofać się, dokonać innego wyniku i spróbować ponownie.