如何构造 yacc 代码以支持可选的非终结符

Question

在 yacc 中对可选数据建模的最佳方法是什么？我有以下声明：

StmtBlock           :    '{' VariableDeclList StmtList '}' {  $$ = new StmtBlock($2, $3); }
                    ;

VariableDeclList 和 StmtList 都是可选的（epsilon），因此我将它们建模如下：

VariableDeclList    :    VariableDeclList VariableDecl  { ($$=$1)->Append($2); }
                    |    { $$ = new List<VarDecl*>; }

。

StmtList            :    StmtList Stmt { ($$=$1)->Append($2); }
                    |    { $$ = new List<Stmt*>; }
                    ;

唯一的问题是当我认为这会导致移位/归约冲突时 当我尝试编译代码时，我的 y.ouput 文件具有以下内容：

State 74 conflicts: 1 shift/reduce
...
state 74

   38 StmtBlock: '{' VariableDeclList . StmtList '}'
   39 VariableDeclList: VariableDeclList . VariableDecl

    T_Bool        shift, and go to state 2
    T_Int         shift, and go to state 3
    T_Double      shift, and go to state 4
    T_String      shift, and go to state 5
    T_Identifier  shift, and go to state 8

    T_Identifier  [reduce using rule 18 (Epsilon)]
    $default      reduce using rule 18 (Epsilon)

    VariableDecl  go to state 80
    Variable      go to state 13
    Type          go to state 34
    Epsilon       go to state 81
    StmtList      go to state 82
...

是否有更合适的方法来对此进行建模？

Answer 1

正如您所注意到的，如果 Stmt 和 VariableDecl 无法通过它们的第一个标记来区分，这将导致移位/归约冲突 - 在您的示例中是 T_Identifier 可能会开始。您可以尝试多种方法：

• 将两个列表组合成一个 VariableDeclOrStmtList，其中可以包含混合的 Stmt 或 VariableDecl反正。 之后不存在 VariableDecls

• 使用更多前瞻来确定差异——要么使用 bison 的 GLR 模式，要么使用 btyacc 之类的东西，可以推迟确定某物是否是Stmt 或 VariableDecl 直到它看到足够的信息来决定

• 在这些结构的开头使用不同的标记来明确区分它们。这些可以是您语言中的真实标记，也可以是词法分析器根据某些附加上下文插入的合成标记（这意味着基本上在词法分析器中进行更多的前瞻操作）。

编辑

对于第一个建议，您将拥有如下规则：

VarDeclOrStmtList : VarDeclOrStmtList VariableDecl { ($=$1)->Append($2); }
                  | VarDeclOrStmtList Stmt         { ($=$1)->Append($2); }
                  | { $ = new List<Node *>; }
                  ;

其中 Node 是 VarDecl 和 Stmt< 的公共基类/代码>。然后，在 StmtBlock 操作中，调用一个遍历 List 的函数，将其拆分为 List 和 List< ;Stmt *> 并在格式不正确时给出错误消息。