Насколько я понимаю, в следующем случае для построения нисходящего парсера требуется левое факторинг. Но трудно понять, как это сделать? Может ли кто-нибудь помочь мне здесь? Спасибо.
s = a | b
b = c d
c = (e | f) g
e = a | h
Как оставить фактор контекстно-свободной грамматики?
Ответы (1)
Каждый нетерминал упоминается здесь только один раз, поэтому мы можем объединить всю грамматику в одном выражении:
s = a | ((a | h | f) g d)
Таким образом, у нас есть два основных варианта: за терминалом a может следовать 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
Затем мы можем вывести a как общий начальный символ в b', введя опцию E (пусто):
s = b'' | c'
b'' = a (e' | E)
c' = (h | f) e'
e' = g d
Грамматика теперь однозначна.
person
500 - Internal Server Error
schedule
05.03.2012
a,d,f,gиh. Если это простые терминалы, левый факторинг не нужен, насколько мне известно. - person Bart Kiers schedule 03.03.2012b also contains a in its left if you go through b->c->e->a? это означает, что это может бытьs = a | a + something. Вы все еще говорите, что левый факторинг не требуется? Спасибо. - person Bee schedule 03.03.2012