bili_取名太难了:有些同学不懂什么是消除左递归,我来发表一下个人理解:
up主的做法是使左递归变为右递归,从而消除“左”递归,并不是消除递归
原本:T——>T , S | S
如果你试一下你会发现(做一个数量少的左递归): T——>T , S——>T , S , S ——>T , S , S , S ——>S , S , S , S
(不断用T——>T , S 替换 ,,最后用 T——>S 停止递归)
假设我们把 S 当成开头 ,然后去使得 S 变为 S, S 再变为 S , S , S 就会变成有递归了。
具体实现:
T ——>ST'
T' ——> , ST' | ε T ——>ST'——>S , ST' '——>S , S , ST''——>S , S , S , ST''——>S , S , S , S (最后用ε停止 )