Mat*_*att 20 c grammar parsing expression operator-precedence
我遵循"优先级爬坡"部分中给出的解释这个网页实现使用各种前缀的一元和二元中缀运算符的优先级爬坡算法算术评估.我还想包括三元运算符(即三元条件运算符?:).
网页上给出的算法使用以下语法:
E --> Exp(0)
Exp(p) --> P {B Exp(q)}
P --> U Exp(q) | "(" E ")" | v
B --> "+" | "-" | "*" |"/" | "^" | "||" | "&&" | "="
U --> "-"
如何将三元运算符合并到这个语法中？
Ale*_*nze 24
具体来说,我将以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 --> "-"
我已经遇到过这个问题,搜索有关将三元运算符转换为反向波兰表示法(RPN)的信息,因此虽然我没有一个可靠的实现来实现?:Precedence Climbing 的运算符,但我认为我可以提供一些线索?:使用两个堆栈将运算符转换为RPN ...这类似于您给出的网页中的Shunting Yard算法.
(编辑)我必须指出我在这里做的不是很有效(必须评估三元运算符的两个分支),但是要证明?:在现有框架中合并一个新的operator()是多么容易( RPN转换代码)(通过声明?并:具有两个最低优先级).
我想从一些例子开始,?:根据我的解析器将表达式转换为RPN ...我添加了两个运算符而不仅仅是一个,?而且:,我不认为它会产生很大的不同,因为:并且?总会放在一起(RPN和原始表达式具有相同数量的令牌更方便).在示例中,您可以看到它是如何工作的.
例1: 1 + ((0+1) ? 2 : 3 + 8) + 4
RPN: 1 0 1 + 2 3 8 + : ? + 4 +
现在让我们来评估RPN.
1 - 将第一个元素推入堆栈,我们遇到了第一个二元运算符:
1 0 1和运算符+,我们添加前2个元素,将堆栈转换为1 1
2 - 然后再推三个元素,我们遇到了第二个二元运算符:
1 1 2 3 8 + ------> 1 1 2 11
3 -现在我们有:和?.这实际上告诉我们基于谓词(堆栈上第3个最顶层的元素)选择结果分支(堆栈顶部的第2个最顶层元素2)或备用分支(堆栈中最顶层的元素). .由于谓词是1(真),我们选择2并丢弃11.解析器弹出3个元素(谓词/结果/替代)并推回所选择的(在这种情况下,后续分支),因此堆栈变为111
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