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

StackOverflow https://stackoverflow.com/questions/243383

Domanda

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

  

Molti linguaggi di programmazione possono essere analizzati usando alcune varianti di un parser LR. Un'eccezione notevole è C ++.

Perché è così? Quale particolare proprietà di C ++ rende impossibile analizzare i parser LR?

Usando Google, ho scoperto solo che C può essere perfettamente analizzato con LR (1) ma C ++ richiede LR (& # 8734;).

È stato utile?

Soluzione

C'è una discussione interessante su Lambda the Ultimate che discute il grammatica LALR per C ++ .

Include un collegamento a una Tesi di dottorato questo include una discussione sull'analisi del C ++, che afferma che:

  

" la grammatica C ++ è ambigua,   dipendente dal contesto e potenzialmente   richiede infiniti lookahead per risolvere   alcune ambiguità " ;.

Continua con un numero di esempi (vedi pagina 147 del pdf).

L'esempio è: 

int(x), y, *const z;

significato 

int x;
int y;
int *const z;

Confronta con: 

int(x), y, new int;

significato 

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

(un'espressione separata da virgola).

Le due sequenze di token hanno la stessa sottosequenza iniziale ma alberi di analisi diversi, che dipendono dall'ultimo elemento. Ci possono essere arbitrariamente molti token prima di quello non ambiguo.

Altri suggerimenti

I parser LR non possono gestire regole grammaticali ambigue, in base alla progettazione. (Ha reso la teoria più semplice negli anni '70 quando le idee venivano elaborate).

C e C ++ consentono entrambe la seguente dichiarazione: 

x * y ;

Ha due analisi diverse:

  1. Può essere la dichiarazione di y, come puntatore a digitare x
  2. Può essere una moltiplicazione di xey, eliminando la risposta.

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

Il compilatore deve accettare quello appropriato nelle circostanze appropriate e in assenza di qualsiasi altra informazione (ad esempio, conoscenza del tipo di x) deve raccogliere entrambi per decidere in seguito cosa fare. Quindi una grammatica deve permetterlo. E questo rende la grammatica ambigua.

Quindi l'analisi pura di LR non può gestirlo. Né molti altri generatori di parser ampiamente disponibili, come Antlr, JavaCC, YACC o Bison tradizionale, o persino parser in stile PEG, possono essere usati in un & Quot; pure & Quot; modo.

Esistono molti casi più complicati (l'analisi della sintassi del modello richiede un lookahead arbitrario, mentre LALR (k) può guardare avanti alla maggior parte dei token k), ma solo un solo controesempio serve per abbattere puro Analisi di LR (o degli altri).

I parser C / C ++ più reali gestiscono questo esempio usando alcuni tipo di parser deterministico con un trucco extra: si intrecciano con l'analisi della tabella dei simboli raccolta ... in modo che al momento " x " è incontrato, il parser sa se x è un tipo o no, e può quindi scegli tra i due potenziali analisi. Ma un parser ciò non è privo di contesto e parser LR (quelli puri, ecc.) sono (nella migliore delle ipotesi) liberi dal contesto.

Uno può imbrogliare e aggiungere controlli semantici per tempo di riduzione per regola nel file ai parser LR per fare questo chiarimento. (Questo codice spesso non è semplice). La maggior parte degli altri tipi di parser hanno alcuni mezzi per aggiungere controlli semantici in vari punti nell'analisi, che può essere usato per fare questo.

E se trucchi abbastanza, puoi far funzionare i parser LR C e C ++. I ragazzi del GCC lo fecero per un po ', ma lo diedero per l'analisi codificata a mano, penso perché volevano migliore diagnostica degli errori.

C'è un altro approccio, comunque, che è carino e pulito e analizza C e C ++ bene senza alcuna tabella dei simboli hackery: parser GLR . Questi sono parser completi senza contesto (avendo effettivamente infinito guarda avanti). I parser GLR accettano semplicemente entrambi analisi, producendo un " albero " (in realtà un grafico aciclico diretto che è per lo più ad albero) quello rappresenta l'analisi ambigua. Un passaggio post-analisi può risolvere le ambiguità.

Usiamo questa tecnica nei front-end C e C ++ per i nostri DMS Reengineering Tookit (a partire da giugno 2017 questi gestiscono il C ++ 17 completo nei dialetti MS e GNU). Sono stati usati per elaborare milioni di linee 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 del C ++. )

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

qual è la più piccola serie di modifiche alla grammatica C ++ che sarebbe necessaria affinché questa nuova grammatica potesse essere perfettamente analizzata da un " " senza contesto; parser yacc? (facendo uso di un solo 'hack': la disambiguazione di typename / identificatore, il parser che informa il lexer di ogni typedef / class / struct)

Ne vedo alcuni:

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

    Esistono 3 tipi di names tokens:

    • types: tipo incorporato o a causa di un typedef / class / struct
    • template-funzioni
    • identificatori: funzioni / metodi e variabili / oggetti

    Considerare le funzioni del modello come token diversi risolve l'ambiguità func<. Se func è un nome di funzione modello, allora < deve essere l'inizio di un elenco di parametri del modello, altrimenti Type a(2); è un puntatore a funzione e Type a(); è l'operatore di confronto.

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

  3. typedef int func_type(); è completamente proibito, deve essere scritto typedef int (func_type)();

  4. typedef int (*func_ptr_type)(); e int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); sono vietati.

    Una funzione typedef deve essere un puntatore funzione typedef: int a,b,c[9],*d;

  5. La ricorsione del modello è limitata a 1024, altrimenti un massimo maggiore potrebbe essere passato come opzione al compilatore.

    6. Anche

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

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

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

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

    Un'alternativa altamente preferita sarebbe quella di cambiare la terribile sintassi del puntatore a funzione,

    (int (MyClass::*)(char*))

    risincronizzato come:

    typedef int type, *type_ptr;

    questo è coerente con l'operatore del cast typedef int type;

    7. Anche

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

    sizeof int

    sizeof char

  8. sizeof long long, int, #type int : signed_integer(4) e co. potrebbe essere dichiarato in ciascun file sorgente. Pertanto, ogni file sorgente che utilizza il tipo unsigned_integer(4) dovrebbe iniziare con

    #type

    e source.cpp sarebbero vietati al di fuori di tale direttiva ambiguous_syntax questo sarebbe un grande passo verso la stupida <=> ambiguità presente in così tante intestazioni C ++

Il compilatore che implementa il C ++ resintassato, se incontra una fonte C ++ che utilizza una sintassi ambigua, sposta <=> troppo una cartella <=> e creerebbe automaticamente un tradotto inequivocabile prima di compilarlo.

Aggiungi le tue sintassi C ++ ambigue se ne conosci alcune!

Come puoi vedere nella mia rispondi qui , C ++ contiene sintassi che non può essere analizzata in modo deterministico da un parser LL o LR a causa della fase di risoluzione del tipo (in genere post-analisi) che modifica ordine delle operazioni , e quindi la forma fondamentale del AST (in genere dovrebbe essere fornito da un'analisi del primo stadio).

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 (& # 8734;) significa uno sguardo infinito. Cioè, il parser dovrebbe sapere tutto ciò che stava per capire dove si trova ora.

Il " typedef " il problema in C ++ può essere analizzato con un parser LALR (1) che crea una tabella dei simboli durante l'analisi (non un parser LALR puro). Il & Quot; template & Quot; il problema 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. */

   <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. */

È possibile analizzare senza problemi il seguente input: 

 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 sopra e genera un parser che gestisce il " typedef < !> quot; problema senza ambiguità nell'albero di analisi o AST. (Divulgazione: sono il ragazzo che ha creato LRSTAR.)

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top