Co sprawia, że ​​Java jest łatwiejsza do przeanalizowania niż C?


90

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?


7
Fajne pytanie. Prawdopodobnie jednak zbyt szerokie lub głównie uparte.
asteri

37
Jest to ważne pytanie dotyczące parserów i jedyna rzecz szeroka lub oparta na nim to kilka ostatnich zdań (które prawdopodobnie należy porzucić lub zmienić). Zakończ głosami blisko.
R .. GitHub STOP HELPING ICE

1
Odpowiednio zredagowałem pytanie, dzięki @R .. za informację zwrotną.
korrok

3
Praktycznie każdy (standardowy) język komputerowy jest wrażliwy na kontekst ; nie możesz zadeklarować zmiennej jednego typu i nadużywasz jej w większości języków . To co innego niż „wszystkie gramatyki języka” są wrażliwe na kontekst; większość ludzi budujących parsery buduje bezkontekstowy (lub nawet bardziej restrykcyjny) parser, a następnie używa hacków poza parserem, aby sprawdzić właściwości bezkontekstowe.
Ira Baxter,

1
@IraBaxter Nie nazwałbym tego „hackami”. Podzielenie problemu na dwie części wydaje się rozsądną rzeczą do zrobienia, ponieważ analizowanie języków wrażliwych na kontekst nie może być wydajne (a w rzeczywistości nawet analizowanie języków bezkontekstowych nie jest wydajne i dlatego generalnie ograniczamy się do podzbiorów języków bezkontekstowych) . Analiza bezkontekstowa + analiza statyczna w celu sprawdzenia tylko właściwości kontekstowych w AST jest rozsądną rzeczą do zrobienia.
Bakuriu

Odpowiedzi:


76

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.


Dobra odpowiedź. Zobacz także D i C +, które próbują rozwiązać niektóre z tych problemów. s / content / contend /
david.pfx

3
Czytałem już Life After Parsing i odkryłem, że to naprawdę otwiera oczy; dało mi do zrozumienia, że ​​analiza semantyczna wymaga znacznie więcej pracy (rozpoznawanie nazw / typów, ...) niż analizowania. Ja nie próbuje zmienić składnię dowolnym języku. I nie chcą zrozumieć, jakie właściwości mają języka, w którym można zrobić analizę składniową pierwszy, a następnie analizy semantycznej. C nie jest takim językiem (wymaga hackowania leksera); Zawsze myślałem, że Java jest i chcę wiedzieć dlaczego.
korrok

1
@Korrok: przeczytaj moją odpowiedź na temat tworzenia Java / C ++ z parserami GLR. Nie potrzebujesz żadnego hacka leksera . Tak więc różnica tkwi w umysłach ludzi, którzy używają niewłaściwej technologii analizowania. ... To prawda, zbudowanie pełnego interfejsu C ++ (szczególnie C ++ 14, co zrobiliśmy) jest trudniejsze niż zrobienie Java8, ale oba są trudne (pod względem wysiłku i zwracania uwagi na szczegóły) i parsowanie to najłatwiejszy kawałek.
Ira Baxter

1
Zgadzam się z twoim "Life after Parsing": np. Rozwiązanie przeciążenia w C # może zakodować każdy problem 3-SAT i dlatego jest NP-trudne.
Jörg W Mittag

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.