Verschiebung reduzieren und reduzieren Konflikte reduzieren

Question

Es fällt mir schwer, das zu verstehen, und ich brauche etwas Hilfe, um die Konflikte zwischen "shift reduce" und "reduce reduce" zu verstehen. Ich habe eine Grammatik, von der ich nicht verstehen kann, warum sie problematisch ist. Ich könnte die Grammatik anhängen, aber ich möchte lernen, wie das wirklich funktioniert.

Erste Frage: Welche Art von Parser wird von MGrammer erstellt? So wie ich es verstehe, hängen shift reduce und reduce reduce Konflikte von der Art des Parsers ab.

Zweite Frage: Was bedeutet eine Konfliktreduzierung und was bedeutet eine Konfliktverlagerung?

Ich kenne die Grundlagen der lexikalischen Analyse und der formalen Grammatik, aber es ist schon eine Weile her, dass ich mich mit Sprachdesign beschäftigt habe, also ist jede Hilfe hier sehr willkommen.

Aktualisierung:

Ich arbeite mit einem Leerzeichen signifikante Sprache und ich wundere mich über die Möglichkeiten, dies in MGrammar zu tun, werde ich Look-a-head benötigen, um Mehrdeutigkeiten zu lösen?

Answer 1

Einfaches Beispiel:

if cond
    if cond2
        cmd
    else
        cmd2

Frage: Wo wird die else gehören? Für das menschliche Auge sagt die Einkerbung "zur zweiten if ", aber das bedeutet nichts für einen Computer (außer bei der Verwendung von Python ;)). Dies ist ein Konflikt verschieben/verringern .

Eine elegante Lösung ist die Behandlung der else als linksbindender Operator mit der höchsten Priorität (was ihn an den nächstgelegenen "hängen" lässt) if ).

A Konflikte reduzieren/vermindern ist eine Zweideutigkeit. Ich habe kein gutes Beispiel parat, aber es bedeutet, dass es Pfade in der Grammatik gibt, bei denen ein Token zwei Regeln gleichzeitig reduzieren könnte und es keine zusätzlichen Informationen gibt, um zu entscheiden, welche Regel Vorrang haben sollte.

[EDIT] Die Bison-Dokumente haben eine Beispiel für reduzieren/reduzieren .