Transform грамматику G в LL (1)

Question

У меня есть следующие грамматики, и мне нужно, чтобы преобразовать его в LL (1) грамматикой

G = (N; T; P; S) N = {S,A,B,C} T = {a, b, c, d} 
P = { 
S -> CbSb | adB | bc 
A -> BdA | b 
B -> aCd | ë 
C -> Cca | bA | a 
} 

Дело в том, что я знаю, как преобразовать, когда его только производство , но я не могу найти четкого метода решения этого вопроса в Интернете.

Заранее благодарен!

Answer 1

1. Удалить левую рекурсию, прямую и косвенную.
2. Построить таблицу LA(k). Если нет двусмысленности, грамматика (и язык) равна LL(k).

Очевидная левая рекурсия в грамматике:

S ==> C... ==> C...