文脈自由文法を残す方法を教えてください。

Question

私が理解しているように、以下のケースでは、トップダウンパーサーを構築するために左寄りが必要です。 これを行う方法を理解することは難しいですか？誰かがここで私を助けることができる？ありがとう。

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

Answer 1

すべての非ターミナルはここでしか一度参照されているので、我々は単一の式で一緒に全体の文法を引くことができます。

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

だから我々は、2つの基本的なバリエーションを持っていると、端末は、オプションに続きますg、dのいずれか、またはhまたはfのいずれかが常にgとdの後に続く。

だから我々は、我々はその後、Eを導入することにより、B」における共通の開始記号としてプルアップすることができます

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 

を持っています（空）オプション：

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

文法は今や明確です。