Dlaczego nie można analizować C ++ za pomocą parsera LR (1)?

Czytałem o parserach i generatorach parserów i znalazłem to oświadczenie na stronie parsowania LR Wikipedii:

Wiele języków programowania można analizować przy użyciu pewnych odmian parsera LR. Jednym godnym uwagi wyjątkiem jest C ++.

Dlaczego tak się dzieje? Jaka konkretna właściwość języka C ++ powoduje, że nie można przeanalizować parserów LR?

Korzystając z Google, stwierdziłem tylko, że C można doskonale przeanalizować z LR (1), ale C ++ wymaga LR (∞).

Istnieje interesujący wątek na temat Lambda the Ultimate, który omawia gramatykę LALR dla C ++ .

Zawiera link do rozprawy doktorskiej, która zawiera omówienie analizowania w C ++, która stwierdza, że:

„Gramatyka języka C ++ jest niejednoznaczna, zależna od kontekstu i potencjalnie wymaga nieskończonego przewidywania, aby rozwiązać niektóre niejasności”.

Dalej podaje szereg przykładów (patrz strona 147 pliku PDF).

Oto przykład:

int(x), y, *const z;

znaczenie

int x;
int y;
int *const z;

Porównać do:

int(x), y, new int;

znaczenie

(int(x)), (y), (new int));

(wyrażenie oddzielone przecinkami).

Dwie sekwencje tokenów mają ten sam początkowy podciąg, ale różne drzewa parsowania, które zależą od ostatniego elementu. Przed ujednoznaczniającym może znajdować się dowolnie wiele tokenów.

Parsery LR z założenia nie radzą sobie z niejednoznacznymi regułami gramatycznymi. (Ułatwili teorię w latach siedemdziesiątych, kiedy opracowywano pomysły).

C i C ++ zezwalają na następującą instrukcję:

x * y ;

Ma dwie różne analizy:

1. Może to być deklaracja y, jako wskaźnik do typu x
2. Może to być wielokrotność x i y, odrzucając odpowiedź.

Teraz możesz pomyśleć, że to drugie jest głupie i należy je zignorować. Większość by się z tobą zgodziła; jednak są przypadki, w których może to mieć efekt uboczny (np. przeciążenie funkcji multiply). ale nie o to chodzi. Chodzi o to, że istnieją dwie różne analizy, dlatego program może oznaczać różne rzeczy w zależności od tego, jak powinien zostać przeanalizowany.

Kompilator musi zaakceptować odpowiednią w odpowiednich okolicznościach, aw przypadku braku innych informacji (np. Znajomość typu x) musi zebrać oba, aby później zdecydować, co robić. Zatem gramatyka musi na to pozwolić. A to sprawia, że ​​gramatyka jest niejednoznaczna.

Dlatego czyste parsowanie LR nie może sobie z tym poradzić. Również wiele innych powszechnie dostępnych generatorów parserów, takich jak Antlr, JavaCC, YACC czy tradycyjny Bison, czy nawet parsery w stylu PEG, nie może być używanych w „czysty” sposób.

Istnieje wiele bardziej skomplikowanych przypadków (parsowanie składni szablonu wymaga arbitralnego spojrzenia w przód, podczas gdy LALR (k) może patrzeć w przód na większości k tokenów), ale wystarczy tylko jeden kontrprzykład, aby zestrzelić czysty parsowanie LR (lub innych).

Większość prawdziwych parserów C / C ++ radzi sobie z tym przykładem używając pewnego rodzaju deterministycznego parsera z dodatkowym hackem: przeplatają parsowanie z kolekcją tablic symboli ... tak aby do czasu napotkania "x" parser wiedział, czy x jest typem lub nie, a zatem może wybierać między dwoma potencjalnymi analizami. Ale parser, który to robi, nie jest bezkontekstowy, a parsery LR (czyste itp.) Są (w najlepszym przypadku) bezkontekstowe.

Można oszukiwać i dodawać semantyczne kontrole czasu redukcji dla poszczególnych reguł w parserach LR, aby dokonać tego ujednoznacznienia. (Ten kod często nie jest prosty). Większość innych typów parserów ma pewne sposoby dodawania kontroli semantycznej w różnych punktach analizy, które mogą być do tego użyte.

A jeśli wystarczająco oszukasz, możesz sprawić, by parsery LR działały w C i C ++. Faceci z GCC zrobili to przez jakiś czas, ale zrezygnowali z ręcznego kodowania parsowania, myślę, że chcieli lepszej diagnostyki błędów.

Istnieje jednak inne podejście, które jest ładne i przejrzyste oraz dobrze analizuje C i C ++ bez żadnego hakera w tablicy symboli: parsery GLR . Są to parsery w pełni bezkontekstowe (mające efektywnie nieskończone antycypowanie). Parsery GLR po prostu akceptują obie analizy, tworząc „drzewo” (właściwie skierowany acykliczny graf, który jest głównie podobny do drzewa), które reprezentuje niejednoznaczną analizę. Przebieg po analizie może rozwiązać niejednoznaczności.

Używamy tej techniki w interfejsach C i C ++ dla naszego oprogramowania DMS Reengineering Tookit (od czerwca 2017 obsługują one pełne C ++ 17 w dialektach MS i GNU). Były używane do przetwarzania milionów wierszy dużych systemów C i C ++, z kompletnymi, precyzyjnymi analizami tworzącymi AST z pełnymi szczegółami kodu źródłowego. (Zobacz AST dla najbardziej irytującej analizy języka C ++ ).

Problem nigdy nie jest tak definiowany, ale powinien być interesujący:

Jaki jest najmniejszy zestaw modyfikacji gramatyki C ++, który byłby niezbędny, aby ta nowa gramatyka mogła być doskonale przeanalizowana przez "bezkontekstowy" parser yacc? (wykorzystując tylko jeden `` hack '': ujednoznacznienie nazwy typu / identyfikatora, parser informujący leksera o każdym typie / klasie / strukturze)

Widzę kilka z nich:

1. Type Type;jest zabronione. Identyfikator zadeklarowany jako nazwa typu nie może stać się identyfikatorem innym niż nazwa typu (zwróć uwagę, żestruct Type Type nie jest niejednoznaczna i może być nadal dozwolona).

   Istnieją 3 rodzaje names tokens:

   • types : typ wbudowany lub ze względu na typedef / class / struct
   • funkcje-szablonów
   • identyfikatory: funkcje / metody i zmienne / obiekty

   Rozważanie funkcji szablonowych jako różnych tokenów rozwiązuje tę func<niejednoznaczność. Jeśli funcjest nazwą funkcji szablonu, to <musi być początkiem listy parametrów szablonu, w przeciwnym razie funcjest wskaźnikiem funkcji i <operatorem porównania.

2. Type a(2);jest instancją obiektu. Type a();i Type a(int)są prototypami funkcji.

3. int (k); jest całkowicie zabronione, powinno być napisane int k;

4. typedef int func_type(); i typedef int (func_type)();są zabronione.

   Funkcja typedef musi być wskaźnikiem funkcji typedef: typedef int (*func_ptr_type)();

5. rekursja szablonu jest ograniczona do 1024, w przeciwnym razie zwiększone maksimum mogłoby zostać przekazane jako opcja kompilatorowi.

6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); może być również zabronione, zastąpione przez int a,b,c[9],*d; int (*f)();

   int (*g)()[9];

   int h(char);

   jeden wiersz na prototyp funkcji lub deklarację wskaźnika funkcji.

   Bardzo preferowaną alternatywą byłaby zmiana okropnej składni wskaźnika funkcji,

   int (MyClass::*MethodPtr)(char*);

   podlegać ponownemu opodatkowaniu jako:

   int (MyClass::*)(char*) MethodPtr;

   jest to spójne z operatorem rzutowania (int (MyClass::*)(char*))

7. typedef int type, *type_ptr; również może być zabronione: jedna linia na typedef. Tak to się stanie

   typedef int type;

   typedef int *type_ptr;

8. sizeof int, sizeof char, sizeof long longI co. można zadeklarować w każdym pliku źródłowym. Dlatego każdy plik źródłowy używający tego typu intpowinien zaczynać się od

   #type int : signed_integer(4)

   i unsigned_integer(4)byłoby zabronione poza tą #type dyrektywą, byłby to duży krok w głupią sizeof intniejednoznaczność obecną w tak wielu nagłówkach C ++

Kompilator implementujący C ++ z resyntaxed, napotkałby źródło C ++ korzystające z niejednoznacznej składni, przesunąłby source.cpprównież ambiguous_syntaxfolder i utworzyłby automatycznie jednoznacznie przetłumaczonysource.cpp przed jego kompilacją.

Jeśli znasz jakieś niejednoznaczne składnie C ++, dodaj je!

Jak widać w mojej odpowiedzi tutaj , C ++ zawiera składnię, której nie można deterministycznie przeanalizować przez parser LL lub LR ze względu na etap rozwiązywania typu (zwykle po parsowaniu) zmieniający kolejność operacji , a zatem podstawowy kształt AST ( zwykle oczekuje się, że zostanie dostarczony przez analizę pierwszego etapu).

Myślę, że jesteś blisko odpowiedzi.

LR (1) oznacza, że ​​parsowanie od lewej do prawej wymaga tylko jednego tokenu, aby antycypować kontekst, podczas gdy LR (∞) oznacza nieskończone przewidywanie. Oznacza to, że parser musiałby wiedzieć wszystko, co nadchodzi, aby dowiedzieć się, gdzie jest teraz.

Problem „typedef” w C ++ można przeanalizować za pomocą parsera LALR (1), który podczas analizowania buduje tablicę symboli (nie jest to czysty parser LALR). Problemu „szablonu” prawdopodobnie nie da się rozwiązać tą metodą. Zaletą tego rodzaju parsera LALR (1) jest to, że gramatyka (pokazana poniżej) jest gramatyką LALR (1) (bez niejasności).

/* C Typedef Solution. */

/* Terminal Declarations. */

   <identifier> => lookup();  /* Symbol table lookup. */

/* Rules. */

   Goal        -> [Declaration]... <eof>               +> goal_

   Declaration -> Type... VarList ';'                  +> decl_
               -> typedef Type... TypeVarList ';'      +> typedecl_

   VarList     -> Var /','...     
   TypeVarList -> TypeVar /','...

   Var         -> [Ptr]... Identifier 
   TypeVar     -> [Ptr]... TypeIdentifier                               

   Identifier     -> <identifier>       +> identifier_(1)      
   TypeIdentifier -> <identifier>      =+> typedefidentifier_(1,{typedef})

// The above line will assign {typedef} to the <identifier>,  
// because {typedef} is the second argument of the action typeidentifier_(). 
// This handles the context-sensitive feature of the C++ language.

   Ptr          -> '*'                  +> ptr_

   Type         -> char                 +> type_(1)
                -> int                  +> type_(1)
                -> short                +> type_(1)
                -> unsigned             +> type_(1)
                -> {typedef}            +> type_(1)

/* End Of Grammar. */

Poniższe dane wejściowe można przeanalizować bez problemu:

 typedef int x;
 x * y;

 typedef unsigned int uint, *uintptr;
 uint    a, b, c;
 uintptr p, q, r;

Generator LRSTAR parser odczytuje powyższy zapis gramatyki i generuje parser, który obsługuje „typedef” problem bez dwuznaczności w drzewie parsowania lub AST. (Ujawnienie: jestem facetem, który stworzył LRSTAR.)