compiler-construction - 文脈自由文法を左因子化する方法は？

Question

私が理解しているように、次の場合、トップダウンパーサーを構築するには左ファクタリングが必要です。しかし、それを行う方法を理解するのは難しいですか？誰かがここで私を助けてくれますか？ありがとう。

s = a | b
b = c d
c = (e | f) g
e = a | h

Answer 1

すべての非終端記号はここで 1 回だけ参照されるため、文法全体を 1 つの式にまとめることができます。

s = a | ((a | h | f) g d)

したがって、2 つの基本的なバリエーションがあります。端子 a の後に任意で g の次に d が続くか、または h または f のいずれかの後に常に g の次に d が続きます。

だから私たちは持っています

s =  b' | c'
b' = a | a g d
c' = (h | f) g d

または、共通の gd シーケンスを独自のプロダクションにプルします

s =  b' | c'
b' = a | a e'
c' = (h | f) e'
e' = g d

次に、E (空) オプションを導入することで、a を b' の共通の開始記号としてプルアップできます。

s =  b'' | c'
b'' = a (e' | E)
c' = (h | f) e'
e' = g d

文法は明確になりました。