如何将三元运算符合并到优先攀爬算法中?

我按照本网页 “优先攀登”部分给出的解释,使用带有各种一元前缀和二进制中缀运算符的优先攀爬算法来实现算术评估器。 我还想包括三元运算符(即三元条件运算符?: :)。

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

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

如何将三元运算符合并到这个语法中?

具体来说,我将使用C / C ++ / Java?:作为示例。

似乎在那些语言中?:运算符允许任何有效的表达式?:包括用?:本身形成的表达式和用运算符形成的表达式,其优先级低于?:的优先级?:例如=, (例如: a ? b = c : da ? b , c : da ? b ? c : d : e )。

这表明你应该对待?:在解析表达式时与()完全相同的方式。 解析后? expr : ? expr :它作为一个整体,是一个二元运算符。 那么,你解析( expr )? expr : ? expr :以相同的方式,但前者是表达式,而后者是二元运算符(其中嵌入了表达式)。

那么? expr : ? expr :是一个二元运算符( a ?-expr-: b在“二进制”方面与a * b没有区别),你应该能够支持它,就像你已经支持的任何其他二元运算符一样。

就个人而言,我不会煞费苦心地分裂?:成为他们自己的独立二元运算符。 最后,它仍然是一个三元运算符,它必须与3个操作数相关联,并在表达式评估期间作为一个整体考虑。 如果你正在按照你在问题中提到的文章中的方法并创建一个AST,那么你去, ?:有一个左子节点,一个右子节点(和任何其他二元运算符一样),另外,还有一个中间子节点。

?-expr-:作为一个整体的优先级应该是低的。 但是,在C / C ++(和Java?)中,它并不是最低的。 由你来决定你想要它是什么。

到目前为止,我们还没有涵盖?:的相关性。 在C / C ++和Java中, ?-expr-:与赋值运算符=一样是右关联的。 同样,由你来决定是左联想还是保持正确联想。

还有这个:

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

应该成为这样的事情:

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

我已经遇到过这个问题,寻找有关将三元运算符转换为反向波兰表示法(RPN)的信息,所以虽然我没有一个可靠的实现来实现具有Precedence Climbing的?:运算符,但我认为我可以给出使用两个堆栈将?:运算符转换为RPN的一些线索……这类似于您给出的网页中的Shunting Yard算法。

(编辑)我必须指出我在这里做的不是很有效(必须评估三元运算符的两个分支),但是要certificate在现有框架中合并一个新的运算符( ?: :)是多么容易(RPN转换代码)(通过声明?:具有两个最低优先级)。

我想从一些例子开始,说明如何根据我的解析器将带有?:表达式转换为RPN …我正在添加两个运算符而不只是一个, ? 并且:但是我不认为它会产生很大的不同,因为:? 将永远放在一起(RPN和原始表达式具有相同数量的令牌更方便)。 在示例中,您可以看到它是如何工作的。

实施例1: 1 + ((0+1) ? 2 : 3 + 8) + 4

RPN: 1 0 1 + 2 3 8 + : ? + 4 +

现在让我们来评估RPN。

1 – 将第一个元素推入堆栈,我们遇到第一个二元运算符:

1 0 1和operator + ,我们添加前2个元素,将堆栈转换为1 1

2 – 然后再推三个元素,我们遇到了第二个二元运算符:

1 1 2 3 8 + ——> 1 1 2 11

3 – 现在我们有:? 。 这实际上告诉我们基于谓词 (堆栈上第3个最顶层的元素)选择结果分支 (堆栈顶部的第2个最顶层元素, 2 )或备选分支 (堆栈中最顶层的元素, 11 ) , 1 )。 由于谓词是1(真),我们选择2并丢弃11.解析器弹出3个元素(谓词/结果/替代)并推回所选择的元素(在这种情况下,后续分支),因此堆栈变为

1 2

4 – 消耗剩余的元素:

1 2 + ——> 3

3 4 + ——> 7


例2: 1 + ((0+0+0?0:0) ? 2 : (3 + 8)) + 4

RPN: 1 0 0 + 0 + 0 0 : ? 2 3 8 + : ? + 4 +

评价:

开始:

1 0 0 + 0 + 0 0 : ? 2 3 8 + : ? + 4 +

将0添加到0后:

1 0 0 + 0 0 : ? 2 3 8 + : ? + 4 +

将0添加到0后:

1 0 0 0 : ? 2 3 8 + : ? + 4 +

第一个之后:? 选择0

1 0 2 3 8 + : ? + 4 +

添加3和8后:

1 0 2 11 : ? + 4 +

?:选择11:

1 11 + 4 +

添加1和11之后:

12 4 +

最后:

16


这可能表明可以将带有?:的表达式转换为反向抛光表示法。 正如网页所说,RPN和AST是相同的,因为它们可以相互转换,三元运算符应该能够以类似的方式用Precedence Climbing实现。

需要做的一件事似乎是?:运算符的“优先级”(或优先级)。 我在尝试RPN转换时实际遇到过它。 我给出了问号和冒号的最低优先级:

从上面的例子可以看出,每当我们要执行?:优先级分支备用分支以及谓词都应该已经被评估,从而产生一个数字。 这由优先保证。

以下是优先级(优先级)表。

! ~ > * / % > + - > & > ^ > | > && > || > ? > :

?:具有最低优先级,意味着在1?2 + 3:4 + 5等表达式中? 并且:永远不会把操作数带到它们周围。

? 先于:为了使:出现在之前? 在RPN中。 据我所知,这只是一个设计选择,因为:? 甚至不必首先分成2个运营商。

希望这可以帮助..


参考: http : //en.cppreference.com/w/cpp/language/operator_precedence

将冒号定义为优先级低于问号。 换句话说,一个? b:c将被解析为(a?b):c。 这使得解析器构造一个(if / then / empty-else)抽象语法节点,然后由“:operator”操作该节点以提供所需的else组件。

优先关系还保留了运算符的可组合性。 例如,一个? b:c? d:e解析为(a?b):( c?d):e,正如人们所期望的那样。

希望这可以帮助。