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

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

Frage

Ich war über Parser und Parser-Generatoren zu lesen und fand diese Aussage in Wikipedias LR-Parsing -page:

  

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

Warum ist es so? Was für besondere Eigenschaft von C ++ es unmöglich zu sein, verursacht mit LR-Parser zu analysieren?

Verwenden von Google, fand ich nur, dass C lässt sich perfekt mit LR analysiert werden (1), aber C ++ erfordert LR (∞).

War es hilfreich?

Lösung

Es ist ein interessanter Thread auf Lambda the Ultimate , die die LALR Grammatik für C ++ .

Es enthält einen Link zu einem Doktorarbeit dazu gehört auch eine Diskussion von C ++ Parsing, die besagt, dass:

  

"C ++ Grammatik ist mehrdeutig,   kontextabhängig und potentiell   erfordert unendlich Look-Ahead zu lösen   einige Unklarheiten“.

Es geht auf eine Reihe von Beispielen zu geben (siehe Seite 147 des pdf).

Das Beispiel ist: 

int(x), y, *const z;

Bedeutung 

int x;
int y;
int *const z;

Vergleichen an: 

int(x), y, new int;

Bedeutung 

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

(eine durch Kommata getrennte Ausdruck).

Die beiden Token-Sequenzen haben die gleiche Anfangssequenz, aber verschiedene Syntaxbäume, die auf dem letzten Element abhängen. Es kann vor der Eliminierung von Mehrdeutigkeiten einer beliebig viele Zeichen sein.

Andere Tipps

LR Parser können nicht mehrdeutig Grammatikregeln handhaben, von Entwurf. (Aus der Theorie leichter in den 1970er Jahren, als die Ideen ausgearbeitet wurden).

C und C ++ beide erlauben die folgende Anweisung: 

x * y ;

Es hat zwei verschiedene Parsen:

  1. Es kann die Erklärung von y sein, als Zeiger auf den Typ x
  2. Es kann eine Multiplikation von x und y sein, die Antwort Wegwerfen.

Nun könnte man denken, diese dumme ist und sollte ignoriert werden. Die meisten würden mit Ihnen einverstanden; jedoch gibt es, wo Fällen könnte es hat eine Nebenwirkung (beispielsweise, wenn mehrfach überlastet ist). aber das ist nicht der Punkt. Der Punkt ist sind zwei verschiedene Parsen, und daher ein Programm kann bedeuten, verschiedene Dinge, je nachdem wie die sollte hat analysiert worden.

Der Compiler muss die entsprechende man unter den entsprechenden Umständen und in Ermangelung einer anderen Informationen übernehmen (zum Beispiel Kenntnis von der Art des x) muss sammeln, sowohl um später zu entscheiden, was zu tun ist. Somit ist eine Grammatik muss dies zulassen. Und das macht die Grammatik mehrdeutig.

So reines LR-Parsing dies nicht verarbeiten kann. Auch kann viele andere in breiten Umfang verfügbare Parser-Generatoren, wie Antlr, JavaCC, YACC oder traditionellen Bison oder sogar PEG-Stil-Parser, verwendeten in einer „reinen“ Art und Weise.

Es gibt viele kompliziertere Fälle (Parsing Template Syntax erfordert beliebigen Look-Ahead, während LALR (k) kann höchstens k-Token nach vorne schauen), aber nur dauert es nur ein Gegenbeispiel abzuschießen rein LR (oder andere) Parsing.

Die meisten realen C / C ++ Parser behandeln dieses Beispiel von einigen mit Art determinis Parser mit einem zusätzlichen Hack: sie verflechten Parsen mit Symboltabelle Sammlung ... so dass durch die Zeit „x“ angetroffen wird, der Parser weiß, ob x ein Typ ist oder nicht, und kann somit zwischen den beiden potenziellen Parsen wählen. Aber ein Parser das tut dies nicht kontextfrei ist, und LR-Parser (Die Reinen, etc.) sind (bestenfalls) kontextfrei.

Man kann betrügen, und fügen Sie pro-Regel Reduktion Zeit semantische Prüfungen in der LR-Parser diese Begriffsklärung zu tun. (Dieser Code ist oft nicht einfach). Die meisten anderen Parser-Typen haben einige Mittel semantische Prüfungen an verschiedenen Punkten hinzufügen in der Analyse, dass, kann verwendet werden, um dies zu tun.

Und wenn Sie genug betrügen, können Sie LR-Parser funktioniert für C und C ++. Die Jungs GCC haben für eine Weile, aber es gab up für handcodierte Parsing, denke ich, weil sie wollten, bessere Fehlerdiagnose.

Es gibt einen anderen Ansatz, obwohl, das ist schön und sauber und parst C und C ++ ganz gut ohne Symboltabelle Hacks: GLR-Parser . Diese sind voll kontextfreie Parser (mit effektiv unendlich Schau voraus). GLR-Parser einfach akzeptieren beide parst, Erzeugen einer „Baum“ (tatsächlich einen gerichteten azyklischen Graphen, die wie meist Baum ist) ab, die die mehrdeutige Parse. Ein Post-Parsing-Pass kann die Mehrdeutigkeiten aufzulösen.

Wir verwenden diese Technik, die in der C und C ++ Frontends für unsere DMS Software Reengineering Tookit (Stand: Juni 2017 diese handVoll C ++ 17 in MS und GNU Dialekte). Sie verwendet wurden Millionen von Zeilen zu verarbeiten von großen C und C ++ Systemen mit vollständig, präzisen Parsen Ast mit vollständigen Details des Quellcodes zu erzeugen. (Siehe die AST für C ++ 's drängendsten Parse. )

Das Problem wird nie so definiert, während es interessant sein sollte:

Was ist die kleinste Menge von Änderungen an C ++ Grammatik, die notwendig wäre, so dass diese neue Grammatik perfekt von einem „nicht-kontextfreien“ yacc-Parser analysiert werden könnte? (Nutzung nur von einem ‚Hack‘: die Typnamen / Kennung Begriffsklärung, der Parser der Lexer jeder typedef / Klasse / Struktur zu informieren)

Ich sehe ein paar Einsen:

  1. Type Type; ist verboten. Eine Kennung als Typname deklariert wird, kann keine Nicht-Type-Name-Kennung wird (beachten Sie, dass struct Type Type nicht eindeutig ist und immer noch erlaubt werden könnte).

    Es gibt 3 Arten von names tokens:

    • types: builtin-Typ oder wegen einer typedef / Klasse / Struktur
    • template-Funktionen
    • Bezeichner: Funktionen / Methoden und Variablen / Objekte

    Unter Berücksichtigung Template-Funktionen wie verschiedene Token löst die func< Mehrdeutigkeit. Wenn func ein Template-Funktionsname ist, dann muss < der Beginn einer Vorlage Parameterliste sein, sonst func ein Funktionszeiger und < ist der Vergleichsoperator.

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

  3. int (k); vollständig verboten ist, sollte geschrieben int k;

    4. werden

  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. template Rekursion ist auf 1024 begrenzt, da sonst eine erhöhte Maximal als Option an den Compiler übergeben werden konnte.

  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 stark bevorzugte Alternative wäre die schreckliche Funktionszeiger Syntax zu ändern,

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

    wird resyntaxed wie:

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

    Dies ist im Einklang mit dem Cast-Operator (int (MyClass::*)(char*))

  7. typedef int type, *type_ptr; auch verboten werden könnte: eine Zeile pro typedef. So wäre es geworden

    typedef int type;

    typedef int *type_ptr;

  8. sizeof int, sizeof char, sizeof long long und co. könnte in jeder Quelldatei deklariert werden. Daher soll jede Quelldatei, die von der Art int mit beginnen

    #type int : signed_integer(4)

    und unsigned_integer(4) würde außerhalb dieser #type Richtlinie verboten werden dies wäre ein großer Schritt in die dumme sizeof int Mehrdeutigkeit in so viele C ++ Header

    9. sein

Der Compiler die resyntaxed C ++ Implementierung würde, wenn eine C ++ Quelle Verwendung mehrdeutiger Syntax machen zu begegnen, bewegen source.cpp auch einen ambiguous_syntax Ordner und schaffen würde automatisch eine eindeutige übersetzt source.cpp, bevor es zu kompilieren.

Bitte fügen Sie Ihre mehrdeutig C ++ Syntax, wenn Sie einige wissen!

Wie können Sie in meinem hier beantworten , C ++ enthält Syntax, die nicht deterministisch auf den Typ Auflösungsstufe aufgrund von einem LL oder LR Parser syntaktisch analysiert werden kann (in der Regel nach dem Parsing) Ändern der Reihenfolge der Operationen und damit die grundsätzliche Form des AST (typischerweise erwartet von einer ersten Stufe parst bereitgestellt werden).

Ich glaube, Sie ziemlich nah an die Antwort.

LR (1) bedeutet, dass nur ein Token von links nach rechts Bedürfnissen Parsen für den Kontext Look-Ahead, während LR (∞) bedeutet einen unendlichen Vorgriff. Das heißt, würde der Parser alles wissen hat, um kommen würde, um herauszufinden, wo es jetzt ist.

Die "typedef" -Problem in C ++ kann mit einem LALR (1), die eine Symbol-Parser syntaktisch analysiert wird Tabelle aufbaut, während (nicht einen reinen LALR parser) Parsen. Das „Vorlage“ Problem wahrscheinlich nicht mit dieser Methode gelöst werden. Der Vorteil dieser Art von LALR (1) ist, dass die Parser-Grammatik (siehe unten) ist eine LALR (1) Grammatik (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 ohne ein Problem analysiert werden: 

 typedef int x;
 x * y;

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

Die LRSTAR Parsergenerator die obige Grammatik Notation liest und erzeugt einen Parser, der die "typedef" Problem ohne Zweideutigkeit Griffe in der Parsing-Baum oder AST. (Disclosure: Ich bin der Typ, der LRSTAR erstellt.)

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top