yacc/bison 的最大咀嚼规则——似乎采用最小咀嚼

Question

我正在尝试将一种新的语言结构引入 large/complex 语法中。我知道这会使语法含糊不清，但我希望用 'maximum munch' 规则解决这个问题。也就是说，将我的结构放在首位，因此它会被优先采用。我取得了一些成功，但树的其他部分并没有那么多。考虑：

( 1, 2, 3 )          // triple
( 4, 5 )             // twople
( 6 )                // *not* a oneple, see below
()                   // zerople

(7 + 8) * 9          // single parens used to override usual precedence
( (( 7 + 8 )) * 9 )  // currently this means the same, but nobody would write that!

(( 6 ))              // I want to be a oneple
( ( 6 ) )            // this also a oneple
( ( ( 6 ) ) )        // this also a oneple with a superfluous pair of parens, ambiguous
((  ( 6 )  ))        // superflous parens are innermost
(  (( 6 ))  )        // superfluous parens are outermost

((7 + 8) * (9 + 10)) // not a oneple, despite the (( ... ))

在三对括号内带有 6 的那三个例子是有歧义的，我不在意语法采用其中的哪一个，它们在语义上是相同的。根据 'maximum munch' 规则，它应该取三者的中间，即最里面的括号是多余的。

词法分析器将每个 (、) 作为一个单独的标记。目前，解析器将 ( ( ( 6 ) ) ) 等同于 6 （其中解析为 expr/int) -- 即在我尝试更改语法之前语法做了什么。

该文法具有许多由其他标记定义的标记级别。某些上下文中的某些表达式可以识别双括号 OK。其他人则没有那么多（而且很难将其归结为一个合理大小的例子）。有什么通用的技巧可以让野牛吃得最多？

补充： 这种歧义类似于第一种使用 BNF 的语言中著名的歧义：ALGOL 60

if cond1    then 
  if cond2  then blah2
 else            blah3;      // is this on cond2 False or cond1 False?

解决方法是说 else 附加到尚未获得 else 的最里面的 if/then -- 也就是说，在 cond2 上 False这个案例;离开 cond1 没有 else 分支。（ALGOL 没有 'offside rule'，谢天谢地！）

Addit2: 好的，应大众需求，我开始修改之前的yacc代码是here（现在你会希望你从来没有问过。）这个例如在规则 aexp 中工作（中间线是我的 mod）

  | '(' exp ')'         {$$ = gc3();}
  | '(' '(' exp ')' ')'     {$$ = gc5(buildTuple(cons(,NIL)));}   /* ADC Apr-2020  */
  | '(' exps2 ')'       {$$ = gc3(buildTuple());}

此行无效 -- 在规则 apat 中，pat 一直被解析为多括号普通模式。

apat      : NUMLIT          {$$ = ;}
  | var             {$$ = ;}
  | '(' '(' pat ')' ')'     {$$ = gc5(buildTuple(singleton()));}  /* ADC Apr-2020 */
  | apat_vI         {$$ = ;}
  ;

我试过在 pat 树上下的各种地方插入那条线；我什至尝试过同时将它放入多个作品中，这看起来很狡猾。解析器似乎总是忽略它。

感谢@Chris Dodd 的回答。我认为尽管这给出了 shift/reduce 错误，但我已经阅读了野牛 'does the right thing' 的其他 SO 答案——也就是说，如果你把一个作品放在另一个作品之上，它会优先选择那个作品。

Answer 1

所以你没有显示你的代码，但我猜你正在尝试类似的东西：

%token NUM NAME
%left '+' '-'
%left '*' '/'
%nonassoc PREFIX
%%

expr: expr '+' expr
    | expr '-' expr
    | expr '*' expr
    | expr '/' expr
    | '-' expr %prec PREFIX
    | '(' expr ')'   /* parentheses for grouping */
    | NUM
    | NAME
    | '(' exprlist ',' expr ')' /* tuple */
    | '(' '(' expr ')' ')'      /* one-ple */
    ;

exprlist: expr | exprlist ',' expr ;

此语法有歧义，因此有一个 shift/reduce 冲突。但是默认的 prefer-shift-over-reduce 解决方案将导致它使用 "one-ple" 规则而不是 "parentheses" 规则解析两次。

但是，如果您添加一个 %left ')' 指令，它将以相反的方式解决这个问题（并报告一个 "rule useless due to conflicts" 作为一个规则）

Answer 2

我已经解决了这个问题；这与 %left / %right 优先级无关。

请注意，在 Addit2: 有效的代码中，相同的非终结符 pat 出现在两个可能不明确的规则中；并且区分它们的终端也出现（单对 parens 与加倍对）。而在有问题的示例中， 'competing' 非终端的名称不同；而且没有终端。

在 apat 的规则中，NUMLIT 不能以 ( 开头，var 也不能。 apat_vI 可能以 ( 开头，因此将 pat 的规则移入其中。（如果你在家里跟随，请查看我链接到的回购协议。）

但仅仅将规则移入 apat_vI 还不够好。这是关键的几行：

  | '(' pat_npk ')'     {$$ = gc3();}   
  | '(' npk ')'         {$$ = gc3();}                  
/*    | '(' '(' pat ')' ')'     {$$ = gc5(buildTuple(singleton()));}      /*   ignored */
  | '(' '(' pat_npk ')' ')'     {$$ = gc5(buildTuple(singleton()));}  /* same non-term */

带pat的注释掉的那一行是我移动的那一行，但它并没有解决歧义。（并且不会减少 shift/reduce 冲突的计数。）

查看 pat 的作品，它们是 npk 或 pat_npk。在这种情况下，npk 不能以 ( 开头——所以忽略它； pat_npk 可能。因此，将 pat 更改为 pat_npk，这样可以将 shift/reduce 冲突减少 2 个。

( ( ( 6 ) ) ) 现在被解析为与 (( 6 )) 相同，不同于裸 6。这是使用以下语言的会话：

Main> let foo x = (( x )) in foo 6           -- (( x )) in exp always worked
(( 6 ))
Main> let bar (( x )) = x in bar (( 6 ))     -- (( x )) in pat got treated as bare x
6
Main> let bar (( x )) = x in bar (( (6) ))   -- three pairs of parens treated as a double
6
Main> let bar (( x )) = x in bar (( ((6)) )) -- four pairs of parens treated as two doubles
(( 6 ))

关键特征是：

bison 必须能够看到 apat_vI 的规则中有两个产生式包含相同的非终结符 pat_npk；和
它们的上下文因终端而异（一对括号与双括号）。
然后在传入的令牌字符串中遇到 ( 时，解析器将转移并等待看它是否得到另一个。

就像在 if/else 冲突中一样：鼓励解析器移动第一个 else，然后等待看它是否得到另一个。

yacc/bison 的最大咀嚼规则——似乎采用最小咀嚼

maximum munch rule with yacc/bison -- seems to be taking minimum munch

yacc

bison