68840

Детермінований синтаксичний аналіз (s- та q-граматики)

Лекция

Информатика, кибернетика и программирование

КВграматика називається sграматикою тоді і тільки тоді коли 1 права частина кожного правила починається терміналом; 2 якщо два правила мають співпадаючі ліві частини такі правила називаються альтернативними то праві частини цих правил починаються різними символами. Тепер означимо множину вибору для кожного правила.

Украинкский

2014-09-26

154 KB

1 чел.

Лекція 10

Детермінований синтаксичний аналіз (s- та q-граматики)

Означення 10.1. МП-автомат  R = (Q, , Γ, , q0, Z0) називається  детермінованим  автоматом  (скорочено   ДМП-автоматом),  якщо для кожних  q  Q  і  Z  Γ  виконується 

1) (q, a, Z) містить не більше одного елемента для кожного

а        і   (q, , Z) = ,

або 

2)  (q, a, Z) =  для усіх  а  ,   і  (q, , Z) містить не більше  одного елементу.

Внаслідок  цих   двох   обмежень    ДМП-автомат   у   будь-якій  конфігурації може вибрати не більше одного такту.

Означення   10.2.   Мова,   що   представляється     ДМП-автоматом,  називається детермінованою.

У  теорії  автоматів  [1]  доведено,  що   існують   недетерміновані  МП-автомати, що представляють КВ-мову, які не еквівалентні ніякому  детермінованому.  Тому  деякі   КВ-мови   не   можливо  аналізувати детерміновано. Мова, що допускає детермінований аналіз, називається   детермінованою.   Виявляється,   що   більшість    мов  програмування є детермінованими, або майже такими.

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

Означення 10.3. КВ-граматика називається  s-граматикою  тоді  і тільки тоді, коли  

1) права частина кожного правила починається терміналом;

2) якщо  два  правила  мають  співпадаючі  ліві  частини  (такі  правила називаються альтернативними),  то  праві  частини  цих правил починаються різними символами.

Ці  граматики  називають  також   розділеними   або   простими.  Зрозуміло, що  s-граматики генерують детерміновані мови. Далі будемо  поширювати клас граматик, що генерують детерміновані мови. Для цього  розглянемо декілька додаткових понять.

Для  поданої   КВ-граматики з нетерміналом  Х  означимо                                функцію  НАСТ(Х),  що визначає множину терміналів, які можуть стояти безпосередньо після   Х   у сентенціальній формі. Одночасно  НАСТ(Х)  можна розглядати як  множину  вхідних  символів,  які  можуть  прямувати  за  рядком,  що  породжується нетерміналом  Х, у деякому допустимому рядку.

Тепер означимо множину вибору для кожного правила. Якщо правило  граматики має вигляд  А  b  , де  b - термінал, - рядок символів, то означимо

ВИБІР(А  b) = {b}.

У випадку, коли правило має вигляд   А  , то 

ВИБІР(А  ) = НАСТ(A).

Користуються також записом  ВИБІР(р)  замість   ВИБІР(А  ),  коли  р - номер  правила  А  .  Множина  вибору  деякого  правила  містить усі  вхідні  символи,  при  знаходженні  яких  під  головкою  читання, МП-автомат повинен застосовувати це правило.

Означення 10.4. КВ-граматика називається  q-граматикою  тоді  і  тільки тоді, коли виконуються такі дві умови:

1) права частина кожного правила або починається  з  терміналу,  або  ;

2) множини вибору альтернативних правил  (з однаковими  лівими  частинами)  не перетинаються.

Як бачимо,  q-граматика  є  узагальненням   s-граматики.  Кожна  s-граматика є одночасно і  q-граматикою.

LL(1)-граматики

Для   подальшого   поширення   класу    граматик, що генерують  детерміновані мови, узагальнимо поняття множини вибору.

Для поданих  КВ-граматики  G  і послідовності символів    словника  G  означимо  ПЕРШ() як множину перших терміналів у рядках символів, що  виводяться з .

Будемо вважати, що ПЕРШ(А  ) = ПЕРШ().

Про рядок     будемо говорити, що він анулює, якщо   * .   

Будемо також вважати, що правило граматики  А    анулює, коли    анулює.  

Для поданого правила  А    узагальнене поняття  множини  вибору  означається таким чином  

                           ПЕРШ(), якщо  - не анулює;

    ВИБІР(А  ) =  

                                   ПЕРШ()     НАСТ(A), якщо   - анулює

Означення 10.5. КВ-граматика називається  LL(1)-граматикою тоді  і тільки тоді,  коли  множини  вибору  альтернативних правил не перетинаються.  

Очевидно,  що  клас   LL(1)-граматик  містить  у   собі   усі  q-граматики.

Для   будь-якої   LL(1)-граматики   завжди   можна   побудувати  еквівалентний  ДМП-автомат,  оскільки  для  кожної  конфігурації  за  допомогою множин вибору однозначно визначається  правило  граматики,  що треба застосувати. Назва   LL(1)   пояснюється  тим,  що  автомат  проглядає вхідний рядок, починаючи зліва (left), і знаходить правило для застосування за допомогою найлівішого (leftmost) символу  рядка,  що  виводиться  з  цього  правила.  Одночасно  перетворення   вмісту магазину відбувається згідно з переходом від лівої  частини  правила до правої, тобто правила використовуються зліва направо.

Для   того,   щоб   переконатись,   що   подана   граматика   є  LL(1)-граматикою  та  побудувати  відповідний   ДМП-автомат,   треба знайти множини вибору для кожного правила.

Визначення множин вибору продукцій

Процедура розв’язання цієї задачі складається з таких кроків.

1. Знайти нетермінали і правила, що анулюють. 

2. Побудувати відношення  ПОЧИНАЄТЬСЯ_ПРЯМО_З.

3. Обчислити відношення  ПОЧИНАЄТЬСЯ_З.

4. Обчислити множину  ПЕРШ  для кожного нетерміналу.

5. Обчислити множину  ПЕРШ  для кожного правила.

6. Побудувати відношення  ПРЯМО_ПЕРЕД.

7. Обчислити відношення  ПРЯМО_НА_КІНЦІ.

8. Обчислити відношення  НА_КІНЦІ.

9. Обчислити відношення  ПЕРЕД.

10. Розширити відношення  ПЕРЕД.

11. Обчислити множину  НАСТ  для кожного нетерміналу, що анулює.

12. Обчислити множини вибору.

Розглянемо кожний крок.

Крок 1. З сукупності правил поданої граматики викреслюються усі правила,  праві  частини  яких  містять  термінал.   Нетермінал,  що знаходиться у лівих частинах тільки  викреслених  правил,  називають зайвим. Потім з залишеної сукупності правил викреслюють усі правила,  права частина яких містить  зайві  нетермінали,  і  так  далі,  доки вдається викреслити хоча б одне правило. Залишені правила  утворюють множину правил, що анулюють, а їх  ліві  частини  -  множину  не терміналів, що анулюють.

Виконання  першого  кроку  та  усіх  наступних  розглянемо   на прикладі граматики  G, що містить такі правила

1. S  XYZ                7. Q aa

                                             2. X PQ                  8. Q  

                                             3. Y RV                  9. V  сс

                                             4. R  TU                 10. T  dd

                                             5. P                       11. U ee

                                             6. P  с                     12. Z   

Спочатку викреслюються правила  6, 7,  9,  10,  11, і зайвими стають нетермінали  V, T, U. Потім викреслюються правила  4  і  3, і до множини зайвих нетерміналів додаються символи  R  та  Y.  Нарешті, викреслюється  правило   1,   і  у   множину   зайвих   нетерміналів включається символ  S. Подальше викреслювання правил неможливе, і тому множина правил, що анулюють, утворюється  правилами   2,  5,  8,  12,  а множина нетерміналів, що анулюють, складається з символів  X, P, Q, Z.

Можна показати, що розглянутий алгоритм для кожного нетерміналу визначає, він анулює, чи ні,  якщо  подана  граматика  є  чистою,  тобто кожний нетермінал у ній породжує рядок терміналів.

Крок 2. Якщо  А  та  В - символи поданої граматики, то

А  ПОЧИНАЄТЬСЯ_ПРЯМО_З  В

тоді і тільки тоді, коли граматика   G  містить правило  А  В, де    рядок   анулює (,  або  складається  тільки  з  не терміналів, що анулюють), - довільний рядок символів, можливо, і пустий.  

Матрицю відношення  А  ПОЧИНАЄТЬСЯ-ПРЯМО-З  В  для граматики  G  показано у табл.10.1.

 

                                                        Табл.10.1

S

X

Y

R

P

Q

V

T

U

Z

a

c

d

e

S

1

1

X

1

1

Y

1

R

1

P

1

Q

1

V

1

T

1

U

1

Z

a

c

d

e

Крок 3. Відношення

А  ПОЧИНАЄТЬСЯ_З  В

це рефлексивно-транзитивне замикання попереднього відношення.

Побудуємо матрицю  цього  відношення  для  граматики   G.  Граф відношення  А  ПОЧИНАЄТЬСЯ_ПРЯМО_З  В  показаний на рис.10.1, а граф його рефлексивно-транзитивного замикання - на рис.10.2.

Будемо казати, що вершина  v2  досягається з вершини  v1  через проміжну вершину  v3, якщо v3  суміжна з  v1, а  v2  - з  v3, тобто граф містить ребра  (v1,v3)  та  (v3,v2). У цьому випадку  з  v1  у  v2  існує шлях з однією проміжною вершиною v3. У разі, коли з  vi  у  vj  існує шлях з  k  проміжними вершинами v1, v2, …, vk,   кажуть, що  vj  досягається з  vi  через  k  проміжних вершин. Для того,  щоб побудувати матрицю суміжності транзитивного замикання  графа,  треба  у початковому графі, крім суміжності, врахувати існування  шляхів  з будь-якою кількістю проміжних вершин. Якщо у графі   n   вершин,  то максимальна  кількість  проміжних  вершин  у  простому  шляху   (без повторення вершин) - n-2.

Рис.10.1. Граф відношення  A    ПОЧИНАЄТЬСЯ_ПРЯМО_З   B.

Тривіальний алгоритм обчислення матриці транзитивного замикання відношення  з  матрицею   М     можна  подати  у  вигляді  процедури transit, що показано нижче.

procedure transit

                     begin

                      for i:=1 to n-2 do

                      for j:=1 to n do

                      for k:=1 to n do

                       if M[j,k]=1 then

                         for l:=1 to n do

                           if M[k,l]=1 then M[j,l]:=1

                     end;

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

Рис.10.2. Граф відношення  А  ПОЧИНАЄТЬСЯ-З  В.

Кількість операцій, що потребує цей алгоритм, пропорційна n4. Однак,  Уоршаллом  було  запропоновано  [2]   алгоритм   з   оцінкою обчислювальної складності  O(n3). Цей алгоритм утворюється з попереднього вилученням зовнішнього  циклу  і  зміною  порядку  двох наступних циклів, тобто організацією зовнішнього циклу за проміжними вершинами.

procedure transit1

                    begin

                      for k:=1 to n do

                      for j:=1 to n do

                        if M[j,k]=1 then

                          for l:=1 to n do

                            if M[k,l]=1 then M[j,l]:=1

                    end;

Перше виконання  внутрішнього  подвійного  циклу  враховує  усі шляхи з однією  внутрішньою  вершиною  v1,  друге  -  усі  шляхи  з внутрішніми вершинами, що належать до множини  {v1, v2}, і  так  далі. Останнє  n-е  виконання цього циклу враховує усі шляхи з внутрішніми вершинами з множини усіх вершин графу.

                                                      Табл.10.2

S

X

Y

R

P

Q

V

T

U

Z

a

c

d

e

S

1

1

1

1

1

1

1

1

1

1

X

1

1

1

1

1

Y

1

1

1

R

1

1

1

P

1

1

Q

1

1

V

1

1

T

1

1

U

1

1

Z

1

a

1

c

1

d

1

e

1

Існує  і  ще  швидший  алгоритм  [2],  що  належить  до   класу рекурсивних і має асимптотичну оцінку обчислювальної складності O(nlog27) ≈    n2.81.

Для  того,  щоб  побудувати  матрицю  рефлексивно-транзитивного замикання,  треба  матрицю  транзитивного  замикання   об’єднати   з одиничною.

Матрицю  відношення   А   ПОЧИНАЄТЬСЯ_З   В  для  граматики   G  показано у табл.10.2.

Крок 4.

ПЕРШ(А) = {b | А  ПОЧИНАЄТЬСЯ-З  b, де  b - термінал.

Для граматики  G  маємо

ПЕРШ(S) = {a, с, d},  ПЕРШ(X) = {a, c},  ПЕРШ(Y) = {d},

ПЕРШ(R) = {d},      ПЕРШ(P) = {c},    ПЕРШ(Q) = {a},

ПЕРШ(V) = {c},   ПЕРШ(T) = {d},   ПЕРШ(U) = {e},  ПЕРШ(Z) =  .


 

А также другие работы, которые могут Вас заинтересовать

58586. Звуки [н]. Строчная буква «н» 36.28 KB
  На этапе актуализации знаний предложены задания (в том числе и развивающего характера), которые подготовят учащихся к восприятию нового материала.
58587. Оформление проектной работы. Подготовка и оформление пояснительной записки проекта 2 MB
  Подготовка и оформление пояснительной записки проекта. Обучающая определить требования предъявляемые к оформлению пояснительной записки проекта оформить первую часть пояснительной записки введение.
58588. Олимпийские игры в древности 81.5 KB
  Цель урока: Знакомство с историей Олимпийских игр в древности оценка их значения в жизни Древней Греции и современности; осознание миротворческой роли Олимпийских игр Задачи урока: Способствовать формированию знаний учащихся по истории Олимпийских игр...
58591. Этика и наука 44.5 KB
  Рассказывается миф о царе Эдипе: Царь Лаий и его жена Иокаста получили страшное предсказание от дельфиского оракула: Если в вашей семье родится сын то отец погибнет от его руки. Царь усыновил младенца и назвал Эдипом. Эдип вырос умным и сильным мужчиной. Эдип отправился за ответом к дельфийскому оракулу.
58592. Значение и организация нервной системы 59.5 KB
  Цель урока: Рассмотреть общий план строения нервной системы и определить ее значение в системе всего организма Основные вопросы урока: Общая характеристика нервной системы Этапы развития нервной системы Общий план строения нервной системы человека.
58593. Оur university 344.5 KB
  The families of the words: to arrange, arrangement; to teach, teacher; to instruct, instruction, instructor; to prepare, preparation, preparatory; stomatology, stomatological, stomatologist; medicine, medical, medicinal...
58594. Основы рационального питания 75 KB
  И поэтому нам хочется чтобы вы узнали зачем мы едим из чего состоят продукты какие продукты полезные а какие вредные и что лучше есть чтобы быть здоровым хорошо расти учиться и быть в хорошем настроении.