Jak określić gramatykę dla analizatora składni?

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ć?

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)

f() {}
f(a,b) {b+a}
int x = 5;

Możesz w trywialny sposób określić dwie gramatyki, które przyjmą te próbki:

Trivial Grammar One:

start ::= f() {} | f(a,b) {b+a} | int x = 5;

Trywialna gramatyka druga:

start ::= tokens
tokens ::= token tokens | <empty>
token ::= identifier | literal | { | } | ( | ) | , | + | = | ;

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 methods w klasie, będziesz potrzebować reguły z tym formularzem:

methods ::= method methods | empty

Co jest lepiej powiedziane w EBNF jako:

methods ::= {method}

Prawdopodobnie będzie to oczywiste, gdy chcesz tylko zero lub jedną instancję (co oznacza, że ​​konstrukcja jest opcjonalna, jak w przypadku extendsklauzuli 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 Personwiek, 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.

Gdzie mogę się dowiedzieć, jak określić gramatykę analizatora składni?

Dla większości generatorów parsera, to zwykle jakiś wariant Backus-Naur „s <nonterminal> ::= expressionformatu. 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.

... Nigdy nie jestem pewien, czy gramatyka, którą wymyśliłem, jest dobra (według jakiejkolwiek rozsądnej miary „dobrej”).

„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:

• Lista składa się z zera lub więcej rzeczy .
• Rzecz składa się z identyfikatora , otwartego nawiasu, na liście elementów i nawiasu zamykającego.
• _Item_list_ zawiera zero lub więcej pozycji .
• Poz constsis się z identyfikatorem , znakiem równości, innego identyfikatora i średnikiem.
• Identyfikator jest sekwencją jednego lub więcej znaków az, AZ, 0-9 lub podkreślenia.
• Białe znaki są ignorowane.

Przykład danych wejściowych (wszystkie prawidłowe):

clank { foo = bar; baz = bear; }
clunk {
    quux =bletch;
    281_apple = OU812;
    He_Eats=Asparagus ; }

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

program ::= class*

jako punkt wyjścia. Lub może będziesz musiał to napisać

program ::= ε
         |  class program

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:

class ::= "class" identifier extends-clause? "{" class-member-decl * "}"

To jedna notacja („konkretna składnia”), którą możesz wybrać. Lub równie łatwo możesz o tym zdecydować:

class ::= "(" "class" identifier extends-clause "(" class-member-decl* ")" ")"

lub

class ::= "class" identifier "=" "CLASS" extends-clause? class-member-decl* "END"

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śli returnjest w nawiasach klamrowych, albo co, jeśli obie gałęzie ifwyraż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 jak 1 + "a"w gramatyce, jeśli pracujesz wystarczająco ciężko, ale nie możesz odrzucić 1 + x(gdzie xma ciąg znaków). Więcunikaj niedopieczonych ograniczeń gramatyki i rób je poprawnie jako osobne przejście.