Analiza dowolnych gramatyk bezkontekstowych, głównie krótkich fragmentów

Chcę przeanalizować zdefiniowane przez użytkownika języki specyficzne dla domeny. Te języki są zazwyczaj zbliżone do notacji matematycznych (nie analizuję języka naturalnego). Użytkownicy definiują swoje DSL w notacji BNF, w następujący sposób:

expr ::= LiteralInteger
       | ( expr )
       | expr + expr
       | expr * expr

Wejście podobne 1 + ( 2 * 3 )musi zostać zaakceptowane, podczas gdy wejście podobne 1 +musi zostać odrzucone jako niepoprawne, a wejście podobne 1 + 2 * 3musi zostać odrzucone jako niejednoznaczne.

Główną trudnością jest tutaj radzenie sobie z niejednoznacznymi gramatykami w sposób przyjazny dla użytkownika. Ograniczanie gramatyki do jednoznaczności nie jest opcją: taki jest język - chodzi o to, że pisarze wolą pomijać nawiasy, gdy nie są konieczne, aby uniknąć dwuznaczności. Dopóki wyrażenie nie jest dwuznaczne, muszę je przeanalizować, a jeśli nie jest, muszę je odrzucić.

Mój parser musi działać na dowolnej gramatyce bezkontekstowej, nawet dwuznacznej, i musi akceptować wszystkie jednoznaczne dane wejściowe. Potrzebuję drzewa parsowania dla wszystkich zaakceptowanych danych wejściowych. W przypadku nieprawidłowych lub niejednoznacznych danych wejściowych idealnie chcę mieć dobre komunikaty o błędach, ale na początek wezmę to, co mogę.

Zazwyczaj wywołuję parser na stosunkowo krótkich wejściach, z okazjonalnie dłuższymi wejściami. Zatem asymptotycznie szybszy algorytm może nie być najlepszym wyborem. Chciałbym zoptymalizować dla dystrybucji około 80% danych wejściowych krótszych niż 20 symboli, 19% od 20 do 50 symboli i 1% rzadkich dłuższych danych wejściowych. Prędkość nieprawidłowych danych wejściowych nie jest poważnym problemem. Ponadto oczekuję modyfikacji DSL co około 1000 do 100000 danych wejściowych; Mogę poświęcić kilka sekund na przygotowanie gramatyki, a nie kilka minut.

Jaki algorytm analizowania powinienem zbadać, biorąc pod uwagę moje typowe rozmiary wejściowe? Czy raportowanie błędów powinno być czynnikiem w moim wyborze, czy też powinienem skoncentrować się na analizie jednoznacznych danych wejściowych i ewentualnie uruchomić całkowicie oddzielny, wolniejszy analizator składni, aby uzyskać informacje zwrotne o błędach?

(W projekcie, w którym tego potrzebowałem (jakiś czas temu), użyłem CYK , który nie był zbyt trudny do wdrożenia i działał odpowiednio dla moich rozmiarów wejściowych, ale nie spowodował bardzo fajnych błędów.)

Prawdopodobnie idealnym algorytmem dla twoich potrzeb jest Uogólniona analiza składniowa LL lub GLL. Jest to bardzo nowy algorytm (artykuł został opublikowany w 2010 r.). W pewnym sensie jest to algorytm Earleya wzbogacony o stos strukturalny grafów (GSS) i wykorzystujący spojrzenie z wyprzedzeniem LL (1).

Algorytm jest dość podobny do zwykłego starego LL (1), z tym wyjątkiem, że nie odrzuca gramatyk, jeśli nie są one LL (1): po prostu wypróbowuje wszystkie możliwe analizy LL (1). Używa ukierunkowanego wykresu dla każdego punktu w analizie, co oznacza, że ​​w przypadku napotkania stanu analizy, który był wcześniej rozpatrywany, po prostu łączy te dwa wierzchołki. Dzięki temu nadaje się nawet do gramatyki lewostronnej, w przeciwieństwie do LL. Aby uzyskać szczegółowe informacje na temat jego wewnętrznego funkcjonowania, przeczytaj artykuł (jest to dość czytelny papier, choć zupa z etykietą wymaga wytrwałości).

Algorytm ma wiele wyraźnych zalet związanych z Twoimi potrzebami w porównaniu z innymi ogólnymi algorytmami parsowania (o których wiem). Po pierwsze, wdrożenie jest bardzo łatwe: myślę, że tylko Earley jest łatwiejszy do wdrożenia. Po drugie, wydajność jest całkiem dobra: w rzeczywistości staje się tak szybka jak LL (1) na gramatyce, która jest LL (1). Po trzecie, odzyskanie parsowania jest dość łatwe i sprawdzenie, czy istnieje więcej niż jedna możliwa parsowanie, jest również możliwe.

Główną zaletą GLL jest to, że jest oparty na LL (1) i dlatego jest bardzo łatwy do zrozumienia i debugowania, podczas implementacji, podczas projektowania gramatyki, a także podczas analizowania danych wejściowych. Ponadto ułatwia także obsługę błędów: dokładnie wiesz, gdzie możliwe są parsowania i jak mogły być kontynuowane. Możesz łatwo podać możliwe parsowania w punkcie błędu i, powiedzmy, ostatnie 3 punkty, w których parsowały. Zamiast tego możesz spróbować wyzerować błąd i oznaczyć produkcję, nad którą pracowała najdalej pars, jako „zakończoną” dla tej analizy i sprawdzić, czy parsowanie może być kontynuowane (powiedzmy, że ktoś zapomniał nawiasów). Możesz to zrobić nawet, powiedzmy, dla 5 parsów, które uzyskały najdalej.

Jedynym minusem algorytmu jest to, że jest nowy, co oznacza, że ​​nie ma łatwo dostępnych wdrożeń. To może nie stanowić dla ciebie problemu - sam zaimplementowałem algorytm i było to dość łatwe.

Moja firma (Semantic Designs) z powodzeniem wykorzystała parsery GLR do wykonania dokładnie tego, co sugeruje OP przy analizie obu języków specyficznych dla domeny i analizowaniu „klasycznych” języków programowania za pomocą naszego zestawu narzędzi do reengineeringu DMS. Obsługuje to transformacje programu typu źródło-źródło wykorzystywane do restrukturyzacji programów na dużą skalę / inżynierii wstecznej / generowania kodu do przodu. Obejmuje to automatyczną naprawę błędów składniowych w całkiem praktyczny sposób. Wykorzystując GLR jako podstawę i kilka innych zmian (predykaty semantyczne, dane wejściowe z zestawu tokenów, a nie tylko dane z tokena ...) udało nam się zbudować parsery dla około 40 języków.

Równie ważna, jak umiejętność analizowania instancji pełnych języków, GLR okazał się również niezwykle przydatny w analizowaniu reguł przepisywania między źródłami . Są to fragmenty programu o znacznie mniejszym kontekście niż pełny program, a zatem generalnie mają większą dwuznaczność. Używamy specjalnych adnotacji (np. Nalegając, aby fraza odpowiadała konkretnej nieterminalnej gramatyce), aby pomóc rozwiązać te dwuznaczności podczas / po analizie reguł. Organizując maszynę parsującą GLR i otaczające ją narzędzia, otrzymujemy parsery do przepisywania reguł za „za darmo”, gdy mamy parser dla jego języka. Mechanizm DMS ma wbudowany aplikator przepisujący reguły, którego można następnie użyć do zastosowania tych reguł w celu przeprowadzenia pożądanych zmian kodu.

Prawdopodobnie naszym najbardziej spektakularnym wynikiem jest zdolność do analizy pełnego C ++ 14 , pomimo wszystkich dwuznaczności, z wykorzystaniem gramatyki bezkontekstowej jako podstawy. Zauważam, że wszystkie klasyczne kompilatory C ++ (GCC, Clang) zrezygnowały z tej możliwości i używają ręcznie napisanych parserów (co IMHO znacznie utrudnia ich utrzymanie, ale nie są one moim problemem). Użyliśmy tej maszyny do przeprowadzenia ogromnych zmian w architekturze dużych systemów C ++.

Pod względem wydajności nasze parsery GLR są dość szybkie: dziesiątki tysięcy linii na sekundę. Jest to znacznie poniżej obecnego stanu wiedzy, ale nie podjęliśmy poważnej próby optymalizacji tego, a niektóre wąskie gardła dotyczą przetwarzania strumienia znaków (pełny Unicode). Aby zbudować takie parsery, wstępnie przetwarzamy gramatykę bezkontekstową przy użyciu czegoś bardzo zbliżonego do generatora parsera LR (1); zwykle działa na nowoczesnej stacji roboczej w dziesięć sekund na dużych gramatyce wielkości C ++. Zaskakujące jest to, że w przypadku bardzo złożonych języków, takich jak współczesny COBOL i C ++, generowanie leksykonów zajmuje około minuty; niektóre DFA zdefiniowane w Unicode stają się dość włochate. Właśnie zrobiłem Ruby (z pełną podgramą ze względu na jego niesamowite wyrażenia regularne) jako ćwiczenie na palec; DMS może przetworzyć swój leksyk i gramatykę razem w około 8 sekund.

Istnieje wiele ogólnych parserów bezkontekstowych, które mogą analizować dwuznaczne zdania (zgodnie z niejednoznaczną gramatyką). Pochodzą one pod różnymi nazwami, zwłaszcza z programowaniem dynamicznym lub analizatorami wykresów. Najbardziej znanym i zarazem najprostszym jest prawdopodobnie używany parser CYK. Ta ogólność jest potrzebna, ponieważ musisz poradzić sobie z wieloma parsami i możesz nie wiedzieć do końca, czy masz do czynienia z dwuznacznością, czy nie.

Z tego, co mówisz, sądzę, że CYK nie jest tak złym wyborem. Prawdopodobnie nie musisz wiele zyskać, dodając predykcyjność (LL lub LR), i może to faktycznie kosztować dyskryminujące obliczenia, które powinny być łączone, a nie dyskryminowane (szczególnie w przypadku LR). Mogą również mieć odpowiedni koszt w wielkości produkowanego lasu analizującego (co może odgrywać rolę w błędach niejednoznaczności). W rzeczywistości, chociaż nie jestem pewien, jak formalnie porównać adekwatność bardziej wyrafinowanych algorytmów, wiem, że CYK zapewnia dobre współdzielenie obliczeń.

Nie wierzę teraz, że jest dużo literatury na temat ogólnych parserów CF dla dwuznacznych gramatyk, które powinny akceptować tylko jednoznaczne dane wejściowe. Nie pamiętam, aby je widziałem, prawdopodobnie dlatego, że nawet w przypadku dokumentów technicznych, a nawet języków programowania, dwuznaczność składniowa jest dopuszczalna, o ile można ją rozwiązać innymi środkami (np. Niejednoznaczność wyrażeń ADA).

Zastanawiam się, dlaczego chcesz zmienić algorytm, zamiast trzymać się tego, co masz. To może pomóc mi zrozumieć, jaką zmianę najlepiej może ci pomóc. Czy jest to problem z prędkością, reprezentacja parsów, czy wykrywanie błędów i odzyskiwanie?

Najlepszym sposobem przedstawienia wielu parsów jest udostępniony las, który jest po prostu gramatyką bezkontekstową, która generuje tylko dane wejściowe, ale z dokładnie tymi samymi drzewami parsowania, co gramatyka DSL. To bardzo ułatwia zrozumienie i przetworzenie. Aby uzyskać więcej informacji, sugeruję przyjrzeć się tej odpowiedzi, którą podałem na stronie językowej. Rozumiem, że nie jesteś zainteresowany uzyskaniem lasu analizującego, ale odpowiednia reprezentacja analizowanego lasu może pomóc ci przekazać lepsze wiadomości o tym, co to jest problem z dwuznacznością. Może również pomóc ci zdecydować, że dwuznaczność nie ma znaczenia w niektórych przypadkach (skojarzenie), jeśli chcesz to zrobić.

Wspominasz o ograniczeniach czasowych przetwarzania gramatyki DSL, ale nie dajesz żadnych wskazówek co do jego wielkości (co nie znaczy, że mógłbym odpowiedzieć liczbami, które zrobiłeś).

Niektóre przetwarzanie błędów można w prosty sposób zintegrować z tymi ogólnymi algorytmami CF. Musiałbym jednak zrozumieć, jakiego rodzaju przetwarzania błędów oczekuje się bardziej pozytywnie. Czy masz jakieś przykłady?

Nie mogę swobodnie powiedzieć więcej, ponieważ nie rozumiem, jakie są wasze motywacje i ograniczenia. Na podstawie tego, co mówisz, trzymałbym się CYK (i znam inne algorytmy i niektóre z ich właściwości).