使用yacc /野牛的最大mu子规则-似乎正在使用最小mu子

Question

我正在尝试将一种新的语言构造引入大型/复杂语法中。我知道这会使语法变得模棱两可，但我希望使用“最大嚼数”规则解决该问题。也就是说，将我的构造放在第一位，因此它是优先选择的。我取得了一些成功，但树的其他部分却没有那么成功。考虑：

( 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的示例是模棱两可的，我不理会语法采用哪一个，它们在语义上是相同的。按照“最大嚼食”规则，应该取三个中间的中间部分，即最里面的部分多余。

词法分析器将每个(，)当作一个单独的标记。当前，解析器将((( 6)) )等同于6（其中被解析为expr / int）—即语法是做什么的在尝试更改它之前。

语法具有由其他标记定义的许多标记级别。在某些情况下，某些表达式可以识别双括号。其他人没有那么多（很难将其简化为合理大小的示例）。是否有说服野牛最大程度吃午饭的一般技巧？

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

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

这是通过说else附加到尚未获得if/then的最里面的else来解决的-也就是说，在这种情况下，如果cond2为假；使cond1离开else分支。 （ALGOL没有“越位规则”，谢天谢地！）

Addit2：好吧，根据普遍的需求，我开始修改之前的yacc代码是here（现在您希望自己从未被问到。）例如，这在规则aexp中起作用（中间线是我的mod）

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

此行不起作用-在规则apat中，pat始终被解析为多括号普通模式。

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

我曾尝试在pat的树上上下各行插入该行；我什至尝试将它同时放在多个作品中，这似乎很狡猾。解析器似乎始终忽略它。

感谢您@Chris Dodd的回答。我以为，尽管这样会产生移位/减少错误，但我还是读过其他关于野牛“做正确的事”的答案-也就是说，如果您将一种产品放在另一种产品之上，则它会优先选择这种产品。

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 ;

此语法是模棱两可的，因此产生了一种转移/减少的冲突。但是，默认的“优先于偏移减少”的分辨率将导致其使用“一重”规则而不是“括号”规则进行两次解析。

但是，如果添加%left ')'指令，它将以相反的方式解决此问题（并为单重规则报告“由于冲突而无用的规则”）]