Відкрити головне меню

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

Зміст

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

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

Нехай вхідна граматика задається четвіркою 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]

ПосиланняРедагувати