Perché il C ++ non può essere analizzato con un parser LR (1)?

Stavo leggendo di parser e generatori di parser e ho trovato questa affermazione nella pagina di parsing di LR di wikipedia:

Molti linguaggi di programmazione possono essere analizzati utilizzando alcune varianti di un parser LR. Un’eccezione degna di nota è C ++.

Perché è così? Quale particolare proprietà del C ++ fa sì che sia imansible analizzarla con i parser LR?

Usando google, ho trovato solo che C può essere analizzato perfettamente con LR (1) ma C ++ richiede LR (∞).

C’è un thread interessante su Lambda the Ultimate che discute la grammatica LALR per C ++ .

Include un link a una tesi di dottorato che include una discussione sull’analisi di C ++, che afferma che:

“La grammatica C ++ è ambigua, dipendente dal contesto e potenzialmente richiede uno sguardo infinito per risolvere alcune ambiguità”.

Fornisce un certo numero di esempi (vedi pagina 147 del pdf).

L’esempio è:

int(x), y, *const z; 

senso

 int x; int y; int *const z; 

Paragonare a:

 int(x), y, new int; 

senso

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

(un’espressione separata da virgole).

Le due sequenze di token hanno la stessa sottosequenza iniziale ma diversi alberi di analisi, che dipendono dall’ultimo elemento. Ci possono essere arbitrariamente molti gettoni prima di disambiguating.

I parser LR non sono in grado di gestire regole grammaticali ambigue, in base alla progettazione. (Ha reso la teoria più semplice negli anni ’70, quando le idee erano state elaborate).

Sia C che C ++ consentono la seguente dichiarazione:

 x * y ; 

Ha due diversi parses:

  1. Può essere la dichiarazione di y, come puntatore al tipo x
  2. Può essere un multiplo di xey, buttando via la risposta.

Ora, potresti pensare che quest’ultimo sia stupido e dovrebbe essere ignorato. La maggior parte sarebbe d’accordo con te; tuttavia, ci sono casi in cui potrebbe avere un effetto collaterale (ad esempio, se il multiplo è sovraccarico). ma non è questo il punto. Il punto è che ci sono due differenti parses, e quindi un programma può significare cose diverse a seconda di come questo dovrebbe essere stato analizzato.

Il compilatore deve accettare quello appropriato nelle circostanze appropriate e in assenza di altre informazioni (ad esempio, la conoscenza del tipo di x) deve raccogliere entrambi al fine di decidere in seguito cosa fare. Quindi una grammatica deve permettere questo. E questo rende la grammatica ambigua.

Pertanto l’analisi LR pura non può gestirlo. Né molti altri generatori di parser ampiamente disponibili, come Antlr, JavaCC, YACC, o Bison tradizionali, o persino parser di tipo PEG, sono usati in modo “puro”.

Ci sono molti casi più complicati (la syntax del template di parsing richiede un lookahead arbitrario, mentre LALR (k) può guardare avanti alla maggior parte dei token k), ma solo un controesempio basta per abbattere l’analisi LR pura (o gli altri).

La maggior parte dei parser C / C ++ reali gestiscono questo esempio utilizzando una sorta di parser deterministico con un ulteriore trucco: si intrecciano l’analisi con la raccolta di tabelle di simboli … in modo che quando si incontra “x”, il parser sa se x è un tipo oppure no, e può quindi scegliere tra le due potenziali analisi. Ma un parser che fa ciò non è privo di contesto, e i parser LR (quelli puri, ecc.) Sono (nella migliore delle ipotesi) senza contesto.

Uno può imbrogliare e aggiungere controlli semantici di riduzione della per-regola nei parser di LR per fare questa disambiguazione. (Questo codice spesso non è semplice). La maggior parte degli altri tipi di parser ha alcuni mezzi per aggiungere controlli semantici in vari punti del parsing, che possono essere usati per fare ciò.

E se si imbroglia abbastanza, è ansible far funzionare i parser LR per C e C ++. I ragazzi della GCC lo hanno fatto per un po ‘, ma hanno rinunciato all’analisi parsing a mano, penso perché volevano una migliore diagnostica degli errori.

C’è un altro approccio, però, che è bello e pulito e analizza bene C e C ++ senza alcun hackery della tabella dei simboli: parser GLR . Questi sono parser privi di contesto completo (con un lookahead infinitamente efficace). I parser GLR accettano semplicemente entrambe le parses, producendo un “albero” (in realtà un grafo aciclico diretto che è per lo più ad albero) che rappresenta l’analisi ambigua. Una pass post-analisi può risolvere le ambiguità.

Usiamo questa tecnica nei front end C e C ++ per il nostro software DMS Reengineering Tookit (a partire da giugno 2017 questi gestiscono full C ++ 17 nei dialetti MS e GNU). Sono stati utilizzati per elaborare milioni di righe di grandi sistemi C e C ++, con analisi complete e precise che producono AST con dettagli completi del codice sorgente. (Vedi l’AST per l’analisi più irritante di C ++. )

Il problema non è mai definito in questo modo, mentre dovrebbe essere interessante:

qual è il più piccolo insieme di modifiche alla grammatica C ++ che sarebbe necessario in modo che questa nuova grammatica potesse essere analizzata perfettamente da un parser yacc “non contestualizzato”? (facendo uso solo di un ‘hack’: la disambiguazione typename / identificatore, il parser che informa il lexer di ogni typedef / class / struct)

Ne vedo alcuni:

  1. Type Type; è vietato. Un identificatore dichiarato come typename non può diventare un identificatore di tipo non tipografico (si noti che struct Type Type non è ambiguo e potrebbe essere ancora consentito).

    Esistono 3 tipi di names tokens dei names tokens :

    • types : built-type o a causa di typedef / class / struct
    • template-funzioni
    • identificatori: funzioni / metodi e variabili / oggetti

    Considerare le funzioni dei template come diversi token risolve l’ambiguità delle func< . Se func è un nome di funzione template, allora < deve essere l'inizio di un elenco di parametri del template, altrimenti func è un puntatore di funzione e < è l'operatore di confronto.

  2. Type a(2); è un'istanza di oggetti. Type a(); e Type a(int) sono prototipi di funzioni.

  3. int (k); è completamente vietato, dovrebbe essere scritto int k;

  4. typedef int func_type(); e typedef int (func_type)(); sono vietati

    Una funzione typedef deve essere una funzione pointer typedef: typedef int (*func_ptr_type)();

  5. la ricorsione del template è limitata a 1024, altrimenti un massimo aumentato potrebbe essere passato come opzione al compilatore.

  6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); potrebbe anche essere vietato, sostituito da int a,b,c[9],*d; int (*f)();

    int (*g)()[9];

    int h(char);

    dichiarazione del puntatore di una riga per funzione prototipo o funzione.

    Un'alternativa altamente preferibile sarebbe quella di modificare la syntax del puntatore di funzione awful,

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

    essere risintattato come:

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

    questo è coerente con l'operatore di cast (int (MyClass::*)(char*))

  7. typedef int type, *type_ptr; potrebbe essere vietato anche: una riga per typedef. Così diventerebbe

    typedef int type;

    typedef int *type_ptr;

  8. sizeof int , sizeof char , sizeof long long e co. potrebbe essere dichiarato in ogni file sorgente. Quindi, ogni file sorgente che fa uso del tipo int dovrebbe iniziare

    #type int : signed_integer(4)

    e unsigned_integer(4) sarebbe vietato al di fuori della direttiva #type questo sarebbe un grande passo nella stupida dimensione dell'ambiguità sizeof int presente in così tante intestazioni C ++

Il compilatore che implementa il C ++ resyntaxed, se incontrasse un sorgente C ++ facendo uso di una syntax ambigua, sposta source.cpp anche una cartella source.cpp e creerebbe automaticamente un source.cpp tradotto source.cpp prima di compilarlo.

Per favore aggiungi le tue ambigue syntax C ++ se ne conosci qualcuno!

Come potete vedere nella mia risposta qui , C ++ contiene una syntax che non può essere analizzata in modo deterministico da un parser LL o LR a causa dello stadio di risoluzione del tipo (in genere post parsing) che modifica l’ ordine delle operazioni e quindi la forma fondamentale dell’AST ( tipicamente dovrebbe essere fornito da un analisi di primo livello).

Penso che tu sia abbastanza vicino alla risposta.

LR (1) significa che l’analisi da sinistra a destra richiede solo un token per guardare avanti al contesto, mentre LR (∞) significa uno sguardo infinito. Cioè, il parser dovrebbe sapere tutto ciò che stava arrivando per capire dove si trova ora.

Il problema “typedef” in C ++ può essere analizzato con un parser LALR (1) che costruisce una tabella di simboli durante l’analisi (non un parser LALR puro). Il problema “modello” probabilmente non può essere risolto con questo metodo. Il vantaggio di questo tipo di parser LALR (1) è che la grammatica (mostrata sotto) è una grammatica LALR (1) (nessuna ambiguità).

 /* C Typedef Solution. */ /* Terminal Declarations. */  => lookup(); /* Symbol table lookup. */ /* Rules. */ Goal -> [Declaration]...  +> goal_ Declaration -> Type... VarList ';' +> decl_ -> typedef Type... TypeVarList ';' +> typedecl_ VarList -> Var /','... TypeVarList -> TypeVar /','... Var -> [Ptr]... Identifier TypeVar -> [Ptr]... TypeIdentifier Identifier ->  +> identifier_(1) TypeIdentifier ->  =+> typedefidentifier_(1,{typedef}) // The above line will assign {typedef} to the , // 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. */ 

Il seguente input può essere analizzato senza problemi:

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

Il generatore di parser LRSTAR legge la notazione grammaticale di cui sopra e genera un parser che gestisce il problema “typedef” senza ambiguità nell’albero di analisi o AST. (Divulgazione: sono il ragazzo che ha creato LRSTAR .)