语法分析(续1)

对于表达式规则:

expr -> add
add -> mul | add + mul
mul -> literal | mul * literal
literal -> 0|1|2|3|4|5|6|7|8|9

会有左递归的问题,比如:1+2,针对这个表达式,应用产生式:add -> mul | add + mul,得到 add + mul,
继续应用产生式:add -> mul | add + mul,得到add + mul + mul,发现最左边一直都是add,每应用一次产生式都
多一个 + mul,一直重复下去,无穷无尽,无法推导出最终的表达式。这个问题就是左递归问题。

问题的解决办法是修改规则,增加一条规则,变成以下这样:

add -> mul add'
add' -> + mul add' | ε

这个规则可以改写成下面的形式

add -> mul (+ mul)*

其中*表示零个或多个 + mul,这样就解决了左递归问题。