68838

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

Лекция

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

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

Украинкский

2014-09-26

85 KB

8 чел.

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


 

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

79883. Арифметические устройства 1.81 MB
  Примерами простейших конечных ЦА являются триггеры. Триггеры 4.1 RSтриггер Триггером Т называют логическую схему с положительной обратной связью имеющую два устойчивых состояния которые называются единичным и нулевым и обозначаются 1 и 0. Перевод триггера в единичное состояние путем воздействия на его входы называют установкой set триггера а устанавливающий сигнал и вход на который он воздействует обозначают S от set.
79885. Широкополосные усилители на транзисторах 131 KB
  Одним из наиболее распространенных и наиболее простых способов ВЧкоррекции с помощью частотнозависимой ООС является эмиттерная коррекция когда используется комплексная ООС в эмиттерной цепи с помощью цепи RэкорСэкор рис. Благодаря этой цепи в усилительном каскаде создается достаточно глубокая последовательная ООС по току. Конденсатор Сэ большой емкости шунтирует Rэ по переменному току на всех рабочих частотах поэтому частотнозависимая ООС создается только благодаря цепи RэкорСэкор. Для расширения полосы частот...
79886. Усилители постоянного тока. Операционные усилители 415.5 KB
  Коэффициент усиления Ку отношение приращения значения выходного напряжения к вызвавшему его изменению дифференциального входного напряжения. Входное сопротивление для синфазного сигнала rсф величина равная отношению приращения синфазного входного напряжения к приращению среднего входного тока ОУ rсф обычно на 1 2 порядка больше rвх.сф определяется как отношение изменения выходного напряжения к вызвавшему его изменению синфазного входного сигнала. Коэффициент влияния нестабильности источника питания Кп отношение изменения...
79888. Микропроцессорная техника. Микропроцессоры и микропроцессорные комплекты 388.5 KB
  Микропроцессор МП это обрабатывающее и управляющее устройство способное под программным управлением выполнять обработку информации принятие решений ввод и вывод информации и выполненное в виде одной или нескольких БИС. используемое для временного хранения информации в процессе работы МП. В отличие от ПЗУ в ОЗУ возможно как считывание так и запись информации по сигналам Чт и Зап в ячейку адрес которой находится на ША. По сигналу Вв ввод на ШУ происходит передача информации от внешнего устройства на ШД а по сигналу Выв вывод...
79891. Разработка макияжа и внешнего вида в английском стиле 63.44 MB
  Дневной макияж помогает подчеркнуть природную красоту, сделать акцент на достоинствах и слегка затушевать недостатки. Самый универсальный дневной макияж –естественный макияж. Дневной макияж - это простой, не броский макияж как правило в светлых пастельных тонах. При выполнении дневного макияжа используются легкий тон, светлая пудра, тени для век, тушь и неяркая помада