这个yacc语法的shift/reduce冲突在哪里？

Question

我正在为一种名为 C- 的语言编写解析器。我必须编写语法以使其不含糊，并且我不能在 Bison 中使用任何 %prec 语句。除了 1 个 shift/reduce 冲突外，我已经更正了所有冲突，但我不知道它在哪里。有任何想法吗？我的 .output 文件提供了有关其发生位置的以下信息：

State 163

   44 matched: IF '(' simpleExp ')' matched . ELSE matched
   46 unmatched: IF '(' simpleExp ')' matched .
   48          | IF '(' simpleExp ')' matched . ELSE unmatched

    ELSE  shift, and go to state 169

    ELSE      [reduce using rule 46 (unmatched)]
    $default  reduce using rule 46 (unmatched)

语法：

stmt                : selectStmt
                    ;

expStmt             : exp ';'
                    | ';'

compoundStmt        : '{' localDecls stmtList '}'
                    ;  

stmtList            : stmtList stmt
                    |
                    ;

otherStmt           : compoundStmt
                    | expStmt
                    | iterStmt
                    | returnStmt
                    | breakStmt
                    ;     

localDecls          : localDecls scopedVarDecl
                    |
                    ;

selectStmt          : matched
                    | unmatched
                    ;
                
matched             : IF '(' simpleExp ')' matched ELSE matched
                    | otherStmt
                    ;

unmatched           : IF '(' simpleExp ')' matched
                    | IF '(' simpleExp ')' unmatched
                    | IF '(' simpleExp ')' matched ELSE unmatched
                    ;
                    
iterStmt            : WHILE simpleExp DO selectStmt
                    | FOR ID '=' iterRange DO selectStmt
                    ;

iterRange           : simpleExp
                    | simpleExp TO simpleExp
                    | simpleExp TO simpleExp BY simpleExp
                    ;

returnStmt          : RETURN ';'
                    | RETURN exp ';'
                    ;

breakStmt           : BREAK ';'
                    ;

Answer 1

问题在于，不仅if 语句可以“匹配”。以不匹配语句结尾的迭代语句与以不匹配语句结尾的 if 语句一样不匹配。这就是“匹配”的意思。

因此您必须将迭代语句分为 matched 和 unmatched 变体。（这就是为什么大多数人使用优先级或期望声明来处理悬挂 else。）

这里有一个简单的例子，以防将来有用。（很多非终结符没有改，所以省略了定义，我也扩充了很多缩写。）

statement: matched
         | unmatched
/* Statements which could have been extended with an else clause,
 * but haven't been. An unmatched statement can be the body of an
 * unmatched compound statement, which includes an `if` statement
 * whose `else` clause is unmatched. Unmatched also includes `if`
 * statements without an `else` clause.
 */
unmatched: "if" '(' simpleExp ')' statement
         | "if" '(' simpleExp ')' matched "else" unmatched
         | "while" '(' simpleExp ')' "do" unmatched
         | "for" IDENT '=' iterRange "do" unmatched
/* Statements which cannot be extended with an else clause.
 * In other words, in a `matched` every `else` matches some `if`.
 * Only `matched` statements can come between `if` and `else`, because
 * an unmatched statement would grab the `else` for itself.
 */
matched  : "if" '(' simpleExp ')' matched "else" matched
         | "while" '(' simpleExp ')' "do" matched
         | "for" IDENT '=' iterRange "do" matched
         | expStatement
         | returnStatement
         | breakStatement
         | '{' localDeclarations statementList '}'

这个yacc语法的shift/reduce冲突在哪里？

Where is the shift/reduce conflict in this yacc grammar?

compiler-construction

grammar

yacc

bison

shift-reduce-conflict