如何构建yacc代码以支持可选的非终端

在yacc中为可选数据建模的最佳方式是什么？我有以下声明：如何构建yacc代码以支持可选的非终端

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

两者VariableDeclList和StmtList是可选的（ε）所以我模仿他们如下：

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 
...

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

来源

2011-02-06 blcArmadillo

当你注意，这将导致移位/减少冲突，如果一个语句和VariableDecl无法通过他们的第一个记号加以区别 - 在您的示例T_Identifier可能开始任。有一些事情你可以尝试：

两个清单合并为一个VariableDeclOrStmtList它可以包含语句或VariableDecl以任何方式混合。这比你有什么比较一般，所以你需要一个检查后，确保没有VariableDecls第一语句
使用后，更前瞻，以确定差异 - 要么使用野牛的GLR模式，或者类似的东西btyacc可以推迟决定是否东西是语句或VariableDecl直到它已经看够了这些结构的开头来决定
使用不同的令牌，以明确区分。这些可以是您的语言中的真实标记，也可以是词法分析器根据某些附加上下文（即基本上在词法分析器中执行更多预测）插入的合成标记。

编辑

对于第一个建议，你就会有这样一个规则：

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

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

来源

2011-02-06 06:46:47

感谢克里斯的建议。你能否指出我在正确的方向上对你如何在你的第一个建议中进行后检查？ – blcArmadillo 2011-02-06 20:39:14

如何构建yacc代码以支持可选的非终端

回答

相关问题