0

我在使用包含普通中缀操作和中缀部分的语法的类似 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+)不会。

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

4

1 回答 1

1

省略很多语法，您有以下产生式，所有这些都可以同时可行。

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

因此，假设我们刚刚阅读( 0了 - 即 anLPAREN和 an INT- 下一个标记是+. 此时，我们需要将 theINT归约为 a atom，但我们无法判断后面的内容是否匹配 theatom或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。

碰巧的是，我很确定这是可能的，但这并不是微不足道的，其后果会影响语法。我也不能给你一个算法，因为 CFG——不像正则表达式——不会在否定或设置差异下关闭。但基本上，您只需要通过非终端级联，将它们拆分，以便每个替代方案都适合atom或expr_not_an_atom- 这也是一种合法的方法，但生成的语法可能难以阅读。

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

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

于 2015-03-16T05:19:13.677 回答