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) =  .


 

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

59099. Руська трійця у Львові 42 KB
  Вивчення нового матеріалу, формування вмінь та навичок (25 хв.): оголошення нової теми; очікувані результати; мотивація навчальної діяльності; сприйняття і осмислення учнями навчального матеріалу.
59100. Рухова активність і здоровя 43 KB
  Посміхайтеся частіше і будьте здорові та щасливі ІІ. Що ж саме про людину ми зараз вивчаємо на уроках біології А навіщо вам його розгадувати що дадуть вам знання організму людини Знання...
59101. Рушничок для мами 49.5 KB
  Ви мабуть чули слово декорації Де їх можна побачити Звичайно у театрі. Де можна побачити такі орнаменти Їх часто використовують для оздоблення різноманітних частин одягу у вишивці розписах вазонів та інших предметів побуту.
59102. Сім чудес світу 45 KB
  Мета: закріпити і систематизувати знання учнів з історії Стародавнього світу, розглянути матеріали про найвизначніші памятки світової культури; розвивати в учнів логічне мислення та зорову память; виховувати любов до прекрасного, інтерес до історії.
59103. Свято врожаю 70.5 KB
  На столах хліб пиріжки печиво тістечка фрукти кавуни мед компот квіти. Просимо Ласкаво просимо Певне чули ви малята І не раз такі слова: Хліб потрібно шанувати Хліб усьому голова Хлопчик. А тому завжди в пошані Хліб у школі і в садку. Шановні батьки гості запрошуємо вас до нашої господи...
59104. Свято квітів. Шепчуть ніжно квіти пелюстками 33 KB
  Здогадалися, хто я така? Я, Флора, королева рослинного світу. Кожного року саме в цей день - у день народження видатного педагога В. Сухомлинського в моїй чарівній країні відкривається карнавал квітів. Я вас щиро запрошую на це чудове осіннє свято.
59105. Свято меду 62 KB
  Свято меду (на Спаса) святкують тоді, коли учні чи студенти перебувають на канікулах. Як же зробити так, щоб молодь прилучилась, більше дізналася про наше українське бджільництво, звичаї пращурів, їх духовну культуру?
59106. Свято останнього дзвоника 57.5 KB
  Ведучий: Підростають щодня дітлахи Непомітно мов квіти весняні; Дуже швидко спливають роки Забираючи в далі незнані. Ведуча: Даль покликала друзі і вас Бо настала уже ця хвилина Зустрічаймо одинадцятий клас Бо сьогодні урочиста днина...
59107. Свято Різдва Христового 28.5 KB
  Степане Та це мабуть колядники прийшли одчиняй скоріше двері Перший колядник. Хай за вікном хуртеча злиться А нам співати і радіти Горить ялинка у світлиці З Різдвом Христовим любі діти Другий колядник. Колядуйте колядуйте Третій колядник. Четвертий колядник.