有规则的语法,有两类运算符:addop、mulop、有优先级(addop) < precedence(mulop); & left-to-right associativity:
expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> factor digit | digit
digit -> 0|1|2|3|4|5|6|7|8|9
200+300+400-5010/52-60+100*10
算术表达式的计算需要产生类似于 C 编译器的结果,即 1640。 优先级和从左到右的关联性规则意味着以下处理,如括号所示:
((200+300)+400)-(((50*10)/5)*2)-60+(100*10)
=> 900-(200)-60+1000
=> 900-260+1000
=> 1640
但是,使用给定的语法为上述表达式构造解析树是不可能的,因为一旦触发第二个规则,就无法恢复到第一个规则。
那么,我是否需要修改语法来启用解析,比如:
expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor | expr
factor -> factor digit | digit
digit -> 0|1|2|3|4|5|6|7|8|9