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


 

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

77213. СОЗДАНИЕ СРЕДЫ РАЗРАБОТКИ ДЛЯ ЯЗЫКА ПРОГРАММИРОВАНИЯ OCAML 96 KB
  OCaml в настоящее время является активно развивающимся языком программирования. Секрет его успеха, возможно, заключается в том, что этот язык интуитивно понятен и прост для изучения даже неопытным программистом.
77214. Cоздание дискретизирующего фильтра для обработки электроокулограмм. Обеспечение работы и настройки фильтра в режиме реального времени 512 KB
  Причиной этих бросков служит тот факт, что глазное яблоко представляет собой электрический диполь (сетчатка заряжена отрицательно относительно роговицы), поэтому при поворотах глазного яблока в районе глаз регистрируется изменение разности потенциалов.
77215. Язык для описания плагинов в среде программирования JetBrains MPS 347.5 KB
  С каждым годом приложения становятся более объемными и сложными. В связи с этим, требуются все более изощренные подходы к программированию для создания новых программ. Попробуем проследить, как развивались средства программирования, чтобы удовлетворять нуждам программистов по написанию сложных проектов.
77216. Применение нейронных сетей к ранжированию результатов информационного поиска 282 KB
  Существует ряд алгоритмов машинного обучения, которые позволяют определять ранг документов. Например, RankProp, PRank и RankBoost. Данные адаптивные алгоритмы тренируются на обучающей выборке документов, чтобы выявить зависимости положения документа от его признаков.
77217. Распознавание автомобильных номеров с помощью нейронных сетей 230 KB
  В современных условиях, когда прослеживается явная тенденция к автоматизации большинства процессов, которые раньше предполагали безоговорочное участие человека, идея автоматической идентификации автомобиля по номерной пластине с целью дальнейшего использования...
77218. Создание физически-корректного дождя и сопутствующих эффектов 5.78 MB
  Целью курсовой работы была разработка и реализация дешевых, с точки зрения вычислений, но мощных алгоритмов визуализации как непосредственно самого дождя, так и различных эффектов его сопровождающих.
77219. Расширение функциональности графического редактора языка DRL 474.5 KB
  Сейчас большинство организаций разрабатывают семейства продуктов, и только немногие системы или продукты остаются уникальными. Похожая ситуация и в программной инженерии - рынок требует всё большего качества программных продуктов, уменьшения времени выхода на рынок и уменьшения их цены.
77220. Поиск оптимального ректификационного преобразования 673.5 KB
  В задаче восстановления трёхмерных сцен по двум изображениям, взятых с различных точек одним из главных этапов является поиск соответствующих точек на этих изображениях. Поиск производится вдоль эпиполярных прямых, и удобным для вычислений является случай...
77221. Массовая задача построения маршрутов движения судов 222.21 KB
  В данной работе рассматривалась следующая постановка задачи: Пространство представляет собой плоскость препятствиями являются многоугольники полученные сечением рельефа морского дна на глубине соответствующей осадке судна.