Алгоритм спадного розбору. Спадні розпізнавача

1. Завдання розбору
Розбір сентенціальной форми означає побудову виводу і, можливо
синтаксичного дерева для неї. Програму розбору називають також рас-
пізнавальний, так як вона розпізнає тільки пропозиції розглядає-
мій граматики. Саме це і є нашим завданням в даний момент.
Всі алгоритми розбору, які бутут тут описані називаються алгоритми-
тмамі зліва направо з огляду на те, що вони обробляють спочатку самі ле-
ші символи оброблюваної ланцюжка і просуваються по ланцюжку тільки
тоді, коли це необхідно. Можна подібним способом визначити розбір
справа наліво, але він менш природний. Інструкції в програмі виконуємо-
ются зліва направо, та й ми читаємо зліва направо.
Розрізняють дві категорії алгоритмів розбору: спадний (зверху вниз)
і висхідний (знизу вгору). Їх називають також розгорткою і пакунків.
(В даному рефераті буде розглянуто процес тільки спадного раз-
бору. ) Соотетственно, ці терміни відповідають і способу побудови
синтаксичного дерева. При низхідному розборі дерево будується від кореня
(Початкового символу) вниз до кінцевим вузлам. Метод висхідного розбору
полягає в тому, що відправляючись від заданої ланцюжка, намагаються привести її
до початкового символу. Як приклад спадного розбору розглянемо
пропозиція (1) в такій граматиці цілих чисел (послідовностей,
що складаються з однієї і більше цифр):
N:: = D | ND
D:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (1)
На першому кроці безпосередній висновок N => ND буде будуватися так,
як показано в першому дереві на рис. 1. На кожному наступному кроці
найлівіший нетермінал V поточної сентенціальной форми xVy замінюється
на праву частину правила u V:: = u, в результаті чого виходить сле-
дме сентенціальная форма. Цей процес для пропозиції (1) представлення
ний на рис. 1. у вигляді п'яти дерев. Фокус у тому, звичайно, що
треба отримати ту сентенціальную форму, яка сопадает із заданою
ланцюжком.
N N N N N
| | | |
*-------* *-------* *-------* *-------* | | | | | | | |
N D N D N D N D
| | | |
D D D 5
| |
3 3
N => N D => D D => 3 D => 3 5
Рис. 1. Спадний розбір і побудову
виведення
2. Спадні розбір з поверненнями
Алгоритм спадного розбору будує синтаксичне дерево, як уже
було сказано, починаючи з кореня, поступово опускаючись до рівня запропонованого-
вання, як було показано раніше. Опис ускладнюється головним чином
через необхідність допоміжних операцій, які необхідні гла-
вним чином для того, щоб виконувати повернення з твердою впевненістю,
що всі можливі спроби побудови дерева були зроблені.
Щоб звести до мінімуму осложнеія, давайте опишемо цей алгоритм раз-
бору образно. Уявімо, що на будь-якому етапі розгляду, в кожному вузлі вже
побудованої частини дерева знаходиться по одній людині. Люди, які
знаходяться в термінальних вузлах, займають місця відповідно символів
пропозиції.
Якомусь людині належить провести розбір пропозиції x. Перш за все-
го йому необхідно відшукати висновок Z => + x, де Z - початковий символ; сле-
послідовно першим безпосереднім висновком має бути висновок
Z => y де Z:: = y - правило. Нехай для Z існують правила
Z:: = X X .. X | Y Y .. Y | Z Z .. Z
1 2 n 1 2 m 1 2 1
Спочатку людина намагається визначити правило Z:: = XX .. X. Якщо
1 2 n
не можна побудувати дерево, використовуючи це правило, він робить спробу примі-
нитка друге правило Z:: = YY ... Y. У разі невдачі він переходить до
1 2 m
наступного правилом і т.д.
Як йому визначити, чи правильно він вибрав безпосередній висновок
Z => X X .. X? Зауважимо, що якщо висновок є правильним, то для деяких
1 2 n
ланцюжків x матиме місце x = xx .. x, де X => * x для i = 1 ,..., n.
i 1 2 n i i
Перш за все людина, яка виконує розбір, візьме собі прийомного сина
M, що повинен буде знайти висновок X => * x для будь-якого x, такого,
1 1 1 1
що x = x ... Якщо синові M вдасться знайти такий висновок, він (і будь-який з
1 1
синів, онуків і т.д.) закриває ланцюжок x в пропозиції x і спільно-
1
ет своєму батькові про успіх. Тоді його батько усиновить M, щоб той знайшов
2
висновок X => * x, де x = x x ... і чекає відповіді від нього і т.д. Як тільки-
2 2 1 2
до повідомив про успіх син M, він усиновить ще і M, щоб той знайшов
i-1 i
висновок X => * x. Повідомлення про успіх, який прийшов від сина M, означає
i i n
що розбір пропозиції закінчений.
Як бути, якщо синові M не вдається знайти висновок X => * x? У цьому
i i i
M випадку повідомляє про невдачу свого батька, той від нього відрікається і
i
дає старшому братові M, M таке розпорядження: "Ти вже знайшов висновок,
i i-1
але цей висновок є невірним. Знайди-но мені інший ". Якщо M зуміє знайти
i-1
інший висновок, він знов повідомить про успіх, і все продовжиться по-пре-
жнемо. Якщо ж M повідомить про невдачу, батько зречеться і від нього, і
i-1
тоді вже старшого брата M, попросять зробити ще одну попит-
i-2
ку. Якщо доведеться зректися навіть від M, значить, безпосередній ви-
1
вод Z => X X .. X був невірний, і людина, що починав розбір, попи-
1 2 n
шається скористатися іншим висновком Z => Y .. Y.
1 m
Як же діє кожен з M? Покладемо, його метою є тер-
1
міна X. Вхідна ланцюжок має вигляд x = xx .. x T.. , де символи в
1 2 i-1
x, x ,..., x вже закриті іншими людьми. M перевіряє, чи співпадає
1 2 i-1 i
Чи черговий незакритий символ T з його метою X. Якщо це так, він
i
закриває цей символ і повідомляє про успіх. Якщо ні, повідомляє про
невдачі.
Якщо мета M - нетермінал X, M поступає точно так само, як
1 1
і його батько. Він починає перевіряти праві частини правил, що відносяться до
нетерміналу, і, якщо необхідно, теж усиновляє або зрікається
синів. Еслівсе його сини повідомляють про успіх то M в свою чергу
i
повідомляє про успіх батька. Якщо батько просить M знайти інший висновок, а це-
i
наливаю є нетермінальний символ, то M повідомляє про невдачу, так як
i
іншого такого висновку не існує. В іншому випадку M просить свого
i
молодшого сина знайти інший висновок і реагує на його відповідь також, як і
раніше. Якщо всі сини повідомлять про невдачу, він повідомить про невдачу своє-
му батькові.
Тепер, напевно, зрозуміло, чому цей метод називається прогнозую-
ющім або цілеспрямованим. Використовується і назва "спадний" через
способу побудови синтаксичного дерева. При розборі відправляються від
початкового символу й сходили до пропозиції (див. рис. 2)
Z
|
*---*-------* | | |
F | T
| | |
T |
| |
F |
| |
i + i * i
Рис. 2. Частковий спадний розбір пропозиції i + i * i.
Привабливість цього методу (і його представлення) в тому і сос-
тоит, що кожна людина повинна пам'ятати лише про свою мету, про своє від-
це, про своїх синів, а також про своє місце в граматиці і вихідний це-
нирці. І нікому не потрібні точні відомості про те, що відбувається в інших
місцях. Це якраз і є те, до чого ми взагалі прагнемо в программир-
вання: у кожному сегменті програми або в підпрограмі необхідно забо-
тіться про власну вхідний і вихідний інформації і ні про що більше.
Для імітації усиновлення та зречення синів у програмах вико-
ють стек типу LIFO (останній увійшов - перший вийшов), або, як його іноді
називають, "магазин".
Опишемо алгоритм у більш явному вигляді:
Покладемо, по-перше, що граматика задана списком в одновимірному мас-
сиве GRAMMAR таким чином, що кожне безліч правил
U:: = x | y |...| z
представлено, як Ux | y |...| z | $. Тобто кожен символ займає одну
клітинку, за кожною правою частиною слід вертикальна риска "|", а за
останнім символом слід "|$". Таким чином, граматика
Z:: = E #
E:: = T + E | T
T:: = F * T | F
F:: = (E) | i
буде виглядати як
ZE # | $ ET + E | T | $ TF * T | F | $ F (E) | i | $
Кожен елемент стека відповідає людині і складається з п'яти
компонент
(GOAL, i, FAT, SON, BRO)
які означають наступне:
1. GOAL - мета, тобто символ, що людина шукає. Таким обра-
зом, в незакритій в даний момент частини пропозиції йому належить
знайти таку голову, що приводиться до GOAL, і закрити її. GOAL
передається йому батьком.
2. i - індекс у масиві GRAMMAR, який вказує на той символ в
правій частині для GOAL, з яким людина працює в даний момент.
3. FAT - ім'я батька (номер елемента стека, відповідного від-
цу).
4. SON - ім'я самого останнього (молодшого) з синів.
5. BRO - ім'я його старшого брата.
Нуль в будь-якому з полів означає, що ця величина відсутній.
У програмі значення змінної v дорівнює кількості що беруть участь в
розборі людей (кількості елементів в стеку в поточний момент), c -
ім'я (номер елемента в стеку) людини, що працює в даний момент.
Інші очікують кінця його роботи. Індекс j относітстя до самого ле-
вому (незакритими) символу вхідний ланцюжка INPUT (1 ),..., INPUT (n).
а) Z б) СТЕК МЕТА i FAT SON BRO
|
*---------*------* 1 Z 4 0 15 0
| | 2 E 10 1 7 0
E # 3 T 20 2 4 0
| 4 F 28 3 5 0
*--*------* 5 i 0 4 0 0
| | | 6 + 0 2 0 3
T | E 7 E 12 2 8 6
| + | 8 T 18 7 12 0
F T 9 F 28 8 10 0
| | 10 i 0 9 0 0
i *---*---* 11 * 0 8 0 9
| | | 12 T 20 8 13 11
F * T 13 F 28 12 14 0
| | 14 i 0 13 0 0
i F 15 # 0 1 0 2
|
i
Рис 3. Стек після спадного розбору i + i * i
а) - синтаксичне дерево б) - стек після розбору
Поле SON використовується для зберігання посилання на останнього (молодше-
го) сина. Тоді поле BRO елемента, що відповідає цьому синові, вкаже
на старшого брата. Для ілюстрації розглянемо зображене на
рис .3 а) синтаксичне дерево для пропозиції i + i * i вищеописаної
граматики. Стан стека після закінчення роботи показано на рис.3 б).
Тепер у людини 2 (S (2)) є мета E; передбачається, що він в соотв-
тствіі з синтаксичним деревом використовує правило E:: = T + E. Таким
чином, йому для того, щоб знайти символи T, +, E буде потрібно три сини.
Значення поля S (2). SON = 7, так що молодшим сином є людина, c
номером 7, мета якого E. Назва середнього сина - число 6, визначається
значенням поля S (7). BRO; - мета цього сина - знак "+". Ім'я старшого
сина знаходиться в полі BRO людини 6 і дорівнює 3.
Очевидно, що у нас є список синів кожної людини і
елементи цього списку пов'язані в стеку між собою. Тобто стек в його
остаточному вигляді являє собою внутрішню форму синтаксичного
дерева.
Розглянемо тепер сам алгоритм спадного розбору. Для зручності
читання розділимо його на шість названих частин.
1. ПОЧАТКОВА УСТАНОВКА
S (1): = (Z, 0,0,0,0); c: = 1; v: = 1; j: = 1; перехід на НОВА ЛЮДИНА
(перший усиновлення. Мета усиновлення - початковий символ Z.)
2. НОВА ЛЮДИНА
IF GOAL термінал THEN Нова людина вивчає свою мету.
IF INPUT (j) = GOAL THEN Мета - термінал.
BEGIN j: = j +1; Якщо GOAL збігається з символом з
GO TO УСПІХ; пропозиції, людина закриває цей
ELSE GO TO НЕВДАЧА символ і повідомляє про успіх.
i: = індекс у GRAMMAR правою Невідповідність - повідомляє про невдачу.
частини для GOAL; Мета нової людини - нетермінал.
GO TO ЦИКЛ Підготовка до перегляду правих частин
в правилах для GOAL
3. ЦИКЛ
IF GRAMMAR (i )="|" Перегляд правій частині
THEN IF FAT =/= 0 Досягли кінця правій частині, тому
THEN GO TO УСПІХ повідомляємо про успіх. Якщо ні батька,
ELSE STOP - пропозиція; то зупинка - закінчено розбір
пропозиції
IF GRAMMAR (i )="$" Немає більше правих частин, які
THEN IF FAT =/= 0 можна було б спробувати, тому
THEN GO TO НЕВДАЧА повідомлення про невдачу або, якщо немає батька
ELSE STOP - не зупинка, не розпізнавши пропозиції
пропозиція;
v: = v +1; GRAMMAR (i) - інша мета, яку
S (v): = (GRAMMAR (i), 0, c, 0, можна спробувати знайти. Беремо сина.
SON); Тоді старший брат - той, хто був до
цього молодшим сином
Переключити увагу на молодшого сина
SON: = v; c: = v; і чекати від нього відповіді
GO TO НОВА ЛЮДИНА
4. УСПІХ
c: = FAT; Повідомити про успіх свого батька. Він
i: = i +1; GO TO ЦИКЛ зробить наступний крок.
5. НЕВДАЧА
c: = FAT; Повідомити про невдачу своєму батькові. Він
v: = v-1; відступить від сина і попросить його
SON: = S (SON). BRO; старшого брата зробити ще одну
GO TO ЩЕ РАЗ спробу.
6. ЩЕ РАЗ
IF SON = 0 THEN Чи є ще син, який може перед-
BEGIN WHILE GRAMMAR (i) прийняти ще одну спробу? Ні.
=/="|" Тоді пропускається права частина -
DO i: = i +1; Це не та, яка потрібна - перехід до
i: = i +1 GO TO ЦИКЛ наступною.
END;
i: = i-1; c: = SON; Є син. Його просять повторити спробу
IF GOAL нетермінал Його мета - нетермінал, так що він по-
THEN GO TO ЩЕ РАЗ намагається ще раз добитися успіху.
j = j-1 Його мета термінал. Спроба не призведе
GO TO НЕВДАЧА до успіху. Тому він відкриває свій
символ і повідомляє про невдачу.
Блок схема даного алгоритму наведена нижче.
*---------* | 1 |
*----*----* *---------------------------->| *------* | * *----->| |
| Ні/| | | |
| *-----------< 2> | | * |
| Ні/А/| | Д/|
| *----------< 4> | * | *-------< 9> |
| |/| | | | |/|
| | * | | | | | * |
| | | Так | | Так | | | | Ні |
| | * | | | | | *---*---* |
| | *---* Н/| | | | | | 10 | |
| | | 6 | - <5> | * | | | *---*---* |
| | *---*/|/| | | | |
| | * | *- <3> | | | * |
| | | Так | |/| | |/Да |
| *-* | | | * | | | -----* *- | 7 | | | | *-----* | |/
*-* | | | Ні | | *
| *--|-------------* | | Ні
| | А | *---*---* |
*---*---* | *-------* | 8 |-------* *-------* Рис 4. Блок-схема алорітма спадного розбору
1. S (1): = (Z, 0,0,0,0); c: = 1; v: = 1;
2. GOAL - термінал?
3. j: = j +1; INPUT (j) = GOAL?
4. GRAMMAR (i) = "Кінець"?
5. FAT =/= 0?
6. STOP - Кінець роботи;
7. v: = v +1; S (v): = (GRAMMAR (i), 0, c, 0, SON);
SON: = v; c: = v;
8. c: = FAT; i: = i +1;
9. SON = 0?
10. Поки GRAMMAR (i) =/= "Кінець":
i: = i +1,
j: = j +1;
i: = i -1;
c: = SON;
11. GOAL - нетермінал?
12. C: = FAT; v: = v-1; SON: = S (SON) * BRO.
3. Проблеми спадного розбору
Пряма лівостороння рекурсія
У алгоріме, описаному раніше, є один серйозний недолік,
який виявляється, коли мета визначена з використанням левосто-
ронней рекурсії. Якщо X - наша мета, а першого ж правило має вигляд
X:: = X ..., то ми негайно усиновляє того, хто буде шукати
X. Він у свою чергу негайно заведе собі сина, щоб той шукав
X. Таким чином, кожен буде звалювати відповідальність на свого си-
ну, і для вирішення завдання не вистачить населення Китаю.
З цієї причини правила граматики написані із застосуванням право-
сторонньої рекурсії замість більш звичної лівосторонньої. Кращий спосіб
позбавитися від прямої лівосторонньої рекурсії - записувати правила, ис-
користуючись ітеративні і факультативні позначення. Запишемо правила
(3.1) E:: = E + T | T як E:: = T (+ T)
і
T:: = T * F | T/F | F як T:: = F (* F |/F)
Зараз будуть сформульовані два основні принципи, на підставі
яких правила мови, що включають пряму лівосторонній рекурсію, пре-
оьразуются в еквівалентні правила, що використовують ітерацію.
(3.2) Факторизація. Якщо існують правила виду
U:: = xy | xw | ... | xz, то їх треба замінити на
U:: = x (y | w |...| z), де дужки є метасимволів
Допустима факторизація в більш загальній формі, така як у аріфметіче-
ських виразах. Наприклад, якщо в (3.2) y = yy і w = yw, ми могли б за-
1 2 1 2
нити U:: = x (y | w |...| z) на
U:: = x (y (y | w )|...| z).
1 2 2
Зауважимо, що вихідні правила U:: = x | xy ми перетворимо до виду
U:: = x (y | Л), де Л - порожній ланцюжок. Коли б не використовували по-
добное перетворення, Л завжди поміщається як остання альтернатив-
ва, тому що ми приймаємо умову, що якщо мета - Л, то ця мета все-
гда зіставляється.
Крім того що факторизація дозволяє нам виключити пряму річку-
рсію, використання цього прийому скорочує розміри граматики і позво-
ляєт проводити розбір більш ефективно. В цьому ми переконаємося пізніше.
Після факторизації (3.2) у граматиці залишиться не більше однієї пра-
вої частини з прямою лівосторонньої рекурсією для каждогоіз нетерміналов.
Якщо така права частина є, ми робимо наступне:
(3.3) Нехай U:: = x | y |...| z | Uv - правила, у яких залишилася леворе-
курсивний права частина. Ці правила означають, що членом син-
таксіческого класу U є x, y або z, за якими або ні-
чого не слід, або слід тільки v. Тоді перетворимо ці
правила до виду U:: = (x | y | ... | z) (v).
Ми використовували (3.3) щоб зробити перетворення в (3.1),
що дозволяє позбутися від непотрібних дужок що полягають у T. У качес-
тверд іншого прикладу перетворимо A:: = BC | BCD | Axz | Axy
а) Z б) Z
| |
*----*-* *-*-*-*-*-*-* | | | | | | | | | |
E + T T + T + T + T
|
*--*-* | | |
E + T
|
*-*-* | | |
E + T
|
T
Рис 5. Дерева, що використовують рекурсію і ітерацію
Застосувавши правило (3.2) отримаємо A:: = BC (D | Л) | Ax (z | y); Застосувавши
(3.3), отримаємо A:: = BC (D | Л) (x (z | y)). Можна позбутися від однієї па-
ри дужок, після чого отримаємо A:: = BC (D | Л) (x (z | y)).
Після таких змін ми, звичайно, повинні змінити і наш алгоритм
спадного розбору. Тепер алгоритм повинен вміти обробляти альтер-
Натів не тільки в одній правій частині, а й у її подцепочках, повинен
враховувати в своїй роботі існування порожній ланцюжка Л, повинен уміти
обробляти ітерацію.
Використання ітерації замість рекурсії частково змінює і структуру
дерев. Таким чином, рис 3.а мав би бути схожим на рис. 3.б. Але
ці два дерева слід розглядати як еквівалентні; оператори "плюс"
повинні замінюватися зліва направо.
Загальна лівостороння рекурсія
Ми не вирішили всієї проблеми лівосторонньої рекурсії: з прямою ліво-
сторонньої рекурсією покінчено, але загальна лівостороння рекурсія ще ос-
талась. Таким чином, правила
U:: = Vx і V:: = Uy | v
дають висновок U => + Uyx. Позбутися від цього не так просто, але виявити
ситуацію можна. Виключимо з вихідної граматики всі правила з прямою
лівосторонньої рекурсією. Символ U, що отримали в результаті цих пре-
утворень граматики, може бути леворекурсівним тоді і тільки тоді
коли U FIRST + U. Як перевірити це відношення, нам вже відомо.
Подання граматики в оперативній пам'яті
Однією з проблем, що виникають при реалізації тих, які сходять методів,
є представлення граматики в обчислювальній машині. Одне з
можливих уявлень вже використовувалося раніше. Очевидно, що воно
невдало через обсягу роботи необхідної для пошуку правил, відпо-
чих кожному нетерміналу. Мова піде про інше поданні. Перш
ніж почати виклад, варто згадати про те що написати конструктор,
який сприймає граматику, проводить будь-які з перетворень, про
яких тільки що говорилося, перевіряє чи не є правила рекур-
пасивного, і складає таблиці для граматики в одній з описуваних да-
леї форм досить легко.
Для подання граматики використовується облікова структура, на-
зване синтаксичним графом. Кожен вузол представляє символ S з
правій частині і складається з чотирьох компонентів: ІМ'Я, ВИЗНАЧЕННЯ (ОДР),
АЛЬТЕРНАТИВА (АЛТ) і наступника (ПРЕМ), де
1. Ім `я - це сам символ S в деякій внутрішню форму.
2. ВИЗНАЧЕННЯ дорівнює 0, якщо S - термінал; в іншому випадку ця
компонента вказує на вузол відповідний першого символу в
першо правій частині для S.
3. АЛЬТЕРНАТИВА вказує на перший символ тієї альтернативи пра-
вої частини яка слідує за правою частиною, що містить даний
вузол (0, якщо такий правій частині немає). Це тільки символи
в правих частинах.
4. Наступник вказує на наступний символ правій частині (0, якщо
такого символу немає).
Крім того, кожен нетермінальний символ представлений вузлом, відбутися у-
ящім з однієї компоненти, що вказує а перший символ в першу
правій частині, що відноситься до цього символу. Прикладом може служити
рис. 4, на якому зображено розташування компонент вузла синтаксичної-
го графа граматики:
*---------------------------* | ІМ'Я |
*--------*---------*--------* | ОПР | АЛТ | ПРЕМ |
*--------*---------*--------* Рис 6. Розташування компонент вузла синтаксичного
графа граматики
Детально про синтаксичних графах див у книзі Д. Гріса "Конструі-
вання компіляторів для цифрових обчислювальних машин "
Розбір без повернень
Програма розбору в компіляторі ні в якому разі не повинна прибути-
гать до повернень. Ми повинні мати впевненість у тому, що кожна перед-
покладаємося мета вірна. Це нреобходімо тому, чтонам належить зв'язати
семантику з синтаксисом, і в міру того, як ми будемо прогнозувати і
знаходити цілі, ці символи будуть оброблятися семантично. Ось неко-
торие приклади "обробки": 1) при обробці описів змінних Ідент-
фікатори поміщаються в таблицю символів; 2) при обробці арифметичних
виразів перевіряють, чи сумісні типи операндів.
Якщо повернення стався через те, що прогнозована мета невірна,
доведеться знищити результати семантичної обробки, зробленого під
час пошуків цієї мети. Зробити це не так-то просто, тому постараюсь
емся провести граматичний розбір без повернень.
Для того, щоб позбутися від повернень, в компіляторах як
контексту звичайно використовується наступний "незакритий" символ вихідної про-
грами. Тоді на граматику накладається таку вимогу: якщо є
альтернативи x | y |...| z, то безлічі символів, якими можуть починатися
виведені з x, y, .., z слова, повинні бути попарно різні. Тобто якщо
x => * Au і y => * Bv то A =/= B. якщо цю вимогу виконано, можна
досить просто визначити, яка з альтернатив x, y або z - наша мета.
Зауважимо, що факторизація надає тут велику допомогу. Якщо є пра-
вило U:: = xy | xz, ео перетворення цього правила до виду U:: = x (y | z)
допомагає зробити множесва перших символів для різних альтернатив непе-
ресекающіміся.
4. Висновок
У даному рефераті розглядалися спадні розпізнавача,
алгоритм спадного розбору і проблеми пов'язані з тих, що сходять
розбором. Одна з перших статей, що розглядають фіксований ал-
горітм спадного розбору, належить Айронс. Але його метод не
був тих, що сходять розбором в чистому вигляді, а був змішанням НІС-
тих, хто ходить і висхідних розборів. Алгоритм, наведений в даному рефе-
рапіе, вперше був запропонований в огляді Флойда. Він же ввів і поняття
"батько - син - брат". Способи позбавлення від повернень описані Унге-
ром.
5. Список літератури
1. Гриссом. Конструювання компіляторів для цифрових ви-
числівників машин. М., Мир, 1975р.
2. Ахо А., Ульман Дж. Теорія синтаксичного аналізу, пере-
вода та компіляції. М. Світ 1978р.
3. Ф. Льюїс, Д. Розенкранц, Р. Стірнз. Теоретичні основи
проектування компіляторів. М., Мир, 1979р.
4. Фельдман Дж., Гріс Д. Системи побудови трансляторів.
Сб Алгоритми і алгоритмічні мови, вып.5, ВЦ АН СРСР, 1971р.