Shift/reduce-Konflikt in Happy Grammatik

Question

Ich habe die folgende bekam Glückliche Grammatik (stark abgespeckte)

%token 
    '{' { Langle } 
    '}' { Rangle } 
    '..' { DotDot } 
    '::' { ColonColon } 
    '@' { At } 
    mut { Mut } 
    ident { Ident } 

%% 

pattern 
    : binding_mode ident at_pat { error "identifier pattern" } 
    | expr_path     { error "constant expression" } 
    | expr_path '{' '..' '}'  { error "struct pattern" } 

binding_mode 
    : mut      { } 
    |       { } 

at_pat 
    : '@' pat     { } 
    |       { } 

expr_path 
    : expr_path '::' ident  { } 
    | ident      { } 

Welche Verschiebung/reduzieren Konflikte um Identifikatoren in Muster hat. Standardmäßig wählt Happy die Verschiebung, aber in diesem Fall ist das nicht, was ich will: es versucht, alles in constant expression zu schuhen, selbst wenn es ein identifier pattern sein könnte.

Ich habe gelesen, dass Präzedenz/Assoziativität der Weg ist, um diese Art von Problem zu lösen, aber nichts, was ich hinzugefügt habe, war in der Lage, die Grammatik in die richtige Richtung zu bewegen (um fair zu sein, habe ich meistens genommen Aufnahmen im Dunkeln).

einige offensichtliche tokenization verwenden, würde ich gerne haben:

• xidentifier pattern
• mut x erhalten identifier pattern
• std::pi zu erhalten constant expression
• point{..} zu erhalten struct pattern
• zu ergebenstruct pattern

Grundsätzlich zu erhalten, es sei denn, ein { oder :: Token warten verbraucht wird, sollte eine Kennung zum identifier pattern Fall gehen.

---

Ich entschuldige mich, wenn meine Frage nicht klar ist - ein Teil des Problems ist, dass ich eine harte Zeit Ortung habe, was das Problem selbst ist. :(

Answer 1

Zuerst ist es wichtig zu verstehen, was eine Verschiebung ist.Eine Verschiebung ist das Ergebnis der Annahme der nächsten Input-Token, und setzen Sie es auf den Parser-Stack (wo es schließlich Teil einer Produktion sein wird, aber es ist nicht notwendig, um zu wissen, welche noch.) Eine Reduzierung nimmt Null oder mehr Token von der Spitze des Stapels, die mit der rechten Seite einiger Produktion übereinstimmen, und ersetzt sie durch die linke Seite.

Wenn die Parser beschließt, identifier pattern aus binding_mode ident at_pat zu erstellen, wo at_pat leer ist, es verschiebt nicht, es reduziert sich.Tatsächlich reduziert es zweimal: zuerst reduziert es null gestapelte Symbole in eine leere at_pat und dann reduziert es die oberen drei Stapel Symbole in ein identifier pattern. Hätte es keine binding_mode gegeben, hätte es ident auf expr_path reduziert und dann die expr_path in eine constant_expression reduziert. Das wäre also ein Konflikt reduzieren/reduzieren.

Aber es gibt ein anderes Problem, gerade weil binding_mode Nullable ist. Wenn der Parser einen ident sieht, weiß er nicht, ob ein binding_mode möglich ist oder nicht, also weiß er nicht, ob er einen leeren binding_mode reduzieren oder den verschieben soll. Das ist ein Shift/Reduce-Konflikt. Da die Verschiebung bevorzugt reduziert wird, wählt man die Verschiebung ident, was bedeutet, dass eine leere binding_mode nicht erzeugt werden kann, was wiederum den Konflikt reduzieren/reduzieren (und verhindert, dass ident @ pat überhaupt erkannt wird).)

Um all das zu entwirren, müssen wir damit beginnen, die Notwendigkeit zu vermeiden, eine leere binding_mode zu reduzieren. Wir machen das mit dem üblichen Eliminierungsalgorithmus der Nullable-Produktion, bei dem zwei Kopien der rechten Seite gemacht werden, eine mit dem nullbaren Nichtterminal und die andere ohne; Wir entfernen dann die Nullable-Produktion. Sobald wir das tun, erscheint der Reduzieren/Reduzieren-Konflikt.

Um den Konflikt zu reduzieren/zu reduzieren, müssen wir explizit angeben, welche Produktion bevorzugt wird. Reduzieren/Reduzieren von Konflikten kann nicht durch Präzedenzdeklarationen aufgelöst werden, da der Präzedenzalgorithmus immer den Vergleich zwischen einer Produktion (die reduziert werden könnte) und einem Terminal (das verschoben werden könnte) beinhaltet. Also muss die Auflösung explizit sein, und das bedeutet, dass wir sagen müssen, dass ein blankes ident ein Muster ist, während ein expr_path, das kein ident ist, ein konstanter Ausdruck ist. Das gibt uns folgendes:

(Beachten Sie, dass ich Nicht-Terminals verwendet habe, um die drei verschiedenen Produktionen für pattern zu etikettieren, anstatt sich auf Aktionen zu verlassen. Für mich macht es leichter darüber nachzudenken und zu lesen.)

pattern: identifier_pattern | constant_expression | struct_pattern 

Hier ist die null-Produktion Elimination:

identifier_pattern: ident at_pat 
        | binding_mode ident at_pat 

Hier ist das ausdrückliche Verbot idents:

constant_expression: complex_expr_path 

struct_pattern:  expr_path '{' '..' '}' 

binding_mode ist nicht mehr nullable:

binding_mode: mut 

at_pat 
    : '@' pat 
    | %empty 

Hier haben wir die zwei verschiedenen expr_paths erstellen:

complex_expr_path 
    : complex_expr_path '::' ident 
    | ident '::' ident 

expr_path: ident | complex_expr_path 

Ich hoffe, dass Lösung eine Beziehung zu Ihrem ursprünglichen Grammatik hat.