为什么 yacc 或 bison 将 $1 翻译成 yyvsp[(1) - (1)].s？

Question

Yacc 源如下：

element:    IDENTIFIER                { $$ = gst_element_factory_make (, NULL);
                        if ($$ == NULL) {
                          ADD_MISSING_ELEMENT (graph, );
                          SET_ERROR (graph->error, GST_PARSE_ERROR_NO_SUCH_ELEMENT, _("no element \"%s\""), );
                          /* if FATAL_ERRORS flag is set, we don't have to worry about backwards
                           * compatibility and can continue parsing and check for other missing
                           * elements */
                          if ((graph->flags & GST_PARSE_FLAG_FATAL_ERRORS) == 0) {
                            gst_parse_strfree ();
                            YYERROR;
                          }
                        }
                        gst_parse_strfree ();
                                              }
    |   element ASSIGNMENT        { gst_parse_element_set (, , graph);
                        $$ = ;

翻译成这样的代码：

 { (yyval.e) = gst_element_factory_make ((yyvsp[(1) - (1)].s), NULL);
                    if ((yyval.e) == NULL) {
                      ADD_MISSING_ELEMENT (graph, (yyvsp[(1) - (1)].s));
                      SET_ERROR (graph->error, GST_PARSE_ERROR_NO_SUCH_ELEMENT, _("no element \"%s\""), (yyvsp[(1) - (1)].s));
                      /* if FATAL_ERRORS flag is set, we don't have to worry about backwards
                       * compatibility and can continue parsing and check for other missing
                       * elements */
                      if ((graph->flags & GST_PARSE_FLAG_FATAL_ERRORS) == 0) {
                        gst_parse_strfree ((yyvsp[(1) - (1)].s));
                        YYERROR;
                      }
                    }
                    gst_parse_strfree ((yyvsp[(1) - (1)].s));
                                          }
break;

其中一个翻译转换：

gst_element_factory_make (, NULL)

至：

gst_element_factory_make ((yyvsp[(1) - (1)].s), NULL)

[(1) - (1)] 让我很困惑。为什么[(1) - (1)]句代表值？

Answer 1

正如 Jonathan Leffler 在评论中所说，bison 和 yacc 生成正确的代码，其风格便于代码生成，而不适合人类读者。

但是，各种堆栈的处理相当简单。 Bison维护着两三个栈：状态栈；价值堆栈；以及可选的位置堆栈。这三个堆栈是独立的，否则就需要创建一个包含状态、值和（如果需要）位置的堆栈槽结构。

堆栈的大小始终相同，这意味着在值堆栈（以及位置堆栈）的开头有一个未使用的槽。如果你参考LR解析算法的经典描述，比如龙书的"LR Parsing Algorithm"部分——我有的那个版本的§4.7——你会看得很清楚；堆栈比语法符号多一个状态，所以没有 X0:

s<sub>0</sub> X<sub>1</sub> s<sub>1</sub> X<sub>2</sub> s<sub>2</sub> … X<sub>m</sub> s<sub>m</sub>

（Bison 实际上并不将文法符号保存在堆栈中，因为符号本身很容易计算。相反，它保存与符号关联的语义值。）

代码中，yyvsp和yyssp分别是指向值栈顶和状态栈顶的指针。（yylsp 是指向位置堆栈顶部的指针，如果有的话。）

它们实际上指向各自堆栈的顶部元素，而不是指向顶部元素之后的一个。前一个元素指针在一般堆栈实现中更常见，因为如果堆栈为空，通常可能没有要指向的顶部元素。但是，在这种特殊情况下，堆栈永远不会为空，因此总会有一个顶部元素。（算法开始时，栈顶状态是0，栈顶的值和位置就是上面提到的未使用的槽位。）和往常一样，栈的其余部分从栈顶往下走，所以倒数第二个元素（如果有）位于 yyvsp - 1，倒数第三个元素位于 yyvsp - 2.

请记住，在 C 中，*yyvsp 与 yyvsp[0] 的含义完全相同。或者，一般来说，yyvsp[k] 与 *(yyvsp + k) 相同。即使 k 为负也是如此，所以我们可以写 yyvsp[-1] 来引用堆栈中的倒数第二个元素。

您引用的代码实现了产生式的归约动作；归约动作通常计算结果非终结符的语义值。假设减少的产量是：

A → X<sub>1</sub> X<sub>2</sub> … X<sub>m</sub>

在这种情况下，值堆栈的顶部恰好是

V<sub>1</sub> V<sub>2</sub> … V<sub>m</sub>

(其中Vi是符号Xi[=的语义值65=])。或者，用野牛的话来说：

… $m

这意味着</code>是<code>yyvsp[1-m]，</code>是<code>yyvsp[2-m]，依此类推，直到$m在yyvsp[m-m]。而这正是 bison 生成的代码所做的；它将 $i 表示为 yyvsp[(i)-(m)]，其中 m 是要减少的右侧的长度（以语法符号表示）。

为什么 yacc 或 bison 将 $1 翻译成 yyvsp[(1) - (1)].s？

Why does yacc or bison translate $1 to yyvsp[(1) - (1)].s?

c

bison

yacc