Jestem zaznajomiony z faktem, że gramatyki C i C ++ są zależne od kontekstu , aw szczególności potrzebujesz "hackowania leksera" w C. Z drugiej strony mam wrażenie, że możesz parsować Javę tylko za pomocą 2 żetony przewidywania, pomimo znacznego podobieństwa między tymi dwoma językami.
Co należałoby zmienić w C, aby było łatwiejsze do przeanalizowania?
Pytam, ponieważ wszystkie przykłady wrażliwości C na kontekst, które widziałem, są technicznie dopuszczalne, ale okropnie dziwne. Na przykład,
foo (a);
mogłoby wywołać funkcję void fooz argumentem a. Albo może to być deklaracja, aże jest to obiekt typu foo, ale równie łatwo możesz pozbyć się parantez. Po części ta dziwność pojawia się, ponieważ reguła produkcji „bezpośredniego deklaratora” dla gramatyki języka C spełnia podwójny cel deklarowania zarówno funkcji, jak i zmiennych.
Z drugiej strony gramatyka Java ma oddzielne reguły tworzenia deklaracji zmiennych i deklaracji funkcji. Jeśli piszesz
foo a;
to wiesz, że jest to deklaracja zmiennej i foomożna ją jednoznacznie przeanalizować jako nazwę typu. Może to nie być prawidłowy kod, jeśli klasa foonie została zdefiniowana gdzieś w bieżącym zakresie, ale jest to zadanie analizy semantycznej, które można wykonać w późniejszym przebiegu kompilatora.
Widziałem, że jest napisane, że C jest trudny do przeanalizowania z powodu typedef, ale możesz także zadeklarować własne typy w Javie. Poza tym direct_declarator, które reguły gramatyczne języka C są wadliwe?
Odpowiedzi:
Parsowanie C ++ jest coraz trudniejsze. Parsowanie Javy staje się równie trudne.
Zobacz tę SO odpowiedź omawiającą, dlaczego C (i C ++) są „trudne” do przeanalizowania . Krótkie podsumowanie jest takie, że gramatyki C i C ++ są z natury niejednoznaczne; dadzą ci wiele analiz i musisz użyć kontekstu, aby rozwiązać niejednoznaczności. Następnie ludzie popełniają błąd, zakładając, że podczas analizowania trzeba rozwiązywać niejednoznaczności; nie tak, patrz poniżej. Jeśli będziesz nalegać na rozwiązywanie niejednoznaczności podczas parsowania, twój parser stanie się bardziej skomplikowany i trudniejszy do zbudowania; ale ta złożoność to rana zadana sobie przez samego siebie.
IIRC, "oczywista" gramatyka LALR (1) Javy 1.4 nie była dwuznaczna, więc była "łatwa" do przeanalizowania. Nie jestem pewien, czy współczesna Java nie ma przynajmniej długodystansowych lokalnych niejasności; zawsze istnieje problem z podjęciem decyzji, czy „... >>” zamyka dwa szablony, czy jest „operatorem przesunięcia w prawo”. Podejrzewam, że współczesna Java nie parsuje już z LALR (1) .
Ale można ominąć problem parsowania, używając silnych parserów (lub słabych parserów i hacków zbierania kontekstów, jak robią to głównie interfejsy C i C ++) dla obu języków. C i C ++ mają dodatkową komplikację posiadania preprocesora; w praktyce są one bardziej skomplikowane niż wyglądają. Jednym z twierdzeń jest to, że parsery C i C ++ są tak trudne, że trzeba je pisać ręcznie. To nieprawda; możesz dobrze zbudować parsery Java i C ++ za pomocą generatorów parserów GLR.
Ale analizowanie tak naprawdę nie jest przyczyną problemu.
Po parsowaniu będziesz chciał coś zrobić z drzewem AST / parse. W praktyce trzeba wiedzieć, dla każdego identyfikatora, jaka jest jego definicja i gdzie jest używana ("rozwiązywanie nazw i typów", niechlujnie, budowanie tablic symboli). Okazuje się, że jest to DUŻO więcej pracy niż poprawne ustawienie parsera, złożone przez dziedziczenie, interfejsy, przeciążenie i szablony, a także zagmatwane faktem, że semantyka tego wszystkiego jest zapisana w nieformalnym języku naturalnym, rozłożonym na dziesiątki do setek stron standardu językowego. C ++ jest tutaj naprawdę zły. Z tego punktu widzenia Java 7 i 8 stają się dość okropne. (A tabele symboli to nie wszystko, czego potrzebujesz; zobacz moją biografię na dłuższy esej na temat „Life After Parsing”).
Większość ludzi zmaga się z czystą częścią parsowania (często nigdy nie kończy; sprawdź samo SO, aby uzyskać wiele, wiele pytań dotyczących tego, jak zbudować działające parsery dla prawdziwych langug), więc nigdy nie widzą życia po przeanalizowaniu. A potem otrzymujemy ludowe twierdzenia o tym, co jest trudne do przeanalizowania i brak sygnału o tym, co dzieje się po tym etapie.
Naprawienie składni C ++ nigdzie Cię nie zaprowadzi.
Jeśli chodzi o zmianę składni C ++: zauważysz, że musisz załatać wiele miejsc, aby zająć się różnorodnością lokalnych i rzeczywistych niejednoznaczności w dowolnej gramatyce C ++. Jeśli nalegasz, poniższa lista może być dobrym punktem wyjścia . Uważam, że nie ma sensu robić tego, jeśli nie jesteś komitetem normalizacyjnym C ++; gdybyś to zrobił i zbudował kompilator używając tego, nikt rozsądny nie użyłby tego. Za dużo zainwestowano w istniejące aplikacje C ++, aby przełączyć się dla wygody ludzi tworzących parsery; poza tym ich ból minął, a istniejące parsery działają dobrze.
Możesz napisać własny parser. W porządku; po prostu nie oczekuj, że reszta społeczności pozwoli ci zmienić język, którego muszą używać, aby ci to ułatwić. Wszyscy chcą, aby było to dla nich łatwiejsze, a to oznacza użycie języka w formie udokumentowanej i wdrożonej.
źródło