Wie yacc weiß für Vorgriff

Question

Wie konnte yacc weiß * zu verschieben, aber nicht zu reduzieren T to E in Zeile 10

STACK  INPUT BUFFER ACTION 
$   num1+num2*num3$ shift 
$num1  +num2*num3$  reduc 
$F   +num2*num3$  reduc 
$T   +num2*num3$  reduc 
$E   +num2*num3$  shift 
$E+  num2*num3$   shift 
$E+num2 *num3$    reduc 
$E+F  *num3$    reduc 
$E+T  *num3$    shift  /////****// 
E+T*  num3$    shift  /////****// 
E+T*num3 $     reduc 
E+T*F  $     reduc 
E+T   $     reduc 
E   $     accept 

Hat Design automatisch Tisch?

Answer 1

Basierend auf der Spur Sie zur Verfügung gestellt haben, vermute ich, dass die Grammatik wie folgt aussieht:

• E → T | E + T
• T → F | T * F
• F → num

ohne andererseits die Angabe verwendet yacc die LALR (1) Parsing-Algorithmus, der einen Token von Vorgriffs-verwendet Bruch Verbindungen zu helfen, wenn bestimmt wird, ob eine Verschiebung durchzuführen, oder die Aktion zu reduzieren. An dem von Ihnen angegebenen Punkt hatte der Parser T auf seinem Stack mit einem Lookahead von *. Beachten Sie, dass es in der Grammatik keine Möglichkeit gibt, dass ein * Symbol einem T Nichtterminal in irgendeiner Ableitung rechtlich folgt (formal, * ∉ FOLLOW (T)). Das bedeutet, dass der Parser hier nicht reduziert werden soll, da LALR (1) niemals bei einem Lookahead, das nicht in der FOLLOW-Menge für das gegebene Nonterminal gesetzt ist, reduziert wird.

Um zu sehen, wie dies genau funktioniert, könnten Sie den LALR (1) Parsing-Automaten für diese Grammatik konstruieren und sich die Lookaheads anschauen, die jedem Element zugeordnet sind. In diesem Zustand wird es zwei Elemente, ein fertiges Element des Formulars

T → F

und der folgende Verschiebung Artikel:.

T → T * F

Das Reduzieren Element wird nicht * in seiner Lookahead-Set (ich glaube, es wird nur haben $), so dass die LALR (1) Zustand für den Parser wird wie folgt aussehen:.

T → F. [$]

T → T * F [$]

Wenn der Parser einen * sieht, weiß es daher, die Reduktion nicht vorzunehmen und stattdessen zu verschieben, da der Vorausschau-Set für das Reduzieren-Element kein * enthält.