Page 41 - 4761

Для моделювання роботи цих двох груп розпізнавачі використовуються двома
алгоритмами: алгоритм з підбором альтернатив – для низхідних розпізнавачів; алгоритм
“зсув-згортка” – для висхідних розпізнавачів.
Висхідний синтаксичний аналіз, як правило, більш прийнятний ніж низхідний, бо
для мови програмування легше побудувати правосторонній розпізнавач. А клас мов,
заданих висхідним розпізнавачем, ширше, ніж клас мов, заданих низхідним
розпізнавачем. З іншого боку низхідний синтаксичний аналіз має перевагу з точки зору
процесу трансляції, оскільки на його основі легше організувати процес породження
ланцюгів результуючої мови.
Помилка в процесі виконання алгоритму виникає, коли неможливо виконати
черговий крок, наприклад. якщо не встановлено відношення передування між
порівнюваними символами (К2 і К4), або якщо не вдається знайти потрібне правило в
граматиці (К4). Тоді виконання алгоритму припиняється.

3.6 Граматики передування

Принцип організації розпізнавача вхідних алгоритмів мови, заданої граматикою
передування, базується на тому, що для кожної впорядкованої пари символів в граматиці
встановлюється деяке відношення, яке називається відношення передування.
В процесі розбору вхідного ланцюга порівнюється поточний символ вхідного
ланцюга з одним із символів, який знаходиться в вершині стеку. В процесі порівняння
перевіряється, яке з можливих відношень передування існує між цими 2 символами. В
залежності від знайденого відношення або зсув (переніс), або згортка. При відсутності
відношення передування між символами алгоритм сигналізує про помилку.
Задача заключається в тому, щоб мати можливість виділити відношення
передування між символами граматики. Якщо це можливо, то граматика може бути
віднесена до одного з класів граматики передування.
Існує декілька видів граматики передування. Вони розрізняються по тому, які
відношення передування в них визначені і між типами яких символів (термінальний чи
нетермінальний) можуть бути встановлені ці відношення:
Види граматик передування:
1. Простого передування.
2. Розширеного передування.
3. Слабкого передування.
4. Змішаної стратегії передування.
5. Операторного передування.
Розглянемо 2 найбільш простих і поширених типи – граматики простого і
операторного передування.

3.7 Граматика простого передування (ГПП)

ГПП – називають таку приведену (без циклів, безплідних і недосяжних символів і λ
правил) КВ-граматику G (VN, VT, P, S) , V = VT U VN, в якій:
1. Для кожної впорядкованої пари термінальних і нетермінальних символів
виконується не більше ніж одне з трьох відношень передування:
– B i =  B j ( B i, B j,  V), якщо і тільки якщо  правило А x B i B j y  P, де A
 V N, x,y  V*;
– B i < B j , якщо і тільки якщо  правило А x B i By  P, і вивід
* *
D S j z, де A, D  VN, x, y, z V ;
– B i  > B j , якщо і тільки якщо  правило А xCB j y  P, і вивід
* *
C z B i або  правило А xCDy  P, і виводи C z B ii
*
*
D B jw , де A, C, D  VN, x, y, z, wV .
39