Как Yacc знает прогностическим

Question

Как мог Yacc знает перекладывать * но не снижать T to E в строке 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 

ли она автоматически дизайн таблицы?

Answer 1

Основываясь на след предоставленной Вами, я предполагаю, что грамматика выглядит следующим образом:

• E → T | E + T
• T → F | Т * Р
• F → Num

без указания в противном случае, yacc использует LALR (1) алгоритм синтаксического анализа, который использует маркер опережающего просмотра, чтобы помочь разорвать связи при определении, следует ли выполнить сдвиг или уменьшить действие. В тот момент, когда вы указали, у парсера был T на стеке с таблицей *. Обратите внимание, что в грамматике нет способа, чтобы символ * юридически следил за нетерминалом T при любом деривации (формально * ∉ ПОСЛЕДУЮЩИЕ (T)). Это означает, что синтаксический анализатор знает, что здесь не следует сокращать, так как LALR (1) никогда не будет уменьшаться на фоне, которое не находится в наборе FOLLOW для данного нетерминала.

Чтобы понять, как это работает, вы можете построить LALR (1) синтаксический анализатор для этой грамматики и посмотреть на определения, связанные с каждым элементом. В этом состоянии, будет два пункта, заполненный пункт формы

Т → Р

и следующий пункт сдвиг:.

Т → Т * Р

Элемент уменьшения не будет иметь * в своем наборе взглядов (я считаю, что он просто будет $), поэтому LALR (1) состояние парсер будет выглядеть следующим образом:.

T → F. [$]

T → T * F [$]

В результате, когда синтаксический анализатор видит *, он не знает, как это сделать, и вместо этого сдвигается, так как в контрольном наборе для элемента уменьшения не содержится *.