BNF 中的递归定义
Recursion definitions in BNF
我最近开始学习编程语言，我正在努力更好地理解 BNF 中的递归定义。
例如，如果我们将标识符视为由字母和数字组成但始终以字母开头的任何内容，则此类标识符的定义为
<identifier> ::= <letter> | <identifier> <character>
<character> ::= <digit> | <letter>
但是当我们考虑数字的定义时，它会变得很有趣。应该是这个
<number> ::= <digit> | <number> <digit>
还是这个？
<number> ::= <digit> | <digit> <number>
– 从句法上看，它们似乎都是正确的，但我的直觉告诉我它们的语义会有所不同——一个数字是 0123456789，另一个是 9876543210。我错了吗？两个数字定义都有效吗？
如果允许数字以前导零开头，则数字的两种定义都是正确的。由于我们通常不允许这样做，因此更常见的定义是：
<non-zero-number> ::= <non-zero-digit> | <non-zero-number> <digit>
<number> ::= 0 | <non-zero-number>
这个和 <identifier> 定义都是左递归的，因为它们描述的字符串的 leftmost 字符是特殊的（因为它的可能值是有限的）。如果我们试图描述一组最后（最右边的）字符受到限制的字符串，我们可能会使用右递归。
自从我们从左到右阅读以来，最左边元素特殊的语法比最右边元素特殊的语法多得多。 （同样从左到右工作的解析算法往往针对这种常见情况进行了优化。）
（我完全知道并非所有人都是从左到右阅读的。我们中的许多人都是从右到左阅读的，我无意建议哪一个更好。这将是更文化中立地谈论阅读或解析 "from beginning to end"，并区分 "leading recursion" 和 "trailing recursion"。事实上，在与语言关系不大的不同 CS 上下文中，通常谈论 "tail recursion"；也就是说，在函数的最后完成递归。但是负责现代解析理论的数学家是用英语写作的，从左到右的偏见悄悄进入了术语。）
由于左递归和右递归都同样擅长描述字符位置没有区别的字符串集，我们可以使用其中任何一个来描述数字，就像你的问题一样。我们甚至可以使用右递归语法来描述左区分字符串，方法是分离第一个位置并将其粘在后面：
<suffix> ::= <empty> | <letter> <suffix> | <digit> <suffix>
<identifier> ::= <letter> <suffix>
但这感觉不自然，因为标识符实际上只是一个单一的东西。
我最近开始学习编程语言，我正在努力更好地理解 BNF 中的递归定义。
例如，如果我们将标识符视为由字母和数字组成但始终以字母开头的任何内容，则此类标识符的定义为
<identifier> ::= <letter> | <identifier> <character>
<character> ::= <digit> | <letter>
但是当我们考虑数字的定义时，它会变得很有趣。应该是这个
<number> ::= <digit> | <number> <digit>
还是这个？
<number> ::= <digit> | <digit> <number>
– 从句法上看，它们似乎都是正确的，但我的直觉告诉我它们的语义会有所不同——一个数字是 0123456789，另一个是 9876543210。我错了吗？两个数字定义都有效吗？
如果允许数字以前导零开头，则数字的两种定义都是正确的。由于我们通常不允许这样做，因此更常见的定义是：
<non-zero-number> ::= <non-zero-digit> | <non-zero-number> <digit>
<number> ::= 0 | <non-zero-number>
这个和 <identifier> 定义都是左递归的，因为它们描述的字符串的 leftmost 字符是特殊的（因为它的可能值是有限的）。如果我们试图描述一组最后（最右边的）字符受到限制的字符串，我们可能会使用右递归。
自从我们从左到右阅读以来，最左边元素特殊的语法比最右边元素特殊的语法多得多。 （同样从左到右工作的解析算法往往针对这种常见情况进行了优化。）
（我完全知道并非所有人都是从左到右阅读的。我们中的许多人都是从右到左阅读的，我无意建议哪一个更好。这将是更文化中立地谈论阅读或解析 "from beginning to end"，并区分 "leading recursion" 和 "trailing recursion"。事实上，在与语言关系不大的不同 CS 上下文中，通常谈论 "tail recursion"；也就是说，在函数的最后完成递归。但是负责现代解析理论的数学家是用英语写作的，从左到右的偏见悄悄进入了术语。）
由于左递归和右递归都同样擅长描述字符位置没有区别的字符串集，我们可以使用其中任何一个来描述数字，就像你的问题一样。我们甚至可以使用右递归语法来描述左区分字符串，方法是分离第一个位置并将其粘在后面：
<suffix> ::= <empty> | <letter> <suffix> | <digit> <suffix>
<identifier> ::= <letter> <suffix>
但这感觉不自然，因为标识符实际上只是一个单一的东西。