(1)L →E;L|ε (2)E →TE' (3)E' →+TE'|-TE'|ε (4)T →FT' (5)T' →*FT'|/FT'|mod FT'|ε (6)F →(E)|id|num 消除上述文法的左递归
时间: 2023-08-21 18:48:48 浏览: 95
消除文法的左递归
5星 · 资源好评率100%
消除左递归的方法如下:
(1) L → E L'
L' → ; E L' | ε
(2) E → T E'
(3) E' → + T E' | - T E' | ε
(4) T → F T'
(5) T' → * F T' | / F T' | mod F T' | ε
(6) F → ( E ) | id | num
解释一下这个转换过程:
首先,我们把文法中所有左递归的产生式找出来。在这个文法中,有两个左递归的产生式:L → E L' 和 E' → + T E' | - T E'。
接着,我们给每个左递归的产生式引入一个新的非终结符。对于 L → E L' 这个产生式,我们引入一个新的非终结符 L',得到 L → E L',L' → ; E L' | ε。对于 E' → + T E' | - T E' 这个产生式,我们引入一个新的非终结符 E'',得到 E → T E',E' → E'' T,E'' → + | - | ε。
最后,我们把每个产生式中的左递归消除掉。对于 L → E L' 这个产生式,我们把它改写为 L → T L', L' → ; T L' | ε。对于 E → T E' 这个产生式,我们不需要做任何改动。对于 E' → E'' T 这个产生式,我们把它改写为 E' → T E'', E'' → + T E'' | - T E'' | ε。对于 T → F T' 这个产生式,我们不需要做任何改动。对于 T' → * F T' | / F T' | mod F T' | ε 这个产生式,我们把它改写为 T' → F' T'', T'' → * F' T'' | / F' T'' | mod F' T'' | ε。对于 F → ( E ) | id | num 这个产生式,我们不需要做任何改动。
这样,我们就成功地消除了文法中的左递归。
阅读全文