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


 

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

46930. The simple sentence. The semantic classification of simple sentence 37.5 KB
  The simple sentence s ny sentence in generl is orgnised s system of functionexpressing positions the content of the functions being the reflection of situtionl event. The nomintive prts of the simple sentence ech occupying notionl position in it re subject predicte object dverbil ttribute prentheticl enclosure ddressing enclosure; specil seminotionl position is occupied by n interjectionl enclosure. The ultimte nd highest object of this integrl modifiction is the sentence s whole nd through the sentence the reflection of the...
46932. Профессиональные риски в СР. Проблемы профессионального здоровья специалиста, пути его сохранения и совершенствования 37.5 KB
  Проблемы профессионального здоровья специалиста пути его сохранения и совершенствования. Важнейшая задача органов управления в ведении которых находятся социальные службы и учебные центры осуществляющие подготовку и переподготовку социальных работников не столько содействие им в профессиональном развитии и продвижении по службе а сохранение здоровья социальных работников профилактика их профессиональных заболеваний проведение консультаций относительно профессиональных рисков в социальной работе. Важную роль в освоении профессии...
46935. ДОСЛІДЖЕННЯ ПРОГРАМИ ФІЗИЧНОГО ВИХОВАННЯ ДЛЯ 5-9 КЛАСІВ СПЕЦІАЛЬНОГО ЗАГАЛЬНОГО ЗАКЛАДУ ДЛЯ СЛІПИХ ДІТЕЙ 240.5 KB
  Розглянути особливості проведення занять з дітьми з особливими потребами. Вивчити особливості корекційних занять з дітьми з особливими потребами. Узагальнити дані науково-дослідницької роботи по впровадженню корекційних вправ в процесі фізичного виховання дітей шкільного віку. Проаналізувати особливості фізичного виховання дітей-інвалідів.
46937. Сущность экологических проблем. Причины возникновения, пути решения 37.93 KB
  Рост потребления природных ресурсов сопровождается с одной стороны истощением природы с другой увеличением масштабов образования отходов. тонн только твердых отходов в том числе 80 млрд. Особую тревогу вызывает рост складируемых токсичных отходов количество которых достигло 2 млрд. тонн ежегодно образующихся токсичных отходов используется и обезвреживается только одна треть.
46938. Информационная война 38.52 KB
  Informtion wr термин имеющий два значения. Воздействие на гражданское население и или военнослужащих другого государства путём распространения определённой информации. Целенаправленные действия предпринятые для достижения информационного превосходства путём нанесения ущерба информации информационным процессам и информационным системам противника при одновременной защите собственной информации информационных процессов и информационных систем. Шварценберг уточняет что процесс передачи политической информации происходит от одной...