以下のような規則を考える

E→E+T

E→T

一行で書くなら

E → T | E + T

このとき1つ目の規則を左再帰という

すなわち、Eの右辺の最初の記号にEが来てしまうこと

このとき、この規則は曖昧性を含んでしまう

FIRST集合的には、FIRST(T) \subset FIRST(E+T)になるから。

そこで左再帰の除去をする

Parsecではchainlを使うと左再帰を除去したBNFを実装できる

左再帰は無限ループになるのが問題なのであって、曖昧な文法という意味ではない？

直接左再帰

1つの規則による左再帰

一般の左再帰

「一般の左再帰」という用語なのかな

複数の規則による左再帰

例

参考