Warum kann C ++ nicht mit einem LR (1) -Parser analysiert werden?

153

Ich habe über Parser und Parsergeneratoren gelesen und diese Aussage auf der LR-Parsing-Seite von Wikipedia gefunden:

Viele Programmiersprachen können mit einer Variation eines LR-Parsers analysiert werden. Eine bemerkenswerte Ausnahme ist C ++.

Wieso ist es so? Welche besondere Eigenschaft von C ++ macht es unmöglich, mit LR-Parsern zu analysieren?

Mit Google habe ich nur festgestellt, dass C perfekt mit LR (1) analysiert werden kann, aber C ++ erfordert LR (∞).

Heiter
quelle
7
Genau wie: Sie müssen die Rekursion verstehen, um die Rekursion zu lernen ;-).
Toon Krijthe
5
"Sie werden Parser verstehen, wenn Sie diesen Satz analysieren."
ilya n.

Antworten:

92

Es gibt einen interessanten Thread zu Lambda the Ultimate , der die LALR-Grammatik für C ++ behandelt .

Es enthält einen Link zu einer Doktorarbeit , die eine Diskussion über das C ++ - Parsen enthält, in der es heißt:

"Die C ++ - Grammatik ist mehrdeutig, kontextabhängig und erfordert möglicherweise einen unendlichen Lookahead, um einige Mehrdeutigkeiten aufzulösen."

Es werden einige Beispiele angeführt (siehe Seite 147 des PDFs).

Das Beispiel ist:

int(x), y, *const z;

Bedeutung

int x;
int y;
int *const z;

Vergleichen mit:

int(x), y, new int;

Bedeutung

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

(ein durch Kommas getrennter Ausdruck).

Die beiden Token-Sequenzen haben dieselbe anfängliche Teilsequenz, aber unterschiedliche Analysebäume, die vom letzten Element abhängen. Es können beliebig viele Token vor dem eindeutigen sein.

Rob Walker
quelle
29
Es wäre cool, eine Zusammenfassung über die Seite 147 auf dieser Seite zu haben. Ich werde diese Seite allerdings lesen. (+1)
Fröhlich
11
Das Beispiel ist: int (x), y, * const z; // Bedeutung: int x; int y; int * const z; (eine Folge von Deklarationen) int (x), y, new int; // Bedeutung: (int (x)), (y), (new int)); (ein durch Kommas getrennter Ausdruck) Die beiden Token-Sequenzen haben dieselbe anfängliche Teilsequenz, aber unterschiedliche Analysebäume, die vom letzten Element abhängen. Es können beliebig viele Token vor dem eindeutigen sein.
Blaisorblade
6
Nun, in diesem Zusammenhang bedeutet ∞ "beliebig viele", da der Lookahead immer durch die Eingabelänge begrenzt wird.
MauganRa
1
Ich bin ziemlich verwirrt über das Zitat aus einer Doktorarbeit. Wenn es eine Mehrdeutigkeit gibt, kann per Definition KEIN Lookahead jemals die Mehrdeutigkeit "auflösen" (dh entscheiden, welche Analyse die richtige ist, da mindestens 2 Parsen von der Grammatik als korrekt angesehen werden). Darüber hinaus erwähnt das Zitat die Mehrdeutigkeit von C, aber die Erklärung zeigt keine Mehrdeutigkeit, sondern nur ein nicht mehrdeutiges Beispiel, bei dem eine Analyseentscheidung nur nach einer willkürlich langen Vorausschau getroffen werden kann.
Dodecaplex
231

LR-Parser können nicht mit mehrdeutigen Grammatikregeln umgehen. (Erleichterte die Theorie in den 1970er Jahren, als die Ideen ausgearbeitet wurden).

C und C ++ erlauben beide die folgende Anweisung:

x * y ;

Es hat zwei verschiedene Parsen:

  1. Dies kann die Deklaration von y als Zeiger auf den Typ x sein
  2. Es kann eine Multiplikation von x und y sein, die die Antwort wegwirft.

Jetzt könnte man denken, dass Letzteres dumm ist und ignoriert werden sollte. Die meisten würden dir zustimmen; Es gibt jedoch Fälle, in denen es zu Nebenwirkungen kommen kann (z. B. wenn die Multiplikation überlastet ist). aber das ist nicht der Punkt. Der Punkt ist, dass es zwei verschiedene Parses gibt, und daher kann ein Programm verschiedene Dinge bedeuten, je nachdem, wie dies hätte analysiert werden sollen.

Der Compiler muss die entsprechende unter den entsprechenden Umständen akzeptieren und in Ermangelung anderer Informationen (z. B. Kenntnis des Typs von x) beide sammeln, um später zu entscheiden, was zu tun ist. Eine Grammatik muss dies also zulassen. Und das macht die Grammatik mehrdeutig.

Somit kann das reine LR-Parsen damit nicht umgehen. Auch viele andere weit verbreitete Parser-Generatoren wie Antlr, JavaCC, YACC oder traditionelle Bison- oder sogar PEG-Parser können nicht "rein" verwendet werden.

Es gibt viele kompliziertere Fälle (die Syntax von Parsing-Vorlagen erfordert einen beliebigen Lookahead, während LALR (k) höchstens k Token vorausschauen kann), aber nur ein Gegenbeispiel ist erforderlich, um das reine LR-Parsing (oder die anderen) abzuschießen .

Die meisten echten C / C ++ - Parser behandeln dieses Beispiel, indem sie eine Art deterministischen Parser mit einem zusätzlichen Hack verwenden: Sie verflechten die Analyse mit der Symboltabellensammlung ... sodass der Parser zum Zeitpunkt des Auftretens von "x" weiß, ob x ein Typ ist oder nicht, und kann somit zwischen den beiden möglichen Parsen wählen. Ein Parser, der dies tut, ist jedoch nicht kontextfrei, und LR-Parser (die reinen usw.) sind (bestenfalls) kontextfrei.

Man kann die LR-Parser betrügen und semantische Überprüfungen der Regelverkürzungszeit pro Regel hinzufügen, um diese Disambiguierung durchzuführen. (Dieser Code ist oft nicht einfach). Die meisten anderen Parsertypen verfügen über einige Mittel, um an verschiedenen Stellen der Analyse semantische Überprüfungen hinzuzufügen, die dazu verwendet werden können.

Und wenn Sie genug schummeln, können Sie LR-Parser für C und C ++ arbeiten lassen. Die GCC-Leute haben es eine Weile gemacht, aber es für das handcodierte Parsen aufgegeben, denke ich, weil sie eine bessere Fehlerdiagnose wollten.

Es gibt jedoch einen anderen Ansatz, der nett und sauber ist und C und C ++ ohne Hacking in Symboltabellen einwandfrei analysiert: GLR-Parser . Dies sind vollständig kontextfreie Parser (mit effektiv unendlichem Lookahead). GLR-Parser akzeptieren einfach beide Parsen und erzeugen einen "Baum" (eigentlich ein gerichteter azyklischer Graph, der meistens baumartig ist), der die mehrdeutige Analyse darstellt. Ein Durchlauf nach dem Parsen kann die Mehrdeutigkeiten beheben.

Wir verwenden diese Technik in den C- und C ++ - Frontends für unser DMS Software Reengineering Tookit (ab Juni 2017 verarbeiten diese C ++ 17 in MS- und GNU-Dialekten). Sie wurden verwendet, um Millionen von Zeilen großer C- und C ++ - Systeme mit vollständigen, präzisen Analysen zu verarbeiten, die ASTs mit vollständigen Details des Quellcodes erzeugen. (Siehe AST für die ärgerlichste Analyse von C ++. )

Ira Baxter
quelle
11
Während das Beispiel 'x * y' interessant ist, kann dasselbe in C passieren ('y' kann ein typedef oder eine Variable sein). C kann jedoch von einem LR (1) -Parser analysiert werden. Was ist also der Unterschied zu C ++?
Martin Cote
12
Meine Antwort hatte bereits bemerkt, dass C das gleiche Problem hatte, ich denke, Sie haben das verpasst. Nein, es kann aus demselben Grund nicht von LR (1) analysiert werden. Äh, was meinst du mit 'y' kann ein typedef sein? Vielleicht meintest du 'x'? Das ändert nichts.
Ira Baxter
6
Parse 2 ist in C ++ nicht unbedingt dumm, da * überschrieben werden kann, um Nebenwirkungen zu haben.
Dour High Arch
8
Ich sah x * yund kicherte - es ist erstaunlich, wie wenig man an solche kleinen Zweideutigkeiten denkt.
New123456
51
@altie Sicherlich würde niemand einen Bitverschiebungsoperator überladen, damit er die meisten Variablentypen in einen Stream schreibt, oder?
Troy Daniels
16

Das Problem wird niemals so definiert, obwohl es interessant sein sollte:

Was ist die kleinste Menge an Änderungen an der C ++ - Grammatik, die erforderlich wären, damit diese neue Grammatik von einem "nicht kontextfreien" Yacc-Parser perfekt analysiert werden kann? (Verwenden Sie nur einen 'Hack': die Disambiguierung von Typname / Bezeichner, der Parser informiert den Lexer über jede Typedef / Klasse / Struktur)

Ich sehe einige:

  1. Type Type;ist verboten. Ein als Typname deklarierter Bezeichner kann nicht zu einem Bezeichner ohne Typnamen werden (Hinweis, der struct Type Typenicht mehrdeutig ist und dennoch zulässig sein könnte).

    Es gibt 3 Arten von names tokens:

    • types : builtin-type oder wegen eines typedef / class / struct
    • Template-Funktionen
    • Bezeichner: Funktionen / Methoden und Variablen / Objekte

    Das Betrachten von Vorlagenfunktionen als unterschiedliche Token löst die func<Mehrdeutigkeit. Wenn funces sich um einen Vorlagenfunktionsnamen handelt, <muss dies der Anfang einer Vorlagenparameterliste sein, andernfalls funchandelt es sich um einen Funktionszeiger und <um den Vergleichsoperator.

  2. Type a(2);ist eine Objektinstanziierung. Type a();und Type a(int)sind Funktionsprototypen.

  3. int (k); ist völlig verboten, sollte geschrieben werden int k;

  4. typedef int func_type(); und typedef int (func_type)();sind verboten.

    Eine Funktion typedef muss ein Funktionszeiger typedef sein: typedef int (*func_ptr_type)();

  5. Die Vorlagenrekursion ist auf 1024 begrenzt, andernfalls kann ein erhöhtes Maximum als Option an den Compiler übergeben werden.

  6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); könnte auch verboten werden, ersetzt durch int a,b,c[9],*d; int (*f)();

    int (*g)()[9];

    int h(char);

    eine Zeile pro Funktionsprototyp oder Funktionszeigerdeklaration.

    Eine sehr bevorzugte Alternative wäre, die schreckliche Funktionszeigersyntax zu ändern.

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

    resyntaxiert werden als:

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

    Dies stimmt mit dem Darsteller überein (int (MyClass::*)(char*))

  7. typedef int type, *type_ptr; könnte auch verboten sein: eine Zeile pro typedef. So würde es werden

    typedef int type;

    typedef int *type_ptr;

  8. sizeof int, sizeof char, sizeof long longUnd co. könnte in jeder Quelldatei deklariert werden. Daher sollte jede Quelldatei, die den Typ intverwendet, mit beginnen

    #type int : signed_integer(4)

    und unsigned_integer(4)wäre außerhalb dieser #type Direktive verboten, wäre dies ein großer Schritt in die dumme sizeof intMehrdeutigkeit, die in so vielen C ++ - Headern vorhanden ist

Der Compiler, der das resyntaxierte C ++ implementiert, würde, wenn er auf eine C ++ - Quelle stößt, die mehrdeutige Syntax verwendet, source.cppauch einen ambiguous_syntaxOrdner verschieben und source.cppvor dem Kompilieren automatisch eine eindeutige Übersetzung erstellen.

Bitte fügen Sie Ihre mehrdeutigen C ++ - Syntaxen hinzu, wenn Sie welche kennen!

reuns
quelle
3
C ++ ist zu gut verankert. Niemand wird dies in der Praxis tun. Die Leute (wie wir), die Frontends bauen, beißen einfach in die Kugel und übernehmen die Technik, damit die Parser funktionieren. Und solange Vorlagen in der Sprache vorhanden sind, erhalten Sie keinen reinen kontextfreien Parser.
Ira Baxter
9

Wie Sie in meiner Antwort hier sehen können , enthält C ++ eine Syntax, die von einem LL- oder LR-Parser nicht deterministisch analysiert werden kann, da die Typauflösungsstufe (normalerweise nach dem Parsen) die Reihenfolge der Operationen und damit die Grundform des AST ändert ( wird normalerweise von einer Analyse der ersten Stufe erwartet).

Sam Harwell
quelle
3
Die Parsing-Technologie, die mit Mehrdeutigkeiten umgeht, erzeugt beim Parsen einfach beide AST-Varianten und entfernt je nach Typinformationen einfach die falsche.
Ira Baxter
@Ira: Ja, das ist richtig. Der besondere Vorteil davon ist, dass Sie die Trennung der Analyse der ersten Stufe beibehalten können. Obwohl es im GLR-Parser am häufigsten bekannt ist, gibt es keinen besonderen Grund, warum Sie C ++ nicht mit einer "GLL?" Parser auch.
Sam Harwell
"GLL"? Na klar, aber Sie müssen die Theorie herausfinden und eine Arbeit schreiben, die Sie für den Rest verwenden können. Wahrscheinlicher ist, dass Sie einen handcodierten Top-Down-Parser oder einen Backtracking-LALR () -Parser verwenden (aber die "abgelehnten" Parser beibehalten) oder einen Earley-Parser ausführen können. GLR hat den Vorteil, eine verdammt gute Lösung zu sein, ist gut dokumentiert und mittlerweile gut bewiesen. Eine GLL-Technologie müsste einige ziemlich bedeutende Vorteile haben, um GLR anzuzeigen.
Ira Baxter
Das Rascal-Projekt (Niederlande) behauptet, einen scannerlosen GLL-Parser zu erstellen. In Arbeit ist es möglicherweise schwierig, Online-Informationen zu finden. en.wikipedia.org/wiki/RascalMPL
Ira Baxter
@IraBaxter Es scheint neue Entwicklungen auf GLL zu geben: siehe dieses Papier von 2010 über GLL dotat.at/tmp/gll.pdf
Sjoerd
6

Ich denke, Sie sind der Antwort ziemlich nahe.

LR (1) bedeutet, dass für das Parsen von links nach rechts nur ein Token benötigt wird, um nach dem Kontext zu suchen, während LR (∞) einen unendlichen Blick nach vorne bedeutet. Das heißt, der Parser müsste alles wissen, was kommen würde, um herauszufinden, wo es jetzt ist.

casademora
quelle
4
Ich erinnere mich aus meiner Compiler-Klasse, dass LR (n) für n> 0 mathematisch auf LR (1) reduzierbar ist. Gilt das nicht für n = unendlich?
Rmeador
14
Nein, es gibt einen unpassierbaren Berg mit einem Unterschied zwischen n und unendlich.
Ephemient
4
Ist die Antwort nicht: Ja, bei unendlich viel Zeit? :)
Steve Fallows
7
Nach meiner vagen Erinnerung daran, wie LR (n) -> LR (1) abläuft, müssen tatsächlich neue Zwischenzustände erstellt werden, sodass die Laufzeit eine nicht konstante Funktion von 'n' ist. Das Übersetzen von LR (inf) -> LR (1) würde unendlich lange dauern.
Aaron
5
"Ist die Antwort nicht: Ja, bei unendlich viel Zeit?" - Nein: Der Ausdruck "bei unendlicher Zeit" ist nur eine unsinnige, kurze Art zu sagen: "Kann bei endlicher Zeit nicht durchgeführt werden". Wenn Sie "unendlich" sehen, denken Sie: "nicht endlich".
ChrisW
4

Das "typedef" -Problem in C ++ kann mit einem LALR (1) -Parser analysiert werden, der beim Parsen eine Symboltabelle erstellt (kein reiner LALR-Parser). Das "Vorlagen" -Problem kann mit dieser Methode wahrscheinlich nicht gelöst werden. Der Vorteil dieser Art von LALR (1) -Parser besteht darin, dass die Grammatik (siehe unten) eine LALR (1) -Grammatik ist (keine Mehrdeutigkeit).

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

Die folgende Eingabe kann problemlos analysiert werden:

 typedef int x;
 x * y;

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

Der LRSTAR-Parsergenerator liest die obige Grammatiknotation und generiert einen Parser, der das "typedef" -Problem ohne Mehrdeutigkeit im Analysebaum oder AST behandelt. (Offenlegung: Ich bin der Typ, der LRSTAR erstellt hat.)


quelle
Dies ist der Standard-Hack, den GCC mit seinem früheren LR-Parser verwendet, um die Mehrdeutigkeit von Dingen wie "x * y" zu behandeln. Leider gibt es immer noch die willkürlich große Lookahead-Anforderung, andere Konstrukte zu analysieren, so dass LR (k) keine Lösung für ein festes k ist. (GCC wechselte zu rekursivem Abstieg mit mehr Ad-Hockery).
Ira Baxter