parsing - 左再帰の除去

Question

私はこの文法を持っています

S->S+S|SS|(S)|S*|a

S+S本当に混乱しているので、この文法から左再帰を排除する方法を知りたいです...

Answer 1

与えられた文法を単純化できるかどうか見てみましょう。

S -> S*|S+S|SS|(S)|a

次のように書くことができます。

S -> S*|SQ|SS|B|a
Q -> +S
B -> (S)

これで、おなじみの領域で左再帰を排除できます。

S  ->  BS'|aS'
S' ->  *S'|QS'|SS'|e
Q  ->  +S
B  ->  (S)

e はイプシロン/ラムダであることに注意してください。

左再帰を削除したので、Q と B はもう必要ありません。

S  ->  (S)S'|aS'
S' ->  *S'|+SS'|SS'|e

これは、左再帰の消去を扱うときに便利です。