移动/减少与中缀部分的冲突

Question

我在使用类似 yacc 的语法实现（特别是使用 ocamlyacc）时遇到了问题，该语法包括普通中缀操作和中缀部分，就像在 Haskell 中一样。我希望所有这些都是语法上的：

(+1)
(1+)
(+)
(1+1)

但是，即使通过摆弄关联性/优先级声明，我也无法做到这一点。我可以在 grammar.output 中看到问题发生的位置（它正在移动到我希望它减少的地方），但我无法哄骗它按照我想要的方式进行。下面是问题的简化演示。

lex.mll 有：

{
  open Parse
  exception Eof
}
rule token = parse
  | [' ' 't'] { token lexbuf }
  | ['n'] { EOL }
  | ['0'-'9']+ as num {INT(int_of_string num)}
  | '+' { PLUS }
  | '*' { TIMES }
  | '(' { LPAREN }
  | ')' { RPAREN }
  | eof { raise Eof }

main.ml 有：

let _ =
  try
    let lexbuf = Lexing.from_channel stdin in
    while true do
      let result = Parse.start Lex.token lexbuf in
      print_string result; print_newline(); flush stdout
    done
  with Lex.Eof -> exit 0

和 parse.mly（问题所在）有：

%token <int> INT
%token PLUS TIMES
%token LPAREN RPAREN
%token EOL
%left PLUS
%left TIMES
%start start
%type <string> start
%%
start:
| expr EOL {$1}
;
expr:
| application {$1}
| expr PLUS expr {"[" ^ $1 ^ "+" ^ $3 ^"]"}
| expr TIMES expr {"[" ^ $1 ^ "*" ^ $3 ^"]"}
;
section:
| LPAREN atom PLUS RPAREN { "(" ^ $2 ^ " +)" }
| LPAREN PLUS atom RPAREN { "(+ " ^ $3 ^ ")" }
| LPAREN PLUS RPAREN { "(+)" }
;
application:
| atom {$1}
| application atom {"[" ^ $1 ^ " " ^ $2 ^ "]"}
;
atom:
| INT {string_of_int $1}
| section { $1 }
| LPAREN expr RPAREN { "(" ^ $2 ^ ")" }
;
%%

运行ocamlyacc告诉我有1 shift/reduce conflict.特别是这里是详细日志的相关部分：

Rules:
   6  section : LPAREN atom PLUS RPAREN
   ...
   9  application : atom
...
12: shift/reduce conflict (shift 21, reduce 9) on PLUS
state 12
        section : LPAREN atom . PLUS RPAREN  (6)
        application : atom .  (9)
        PLUS  shift 21
        INT  reduce 9
        MINUS  reduce 9
        TIMES  reduce 9
        LPAREN  reduce 9
        RPAREN  reduce 9
...
state 21
        section : LPAREN atom PLUS . RPAREN  (6)
        RPAREN  shift 26
        .  error

运行编译后的程序将正确解析以下所有内容：

(1+)
(+1)
(+)
1+2

但失败并显示：

(1+2)

另一方面，如果我创建一个具有高优先级的虚拟令牌HIGH：

%left PLUS MINUS
%left TIMES
%nonassoc HIGH

然后%prec HIGH规则 9：

application: atom %prec HIGH {$1}

在这种情况下，(1+2)会解析，但(1+)不会。

我了解转移/减少冲突的一般背景。我只是不知道如何协商它来解决这个解析挑战。

Answer 1

省略很多语法，你有以下作品，所有这些都可以同时可行。

atom:    LPAREN expr RPAREN
expr:           expr PLUS expr
section: LPAREN atom PLUS RPAREN

因此，假设我们刚刚读取了 （0 - 即一个LPAREN和一个INT - 下一个标记是 +。此时，我们需要将INT减少到atom，但我们无法判断接下来的内容是否符合atom规则或section规则。为了匹配atom规则，我们需要将atom减少到expr - 通过application - 但为了匹配section规则，我们需要它保持为atom。因此，我们有一个转变/减少冲突;我们不知道现在是否需要移动 +，或者在进行更多单位缩减之后。

简单的解决方案是推迟决定。如果section规则是：

section: LPAREN expr PLUS RPAREN

那就没有问题了。我们会继续单位减少，直到我们得到一个expr，然后我们会移动 +，然后我们要么看到一个 ），要么我们看到一些可以开始expr的东西。冲突已解决。

当然，这会改变语言，使其更加宽容。我们可能不想接受：

( 3 + 4 + )

或

( (+) 3 4 + )

但由此产生的语法并不模棱两可。我们可以让解析器继续，然后在减少section时发出错误消息，通过检查$2是否受到适当限制。（这是一种非常常见的技术，它没有任何问题。

或者，我们可以将

expr: expr PLUS expr

规则为两个相互排斥的备选方案：

expr: atom PLUS expr
expr: expr_not_an_atom PLUS expr

这也将解决冲突，因为atom不能减少到expr_not_an_atom.但它留下了如何定义expr_not_an_atom的问题。

碰巧，我很确定这是可能的，但这不是微不足道的，后果会波及语法。我也不能给你一个算法，因为CFGs——与正则表达式不同——不是在否定或集合差分下闭合的。但基本上，您只需级联非终端，拆分它们，以便每个替代方案都适合atom或expr_not_an_atom - 这也是一种合法的方法，但生成的语法可能难以阅读。

如果您使用的是 bison ，您将有另一种选择：生成 GLR 语法。只要您的语言没有歧义，GLR 语法就会找到正确的解析，可能会稍微慢一些，但您的努力要少得多。

如果有帮助，这里有一个稍微相关的答案，其中我提出了一个完整的解决方案来拆分非终端。