Czy parsery GCC i Clang są naprawdę napisane odręcznie?

Wygląda na to, że GCC i LLVM-Clang używają ręcznie zapisywanych rekurencyjnych parserów zejścia , a nie generowanego maszynowo, opartego na Bison-Flex, analizowania oddolnego.

Czy ktoś tutaj mógłby potwierdzić, że tak jest? A jeśli tak, to dlaczego główne platformy kompilatorów używają odręcznych parserów?

Aktualizacja : interesujący blog na ten temat tutaj

Tak:

• GCC używał kiedyś parsera yacc (bison), ale został on zastąpiony przez ręcznie napisany rekursywny parser zejścia w pewnym momencie serii 3.x: patrz http://gcc.gnu.org/wiki/New_C_Parser dla linki do odpowiednich zgłoszeń poprawek.

• Clang używa również ręcznie napisanego rekurencyjnego parsera zejścia: zobacz sekcję „Pojedynczy zunifikowany parser dla C, Objective C, C ++ i Objective C ++” pod koniec http://clang.llvm.org/features.html .

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

To nieprawda.

Prawdą jest, że C i C ++ są dość trudne do przeanalizowania przy użyciu parserów LALR (1) bez hakowania maszyn parsujących i plątania się w danych tabeli symboli. W rzeczywistości GCC parsował je, używając YACC i dodatkowych hackerów, i tak, to było brzydkie. Teraz GCC używa odręcznych parserów, ale nadal z hackerem tablicy symboli. Ludzie z Clang nigdy nie próbowali używać automatycznych generatorów parserów; AFAIK parser Clang zawsze był ręcznie kodowany rekursywnie.

Prawdą jest, że C i C ++ są stosunkowo łatwe do przeanalizowania z silniejszymi automatycznie generowanymi parserami, np. Parserami GLR , i nie potrzebujesz żadnych hacków. W Elsy C ++ parser jest jednym z przykładów. Nasz interfejs C ++ jest kolejnym (podobnie jak wszystkie nasze interfejsy „kompilatorów”, GLR jest całkiem wspaniałą technologią parsowania).

Nasz interfejs C ++ nie jest tak szybki jak GCC iz pewnością wolniejszy niż Elsa; włożyliśmy niewiele energii w jego dokładne dostrojenie, ponieważ mamy inne, bardziej palące problemy (niemniej jednak zostało ono użyte w milionach wierszy kodu C ++). Elsa jest prawdopodobnie wolniejsza niż GCC tylko dlatego, że jest bardziej ogólna. Biorąc pod uwagę dzisiejsze prędkości procesora, różnice te mogą nie mieć większego znaczenia w praktyce.

Ale "prawdziwe kompilatory", które są dziś szeroko rozpowszechniane, mają swoje korzenie w kompilatorach sprzed 10, 20 lub więcej lat. Nieskuteczność liczyła się wtedy znacznie bardziej i nikt nie słyszał o parserach GLR, więc ludzie robili to, co umieli. Clang jest z pewnością nowszy, ale twierdzenia ludowe przez długi czas zachowują swoją „zdolność przekonywania”.

Nie musisz już tego robić w ten sposób. Możesz bardzo rozsądnie użyć GLR i innych podobnych parserów jako front-endów, z ulepszeniem w utrzymywalności kompilatora.

Co to jest prawdą, jest to, że coraz gramatyki, który odpowiada zachowaniu przyjaznego sąsiedztwa kompilator jest trudne. Podczas gdy praktycznie wszystkie kompilatory C ++ implementują (większość) oryginalnego standardu, zwykle mają również wiele rozszerzeń z ciemnymi rogami, np. Specyfikacje DLL w kompilatorach MS itp. Jeśli masz silny silnik parsujący, możesz spędzić czas próbując uzyskać ostateczna gramatyka, aby pasowała do rzeczywistości, zamiast próbować naginać gramatykę, aby dopasować ją do ograniczeń generatora parsera.

EDYCJA Listopad 2012: Od czasu napisania tej odpowiedzi ulepszyliśmy nasz interfejs C ++, aby obsługiwał pełny C ++ 11, w tym dialekty ANSI, GNU i MS. Chociaż było wiele dodatkowych rzeczy, nie musimy zmieniać naszego silnika parsującego; właśnie zmieniliśmy zasady gramatyczne. My nie musimy zmieniać analizę semantyczną; C ++ 11 jest semantycznie bardzo skomplikowany i ta praca utrudnia uruchomienie parsera.

EDYCJA Luty 2015: ... teraz obsługuje pełne C ++ 14. (Zobacz pobieranie czytelnego dla człowieka kodu AST z kodu c ++, aby zapoznać się z analizami GLR prostego fragmentu kodu i niesławną C ++ „najbardziej irytującą analizą”).

EDYCJA Kwiecień 2017: Teraz obsługuje (wersję roboczą) C ++ 17.

Parser Clanga to odręcznie napisany parser rekurencyjny, podobnie jak kilka innych otwartych i komercyjnych interfejsów C i C ++.

Clang używa parsera zstępującego rekurencyjnego z kilku powodów:

• Wydajność : ręcznie napisany parser pozwala nam napisać szybki parser, optymalizując gorące ścieżki w razie potrzeby, i zawsze mamy kontrolę nad tą wydajnością. Posiadanie szybkiego parsera umożliwiło użycie Clanga w innych narzędziach programistycznych, w których zazwyczaj nie używa się "prawdziwych" parserów, np. Podświetlanie składni i uzupełnianie kodu w środowisku IDE.
• Diagnostyka i naprawianie błędów : ponieważ masz pełną kontrolę dzięki ręcznie napisanemu parserowi zejścia rekurencyjnego, łatwo jest dodać specjalne przypadki, które wykrywają typowe problemy i zapewniają doskonałą diagnostykę i usuwanie błędów (np. Patrz http: //clang.llvm .org / features.html # expressivediags ) Dzięki automatycznie generowanym parserom jesteś ograniczony do możliwości generatora.
• Prostota : parsery zstępujące rekurencyjnie są łatwe do napisania, zrozumienia i debugowania. Nie musisz być ekspertem od analizowania ani uczyć się nowego narzędzia do rozszerzania / ulepszania parsera (co jest szczególnie ważne w przypadku projektów typu open source), ale nadal możesz uzyskać świetne wyniki.

Ogólnie rzecz biorąc, dla kompilatora C ++ nie ma to większego znaczenia: część parsująca C ++ jest nietrywialna, ale nadal jest jedną z łatwiejszych części, więc opłaca się zachować prostotę. Analiza semantyczna - w szczególności wyszukiwanie nazw, inicjalizacja, rozwiązywanie przeciążeń i tworzenie instancji szablonów - jest o rząd wielkości bardziej skomplikowana niż analiza. Jeśli potrzebujesz dowodu, sprawdź dystrybucję kodu i zatwierdzeń w komponencie "Sema" Clanga (do analizy semantycznej) w porównaniu z komponentem "Parse" (do analizowania).

parser gcc jest napisany odręcznie. . Podejrzewam, że to samo dotyczy brzęku. Dzieje się tak prawdopodobnie z kilku powodów:

• Wydajność : coś, co zostało ręcznie zoptymalizowane pod kątem konkretnego zadania, prawie zawsze będzie działać lepiej niż ogólne rozwiązanie. Abstrakcja zwykle ma hit wydajnościowy
• Czas : przynajmniej w przypadku GCC, GCC poprzedza wiele bezpłatnych narzędzi programistycznych (pojawiło się w 1987 roku). W tamtym czasie nie było darmowej wersji yacc itp., Co, jak sobie wyobrażam, byłoby priorytetem dla ludzi z FSF.

Prawdopodobnie nie jest to przypadek syndromu „nie wynaleziono tutaj”, ale raczej „nie było nic zoptymalizowanego specjalnie do tego, czego potrzebowaliśmy, więc napisaliśmy własny”.

Tam dziwne odpowiedzi!

Gramatyki C / C ++ nie są bezkontekstowe. Są wrażliwe na kontekst ze względu na pasek Foo *; Dwuznaczność. Musimy zbudować listę typedef, aby wiedzieć, czy Foo jest typem, czy nie.

Ira Baxter: Nie widzę sensu w twoim GLR. Po co budować drzewo parsowania, które zawiera niejednoznaczności. Parsowanie oznacza rozwiązywanie niejednoznaczności, budowanie drzewa składni. Rozwiązujesz te dwuznaczności w drugim przejściu, więc nie jest to mniej brzydkie. Dla mnie jest o wiele brzydszy ...

Yacc jest generatorem parsera LR (1) (lub LALR (1)), ale można go łatwo zmodyfikować, aby był zależny od kontekstu. 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 ...

Aż do GCC 3.x parser C jest generowany przez yacc / bison, z tablicą typedefs budowaną podczas parsowania. Dzięki budowaniu tabel typu "in parse", gramatyka języka C staje się lokalnie bezkontekstowa, a ponadto "lokalnie LR (1)".

Teraz, w Gcc 4.x, jest to parser rekurencyjny. Jest to dokładnie ten sam parser co w Gcc 3.x, wciąż jest to LR (1) i ma te same reguły gramatyczne. Różnica polega na tym, że parser yacc został przepisany ręcznie, przesunięcie / zmniejszenie jest teraz ukryte w stosie wywołań i nie ma "state454: if (nextsym == '(') goto state398" jak w gcc 3.x yacc's parser, więc łatwiej jest łatać, obsługiwać błędy i drukować ładniejsze komunikaty, a także wykonywać niektóre z następnych kroków kompilacji podczas parsowania Za cenę znacznie mniej „łatwego do odczytania” kodu dla nooba gcc.

Dlaczego przeszli z yacc na zejście rekurencyjne? Ponieważ konieczne jest unikanie yacc do parsowania C ++ i ponieważ GCC marzy o byciu kompilatorem wielojęzycznym, tj. Dzieleniu maksymalnego kodu między różnymi językami, które może kompilować. Dlatego parser C ++ i C są napisane w ten sam sposób.

C ++ jest trudniejszy do przeanalizowania niż C, ponieważ nie jest „lokalnie” LR (1) jak C, nie jest nawet LR (k). Spójrz, func<4 > 2>która funkcja szablonu, której wystąpienie ma wartość 4> 2, czyli func<4 > 2> musi być odczytana jako func<1>. To zdecydowanie nie jest LR (1). Teraz rozważyć func<4 > 2 > 1 > 3 > 3 > 8 > 9 > 8 > 7 > 8>. Tutaj rekursywne zejście może łatwo rozwiązać niejednoznaczność za cenę kilku dodatkowych wywołań funkcji (parametr_parse_template_parameter to niejednoznaczna funkcja parsera. to działa).

Nie wiem, dlaczego nie byłoby możliwe dodanie do rekurencyjnych pod gramatyki yacc / bison, może to będzie następny krok w rozwoju parsera gcc / GNU?

Wygląda na to, że GCC i LLVM-Clang używają ręcznie zapisywanych rekurencyjnych parserów zejścia, a nie generowanego maszynowo, opartego na Bison-Flex, oddolnego parsowania.

Zwłaszcza żubr nie wydaje mi się, aby poradził sobie z gramatyką bez niejednoznacznego analizowania niektórych rzeczy i wykonywania 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 żadnych generatorów parsera C, które pozwalają na monadę stanu dostarczaną przez użytkownika.

Teoretycznie naprawianie błędów byłoby punktem na korzyść ręcznego parsera, ale moje doświadczenie z GCC / Clang jest takie, że komunikaty o błędach nie są szczególnie dobre.

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