Page 41 - 4761
P. 41

Для  моделювання  роботи  цих  двох  груп  розпізнавачі  використовуються  двома
                  алгоритмами: алгоритм з підбором альтернатив – для низхідних розпізнавачів; алгоритм
                  “зсув-згортка” – для висхідних розпізнавачів.
                         Висхідний синтаксичний аналіз, як правило, більш прийнятний ніж низхідний, бо
                  для  мови  програмування  легше  побудувати  правосторонній  розпізнавач.  А  клас  мов,
                  заданих  висхідним  розпізнавачем,  ширше,  ніж  клас  мов,  заданих  низхідним
                  розпізнавачем. З іншого боку низхідний синтаксичний аналіз має перевагу з точки зору
                  процесу  трансляції,  оскільки  на  його  основі  легше  організувати  процес  породження
                  ланцюгів результуючої мови.
                         Помилка  в  процесі  виконання  алгоритму  виникає,  коли  неможливо  виконати
                  черговий  крок,  наприклад.  якщо  не  встановлено  відношення  передування  між
                  порівнюваними  символами  (К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
   36   37   38   39   40   41   42   43   44   45   46