Алгоритм Ерлі

Алгоритм Ерлі — алгоритм синтаксичного аналізу, призначений для перевірки коректності вхідного рядка.

Основні поняття алгоритму

Алгоритм Ерлі за вхідним ланцюжком та граматикою породжує список розобру для даного вхідного ланцюжка в заданій граматиці.

Нехай вхідна граматика задається четвіркою G = (T,N, S, P).

Вхідний ланцюжок задається послідовністю терміналів w=a1,a2,…,an

Списком розбору будемо називати послідовність списків ситуацій I0, I1,… In.

Ситуацією будемо називати конструкцію вигляду [A-> X1,..,Xk∙Xk+1,…,Xm, i] (де k,i — довільні натуральні числа від 0 до m, а ∙ — метасимвол, який не належить ні N ні T), якщо A-> X1,.., Xm — правило з P.

Список ситуацій Ij для слова w будемо будувати таким чином:

[A->α∙β, i] (i≤j) належить Ij тоді і тільки тоді, якщо існують такі γ та δ, що S=>* γAδ, γ=>*a1…ai та α=>*ai+1…aj. Тобто певна частина слова w [1..j] може бути виведена використовуючи A-> α∙β.
Зрозуміло, що w буде належати L(G) т. і т.т., якщо [S->α∙,0] буде належати In.

Одержаний список розбору може слугувати базою для багатьох алгоритмів, зокрема побудови правого розбору ланцюжка.

Вхід алгоритму

1)Граматика G = (T,N, S, P)
2)Вхідний ланцюжок w=a1,a2,…,an

Вихід алгоритму

Список розбору I0, I1,… In.

Алгоритм

Спочатку ініціюємо список I0.
1. Для всіх правил S → α, включити [S → ∙α, 0] в І0.
Поки в I0 можна включати, виконуємо кроки 2-3
2. Якщо [B → γ∙, 0] належить I0, то включити в І0 всі ситуації вигляду [A → αB∙β, 0] (якщо вони ще не там) для всіх [A → α∙Bβ, 0], що вже належать I0.
3. Якщо A → [α∙Bβ, 0] належить I0, то включити в I0 ситуації вигляду [B → ∙γ, 0](якщо вона ще не там) для всіх правил вигляду B → γ.
Нехай ми маємо побудовані списки I0, I1,… Ij-1.
4. Для кожної ситуації [B → α∙ajβ, i] з Ij-1 включити до Ij ситуацію [B → αaj∙B, i] Поки в Ij можна включати, виконуємо кроки 5-6.
5. Нехай [A → α∙, i] належить до Ij. Шукати в Ii ситуації вигляду [B → α∙Aβ, k]. Для кожної з них включити до Ij ситуацію [B → αA∙β, k].
6. Нехай [A → α∙Bβ, i] належить Ij. Для кожного правила B → γ включити до Ij ситуацію [B → ∙γ, j]

Посилання

• JavaScript реалізація алгоритму з можливістю генерації лісу синтаксичних дерев (у випадку неоднозначної граматики) [ 11 червня 2018 у Wayback Machine.]