Czy parsery GCC i Clang są naprawdę ręcznie pisane?

Istnieje twierdzenie ludowe, które mówi, że C jest trudne do przeanalizowania, A C++ zasadniczo niemożliwe.

To nieprawda.

Prawdą jest, że C i C++ są dość trudne do parsowania przy użyciu parserów LALR(1) bez hakowania maszynerii parsowania i splątania danych z tabeli symboli. GCC w rzeczywistości używane do parsowania ich, za pomocą YACC i dodatkowe hackery jak ten, i tak to było brzydkie. teraz GCC używa odręcznych parserów, ale nadal z hackery tabeli symboli. The Clang people never tried używać zautomatyzowanych generatorów parserów; AFAIK parser Clang zawsze był ręcznie kodowany rekurencyjnie.

Prawdą jest, że C i C++ są stosunkowo łatwe do przetworzenia dzięki silniejszym automatycznie generowanym parserom, np. parsery GLR , i nie potrzebujesz żadnych hacków. Jednym z przykładów jest parser Elsa C++. Nasz C++ Front End jest inny (podobnie jak wszystkie nasze "Kompilatory" front ends, GLR jest dość wspaniałą technologią parsowania).

Nasz C++ front end nie jest tak szybki jak GCC, a na pewno wolniejszy od Elsa; włożyliśmy trochę energii w jego strojenie, ponieważ mamy inne bardziej palące problemy (non-eless został użyty na milionach linii kodu C++). Elsa jest prawdopodobnie wolniejsza niż GCC tylko dlatego, że jest bardziej ogólna. Biorąc pod uwagę prędkości procesora w dzisiejszych czasach, te różnice mogą nie mieć większego znaczenia w praktyce.

Ale "prawdziwe Kompilatory", które są dziś szeroko rozpowszechnione, mają swoje korzenie w kompilatorach sprzed 10 czy 20 lat lub więcej. Nieefektywność miała wtedy znacznie większe znaczenie, a nikt nie słyszał o parserach GLR, więc ludzie robili to, co umieli. Clang jest z pewnością nowszy, ale wtedy teorie ludowe zachowują swoją "perswazyjność" przez długi czas.

Nie musisz już tego robić w ten sposób. Można bardzo rozsądnie używać GLR i innych tego typu parserów jako przednich końców, z poprawą konserwacji kompilatora.

Co jest prawdą, jest to, że uzyskanie gramatyki pasującej do twojego przyjaznego zachowanie kompilatora jest trudne. Podczas gdy praktycznie wszystkie kompilatory C++ implementują (większość) oryginalnego standardu, mają również wiele rozszerzeń ciemnego rogu, np. specyfikacje DLL w kompilatorach MS, itp. Jeśli masz silny silnik parsowania, możesz spędź czas próbując uzyskać ostateczną gramatykę, aby dopasować ją do rzeczywistości, zamiast próbować wyginać gramatykę, aby dopasować ją do ograniczeń generatora parserów.

EDIT listopad 2012: od napisania tej odpowiedzi poprawiliśmy nasz interfejs C++ do obsługi pełnego C++11, w tym dialektów ANSI, GNU I MS. Chociaż było wiele dodatkowych rzeczy, nie musimy zmieniać naszego silnika parsowania; po prostu zmieniliśmy zasady gramatyki. My czy musieliśmy zmienić analizę semantyczną; C++11 jest semantycznie bardzo skomplikowany, a ta praca zamyka wysiłek, aby uruchomić parser.

Edycja luty 2015: ... teraz obsługuje pełne C++14. (Zobacz get human readable AST from C++ code for GLR parses of a simple bit kodu, A C++'S niesławny" najbardziej irytujący parse").

Edycja Kwiecień 2017: now handles (draft) C++17.

Parser clanga jest ręcznie pisanym parserem rekurencyjnym, podobnie jak kilka innych open-source i komercyjnych front endów C i C++.

• wydajność : ręcznie pisany parser pozwala nam pisać szybki parser, optymalizując gorące ścieżki w razie potrzeby, a my zawsze mamy kontrolę nad tą wydajnością. Posiadanie szybkiego parsera pozwoliło na użycie Clang w innych narzędziach programistycznych, gdzie" prawdziwymi " parserami są zazwyczaj nie używane, np. podświetlanie składni i uzupełnianie kodu w IDE.
• Diagnostyka i odzyskiwanie błędów : ponieważ masz pełną kontrolę za pomocą ręcznie pisanego parsera rekurencyjnego opadania, łatwo jest dodać specjalne przypadki, które wykrywają typowe problemy i zapewniają doskonałą diagnostykę i odzyskiwanie błędów (np. http://clang.llvm.org/features.html#expressivediags ) Dzięki automatycznie generowanym parserom ograniczasz się do możliwości generatora.
• prostota : rekurencyjne parsery są łatwe do napisania, zrozumienia i debugowania. Nie musisz być ekspertem od parsowania ani uczyć się nowego narzędzia do rozszerzania / ulepszania parsera (co jest szczególnie ważne w projekcie open-source), ale nadal możesz uzyskać świetne wyniki.

Ogólnie rzecz biorąc, dla kompilatora C++, to po prostu nie ma większego znaczenia: część przetwarzania C++ jest nietrywialna, ale nadal jest jedną z łatwiejszych części, więc opłaca się zachować to proste. Semantic analiza - - - szczególnie wyszukiwanie nazw, inicjalizacja, rozdzielczość przeciążenia i instancja szablonu - - - jest o rząd wielkości bardziej skomplikowana niż parsowanie. Jeśli chcesz mieć dowód, sprawdź rozkład kodu i commity w komponencie "Sema" clanga (do analizy semantycznej) kontra jego komponencie "Parse" (do analizy).

Parser Gcc jest napisany ręcznie.. To samo podejrzewam o clang. Jest to prawdopodobnie z kilku powodów:

• wydajność : coś, co ręcznie zoptymalizowałeś do konkretnego zadania, prawie zawsze będzie działać lepiej niż ogólne rozwiązanie. Abstrakcja zwykle ma hit performance
• Timing : przynajmniej w przypadku GCC, GCC wyprzedza wiele darmowych narzędzi programistycznych(wyszło w 1987). Nie było darmowej wersji yacc itp. w tym czasie, który Myślę, że to byłby priorytet dla ludzi z FSF.

Prawdopodobnie nie jest to przypadek syndromu "nie wymyślonego tutaj", ale bardziej na wzór "nie było nic zoptymalizowanego specjalnie do tego, czego potrzebowaliśmy, więc napisaliśmy własne".

Dziwne odpowiedzi tam!

Gramatyki C/C++ nie są wolne od kontekstu. Są wrażliwe na kontekst z powodu paska Foo*; niejednoznaczności. Musimy zbudować listę typedefów, aby wiedzieć, czy Foo jest typem, czy nie.

Yacc jest generatorem parserów LR(1) (lub LALR(1)), ale można go łatwo zmodyfikować, aby był wrażliwy na kontekst. I nie ma w tym nic brzydkiego. Yacc / Bison został stworzony, aby pomóc w parsowaniu języka C, więc prawdopodobnie nie jest to najbrzydsze narzędzie do generowania parsera C...

Do GCC 3.x parser C jest generowany przez yacc/bison, z tabelą typedefs zbudowaną podczas parsowania. Z" in parse "typedefs table building, gramatyka C staje się lokalnie wolna od kontekstu, a ponadto" lokalnie LR (1)"

Dlaczego przełączyli się z Yacc na recursive descent? Ponieważ jest to całkiem konieczne, aby unikać Yacc do parsowania C++, i ponieważ GCC marzy, aby być kompilatorem wielojęzycznym, tzn. dzieląc maksimum kodu między różnymi językami, które może skompilować. To dlatego C++ i parser C są napisane w ten sam sposób.

C++ jest trudniejsze do przetworzenia niż C, ponieważ nie jest" lokalnie " LR(1) jako C, nie jest nawet LR (k). # Patrz at func<4 > 2>, która jest funkcją szablonową utworzoną z 4 > 2, tzn. func<4 > 2> musi być odczytane jako func<1>. To zdecydowanie nie jest LR (1). Zastanów się, func<4 > 2 > 1 > 3 > 3 > 8 > 9 > 8 > 7 > 8>. To tutaj rekurencyjne zejście może łatwo rozwiązać wieloznaczność, za cenę kilku kolejnych wywołań funkcji (parse_template_parameter jest wieloznaczną funkcją parsera. Jeśli parse_template_parameter (17tokens) nie powiodło się, spróbuj ponownie parse_template_parameter(15tokens), parse_template_parameter(13tokens) ... dopóki nie zadziała).

I don ' t know why it czy nie byłoby możliwości dodania do gramatyk rekurencyjnych Yacc/bison, może będzie to kolejny krok w rozwoju parserów gcc / GNU?

Wygląda na to, że GCC i LLVM-Clang używają odręcznych rekurencyjnych parserów opadania, a nie generowanych maszynowo, opartych na Bison-Flex, analizujących od dołu do góry.

Bison w szczególności nie sądzę, że poradzi sobie z gramatyką bez dwuznacznego parsowania niektórych rzeczy i robienia drugiego przejścia później.

Wiem, że Haskell ' s Happy pozwala na monadyczne (tj. zależne od stanu) parsery, które mogą rozwiązać konkretny problem ze składnią C, ale nie znam generatorów parserów C, które pozwalają na monada stanowa dostarczana przez użytkownika.

W teorii, odzyskiwanie błędów byłoby punktem na korzyść ręcznie pisanego parsera, ale moje doświadczenie z GCC/Clang było to, że komunikaty o błędach nie są szczególnie dobre.

Jeśli chodzi o wydajność-niektóre z twierdzeń wydają się bezpodstawne. Generowanie dużej maszyny stanowej za pomocą generatora parsera powinno skutkować czymś, co jest O(n) i wątpię, aby parsowanie było wąskim gardłem w wielu narzędziach.