c - 如何将三元运算符合并到优先级攀升算法中？

Question

我遵循了 this webpage 上“优先攀登”部分给出的解释。使用具有各种一元前缀和二元中缀运算符的优先级攀升算法来实现算术评估器。我还想包括三元运算符(即三元条件运算符 ?:)。

网页上给出的算法使用了如下语法:

E --> Exp(0) 
Exp(p) --> P {B Exp(q)} 
P --> U Exp(q) | "(" E ")" | v
B --> "+" | "-"  | "*" |"/" | "^" | "||" | "&&" | "="
U --> "-"

如何将三元运算符合并到此语法中？

Answer 1

具体来说，我以C/C++/Java的?:为例

在那些语言中，?: 运算符似乎允许 ? 和 : 之间的任何有效表达式，包括由 构成的表达式?: 本身以及由运算符组成的运算符，其优先级低于 ?: 的优先级，例如= 和 ,(例如:a ? b = c : d, a ? b , c : d, a ? b ? c : d : e).

这表明您应该以与 ( 和 ) 完全相同的方式对待 ? 和 : 而解析表达式。当你解析出 时？ expr :，它整体上是一个二元运算符。所以，你解析 ( expr ) 和 ？ expr : 同理，但前者是表达式，后者是二元运算符(内嵌表达式)。

现在 ？ expr : 是二元运算符(a ?-expr-: b 在“二元性”方面与 a * b 没有区别)，你应该是能够像您已经支持的任何其他二元运算符一样支持它。

就我个人而言，我不会费心将 ?: 拆分成它们自己的独立二元运算符。最后，它仍然是一个三元运算符，它必须链接到 3 个操作数，并在表达式评估期间作为一个整体考虑。如果您正在按照问题中提到的文章中的方法创建 AST，那么您就可以了，?: 有一个左子节点，一个右子节点(与任何其他二进制文件一样运算符)，另外还有一个中间子节点。

?-expr-: 整体的优先级应该是低的。不过，在 C/C++(和 Java？)中，它并不是最低的。由您决定您想要它成为什么。

到目前为止，我们还没有介绍 ?: 的关联性。在 C/C++ 和 Java 中，?-expr-: 与赋值运算符 = 一样是右结合的。同样，由您决定是使其左结合还是保持右结合。

还有这个:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"

应该变成这样:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^" | "?" E ":"
U --> "-"