Перегляд вихідного коду сторінки Алгоритм Ерлі

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

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

Нехай вхідна граматика задається четвіркою 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-> α∙β.<br />
Зрозуміло, що w буде належати L(G) т. і т.т., якщо [S->α∙,0] буде належати In.

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

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

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

=== Вихід алгоритму ===
Список розбору I0, I1,… In.<br />

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

== Посилання ==
* [https://github.com/lagodiuk/earley-parser-js JavaScript реалізація алгоритму з можливістю генерації лісу синтаксичних дерев (у випадку неоднозначної граматики)] {{Webarchive|url=https://web.archive.org/web/20180611152031/https://github.com/lagodiuk/earley-parser-js |date=11 червня 2018 }}

{{Compu-lang-stub}}
{{Comp-stub}}
{{refimprove|date=серпень 2017}}
{{Переписати|дата=грудень 2015}}
[[Категорія:Рядкові алгоритми]]
[[Категорія:Алгоритми синтаксичного розбору]]
[[Категорія:Динамічне програмування]]