1

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

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

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

  if :
    IF RPAREN exp LPAREN stmt                                { marks (A.If ($3, $5, None)) (1, 5) }
  | IF RPAREN exp LPAREN stmt ELSE stmt                      { marks (A.If ($3, $5, $7)) (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

我已经读过移位/减少冲突是由于语法规范中的歧义造成的，但我不知道如何以一种不歧义的方式指定它？

4

1 回答 1

3

语法当然是模棱两可的，尽管您知道每个字符串的含义，而且尽管ocamlyacc报告了移位/归约冲突，但它生成的语法也会为每个有效输入生成正确的解析。

歧义来自

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

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

语法可以重写，虽然有点麻烦。基本思想是将语句分为两类：“匹配”（表示else语句中的每个都与某些匹配if）和“不匹配”（表示后面else将匹配语句中的某些if。完整的语句可能不匹配, 因为else子句是可选的，但是在 anif和 an之间永远不能有不匹配的语句else，因为它else必须匹配ifunmatched 语句中的 an。

以下语法基本上是您提供的语法，但重写为使用野牛风格的单引号标记，我发现它更具可读性。我不知道 ocamlyacc 是否处理这些。（顺便说一句，你的语法说明 IF RPAREN exp LPAREN...了，用左括号和右括号的通用定义，将意味着if ) exp (. 这就是我发现单引号字符终端更具可读性的原因之一。）

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 手册中建议的优先级声明。

于 2015-09-25T06:48:16.917 回答