НОУ ІНТУІТ, Лекція, Синтаксичні аналізатори
Умови використання методу рекурсивного спуску
Метод рекурсивного спуску без повернень можна використовувати лише для граматик, правила яких задовольняють такій умові: першого символу кожного правила має бути достатньо для того, щоб визначити, яке правило застосовується в даному випадку. Більш точно цю умову можна формалізувати шляхом визначення множини FIRST.
Визначення.Для КС-граматики G і ланцюжка w , що складається з термінальних і нетермінальних символів , визначимо безліч FIRST k (w) наступним чином:
Іншими словами, безліч FIRST k (w) складається з усіх термінальних префіксів довжини k термінальних ланцюжків, що виводяться з w .
Приклад.Розглянемо граматику, що породжує підмножину типів мови Pascal.
Для цієї граматики ми маємо:
Зрозуміло, що якщо ланцюжок w складається тільки з терміналів, то FIRST k (w) - це перші k символів ланцюжка w , якщо w & gt; =, або це сам ланцюжок w , якщо w
Алгоритм побудови безлічі FIRST
Насамперед, визначимо безліч FIRST для всіх символів граматики:
- якщо X - термінал, то FIRST(X) = X
- для правила додамо до безлічі FIRST (X)
- якщо X - нетермінал і - правило граматики, то додамо термінал а FIRST(X) , якщо для деякого i цей термінал a належить і належить всім множинам , , тобто * \ varepsilon ." style = "display: inline; "> Якщо належить всім , то додамо в FIRST(Y) .
Тепер сформулюємо сам алгоритм побудови множини FIRST (w).
Вхід.КС- граматика G = (N, T, P, S) і ланцюжок w термінальних і нетермінальних символів.
Метод.Додамо в FIRST (X 1 X 2 …X k) всі непустісимволи із FIRST (X1) . Потім, якщо належить FIRST (X1), то додамо всі непусті символи з FIRST (X2) і так далі. Нарешті, якщо всім j FIRST (Xj) містить порожній символ , ми додамо в безліч FIRST (X1 X2…Xk) .
Приклад.Розглянемо граматику з правилами:
Для цієї граматики множини FIRST визначаються таким чином: