13

当使用右侧为空的规则编写（“理论”）语法时，总是使用诸如 ε（或 1）之类的符号来明确表示这种空性：

A → ε | a A

Yacc 和其他人中的这种语法看起来像

a: | 'a' a

或“更糟”

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

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

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); }
 ;

Indeed$empty看起来像一个伪符号，例如$acceptBison 为初始规则生成的$@n伪符号，或者中间规则操作的伪符号，或者$eof是文件结尾的伪符号。但它绝对不是符号，恰恰是符号的缺失。

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

所以这是语法上的细微差别，但更符合整体语法。归功于 Joel E. Denny。

4

5 回答 5

7

我通常只使用评论：

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

无需更改即可正常工作，并使意图清晰......

IMO，这在标题下“如果它没有坏，就不要修理它”

于 2013-02-01T20:35:40.653 回答
3

我建议如下：

定义声明：

%empty ID

其语义是双重的：

1)ID可用作 RHS 中唯一的非规则标记，以指示 RHS 是 epsilon 产生式；和

2) 未标记的 epsilon 产生式ID将被视为语法错误。

因此，通过声明：

%empty epsilon

epsilon 必须用于标记空的 RHS；没有任何%empty声明，现状保持不变，空的 RHS 没有标记（可能有注释除外）。

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

就个人而言，我可能会使用这样的声明，尽管老实说我很习惯使用注释来标记一个空的 RHS，而且我不相信我曾经不小心创建了一个空的 RHS。所以我不会将它标记为优先功能请求，但我也不会反对它的实现。

于 2013-02-01T21:14:42.427 回答
2

我已经使用了epsilon自己，以及marker我在大括号中附加了一些代码的空产品的变体。

野牛语法中的保留符号会很有用；我喜欢建议的 $ 前缀，以避免与用户命名的符号发生冲突。

于 2013-02-01T14:59:38.230 回答
0

1）嗯，有明显的

e：一个'b'
一个：'一个'
 | 空的
空的：

2）是的，这将非常有帮助。

3) $accept,$end和$undefined符号总是被定义，并保留给 Bison 内部使用（例如，它们不能出现在语法中）。Bison$@n为中间规则动作生成，但这些也不能在用户的语法中使用。

如果我没记错的话，用户可以在语法中使用的唯一预定义标记是error. 那么，您为什么不建议empty使用该专用符号呢？这似乎是相当合理的。还是你建议$error也介绍？

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

于 2013-02-01T15:40:35.783 回答
0

当然，从某种意义上说，如果它包含一个动作，产生式就不是真正的“空”，因为在 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 实际实现的痛苦。其余的将或多或少按照您指定的方式工作，一个警告“空”规则的选项，除非“空”规则包含 %assert(epsilon)。

在优先级方面，我认为当野牛可证明创建了一个不可能接受输入语法的解析器（例如，一个或多个产品永远不会触发）时，报告它的优先级要高得多。至少，我上次看时没有那种能力，但我有一只相当老的野牛:-)。并且它仍然无法用英语解释具有常见左前缀的产生式问题，这些问题因嵌入式动作而不同？除非它变得更好，否则我认为还有很多解释性改进要做，这将比检查无意中的空规则更有帮助。

It would be interesting to see some data on the most common errors students run into (I guess I would not have picked this one as a contender!). That would be kind of an interesting experiment: hack the student copy of bison so it sends every run into a database, use some software to clean it up and analyze the most common misunderstandings.

于 2013-02-07T06:19:01.473 回答