规则的空右侧符号的表示法

Question

在编写一个（"理论上的"）语法时，如果规则的右侧为空，通常会使用符号 ε（或 1）来明确表示这个空值：

A → ε | a A

在 Yacc 和其他类似的语法中，这样的文法看起来会像这样

a: | 'a' a

或者更糟。

a:       { $$ = new_list(); }
 | a 'a' { $$ = $1; $$->append($1); }
 ;

在“现实世界中的语法”（如 Yacc、Bison 等）中，规则的空右侧部分没有明确标记为空，这一事实让我感到困扰：很容易忽略右侧为空的事实，或者更糟糕的是忘记插入 | 并实际使用中间规则动作：

a:       { $$ = new_list(); }
   a 'a' { $$ = $1; $$->append($1); }
 ;

1）我不知道是否有任何工具提供使空rhs显式的方法。是否有这样的工具？

Bison的未来版本可能会支持专用符号，当在非空rhs中使用时产生错误，并在留下隐式空rhs时产生警告。

2）人们认为这有用吗？

3）你建议使用什么符号表示？

目前的候选符号是$empty：

a: $empty { $$ = new_list(); }
 | a 'a'  { $$ = $1; $$->append($1); }
 ;

编辑

所选的语法是%empty：

a: %empty { $$ = new_list(); }
 | a 'a'  { $$ = $1; $$->append($1); }
 ;

的确，$empty看起来像一个伪符号，例如Bison为初始规则生成的$accept或中间规则操作的$@n伪符号，或表示文件结尾的$eof。但它绝对不是一个符号，而是恰好没有符号。

另一方面，%明显表示指令（某种属性/元数据），例如%pred。

所以这只是语法上的微小差异，但与整体语法更加一致。功劳归于Joel E. Denny。

- akim

Answer 1

通常我只使用注释：

a: /*epsilon*/ { $$ = new_list(); }
 | a 'a'  { $$ = $1; $$->append($1); }
 ;

不需要更改即可正常工作，并且可以清晰表达意图。

在我看来，这属于“不破坏已有的东西”范畴。

- Chris Dodd

---

我也使用注释，而且我不记得曾经犯过这样的错误。然而，我看到学生们以各种方式失败，我更喜欢显式而非隐式（我使用注释是因为没有其他选择），并且我也更喜欢尽早进行检查（编译时而非运行时）。 - akim

POSIX Yacc不支持%empty [-Wyacc]。因此，我像上面提到的那样添加了注释，但这会产生归约-归约冲突。如何解决空和非空产生式的归约-归约冲突？ - amalp12

@amalp12：一个空规则就是一个空规则，所以如果你有一个归约/归约冲突，无论你使用%empty、/* empty */还是只是空格，都没有关系。如果归约/归约冲突对你造成了问题，你需要通过重构语法来消除它，就像任何其他的归约/归约冲突一样。通常，这取决于规则在哪些上下文中被使用。 - Chris Dodd

如何优先考虑不为空的生产，只有在其他生产不存在时才考虑空值？ - amalp12

生产优先级（用于解决reduce/reduce冲突）来自源文件中的顺序。因此，a：| a'a';将优先考虑空规则，而a：a'a'|;将优先考虑非空规则。 - Chris Dodd

Answer 2

我建议如下：

定义声明：

%empty ID

其语义有两种：

1）在右部使用ID作为唯一的非规则标记，表示该右部是一个epsilon产生式；并且

2）没有用ID标记的epsilon产生式将被视为语法错误。

因此，有了这个声明：

%empty epsilon

epsilon 应该用于标记空的右侧；没有任何 %empty 声明，现状保持不变，其中空的右侧未被标记（除非有注释）。

这将允许喜欢显式标记空的右侧的用户立即这样做，而不会对现有的语法文件或不想以这种方式显式标记空的右侧的用户产生任何影响。

个人而言，我可能会使用这样的声明，虽然老实说，我已经习惯了使用注释来标记空的右侧，并且我认为我从来没有意外地制作一个空的右侧。因此，我不会把它标记为优先特性请求，但我也不会反对它的实现。

- rici

---

使用指令是一个有趣的想法！但似乎你认为不使用 $empty 会出错：这不是我考虑的，它只会产生一个警告 -Wempty，默认情况下被禁用。但是我更喜欢为空关键字使用唯一名称，这样阅读别人语法的人就不会误解这个伪标记的性质。 - akim

嗨！好的，我对警告有完全不同的看法。我在许多项目中广泛使用它们（自由软件，但也包括闭源软件）。但我不打算默认启用此警告。但是，如果我理解您的担忧，当在规则中使用时，诊断缺少空标记将是明智的，对吗？这将强制执行一致性：要么完全使用它，要么根本不使用它。这很有道理！ - akim

@akim：没有声明的话，就无法指定空产生式应该是一个错误，除非至少有一个空产生式。因此，如果我有一个不应该有任何空产生式的语法（这是一个常见情况），一致性检查就帮不了我。但我就说到这里。正如我所说，我觉得这个功能不是优先考虑的，我倾向于采用“如果它没坏，就不要修理它”的方法。 - rici

是的，你可以请求错误：-Werror=empty-rule。无论如何感谢您的反馈。随意表达您认为应优先考虑的事情！ - akim

Answer 3

我自己使用过epsilon，以及在空产生式上使用花括号附加代码的marker变体。

在bison语法中使用保留符号会很有用；我喜欢提议的$前缀，以避免与用户命名的符号冲突。

- David Gorsline

---

谢谢。我们可能会使用%empty来代替（作为伪符号，而不是像克里斯在他的回答中建议的指令），因为它实际上是一个关键字，而不是一个符号（它既不像$end一样是终结符，也不像$accept一样是非终结符）。 - akim

Answer 4

当然，如果产生式包含一个动作，从某种意义上说，它并不是真正的“空”，因为在 Yacc/Bison 中很难忽略动作被转换为可为空的非终结符这一事实。如果你（或者书本）在课堂上整个学期都在说“epsilon”，那么“%epsilon”可能比“%empty”更具有逼真感。

我在思考将其纳入更一般的断言机制中：

lines : %assert(epsilon)
      | %assert(on WORD) lines line ;

line : WORD '\n' ;

%assert(nullable(lines))
%assert(!nullable(line))
%assert(WORD in FIRST(lines))
/* etc. */

这个想法是为了稍微减少猜测yacc/bison实际上实现了哪种语言的痛苦，即使启用了所有启发式规则。其余部分基本按照您的要求工作，除非"empty"规则包含%assert(epsilon)，否则会有一个警告选项。

在优先级方面，我认为bison报告它已经创建了一个无法接受输入文法的解析器的能力应该更高（例如，一个或多个产生式永远不会触发）。至少在我上次看的时候还没有这个能力，但我使用的是一个相当旧的bison :-）。而且它是否仍然无法用英语解释具有相同左前缀但嵌入动作不同的产生式的问题？除非它在这方面有了很大的改进，否则我认为还有很多解释性的改进需要做，这将比检查无意中为空的规则更有帮助。

看到学生们最常犯的错误的一些数据会很有趣（我猜我不会选择这个作为一个竞争者！）。这将是一项有趣的实验：修改学生版本的bison，使其将每次运行发送到数据库，使用一些软件清理并分析最常见的误解。

- Ron Burk

---

Bison可以为您提供一些实现细节，例如FIRST集合。请查看bison --trace=help以获取可能的主题列表，特别是--trace=sets。也许它可以放入.output文件中，而不仅仅是保留给维护人员。 - akim

Answer 5

1) 嗯，显而易见的是

e: a 'b'
a: 'a'
 | empty
empty:

2) 是的，那会非常有帮助。

3) $accept、$end和$undefined符号始终被定义，并且专门用于Bison的内部使用（例如，它们不能出现在语法中）。Bison为中间规则操作生成$@n，但这些也不能在用户的语法中使用。

用户可以在语法中使用的唯一预定义标记是error。那么为什么你不建议将empty作为该专用符号呢？那似乎是相当合理的。或者你是在建议引入$error吗？

你考虑过nothing吗？我可能更喜欢那个。

- yroeht

---

你的提议和我的不一样：你的解析器将有更多状态来减少你的“空”非终端符号（最终有两个规约，而原始语法只有一个）。如果添加操作，很容易看出区别：你有两个，我只有一个。 - akim