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


 

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

21172. ОСНОВЫ ПОСТРОЕНИЯ САПР ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ 52 KB
  Цель САПР это повышение качества проектов снижение материальных затрат сокращение сроков проектирования и ликвидация тенденции к росту числа проектировщиков а также повышение производительности их труда. Для САПР характерно системное использование ЭВМ при рациональном распределении функций между человеком и ЭВМ. Предметом САПР являются формализация проектных процедур структурирование и типизация процессов проектирования постановка модели методы и алгоритмы решения проектных задач способы построения технических средств создания...
21173. Современная память 2.18 MB
  В скором будущем будет также стандартизирована память DDR2800 в связи с чем многие материнские платы уже поддерживают этот тип памяти. Остальные же типы памяти не стандартизированы и не факт что материнская плата способна поддержать эту память на заявленной тактовой частоте. Возникает вопрос: почему же производители памяти соревнуясь друг с другом стараются выпускать все более скоростную память Ответ довольно прост это маркетинговый ход. Но так ли это на самом деле и действительно ли производительность памяти целиком и полностью...
21174. СТРУКТУРНАЯ СХЕМА КОНСТРУКТОРСКО-ТЕХНОЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ ПЕЧАТНОЙ ПЛАТЫ 74 KB
  Выбор типа конструкции блока и варианта конструктивного исполнения модуля I уровня ячейки. Выбор компоновочной структуры ячеек ЭА. Выбор типа конструкции ПП. Выбор класса точности ПП.
21175. Тепловые воздействия на конструкции СВТ 175.5 KB
  Комплекс технических средств реализующих тот или иной способ отвода тепла от аппаратуры в окружающую среду назовем системой охлаждения. В зависимости от характера контакта теплоносителя с поверхностью источника тепла различают системы охлаждения прямого и косвенного действия. Воздушные жидкостные и испарительные системы охлаждения могут работать по разомкнутому и замкнутому циклу. В первом случае отработанный нагретый теплоноситель удаляется из системы и больше в ней не используется во втором случае отработанный теплоноситель охлаждается...
21176. Тест начального включения — POST 67.5 KB
  POST выполняет тестирование процессора памяти и системных средств вводавывода а также конфигурирование всех программноуправляемых аппаратных средств системной платы. Часть конфигурирования выполняется однозначно часть управляется джамперами системной платы но ряд параметров позволяет или даже требует конфигурирования по желанию пользователя. Однако для использования такой диагностики необходима вопервых сама платаиндикатор и вовторых словарь неисправностей таблица специфическая для версии BIOS и системной платы. Если не...
21177. ТЕХНОЛОГИЧЕСКАЯ ДОКУМЕНТАЦИЯ. ЕСТД. ТЕХНОЛОГИЧЕСКАЯ ПОДГОТОВКА ПРОИЗВОДСТВА (ТПП). ТЕХНОЛОГИЧНОСТЬ 37 KB
  ТЕХНОЛОГИЧНОСТЬ Состав и правила выполнения технологической документации определяется ГОСТ 3.1001 81 Единой системой технологической документации ЕСТД. Она представляет собой комплекс государственных стандартов и руководящих нормативных документов устанавливающих взаимосвязанные правила и положения по порядку разработки комплектации оформления и обращения технологической документации применяемой при изготовлении и ремонте изделий контроль испытания и перемещения. Основное назначение ЕСТД в установлении во всех организациях и на...
21178. Алгебраїчні доповнення. Обчислення детермінантів 341.5 KB
  Означення алгебраїчного доповнення елементу детермінанта. Такий детермінант називається алгебраїчним доповненням елемента даного детермінанта і позначається як : 6. Детермінант дорівнює сумі добутків елементів будьякого рядка детермінанта на їх алгебраїчні доповнення.3 Доведення: Додамо до кожного елементу mго рядка детермінанта 6.
21179. Ранг матриці. Елементарні перетворення матриці 204 KB
  Елементарні перетворення матриці. Визначення рангу матриці. Такий детермінант називається мінором матриці kго порядка.
21180. Системи лінійних алгебраїчних рівнянь загального виду. Теорія Кронекера-Капеллі. Метод Гаусса 237.5 KB
  Система називається сумісною якщо вона має хоча б один розв язок тобто хоча б один стовпець який перетворює рівняння 9.1 в тотожність і несумісною якщо вона не має розв язків. Система називається означеною якщо вона має один розв язок і неозначеною якщо вона має розв язків більше одного. Аналіз систем рівнянь повинен дати відповідь на два питання чи сумісна система тобто чи має вона розв язок і якщо сумісна то чи вона означена чи ні.