Shift-reduce: wann man aufhören zu reduzieren?

Question

Ich versuche, über shift-reduce Parsen zu lernen. Angenommen, wir haben die folgende Grammatik, mit rekursiven Regeln, die Reihenfolge der Operationen erzwingen, inspiriert durch die ANSI-C-Yacc Grammatik :

S: A;

P
    : NUMBER
    | '(' S ')'
    ;

M
    : P
    | M '*' P
    | M '/' P
    ;

A
    : M
    | A '+' M
    | A '-' M
    ;

Und wollen wir 1 analysieren + 2 mit Parsing-shift-reduce. Zunächst wird die 1 als eine Zahl verschoben. Meine Frage ist, wird es dann auf P reduziert, dann M, dann A, dann S endlich? Woher weiß er, wo aufhören?

Angenommen, es verringert sich den ganzen Weg nach S, dann verschiebt ‚+‘. Wir haben jetzt einen Stapel enthalten:

S '+'

Wenn wir verschieben '2', könnten die Kürzungen sein:

S '+' NUMBER
S '+' P
S '+' M
S '+' A
S '+' S

Nun, die auf beiden Seiten der letzten Zeile, könnte S sein P, M, A, oder NUMBER, und es wäre immer noch in dem Sinne gilt, dass jede Kombination eine korrekte Darstellung des Textes wäre. Wie funktioniert der Parser „wissen“, um es

A '+' M

Damit es den gesamten Ausdruck zu A reduzieren, S dann? Mit anderen Worten, wie weiß es vor dem Schalten das nächste Token reduzieren zu stoppen? Ist das ein Hauptschwierigkeit in LR Parsergenerierung?

---

Edit:. Eine Ergänzung zu der Frage folgt

Jetzt sind wir Parse 1+2*3 annehmen. Einige Schiebe- / Reduzier Operationen sind wie folgt:

Stack    | Input | Operation
---------+-------+----------------------------------------------
         | 1+2*3 | 
NUMBER   | +2*3  | Shift
A        | +2*3  | Reduce (looking ahead, we know to stop at A)
A+       | 2*3   | Shift
A+NUMBER | *3    | Shift (looking ahead, we know to stop at M)
A+M      | *3    | Reduce (looking ahead, we know to stop at M)

Ist das richtig (gewährt, ist es noch nicht vollständig analysiert)? Darüber hinaus hat das Vorgriffs um 1 Symbol auch sagen uns nicht A+M zu A zu reduzieren, da dies nach der Lektüre *3 in einer unvermeidlichen Syntaxfehler führen würde?

Answer 1

Das Problem, das Sie beschreiben, ist ein Thema, mit LR(0) Parser zu schaffen - das heißt, Bottom-up-Parser, die jeden Look-Ahead-Zeichen nicht tun jenseits dem aktuell sie parsen. Die Grammatik Sie beschrieben haben scheint nicht eine LR(0) Grammatik zu sein, weshalb man in Schwierigkeiten geraten, wenn sie versuchen, es zu analysieren w / o Look-Ahead. Es nicht erscheint LR(1) jedoch sein, also indem man 1-Symbol vor dem Eingang Du einfach, ob Verschiebung bestimmen könntest oder reduzieren. In diesem Fall würde ein LR(1) Parser nach vorne schauen, wenn es die 1 auf dem Stapel hatte, dass das nächste Symbol ein + ist, und erkennt, dass es nicht in der Vergangenheit A verringern sollte (denn das ist die einzige Sache ist, um es zu, dass verringern könnte würde immer noch eine Regel mit + in der zweiten Position zusammenpassen).

Eine interessante Eigenschaft von LR Grammatiken ist, dass für jede Grammatik, die LR(k) für k>1 ist, ist es möglich, eine LR(1) Grammatik zu konstruieren, die äquivalent ist. Allerdings ist die gleiche nicht den ganzen Weg nach unten erstrecken, um LR(0) -. Gibt es viele Grammatiken, die nicht zu LR(0) umgewandelt werden

Sehen Sie hier für weitere Details über LR(k)-ness:

http://en.wikipedia.org/wiki/LR_parser

Answer 2

Ich bin mir nicht ganz sicher, ob der Yacc / Bison-Parsing-Algorithmus und wenn sie es vorzieht, zu reduzieren Verschiebung über, aber ich weiß, dass Bison LR (1) Parsing unterstützt das heißt, es hat ein Look-Ahead-Token. Dies bedeutet, dass Token werden nicht sofort an den Stack übergeben. Vielmehr warten sie, bis keine weiteren Reduzierungen passieren kann. Wenn dann Verschieben der nächste Token macht Sinn, dass Betrieb gilt.

Vor allem in Ihrem Fall, wenn Sie die Bewertung 1 + 2, wird es 1. verschiebt Es wird dieses Token zu einem A zu reduzieren, weil die ‚+‘ Look-Ahead-Token gibt an, dass sein einzigen gültigen Kurs. Da es keine weiteren Reduzierungen sind, wird es verschieben, um den ‚+‘ Token auf den Stapel und halten Sie 2 als Look-Ahead. Es wird die 2 verschieben und auf eine M reduzieren, da A + M ein A erzeugt und der Ausdruck abgeschlossen ist.