为什么选择二元运算符而不是一元运算符？

Question

对于同时作为一元和二元的运算符，为什么在像这样的表达式中选择二元运算符a@b？

经过大量的思考和搜索，我仍然无法回答为什么像这样的东西a+b被解析为二进制表达式而不是a(+b)，这显然是胡言乱语。

我不认为上下文无关的语法能够区分这两者，并且试图在这个版本的标准中找到答案并没有给我任何答案。

解析器是否特别选择二进制版本，因为一元版本会是胡言乱语？如果是这样，标准中是否有部分概述了这一点？

Answer 1

上下文无关并不意味着“没有状态”。解析器有很多状态来跟踪给定到目前为止看到的标记，哪些语法规则是可能的，并预测接下来会出现哪些标记。因为没有规则说两个表达式可以直接相邻出现，所以它永远不会考虑这a+b可能是表达式a和+b并排。

例如，假设我们正在使用这个基本语法：

expr ? expr '+' unary_expr | unary_expr
unary_expr ? '+' unary_expr | IDENT

^{（符号：?给出非终结符可以扩展到的规则并|指示替代的可能性。'+'是加号标记，IDENT是任何标识符标记。）}

让我们解析a+b. 我们的解析器的起始状态将是：

1. expr ? expr '+' unary_expr
         ^
2. expr ? unary_expr
         ^
3. unary_expr ? '+' unary_expr
               ^
4. unary_expr ? IDENT
               ^

它在开始时考虑了一些规则。它不知道它会得到哪个，可能是其中的任何一个。请注意，它正在考虑的每个产品还包括一个cursor，我在^上面用插入符号标记了它。这就是规则中解析器所在的位置。

好的，现在它看到了第一个IDENT标记。它将其状态更新为以下内容：

1. expr ? expr '+' unary_expr
              ^
2. expr ? unary_expr
                    ^
3. unary_expr ? IDENT
                     ^

现在它正在考虑三个规则。请注意，光标已向右移动。

如果第一条规则是正确的，那么它刚刚看到了一个表达式并且正在等待'+'下一个。或者，也许第二条规则是正确的，a只是一个一元表达式。在这种情况下，它预计不会再有令牌跟随。解析器不知道它会是哪个，所以它会同时考虑两者。

你会看到如果下一个标记是 a'+'那么它必须是一个二进制加号。为什么？因为第一个规则是唯一一个预测下一个'+'令牌的规则。

因为'+'要被解释为一元加上解析器必须使此规则处于活动状态，光标位于 之前'+'：

unary_expr ? '+' unary_expr 
            ^

你可以看到它没有。

如果上下文无关并不意味着无状态，那么它是什么意思呢？我们从什么“上下文”中“解脱”？

上下文无关是对语法可以包含哪些规则的限制。相反的是上下文敏感的，其中生产可以根据周围环境而变化。上下文相关文法比上下文无关文法更强大，但解析起来要困难得多——即使对人类来说也是如此！语言理论家很早就发现，上下文无关语法占据了一个最佳位置，即强大到足以表达，而不会过于复杂而难以推理。

有关更多详细信息，请参阅： 上下文无关文法与上下文敏感文法？

一个上下文无关文法（CFG）是一个语法其中（正如你指出）每个生产具有形式的？w，其中 A 是非终结符，w 是终结符和非终结符的字符串。非正式地，CFG 是一种文法，其中任何非终结符都可以在任何时候扩展为其任何产生式。文法的语言是可以从起始符号导出的终结符串的集合。

甲上下文敏感语法（CSG）是其中每个生产具有形式蜡语法？wyx，其中 w 和 x 是终结符和非终结符的字符串，y 也是终结符的字符串。换句话说，产生式给出的规则是“如果你在给定的上下文中看到 A ，你可以用字符串 y 替换 A”。不幸的是，这些语法被称为“上下文敏感语法”，因为这意味着“上下文无关”和“上下文敏感”不是对立的，这意味着某些类别的语法可以说需要大量上下文信息，但未被正式视为上下文相关。