左结合是什么意思?

36

我对左结合和右结合的定义感到困惑。我也见过它们被称为左关联和右关联,想知道哪种对应哪种。

我知道它与具有相同优先级的操作的执行顺序有关,例如,a = x * y * z 是否意味着 a = x * (y * z) 或 a = (x * y) * z。我不知道哪种是左结合的,哪种是右结合的。

我已经尝试在Google上搜索,但我只能找到c ++中不同运算符的关联性表格。查看所有示例只会让我更加困惑。

另外让我更加困惑的是:

glm::vec4 transformedVector = translationMatrix * rotationMatrix * scaleMatrix * originalVector;

首先执行缩放矩阵乘法,然后是旋转矩阵,最后进行平移。在这个例子中,矩阵都是glm::mat4类型的,向量是glm::vec4类型的。这是从左到右还是从右到左结合性?这与普通乘法相同还是glm类型的乘法不同?


4
不要在意“-to-right”或“-to-left”(第二部分),这只是一种干扰。请忘掉它。 - Marc van Leeuwen
wikipedia 可以帮助您。 - ygweric
6个回答

阿里云服务器只需要99元/年,新老用户同享,点击查看详情
33

通常情况下,您从左到右阅读。您通常从左到右进行数学计算。这就是从左到右结合性,它是最常见的。

大多数人将解决

x = 23 + 34 + 45
通过对它进行分组。
x = (23 + 34) + 45

这是从左到右的结合性。您可以记住它,因为您从左到右阅读和进行数学运算。

对于数学中的加法而言,这并不太重要。无论如何,你总能得到相同的结果。这是因为加法具有结合律。说一个运算是结合的意味着从左到右和从右到左是一样的。但对于编程中的加法来说,由于溢出和浮点算术(但在任何合理的语言中都不会对正常大小的整数产生影响),所以当你用大数字和轻率使用a+bb+a时,需要记住加法操作发生的顺序。

以您的示例为例:

glm::vec4 transformedVector = translationMatrix * rotationMatrix * scaleMatrix * originalVector

从概念上讲,您首先要从右侧开始咀嚼,因为那是您正在操作的物体所在的位置。然而,在C++中,*通常是从左到右关联的,并且不可能覆盖它。glm可以通过多种方式处理此问题:它可以建立一个缓存等待最终向量到达的乘法项,然后执行从右到左的乘法。它还可以(更可能)使用代数定理,即矩阵乘法是完全结合的,并且只是从左到右进行乘法,然后在文档中向读者保证这与将其视为从右到左相同。但是,您需要了解实现,因为正如先前讨论的那样,它很重要选择实现浮点数之间乘法的方法

为了完整起见,考虑减法。什么是a-b-c?这里确实很重要,它是左关联还是右关联。当然,在数学中,我们定义它为(a-b)-c,但一些奇怪的编程语言可能更喜欢减法是右关联的,并始终将a-b-c解释为a-(b-c)。这种外星语言最好有一个文档页面,说明-是右关联的,因为它是操作规范的一部分,而不是您可以仅从操作符的使用中看出来的东西。


感谢Yu Hao的已删除答案,因为我从中学到了最重要的细节。 - djechlin
1
你还应该指出数学运算是可结合的,而编程语言中的实际运算(特别是浮点数)则不是。例如,如果按照从左到右的顺序对操作进行分组,则 100 + 1e-15 + 1e-15 +...+ 1e-15 的计算结果为 100,但如果按照从右到左的顺序对操作进行分组,并且有足够的操作数(例如使用8个 1e-15 相加),则结果可能大于 100。另外:APL将从右到左作为默认结合性,如果您需要在最后一段提供示例,可以考虑使用它。 - Bakuriu
1
我不是那个点踩者,但变换矩阵被从内向外应用于向量,这是导致 OP 解释为“反向顺序”的原因,并不涉及加号或乘号的结合律或交换律。 - Iwillnotexist Idonotexist
@Bakuriu 很好的发现,已经处理了(没有添加关于APL的内容,但第一个技术细节很重要)。 - djechlin
@Code-Apprentice,理解你正在操作的向量是在内部的。从代数角度来看,矩阵乘法和向量乘法并不完全相等。矩阵乘法发生在一个环中,而向量乘法是一个模操作。 - djechlin
显示剩余9条评论

9
您可以从以下文字中看出: 当我们将运算符组合成表达式时,应用运算符的顺序可能不明显。例如,a + b + c可以解释为((a + b) + c)或(a + (b + c))。如果操作数按照左到右的顺序进行分组,则称+是左结合的。如果它按相反方向对操作数进行分组,则称其为右结合。 A.V. Aho&J.D. Ullman 1977年,第47页

有没有一个好的例子,可以说明右结合实际上在数学上有所不同(而不是操作上,因此忽略浮点类型问题)?在Haskell中,==/=<等运算符是非结合的。而^:$是右结合的运算符,这意味着第一个隐含的括号在右侧。引用@Marc的话:“因此,在嵌套使用时,没有显式括号,最左边的运算符将其直接邻居作为操作数,而其他实例则将左操作数作为(结果)表达式的一部分,该表达式由它们左侧的所有内容组成。” - wide_eyed_pupil
在非关联运算符的情况下,如果子表达式或表达式中的第一个隐含括号位于最左侧或最右侧的非关联运算符上,这并不重要。 - wide_eyed_pupil
逻辑运算符示例:(1 || 0) && 0 = 0; 1 || (0 && 0) = 1 - misiu_mp

5

4
如果一个中缀运算符(或者更广义地说,有未封闭的左、右子表达式的表达式类型)在没有显式括号的嵌套使用中,隐含的括号被放在左边,则该运算符(表达式类型)是左结合的。因为在C++中星号*是左结合的,所以a*b*c等同于(a*b)*c。在嵌套层数更深的情况下,一堆隐式括号出现在左端:(((a*b)*c)*d)*e。 同样地,这意味着该运算符的语法生成规则是左递归的(意味着左子表达式具有与此规则为生成的语法类别相同的语法类别,因此可以直接使用相同的规则(相同的运算符)来形成该子表达式;另一端的子表达式具有更严格的语法类别,并使用相同的运算符需要显式括号)。在C++中,multiplicative-expression(标准第5.6节)的一个产生式是mutliplicative-expression*pm-expression,其中multiplicative-expression在左边。 因此,在没有显式括号的嵌套使用中,最左边的运算符将其相邻的操作数作为操作数,而其他实例则将左侧所有表达式的(结果)表达式作为左操作数。 我承认,我有些过分强调了这一点。上面没有出现“右”的字眼,也没有涉及任何运动;结合性是一种语法性质,因此是静态的。重要的是隐含的括号放在哪里,而不是按照什么顺序写它们(实际上根本不写,否则它们将是明确的)。当然,对于右结合性,只需将上述每个“左”替换为“右”。 总之,我看不到任何有效的理由称之为从左到右的关联性(或者组合),但事实是人们会这么称呼(即使标准文件中也是如此,尽管显式的语法规则也被给出)。 混淆来自于解释,通常会这样说(在没有显式括号的情况下),运算符从左到右执行 (对于右结合的操作符则从右到左执行)。这是具有误导性的,因为它混淆了语法和语义(执行),而且只适用于自底向上求值的操作(所有操作数都在运算符之前求值)。对于具有特殊评估规则的运算符,这是完全错误的。 对于运算符 && (and)和 || (or),其语义是首先计算左操作数,然后计算运算符本身(即确定左侧还是右侧的操作数将产生结果) ,然后可能是计算右操作数。这种从左到右的评估完全独立于结合性:这些运算符恰好是左结合的,可能是因为所有非赋值二元运算符都是左结合的,但是 (c1 && c2)&& c3 (其中包含不必要的括号)与 c1 &&(c2 && c3) 具有等效执行(即从左到右执行条件,直到一个返回 false 并返回该值;或者如果没有返回 true ),我无法想象一个合理的编译器为两种情况生成不同的代码。实际上,我发现右分组更能表达表达式的计算方式,但是这确实没有任何区别;或者对于 or 也是一样。

对于条件(三元)运算符? ...: ,这更加清晰,因为两侧都有开放的子表达式(参见我的开头语句); 中间操作数包含在 中,并且从不需要其他括号。事实上,该运算符被声明为具有结合性,这意味着 c1? x:c2? y:z 应该读作c1?x:(c2?y:z),而不是(c1?x:c2)?y:z (隐式括号位于右侧)。但是,在隐式括号的情况下,两个三元运算符从左到右执行;解释是三元运算符的语义不会首先评估所有子表达式。


回到您问题中的示例,左结合(或从左到右分组)意味着您的矩阵-向量乘积被解析为((M1*M2)*M3)*v。尽管在数学上是等价的,但实际上几乎不可能执行为M1*(M2*(M3*v)),即使那样更有效率。原因是浮点乘法并不真正是结合的(只是近似),因此浮点矩阵乘法也不是结合的;编译器因此无法将一个表达式转换为另一个表达式。请注意,在((M1*M2)*M3)*v中,不能说哪个矩阵先应用于向量,因为它们都没有:首先计算组合线性映射的矩阵,然后将矩阵应用于向量。结果将与M1*(M2*(M3*v))的结果大致相等,其中应用了M3,然后是M2,最后是M1。但如果您希望发生这样的事情,您必须编写这些括号。


2

a = (x * y) * z 是从左到右计算,而 a = x * (y * z) 是从右到左计算。

glm 的矩阵乘法是从左到右关联的,因为它重载了 * 运算符。这里的问题是关于矩阵乘法在几何变换方面的含义,而不是数学上的结合律。


-2
一个运算符的从左到右的结合性意味着运算符的右侧不应该有任何优先级更高的运算符,但可以是相同的优先级。如果在我们的运算符右侧有任何优先级更高的运算符,则必须首先解决它。例如:
x = 2 + 3 * 3;
这里,对于 + 运算符(从左到右结合性),右侧包含一个 * 运算符,它的优先级高于 + 运算符,因此我们必须先解决它。
x = 2 + 9;
x = 11;

enter image description here

enter image description here

enter image description here


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,