Programuję od wielu lat, ale jednym z zadań, które wciąż zajmuje mi wyjątkowo dużo czasu, jest określenie gramatyki parsera, a nawet po tym nadmiernym wysiłku nigdy nie jestem pewien, czy gramatyka, którą wymyśliłem, jest dobra ( przez jakąkolwiek rozsądną miarę „dobra”).
Nie oczekuję, że istnieje algorytm automatyzujący proces określania gramatyki, ale mam nadzieję, że istnieją sposoby na ustrukturyzowanie problemu, który wyeliminuje wiele domysłów i prób i błędów mojego obecnego podejścia.
Moją pierwszą myślą było przeczytanie o parserach i zrobiłem niektóre z nich, ale wszystko, co przeczytałem na ten temat, przyjmuje gramatykę jako coś konkretnego (lub na tyle trywialnego, że można ją określić przez inspekcję) i skupia się na problem z przetłumaczeniem tej gramatyki na parser. Interesuje mnie ten problem bezpośrednio przed: jak określić gramatykę w pierwszej kolejności.
Interesuje mnie przede wszystkim problem określania gramatyki, która formalnie reprezentuje zbiór konkretnych przykładów (pozytywnych i negatywnych). Różni się to od problemu projektowania nowej składni . Dziękujemy Macneilowi za wskazanie tego rozróżnienia.
Nigdy tak naprawdę nie doceniałem rozróżnienia między gramatyką a składnią, ale teraz, gdy zaczynam to rozumieć, mogłem wyostrzyć moje pierwsze wyjaśnienie, mówiąc, że przede wszystkim jestem zainteresowany problemem określenia gramatyki, która wymusi predefiniowana składnia: tak się składa, że w moim przypadku podstawą tej składni jest zwykle zbiór przykładów pozytywnych i negatywnych.
Jak określona jest gramatyka dla analizatora składni? Czy istnieje książka lub odnośnik, który jest de facto standardem opisującym najlepsze praktyki, metodologie projektowania i inne pomocne informacje na temat określania gramatyki dla parsera? Na jakich punktach, czytając o gramatyce parsera, powinienem się skupić?
Odpowiedzi:
Z przykładowych plików będziesz musiał podejmować decyzje na podstawie tego, ile chcesz uogólnić na podstawie tych przykładów. Załóżmy, że masz następujące trzy próbki: (każda jest osobnym plikiem)
Możesz w trywialny sposób określić dwie gramatyki, które przyjmą te próbki:
Trivial Grammar One:
Trywialna gramatyka druga:
Pierwszy jest trywialny, ponieważ przyjmuje tylko trzy próbki. Drugi jest trywialny, ponieważ akceptuje wszystko , co mogłoby potencjalnie korzystać z tych typów tokenów. [W tej dyskusji zakładam, że nie troszczysz się zbytnio o projekt tokenizera: łatwo jest przyjąć identyfikatory, liczby i znaki interpunkcyjne jako swoje tokeny, i możesz pożyczyć dowolny zestaw tokenów z dowolnego języka skryptowego tak czy inaczej.]
Tak więc procedura, którą musisz wykonać, to zacząć od wysokiego poziomu i zdecydować „na ile z każdej instancji chcę zezwolić?” Jeśli konstrukcja składniowa może się powtarzać dowolną liczbę razy, na przykład
method
s w klasie, będziesz potrzebować reguły z tym formularzem:Co jest lepiej powiedziane w EBNF jako:
Prawdopodobnie będzie to oczywiste, gdy chcesz tylko zero lub jedną instancję (co oznacza, że konstrukcja jest opcjonalna, jak w przypadku
extends
klauzuli dla klasy Java), lub gdy chcesz zezwolić na jedną lub więcej instancji (jak w przypadku inicjalizatora zmiennej w deklaracji ). Musisz pamiętać o takich kwestiach, jak wymaganie separatora między elementami (jak,
w liście argumentów), wymaganie terminatora po każdym elemencie (jak w przypadku;
instrukcji oddzielnych) lub brak separatora lub terminatora (w zależności od przypadku z metodami w klasie).Jeśli twój język używa wyrażeń arytmetycznych, możesz łatwo skopiować z istniejących reguł pierwszeństwa. Najlepiej jest trzymać się czegoś dobrze znanego, jak reguły wyrażeń C, niż sięgać po coś egzotycznego, ale pod warunkiem, że wszystko inne jest równe.
Oprócz kwestii pierwszeństwa (co się łączy ze sobą) i kwestii powtórzeń (ile elementów powinien wystąpić, w jaki sposób są rozdzielane?), Musisz także pomyśleć o porządku: czy coś zawsze musi pojawić się przed inną rzeczą? Jeśli jedna rzecz jest uwzględniona, czy należy wykluczyć inną?
W tym momencie możesz mieć pokusę, aby gramatycznie egzekwować niektóre reguły, takie jak
Person
wiek, w którym nie chcesz, aby określano także ich datę urodzenia. Chociaż możesz w tym celu zbudować gramatykę, łatwiejsze może być wymuszenie tego za pomocą „kontroli semantycznej” po przeanalizowaniu wszystkiego. To upraszcza gramatykę i, moim zdaniem, poprawia komunikaty o błędach w przypadku naruszenia reguły.źródło
Dla większości generatorów parsera, to zwykle jakiś wariant Backus-Naur „s
<nonterminal> ::= expression
formatu. Przyjmuję założenie, że używasz czegoś takiego i nie próbujesz ręcznie budować swoich parserów. Jeśli możesz utworzyć parser dla formatu, w którym podano składnię (zamieściłem poniżej przykładowy problem), określenie gramatyki nie jest twoim problemem.Myślę, że przeciwstawiasz się składni składni z zestawu próbek, co jest naprawdę większym rozpoznawaniem wzorców niż analizowaniem. Jeśli musisz się do tego zastosować, oznacza to, że ktokolwiek podaje twoje dane, nie może podać ci jego składni, ponieważ nie ma dobrego opanowania formatu. Jeśli masz możliwość odepchnięcia się i poproszenia ich o formalną definicję, zrób to. To niesprawiedliwe, że dają ci niejasny problem, jeśli możesz ponosić odpowiedzialność za konsekwencje parsera opartego na wywnioskowanej składni przyjmującej złe dane wejściowe lub odrzucającej dobre dane wejściowe.
„Dobry” w twojej sytuacji musiałby oznaczać „analizuje pozytywne i odrzuca negatywne”. Bez jakiejkolwiek innej formalnej specyfikacji składni pliku wejściowego próbki są twoimi jedynymi przypadkami testowymi i nie możesz zrobić nic lepszego. Możesz postawić stopę i powiedzieć, że tylko pozytywne przykłady są dobre i odrzucić cokolwiek innego, ale prawdopodobnie nie jest to zgodne z duchem tego, co próbujesz osiągnąć.
W rozsądniejszych okolicznościach testowanie gramatyki jest jak testowanie czegokolwiek innego: musisz wymyślić wystarczającą liczbę przypadków testowych, aby wykonać wszystkie warianty nieterminali (i terminali, jeśli są one generowane przez leksykon).
Przykładowy problem
Napisz gramatykę, która przeanalizuje pliki tekstowe zawierające listę zgodnie z poniższymi regułami:
Przykład danych wejściowych (wszystkie prawidłowe):
źródło
Odpowiedzi Macneil i Blrfl są świetne. Chcę tylko dodać kilka uwag na temat początku procesu.
Składnia jest tylko sposobem do reprezentowania programu . Tak więc składnia twojego języka powinna być określona przez twoją odpowiedź na to pytanie: Co to jest program?
Można powiedzieć, że program jest zbiorem klas. Dobra, to nam daje
jako punkt wyjścia. Lub może będziesz musiał to napisać
Czym jest klasa? Ma imię; opcjonalna specyfikacja nadklasy; oraz garść deklaracji konstruktora, metody i pola. Ponadto potrzebujesz jakiegoś sposobu pogrupowania klasy w pojedynczą (jednoznaczną) jednostkę, co powinno wiązać się z pewnymi ustępstwami w zakresie użyteczności (np. Oznaczyć ją słowem zastrzeżonym
class
). W porządku:To jedna notacja („konkretna składnia”), którą możesz wybrać. Lub równie łatwo możesz o tym zdecydować:
lub
Prawdopodobnie już podjąłeś tę decyzję w sposób dorozumiany, szczególnie jeśli masz przykłady, ale chcę tylko podkreślić: struktura składni zależy od struktury reprezentowanych przez nią programów. Właśnie to omija „trywialne gramatyki” z odpowiedzi Macneila. Przykładowe programy są jednak nadal bardzo ważne. Służą one dwóm celom. Po pierwsze, pomagają zrozumieć, na poziomie abstrakcyjnym, czym jest program. Po drugie, pomagają ci zdecydować, jakiej konkretnej składni powinieneś użyć do przedstawienia struktury twojego języka.
Po zmniejszeniu struktury powinieneś wrócić i zająć się takimi kwestiami, jak dopuszczanie białych znaków i komentarzy, ustalanie dwuznaczności itp. Są one ważne, ale są drugorzędne w stosunku do ogólnego projektu i są w dużym stopniu zależne od technologia analizowania, której używasz.
Wreszcie, nie próbuj reprezentować wszystkiego w swoim języku w gramatyce. Na przykład, możesz zabronić pewnych rodzajów nieosiągalnego kodu (np. Instrukcja po znaku
return
, jak w Javie). Prawdopodobnie nie powinieneś próbować wtykać tego w gramatykę, ponieważ albo coś przegapisz (ups, co jeślireturn
jest w nawiasach klamrowych, albo co, jeśli obie gałęzieif
wyrażenia powrócą?) Lub sprawisz, że gramatyka będzie zbyt skomplikowana zarządzać. Jest to ograniczenie kontekstowe ; napisz to jako osobne przejście. Innym bardzo częstym przykładem ograniczenia kontekstowego jest system typów. Możesz odrzucić wyrażenia jak1 + "a"
w gramatyce, jeśli pracujesz wystarczająco ciężko, ale nie możesz odrzucić1 + x
(gdziex
ma ciąg znaków). Więcunikaj niedopieczonych ograniczeń gramatyki i rób je poprawnie jako osobne przejście.źródło