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 (∞).
c++
parsing
grammar
formal-languages
Heiter
quelle
quelle
Antworten:
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:
Es werden einige Beispiele angeführt (siehe Seite 147 des PDFs).
Das Beispiel ist:
Bedeutung
Vergleichen mit:
Bedeutung
(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.
quelle
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:
Es hat zwei verschiedene Parsen:
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 ++. )
quelle
x * y
und kicherte - es ist erstaunlich, wie wenig man an solche kleinen Zweideutigkeiten denkt.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:
Type Type;
ist verboten. Ein als Typname deklarierter Bezeichner kann nicht zu einem Bezeichner ohne Typnamen werden (Hinweis, derstruct Type Type
nicht mehrdeutig ist und dennoch zulässig sein könnte).Es gibt 3 Arten von
names tokens
:types
: builtin-type oder wegen eines typedef / class / structDas Betrachten von Vorlagenfunktionen als unterschiedliche Token löst die
func<
Mehrdeutigkeit. Wennfunc
es sich um einen Vorlagenfunktionsnamen handelt,<
muss dies der Anfang einer Vorlagenparameterliste sein, andernfallsfunc
handelt es sich um einen Funktionszeiger und<
um den Vergleichsoperator.Type a(2);
ist eine Objektinstanziierung.Type a();
undType a(int)
sind Funktionsprototypen.int (k);
ist völlig verboten, sollte geschrieben werdenint k;
typedef int func_type();
undtypedef int (func_type)();
sind verboten.Eine Funktion typedef muss ein Funktionszeiger typedef sein:
typedef int (*func_ptr_type)();
Die Vorlagenrekursion ist auf 1024 begrenzt, andernfalls kann ein erhöhtes Maximum als Option an den Compiler übergeben werden.
int a,b,c[9],*d,(*f)(), (*g)()[9], h(char);
könnte auch verboten werden, ersetzt durchint 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*))
typedef int type, *type_ptr;
könnte auch verboten sein: eine Zeile pro typedef. So würde es werdentypedef int type;
typedef int *type_ptr;
sizeof int
,sizeof char
,sizeof long long
Und co. könnte in jeder Quelldatei deklariert werden. Daher sollte jede Quelldatei, die den Typint
verwendet, 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 dummesizeof int
Mehrdeutigkeit, die in so vielen C ++ - Headern vorhanden istDer Compiler, der das resyntaxierte C ++ implementiert, würde, wenn er auf eine C ++ - Quelle stößt, die mehrdeutige Syntax verwendet,
source.cpp
auch einenambiguous_syntax
Ordner verschieben undsource.cpp
vor dem Kompilieren automatisch eine eindeutige Übersetzung erstellen.Bitte fügen Sie Ihre mehrdeutigen C ++ - Syntaxen hinzu, wenn Sie welche kennen!
quelle
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).
quelle
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.
quelle
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).
Die folgende Eingabe kann problemlos analysiert werden:
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