68838

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

Лекция

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

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

Украинкский

2014-09-26

85 KB

6 чел.

Лекція 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), тобто довжина    не дорівнює квадрату цілого числа.


 

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

66235. Моделирование и конструирование швейных изделий 4.1 MB
  Характер принимаемых здесь формул достаточно сложный количество измерений фигур большое и для индивидуального производства которое учитывает особенности телосложения каждой конкретной фигуры был разработан на базе этой методики €œЕдиный метод конструирования одежды...
66236. Деякі аспекти інтерактивного навчання 109.52 KB
  Застосування цих методів виявило певні проблеми й ускладнення: зниження ролі вчителя в навчальному процесі, неекономне витрачання навчального часу, відсутність в учнів достатньої мотивації для такого типу навчання.
66237. Характеристика функций, свойств и требований к одежде различного вида и назначения 1.76 MB
  Характеристика свойств одежды различного вида и назначения Характеристика требований к одежде Характеристика функций одежды В повседневной жизни людей одежда играет огромную роль так же как продукты питания и жилье.
66238. Кабельні лінії 599.54 KB
  Кабельна лінія електропередачі КЛ лінія для передачі електроенергії що складається з одного або декількох паралельних кабелів із з'єднувальними стопорними та кінцевими муфтами закладками і кріпильними деталями. Конструкції силових кабелів залежать від класу напруги.
66239. Использование протокола RIP 99.5 KB
  Протокол RIPX используется для определения типа кадра и номера внешней сети для каждого интерфейса, настроенного на автоматическое определение этих значений. При загрузке протокола NWLink отправляется запрос...
66240. Моделирование радиоэлектронных устройств при помощи программного комплекса Electronics Workbench 966.5 KB
  Для начала разработки необходимо загрузить файл-схему в среду Electronics Workbench, если этот файл уже создан и находится на одном из накопителей компьютера. Это делается посредством выполнения команды меню...
66241. Предмет статистики 117.32 KB
  Предмет статистики характеризує кількісні особливості соціальних та пов’язаних із ними природних процесів у нерозривному зв’язку з їх якісним складом. Істотним у визначенні предмета статистики є те що вона вивчає...
66242. Історія педагогіки 27.5 KB
  Під історією педагогіки ми розуміємо науку про розвиток виховання школи й педагогічної думки в різні історичні періоди. Предмет історії педагогіки як галузі педагогічного знання складає розвиток теорії і практики виховання освіти і навчання...