68838

Контекстно-вільні граматики

Лекция

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

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

Украинкский

2014-09-26

85 KB

7 чел.

Лекція 8

Контекстно-вільні граматики

Граматики  типу  3  (або регулярні)  застосовуються  на  етапі  лексичного  аналізу. Однак, вони не дозволяють описати способи  об’єднання символів у речення типових мов програмування. Наприклад, узгодження  дужок, як згадувалось раніше  не  можна  означити  за  допомогою регулярної граматики.

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

З наведених раніше означень прямує, що клас контекстно-вільних  граматик більш потужний (тобто може генерувати більше мов), ніж клас  регулярних, але менш потужний, ніж клас контекстно-залежних. Наприклад, мова {anbn | n ≥ 0} є контекстно-вільною, але нерегулярною. Вона генерується правилами

                                                           1. S  aSb
                                                            2. S
      

У той же час, мова {anbncn | n ≥ 0}  є контекстно-залежною,  а  не  контекстно-вільною. Переконаємося  у  тому, що подана мова генерується  контекстно-залежною  граматикою   G. Нехай   G = (N, T, P, S),   де  N = {S, A, B, C}, T = {a, b, c},  і  Р  містить продукції:

                                         1. S aSBC                5. bC bc

                                         2. S                        6. CB  BC

                                         3. aB  ab                   7. cC  cc

                                         4. bB  bb

Для будь-якого натурального  n  маємо

S * anS(BC)n  an(BC)n * anBnCn  an bBn-1Cn * anbnCn  anbncCn-1 *

  1n                   21          6(n-1)n/2            31                 4n-1             51                7n-1

anbncn,

де під стрілочкою показаний  номер  правила та кількість його застосувань.

Коли  n = 0,   S    = a0b0c0.

                          21                      

Отже   {anbncn | n ≥ 0}  L(G).

Тепер необхідно показати, що граматика  G  не породжує ніяких  інших рядків. А це прямує з  таких  міркувань.  Перша  сентенціальна  форма, що не містить S завжди має вигляд an(BC)n. Оскільки усі правила заміни нетерміналів  B  та  C  відповідно на термінали  b  та  c  не змінюють порядок розташування літер та їх кількості, то рядок,  що виводиться граматикою  G, завжди має вигляд  anbncn.
                                               
Канонічні форми граматики

Означення 8.1. Кажуть, що граматика  G = ( N, T, P, S ) записана у нормальній формі Хомського, якщо  кожна  продукція  з   Р  має один з трьох видів 

 A  BC,   A, B, C      N,

                                                    A a,      a T,

                                                     S  ,

і символ  S  не входить у праву частину жодного правила.

Означення 8.2. Нормальною формою Грейбах називають форму запису граматики  G = (N, T, P, S),  у якій кожне правило, крім  S  , має вигляд                  A  a   ,   A  N,  a  T,   N*.                  

Теорема 8.1. Для кожної контекстно-вільної грамматики існують еквівалентні у нормальній формі Хомського та у нормальній формі Грейбах.

Доведення цієї теореми можна знайти у [1].

Самовкладання

Означення 8.3. Якщо у граматиці  G = (N, T, P, S)   є  нетермінал  A,  для  якого  виконується співвідношення  A +  1A2,  де  1 та  2 довільні непусті рядки,  то  кажуть,  що   G   містить  самовкладання.  

Наприклад, наведемо дві граматики, що містять самовкладання.

G1  = ({S}, {a,b}, P1, S),  де   Р1 :

1. S aSb

                                                               2. S  ;                              

G2  = ({S, A}, {begin, end, [, ]}, P2, S),  де   Р2 :

1. S begin A end

                                                    2. S  ;                              

                                                    3. S [S] 

Відносно граматики  G2  кажуть, що у ній  А   та   S   виявляють  властивість самовкладання.

У теорії синтаксичного  аналізу  встановлено [1] факт, що формулюється у вигляді наступної теореми.

Теорема 8.1. Будь-яка контекстно-вільна граматика еквівалентна регулярній граматиці тоді і тільки тоді, коли  вона  не  містить  самовкладань.

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

                         Характерна властивість контекстно-вільних мов

Лема   8.1  (про розростання дерев). Для будь-якої  контекстно-вільної мови  L існує така константа   k, що кожний рядок  з L  (z  L)  такий, що  | z |  k,  можна записати у вигляді   z = uvwxy,  де

1) w  ;

2) виконується хоча б одна з умов: 

              а) u   і   v  , 

              б) x    і   y  ;

3) | vwx |  k;

4) uviwxiy  L  для будь-якого цілого невід’ємного  і. 

Доведення. Подана  КВ-мова  L  породжується  КВ-граматикою   G  =  (N, T, P, S). Нехай  m =  | N |, і  l - довжина  найдовшої  правої  частини правил  Р. Візьмемо  k = l2m+3  і розглянемо дерево виводу  R  деякого рядка  z  L(G),  такого, що  | z |  k.  Назвемо вершину  t  дерева  R  вершиною розгалуження, якщо вона  має більше одного прямого нащадка. Побудуємо шлях  r = (t1, t2, … , tp)  у дереві  R  таким чином:
     1) t1  - корень дерева  R;
      2)
ti   -  прямий  нащадок  ti-1  з   найбільшою   кількістю нащадків-листів;

      3) tp - лист.

Вершина  t1  має не менш, ніж  l2m+3  листів-нащадків. Кількість листів-нащадків вершини  ti  не менше, ніж кількість  листів-нащадків  вершини  ti-1,  зменшена  у   l   разів.  Це  прямує  з  того,   що  максимальне число прямих  нащадків  вершини  дорівнює   l,  і  ti  є  нащадок  ti-1  з найбільшою кількістю листів-нащадків. Тому  шлях  r  містить не менш  2m + 3  вершин розгалуження. Оскільки  tp - лист  і  не є вершиною розгалуження,  р > 2m + 3.                           

Нехай  b1, b2, … , b2m+3 -  останні   2m + 3   вершини  розгалуження на шляху  r. Назвемо  bi  лівою  вершиною  розгалуження,  якщо  прямий  нащадок  вершини  bi,  що   не   належить    r,   має  нащадка-листа ліворуч від tp.  В  іншому  разі  будемо  називати  bi  правою вершиною розгалуження.

Серед вершин  b1, b2, … , b2m+3  є або не менш  m +  2  лівих  вершин розгалуження, або не менш   m + 2  правих. Нехай  l1, l2, … , lm+2  - останні  m + 2  ліві вершини  розгалуження   (випадок  правих  вершин розглядається аналогічно). Оскільки  | N | =  m,  серед  вершин  l1, l2, … , lm+2     є  принаймні  дві  пари  вершин  з  однаковими  позначеннями.  Очевидно,  завжди  можна  так  вибрати   вершини,  які відповідають одному нетерміналу (lf, lg, f < g ),  що знайдеться деяка  вершина lq, позначення якої співпадає з позначенням іншої вершини, і виконується співвідношення q < f. Ця ситуація умовно зображена на  рис.8.1. Горизонтальна лінія  показує  крону  дерева  R.  Подвійною  лінією зображено шлях   r.  Лінії  ліворуч  від  шляху   r   з’єднують вершини шляху з їх найлівішими нащадками-листями,  а  праворуч  -  з  найправішими.

Нехай вершини  lf  та  lg  відповідають  нетерміналу   А.  Якщо  вилучити з  R  усіх  нащадків  вершини  lf,  то  залишиться  дерево  виводу з кроною  uAy, де  u  складається  з  листів,  розташованих  ліворуч від листів-нащадків  lf, а  y - з листів, розташованих праворуч. Тому

S + uAy.              (8.1)

Якщо розглянути піддерево з коренем  lf , з  якого  вилучені  нащадки  вершини lg, то неважко бачити, що 

    A + vAx,              (8.2) 

де  v  та  х - частини  крони  цього  піддерева,  що  складаються  з  листів, розташованих відповідно ліворуч та праворуч від lg. Тоді  

    A + w,              (8.3)

звідки прямує  z = uvwxy.

Враховуючи (8.1 – 8.3), маємо

S + uAy + uwy,

і для всіх  i  1

S + uAy + uvAxy + uv2Ax2y +  uvi+2Axi+2y, 

або

S + uviwxiy.

          u                   v                        w                      x                     y

Рис.8.1. Дерево виводу рядка  z.

Таким чином, виконання умови  4) доведено. При існуванні   (m + 2)-х  лівих вершин розгалуження наявність вершин   lf  та  lq  обумовлює  виконання   умови  u    та  v  . Аналогічно, якщо існують  m + 2  праві  вершини розгалуження,  x    та  у  . Отже  умова  2)  теж  завжди виконується. За побудовою дерева  R   w  , оскільки  tp  w  (умова  1).  Нарешті,  вершина  b1 є  (2m + 3)-ю   вершиною  розгалуження, рахуючи від кінця шляху  r. Тому вона  має  не  більш,  ніж  l2m+3 = k  листів-нащадків. Отже, | vwx |  k,  оскільки   vwx   є  підмножина листів-нащадків вершини b1.
    За допомогою цієї леми можна довести, що деякі мови не належать  до класу контекстно-вільних.

Застосування леми про розростання дерев

Нехай подано мову  L = {1p  | p - просте число}, тобто  L = {11, 111, 11111, …}.

З’ясуємо, чи є  L  контекстно-вільною мовою. Припустимо, що L - КВ-мова. Тоді за лемою знайдеться таке просте число k (їх  нескінченно багато), що
                  1
k = uvwxy,   vx  ,  uy  , uviwxiy  L  для всіх  і 0.

Це означає, що існують цілі невід’ємні числа  a, b, c, d, e  такі,  що

1k = 1a 1b 1c 1d 1e,  b + d > 0,  a + e > 0,  c > 0,

 1a (1b)i 1c (1d)i 1e  L.

Отже,  k = a + b + c + d + e  - просте, та  ki = a + bi + c + di + e = a + c +e + i(b + d) – просте для усіх невід’ємних цілих  i.

У окремому випадку, коли  і = а + с + е, маємо ki = a + c + e + ( a + c+ e)( b + d) =( a + c + e )( 1 + b + d ),  тобто  ki - непросте  число,  оскільки  множники  у  правій  частині  більше одиниці. Одержали суперечність,  а  це  означає,  що  припущення  неправильне, і  L не є  КВ-мовою.

Розглянемо ще одну мову  L1 = { |   (0 + 1)*},  тобто рядки цієї мови утворюються парою однакових  послідовностей  з  нулів та одиниць.

Нехай    складається з  k  нулів,  записаних  підряд,  та   k  наступних одиниць. Тоді відповідний рядок  z  має вигляд

z =  = 00 … 011 … 100 … 011 … 1   L1.              

                                                  k          k           k          k 

Припустимо, що L1 контекстно-вільна мова, і k – константа з леми про розростання дерев. Тоді згідно з лемою  z = uvwxy,   де   | vwx |  k.

Очевидно, можливі альтернативи:

    1) v  та  x  знаходяться разом або у першій половині  z, або  у  другій;

    2) v, x  містять одиниці  з  першої  половини   z   та  нулі  з  другої.

У першому випадку  z0 = uwy = uv0wx0y  L1. Це прямує з таких міркувань. Оскільки вилучаються нулі та одиниці  з  однієї половини  z, то середина z0 розташовується  між  символами  іншої половини z. Враховуючи, що  | w | 1, і, як наслідок,  | vx | < k,  одержуємо, що  з  одного  боку  від  середини z0  знаходяться  три  послідовності однакових символів, а з іншого  -  тільки  дві.  Отже,  лема про розростання дерев не виконується для   і = 0.

У другому випадку, якщо середина  z0  співпадає з серединою z,  то  z0  L1, оскільки з лівої половини  z  вилучаються одиниці, а  з  правої  -  нулі.  При  розташуванні  середини  z0  в  іншому  місці  одержуємо ситуацію, аналогічну першому випадку.
       
Тому можна зробити висновок, що  L1  не є  КВ-мовою.

Скориставшись лемою про розростання дерев, можна показати, що мова L2 = {anbncn | n ≥ 0} не є  конткстно-вільною. Дійсно, припустимо, що L2 конткстно-вільна, і розглянемо рядок   =  akbkck,  де  k – константа з леми. Тоді   = uvwxy   і  | vwx |  k. А звідси прямує,  що   = uv0wx0y  L2,  оскільки     утворюється з    вилученням не більше ніж двох видів символів і не може містити однакові кількості символів  a, b, c.

Нарешті, переконаємося, що мова  L3 = {an | n = m2, m ≥ 0}  не належить до класу контекстно-вільних. Припустимо, що  L3  контекстно-вільна, і розглянемо рядок     L3   такий, що   | | = m2, і  m > k, де  k - константа з леми. Тоді   = uvwxy  і  | vwx |  k. Але при цьому   = uv2wx2y  L3,  оскільки  | |  m2 + k < m2 + m < ( m + 1), тобто довжина    не дорівнює квадрату цілого числа.


 

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

33486. Поняття злочину та його ознаки 28 KB
  Злочином є передбачене цим Кодексом суспільно небезпечне винне діяння дія або бездіяльність вчинене субєктом злочину. Три ознаки злочину: суспільна небезпечність діяння винність і передбаченість діяння в законі про кримінальну відповідальність. Суспільна небезпечність як матеріальна ознака злочину полягає в тому що діяння або заподіює шкоду відносинам які охороняються кримінальним законом або містить у собі реальну можливість заподіяння такої шкоди.
33488. Змішана форма вини 28.5 KB
  До таких злочинів належать наприклад порушення вимог законодавства про охорону праці якщо воно спричинило загибель людей або інші тяжкі наслідки ч. 286; порушення чинних на транспорті правил що убезпечують рух якщо це спричинило загибель людей або інші тяжкі наслідки ст. 291; незаконне перевезення на повітряному судні вибухових або легкозаймистих речовин що спричинило загибель людей чи інші тяжкі наслідки ч. У другій групі злочинів складність об'єктивної сторони полягає в тому що передбачене законом умисне діяння спричиняє два...
33489. Помилка в кримінальному праві 27 KB
  Юридична помилка полягає в неправильному уявленні особи про юридичні властивості вчиненого, його правову характеристику
33490. Класифікація злочинів 27.5 KB
  Формальний критерій певний вид і розмір покарання типовий такий що найбільш повно відображає тяжкість конкретної групи категорії злочинів. Так для злочинів невеликої тяжкості закон передбачає як граничний критерій покарання у виді позбавлення волі на строк не більше двох років або інше більш м'яке покарання; для злочинів середньої тяжкості покарання у виді позбавлення волі на строк не більше п'яти років; для тяжких злочинів покарання у виді позбавлення волі на строк не більше десяти років а для особливо тяжких покарання у...
33491. Кримінальна відповідальність 31 KB
  Кримінальній відповідальності підлягає лише особа винна у вчинені злочину або така що умисно або з необережності вчинила передбачене кримінальним законом суспільне небезпечне діяння ч. Ознаки кримінальної відповідальності: 1 це особливий елемент у механізмі кримінальноправового регулювання в межах якого здійснюється реагування держави на вчинений особою злочин; 2 офіційна оцінка поведінки особи як злочину а її самої як злочинця може здійснюватись лише судом в обвинувальному вироку ч. Кримінальну правовідносини що знаменує собою...
33492. Наука кримінального права 30 KB
  Науку кримінального права як систему кримінальноправових поглядів ідей уявлень і понять слід відрізняти від кримінального права як системи сукупності юридичних норм галузі права. Саме наука кримінального права вивчаючи кримінальне законодавство з'ясовуючи його соціальне призначення характер усіх його інститутів їх ефективність виявляє практичне значення кожної норми прогалини в правовому регулюванні досліджує проблеми вдосконалення кримінальноправових норм. Предметом науки кримінального права є такі соціальні явища як злочин і...
33493. Незакінчений злочин 32 KB
  Незакінченим злочином є готування до злочину та замах на злочин ч. У літературі незакінчений злочин нерідко називають: попередньою злочинною діяльністю розпочатим незавершеним злочином невдалою діяльністю у вчиненні злочину. Незакінчений злочин готування до злочину і замах на злочин це не здійснена можливість завдання шкоди об'єкту посягання.
33494. Необхідна оборона 27.5 KB
  підстава необхідної оборони складається з двох елементів а саме: 1 суспільно небезпечного посягання і 2 необхідності е його негайному відверненні чи припиненні Ознаки необхідної оборони визначені в ст. 36 КК характеризують: 1 мету оборони; 2 спрямованість об'єкт заподіяння шкоди; 3 характер дій того хто захищається; 4 своєчасність і 5 співрозмірність оборони. Мета необхідної оборони. 36 КК метою необхідної оборони є захист охоронюваних законом прав та інтересів особи яка захищається або іншої особи а також суспільних...