对于表达式规则:
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,这样就解决了左递归问题。