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

Question

czytałem o parserami i generatorów parsera i znalazłem to oświadczenie w Wikipedii LR analizowania -page:

Wiele języków programowania może być analizowany przy użyciu jakąś odmianę parsera LR. Jednym z godnych uwagi wyjątków jest C++.

Dlaczego tak jest? Jaka szczególna właściwość C++ powoduje, że nie można parsować z parserami LR?

Używając google, stwierdziłem tylko, że C można idealnie przeanalizować przy pomocy LR (1), ale C++ wymaga LR (∞).

Answer 1

Istnieje interesujący wątek na Lambda the Ultimate, który omawia numer LALR grammar for C++.

Zawiera link do PhD thesis która obejmuje dyskusję C++ parsowania, który stanowi, że:

„gramatyki C++ jest niejednoznaczna, zależne od kontekstu i potencjalnie wymaga nieskończonej uprzedzona rozwiązać pewne niejasności ".

Podaje szereg przykładów (patrz strona 147 dokumentu pdf).

Przykładem jest:

int(x), y, *const z; 

oznacza

int x; 
int y; 
int *const z; 

Porównaj z:

int(x), y, new int; 

oznacza

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

(wyrażenie rozdzielane przecinkami).

Dwie sekwencje tokenów mają taki sam początkowy podsekwencja, ale różne drzewa analizy, które zależą od ostatniego elementu. Przed ujednoznacznieniem może być dowolnie wiele żetonów.

Answer 2

Myślę, że jesteś całkiem blisko odpowiedzi.

LR (1) oznacza, że ​​parsowanie od lewej do prawej wymaga tylko jednego znaku, aby patrzeć w przyszłość, podczas gdy LR (∞) oznacza nieskończone patrzenie w przyszłość. Oznacza to, że parser musiałby wiedzieć wszystko, co nadchodziło, aby dowiedzieć się, gdzie jest teraz.

Answer 3

Analizatory składni LR nie mogą obsługiwać niejednoznacznych reguł gramatycznych, zgodnie z projektem. (Uczynił teorię łatwiejszą w latach 70., kiedy pomysły były opracowywane).

C i C++ zarówno umożliwiają następujące oświadczenie:

x * y ; 

Posiada dwie różne analizuje:

1. może być deklaracja y, jako wskaźnik do x typ
2. może on być mnożnikiem x i y, odrzucając odpowiedź.

Teraz możesz myśleć, że to drugie jest głupie i powinno zostać zignorowane. Większość zgodziłaby się z tobą; jednak istnieją przypadki, w których może on wywoływać efekt uboczny (np. jeśli mnożenie jest przeciążone). ale nie o to chodzi. Chodzi o to, że są dwiema różnymi parami, a zatem program może oznaczać różne rzeczy w zależności od tego, jak przeanalizowano ten , który powinien być.

Kompilator musi zaakceptować odpowiedni pod odpowiednimi warunkami, a przy braku jakichkolwiek innych informacji (np. Znajomość typu x) musi zebrać oba, aby zdecydować później, co robić. Dlatego gramatyka musi na to pozwalać. A to sprawia, że ​​gramatyka jest niejednoznaczna.

Tak więc parsowanie LR nie poradzi sobie z tym. Ponadto wiele innych szeroko dostępnych generatorów analizatorów składni, takich jak Antlr, JavaCC, YACC lub tradycyjne Bizon, a nawet parserów w stylu PEG, nie jest używane w "czysty" sposób.

Istnieje wiele bardziej skomplikowanych przypadkach (analizowania składni szablonu wymaga arbitralnego uprzedzona, natomiast LALR (k) może patrzeć w przyszłość w większości żetonów K), ale tylko trwa tylko jeden kontrprzykład zestrzelić czystego LR (lub inne) parsowania.

większość/parser prawdziwy C C++ obsłużyć ten przykład za pomocą pewnego rodzaju deterministyczny parsera z dodatkowym Hack: oni splatają parsowania z tabeli symbol kolekcji ... tak że przez czas „X” jest napotkanych się parser wie, czy x jest typem, czy nie, i może w ten sposób wybrać między dwoma potencjalnymi analizami. Ale analizator składni , który to robi, nie jest pozbawiony kontekstu, a parsery LR (te czyste itp.) Są (w najlepszym wypadku) wolne od kontekstu.

Można oszukiwać i dodawać semantyczne kontrole czasu na podstawie reguł w do parserów LR, aby dokonać tej ujednoznacznienia. (Ten kod często nie jest prosty). Większość innych typów analizatorów składni ma pewne możliwości dodawania semantycznych sprawdzeń w różnych punktach w analizie, które można wykorzystać do tego.

A jeśli oszukasz wystarczająco, możesz sprawić, by parsery LR działały na C i C++. Faceci GCC robili to przez jakiś czas, ale dali mi do ręcznego kodowania, myślę, że chcieli poprawić diagnostykę błędów.

Istnieje jednak inne podejście, które jest ładne i czyste i parsuje C i C++ w porządku bez tablicy symboli hackery: GLR parsers. Są to pełne parserów bez kontekstu (mających faktycznie nieskończony wcześniejszą stronę).Analizatory składni GLR po prostu akceptują analizy zarówno, jak i , tworząc "drzewo" (właściwie skierowany wykres acykliczny, który jest w większości podobny do drzewa), co oznacza dwuznaczną analizę. Przepustka po analizie składniowej może rozwiązać niejednoznaczności.

Używamy tej techniki w C i C++ przodu kończy się dla naszego DMS Software Reengineering Tookit (od czerwca 2017 je obsługiwać pełny C++ 17 w SM i GNU dialektów). Służyły one do przetwarzania milionów linii dużych systemów C i C++, z kompletnymi, dokładnymi analizami składającymi się na AST z kompletnymi szczegółami kodu źródłowego. (Patrz the AST for C++'s most vexing parse.)

Answer 4

Jak widać w moim answer here, C++ zawiera składni, które nie mogą być deterministyczny analizowany przez LL lub LR parser ze względu na scenie rozdzielczość Typ (typowo post-parsowania) zmiana kolejność operacji, a zatem podstawowy kształt AST (zwykle oczekuje się, że zostanie dostarczony przez analizę pierwszego stopnia).

Answer 5

Problemem nie jest zdefiniowana w ten sposób, podczas gdy powinno być ciekawe:

jaki jest najmniejszy zbiór zmian do gramatyki C++, które byłyby konieczne, aby ta nowa gramatyka może być doskonale przetwarzane przez „nie- bez kontekstowy "parser yacc? (Korzystając tylko z jednego 'włamać': ten ujednoznacznienie typename/identyfikator, parser informując lexer każdego typedef/klasa/struct)

widzę kilka z nich:

1. Type Type; jest zabronione. Identyfikator zadeklarowany jako nazwa_typu nie może stać się identyfikatorem innym niż nazwa_pliku (pamiętaj, że struct Type Type nie jest niejednoznaczny i może być nadal dozwolony).

   Istnieją 3 rodzaje names tokens:

   • types: wbudowana typu lub z powodu typedef/klasa/struct
   • szablon-functions
   • identyfikatory: funkcje/metody i zmiennych/obiektów

   Uwzględnianie funkcji szablonu jako różnych tokenów rozwiązuje niejednoznaczność func<. Jeśli func jest nazwą funkcji-szablonu, wówczas < musi być początkiem listy parametrów szablonu, w przeciwnym razie func jest wskaźnikiem funkcji, a operator porównania to <.

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 musi być typedef typedef wskaźnik funkcji: typedef int (*func_ptr_type)();

5. szablon rekurencji jest ograniczona do 1024, inaczej zwiększona maksymalna mogą być przekazywane jako opcja do kompilatora.

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

   int (*g)()[9];

   int h(char);

   jednej linii za prototyp funkcji lub deklaracji wskaźnik funkcji.

   bardzo korzystną alternatywą byłoby zmienić okropny składni wskaźnik funkcji,

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

   jest resyntaxed jak:

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

   co jest spójne z operatorem szarego (int (MyClass::*)(char*))

7. typedef int type, *type_ptr; może być również zabronione: jedna linia na typedef. Zatem byłoby stać

   typedef int type;

   typedef int *type_ptr;

8. sizeof int, sizeof char, sizeof long long i co. może być zadeklarowany w każdym pliku źródłowym. Zatem każdy plik źródłowy wykorzystanie typu int należy rozpocząć

   #type int : signed_integer(4)

   i unsigned_integer(4) byłyby zakazane poza tym #type dyrektywy będzie to duży krok do głupiej sizeof int niejasności obecne w tak wielu nagłówki C++

kompilator realizacji resyntaxed C++ byłoby, gdyby napotkania C++ źródło wykorzystuj składni niejednoznacznej, przesuń source.cpp zbyt folder ambiguous_syntax i automatycznie utworzy jednoznaczny przetłumaczony source.cpp przed skompilowaniem go.

Proszę dodać niejednoznaczne składnie C++, jeśli znasz kilka!