试图解决 shift-reduce 解析问题

Question

我正在尝试为 C 编写语法，但遇到一个我不太明白的问题。相关语法部分：

stmt :
  types decl SEMI                { marks (A.Declare (, )) (1, 2) }
 | simp SEMI                     { marks  (1, 1) }
 | RETURN exp SEMI               { marks (A.Return ) (1, 2) }
 | control                       {  } 
 | block                         { marks  (1, 1) }
 ;

 control :
   if                                                    {  }
  | WHILE RPAREN exp LPAREN stmt                         { marks (A.While (, )) (1, 5) }
  | FOR LPAREN simpopt SEMI exp SEMI simpopt RPAREN stmt { marks (A.For (, , , )) (1, 9) }
  ;

  if :
    IF RPAREN exp LPAREN stmt                                { marks (A.If (, , None)) (1, 5) }
  | IF RPAREN exp LPAREN stmt ELSE stmt                      { marks (A.If (, , )) (1, 7) }
  ;

这行不通。我运行 ocamlyacc -v 并得到以下报告：

83: shift/reduce conflict (shift 86, reduce 14) on ELSE
state 83
    if : IF RPAREN exp LPAREN stmt .  (14)
    if : IF RPAREN exp LPAREN stmt . ELSE stmt  (15)

    ELSE  shift 86
    IF  reduce 14
    WHILE  reduce 14
    FOR  reduce 14
    BOOL  reduce 14
    IDENT  reduce 14
    RETURN  reduce 14
    INT  reduce 14
    MAIN  reduce 14
    LBRACE  reduce 14
    RBRACE  reduce 14
    LPAREN  reduce 14

我读到 shift/reduce 冲突是由于语法规范中的歧义造成的，但我不知道如何以明确的方式来规范它？

Answer 1

语法肯定是有歧义的，虽然你知道每个字符串的意思，而且尽管 ocamlyacc 报告了 shift/reduce 冲突，它生成的语法也会为每个字符串生成正确的解析有效输入。

歧义来自

if ( exp1 ) if ( exp2) stmt1 else stmt2;

显然 stmt1 只有在 exp1 和 exp2 都为真时才会执行。但是，如果 exp1 为假，或者如果 exp1 为真且 exp2 为假，stmt1 会执行吗？那些代表不同的解析；第一个（无效的）解析将 else stmt2 附加到 if (exp1)，而你、我和 ocamlyacc 知道正确的解析将 else stmt2 附加到 if (exp2)。

语法可以重写，虽然有点麻烦。基本思想是将语句分为两类："matched"（这意味着语句中的每个 else 都与一些 if 匹配）和 "unmatched"（这意味着一个else 之后会匹配语句中的一些 if。完整的语句可能是不匹配的，因为 else 子句是可选的，但是 if 之间永远不能有不匹配的语句和 else，因为 else 必须与不匹配语句中的 if 匹配。

下面的语法基本上是您提供的语法，但是重写为使用 bison 样式的单引号标记，我发现它更具可读性。我不知道 ocamlyacc 是否处理这些。（顺便说一下，你的语法说 IF RPAREN exp LPAREN... ，根据左右括号的通用定义，它的意思是 if ) exp (。这就是我发现 single-带引号的字符终端更具可读性。）

Bison 处理这个语法没有冲突。

 /* Fake non-terminals */
%token types decl simp exp
 /* Keywords */
%token ELSE FOR IF RETURN WHILE

%%
stmt: matched_stmt | unmatched_stmt ;
stmt_list: stmt | stmt_list stmt ;
block: '{' stmt_list '}' ;

matched_stmt
 : types decl ';' 
 | simp ';'
 | RETURN exp ';'
 | block
 | matched_control
 ;

simpopt : simp | /* EMPTY */;

matched_control
  : IF '(' exp ')' matched_stmt ELSE matched_stmt
  | WHILE '(' exp ')' matched_stmt
  | FOR '(' simpopt ';' exp ';' simpopt ')' matched_stmt
  ;

unmatched_stmt
  : IF '(' exp ')' stmt
  | IF '(' exp ')' matched_stmt ELSE unmatched_stmt
  | WHILE '(' exp ')' unmatched_stmt
  | FOR '(' simpopt ';' exp ';' simpopt ')' unmatched_stmt
  ;

就个人而言，我会重构一下。例如：

if_prefix  : IF '(' exp ')'
           ;
loop_prefix: WHILE '(' exp ')'
           | FOR '(' simpopt ';' exp ';' simpopt ')'
           ;
matched_control
           : if_prefix matched_stmt ELSE matched_stmt
           | loop_prefix matched_stmt
           ;
unmatched_stmt
           : if_prefix stmt
           | if_prefix ELSE unmatched_stmt
           | loop_prefix unmatched_stmt
           ;

一个常见且更简单但不太严格的解决方案是使用 bison manual 中建议的优先声明。

试图解决 shift-reduce 解析问题

Attempting to resolve shift-reduce parsing issue

parsing

compiler-construction

yacc

ocamlyacc