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


 

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

81308. Марксизм о государстве и праве 35.44 KB
  Именно поэтому в этот период появляются такие направления философии марксизм который ставит перед собой задачу исследовать действительность открыть ее законы понять и объяснить жизнь общества Рассматривая марксистское учение о государстве и праве необходимо прежде всего подчеркнуть что марксистская концепция происхождения государства и права опирается на историко-материалистическое учение об обществе и общественном развитии на классовую трактовку государства и права. Марксистская теория происхождения государства наиболее полно...
81309. Особи, які беруть участь у виконавчому провадженні та залучаються до проведення виконавчих дій 28.53 KB
  До учасників виконавчого провадження належать сторони виконавчого провадження тобто стягувач та боржник представники сторін органи державної влади та місцевого самоврядування. Сторони є головними та обовязковими учасниками виконавчого провадження що мають особисту заінтересованість у наслідках виконавчих дій. Сторонами виконавчого провадження є стягувач і боржник. У Законі Про виконавче провадження ст.
81310. Особи, які сприяють вчиненню виконавчого провадження, їх права та обов’язки 28.86 KB
  Експерт або спеціаліст зобовязаний надати письмовий висновок, а суб\'єкт оціночної діяльності - субєкт господарювання - письмовий звіт з питань, що містяться в постанові державного виконавця, а також надати усні рекомендації щодо дій, які виконуються за його присутності.
81311. Представництво у виконавчому провадженні. Повноваження представника та їх оформлення 26.09 KB
  Особиста участь фізичної особи у виконавчому провадженні не позбавляє її права мати представника крім випадку коли боржник згідно з рішенням зобовязаний вчинити певні дії особисто. Неповнолітні та особи визнані судом недієздатними реалізують свої права та виконують обовязки повязані з виконавчим провадженням відповідно до вимог закону. Участь юридичних осіб у виконавчому провадженні здійснюється їх керівниками чи органами посадовими особами які діють у межах повноважень наданих їм законом або через представників юридичної особи....
81312. Поняття, види, зміст і форма виконавчого документа 28.75 KB
  Відповідно до цього Закону підлягають виконанню державною виконавчою службою такі виконавчі документи: виконавчі листи що видаються судами і накази господарських судів у тому числі на підставі рішень третейського суду та рішень Міжнародного комерційного арбітражного суду при Торговопромисловій палаті і Морської арбітражної комісії при Торговопромисловій палаті...
81313. Стадії виконавчого провадження. Відкриття виконавчого провадження 36.12 KB
  Відкриття виконавчого провадження. Процес виконавчого провадження завжди складається із послідовності дій державного виконавця від відкриття виконавчого провадження до його закінчення. Перша стадія виконавчого провадження.
81314. Органи і посадові особи, які здійснюють виконавче провадження 26.83 KB
  Примусове виконання рішень покладається на державну виконавчу службу яка входить до системи органів Міністерства юстиції України. Примусове виконання рішень здійснюють державні виконавці визначені Законом України Про державну виконавчу службу далі державні виконавці. За наявності обставин що ускладнюють виконання рішення або у разі виконання зведеного виконавчого провадження у встановленому Міністерством юстиції України порядку можуть утворюватися виконавчі групи до складу яких включаються державні виконавці одного або кількох органів...
81315. Підстави для відкриття виконавчого провадження. Вимоги до виконавчого документа 26.92 KB
  У заяві про відкриття виконавчого провадження стягувач вправі зазначити відомості що ідентифікують боржника чи можуть сприяти примусовому виконанню рішення рахунок боржника місце роботи чи отримання ним інших доходів місцезнаходження його майна тощо а також шляхи отримання ним коштів стягнутих з боржника. У заяві про відкриття виконавчого провадження щодо виконання рішення про майнове стягнення стягувач має право просити державного виконавця накласти арешт на майно та кошти боржника та оголосити заборону на його відчуження. У...
81316. Відводи державного виконавця, експерта, спеціаліста, перекладача, суб’єкта оціночної діяльності - суб’єкта господарювання 25.8 KB
  Державний виконавець, експерт, спеціаліст, оцінювач, перекладач не можуть брати участі у виконавчому провадженні і підлягають відводу, якщо вони є близькими родичами сторін, їх представників або інших осіб, які беруть участь у виконавчому провадженні, або заінтересовані в результаті виконання рішення, або є інші обставини, що викликають сумнів у їх неупередженості.