如何修复 yacc：“2 shift/reduce 冲突”错误？

Question

前几天开始用yacc/flex编程，不知道为什么只在第31行递归调用不行(s: SKIP { System.out.println("txt: "+$1); } s).递归调用使我能够在不使用括号的情况下保留数字自由文本。我做错了什么？

%{
  import java.io.*;
%}

%token OPEN_PAREN;
%token CLOSE_PAREN;
%token <sval> SKIP;

%start s

%%

parens  : OPEN_PAREN s CLOSE_PAREN
        | OPEN_PAREN CLOSE_PAREN

exp     : parens

exps    : exp SKIP { System.out.println("S: "+); }
        | exp

s       : SKIP { System.out.println("txt: "+); } s
        | exps
        | s exps

%%

void yyerror(String s)
{
 System.out.println("err:"+s);
 System.out.println("   :"+yylval.sval);
}

static Yylex lexer;
int yylex()
{
 try {
  return lexer.yylex();
 }
 catch (IOException e) {
  System.err.println("IO error :"+e);
  return -1;
 }
}

public static void main(String args[])
{
 System.out.println("[Quit with CTRL-D]");
 Parser par = new Parser();
 lexer = new Yylex(new InputStreamReader(System.in), par);
 par.yyparse();
}

Answer 1

该摘录中只有一个 shift/reduce 冲突，这是 s 中模糊递归的结果。由于与中规动作无关，可以简化为：

s: BEFORE s
 | AFTER
 | s AFTER

这是 BEFORE* AFTER+ 的语法。（事实上 AFTER 在你的语法中实际上是一个非终结符也没有改变任何东西。）

这是不明确的，因为应用第一个和最后一个产生式的顺序不受语法限制。即使在简单的输入

BEFORE AFTER AFTER

有两种不同的解析：

      s                             s
   /     \                       /    \
  /       \                     /      \
BEFORE     s                   s      AFTER
  |      /   \               /   \      |
  |    AFTER   s         BEFORE   s     |
  |      |     |            |     |     |
BEFORE AFTER AFTER       BEFORE AFTER AFTER

可能应用这些分析中的哪一个对您来说并不重要（尽管实际上它确实如此，因为它会影响操作的执行顺序）。但这对bison/yacc很重要，它无法知道顺序是否不重要。

为了解决冲突，我们需要指定一个顺序。有两种可能：

后缀在前缀之前。这是编程语言中常用的顺序，其中后缀运算符（如数组下标）比前缀运算符（如一元减号）绑定得更紧密，因此 -a[1] 与 -(a[1]) 相同，而不是 (-a)[1]。在那种情况下，语法将如下所示：
```
s: t
 | BEFORE s
t: AFTER
 | t AFTER
```
前缀在后缀之前。这样做的好处是前缀部分的动作先于后缀部分的动作执行。（但请注意，t 的右递归性意味着如果其产生式有动作，则动作将从右到左执行。）
```
s: t
 | s AFTER
t: AFTER
 | BEFORE t
```
此替代方案的完全左递归实现：
```
s: t AFTER
 | s AFTER
t: %empty
 | t BEFORE
```

如何修复 yacc：“2 shift/reduce 冲突”错误？

How to fix yacc: "2 shift/reduce conflicts" error?

yacc