Как оставить фактор без контекстной грамматики?

Question

Как я понимаю, в следующем случае для построения нисходящего синтаксического анализатора требуется левый факторинг.Но сложно понять, как это сделать?Может ли кто-нибудь помочь мне здесь?Спасибо.

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

Answer 1

Здесь на каждый нетерминал ссылаются только один раз, поэтому мы можем собрать всю грамматику вместе в одном выражении:

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

Таким образом, у нас есть два основных варианта: за терминалом необязательно следует g, затем d, или же за h или f всегда следует g, затем d.

Итак, мы имеем

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

или, потянув общую последовательность g d в собственное производство

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

Затем мы можем вытянуть вверх как общий начальный символ в b ', введя опцию E (пусто):

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

Грамматика теперь однозначна.