70
правок
Изменения
Нет описания правки
==Алгоритм==
Приведем [[алгоритм Эрли|Алгоритм Эрли]]. Далее разберем, сколько времени тратится в ходе его выполнения на каждом из шагов.
На вход подается [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматика]] <tex>G = (N, \Sigma, P, S)</tex> и строка <tex>w = a_1 a_2 \ldots a_n</tex> из <tex>\Sigma^*</tex>. Результатом работы алгоритма является [[Алгоритм Эрли#Определения|список разбора]] <tex>I_0, I_1, \ldots , I_n</tex> для строки <tex>w</tex>.
'''Построение <tex>I_0</tex>:'''
''Шаг 1.'' Для каждого правила <tex>S \rightarrow \alpha</tex> из <tex>P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>.
Выполнять шаги <tex>(2)</tex> и <tex>(3)</tex> до тех пор, пока в <tex>I_0</tex> можно включать новые ситуации.
''Шаг 2.'' Если <tex>[B \rightarrow \gamma \cdot, 0] \in I_0</tex>, то для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex> включить в <tex>I_0</tex> ситуацию <tex>[A \rightarrow \alpha B \cdot \beta, 0]</tex>.
''Шаг 3.'' Если <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex>, то для всех правил из <tex>P</tex> вида <tex>B \rightarrow \gamma</tex> включить в <tex>I_0</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, 0]</tex>.
'''После того, как построены <tex>I_0, I_1, \ldots , I_{j-1}</tex>, строится <tex>I_j</tex>:'''
''Шаг 4.'' Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a_j \beta, i] \in I_{j-1}</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha a_j \cdot \beta, i]</tex>.
Выполнять шаги <tex>(5)</tex> и <tex>(6)</tex> до тех пор, пока в <tex>I_j</tex> можно включать новые ситуации.
''Шаг 5.'' Если <tex>[A \rightarrow \alpha \cdot, i] \in I_j</tex>, то для всех ситуаций <tex>[B \rightarrow \alpha \cdot A \beta, k] \in I_i</tex> включить <tex>[B \rightarrow \alpha A \cdot \beta, k]</tex> в <tex>I_j</tex>.
''Шаг 6.'' Если <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_j</tex>, то для всех правил <tex>B \rightarrow \gamma</tex> из <tex>P</tex> включить <tex>[B \rightarrow \cdot \gamma, j]</tex> в <tex>I_j</tex>.
==Время работы для однозначной грамматики==
{{Лемма
|about=1
