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


 

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

23338. Проектирование этикеток 124.5 KB
  Задание на лабораторную работу: Определите структуру этикетки: база данных для этикетки; название этикетки; порядок размещения полей в этикетке; порядок размещения этикеток на листе; размер этикеток.
23339. Проектирование экранных форм 371.5 KB
  Выполните конструирование экранной формы. Создайте на экранной форме кнопки: навигации в базе данных; добавления новой записи; закрытия экранной формы. Создайте в экранной форме поле редактирования поле для ввода со списком селекторные кнопки или контрольные индикаторы. Сохраните среду созданной экранной формы.
23340. Создание макросов 107.5 KB
  Задание на лабораторную работу: Изучите правила записи макросов на примерах стандартных макрокоманд F2F9. Создайте свои макрокоманды для выполнения следующих работ: открыть нужные базы данных; удалить базы данных; установить отношения между базами данных; модифицировать отчет; выполнить запрос; Сохраните созданный набор макрокоманд в файле . Отчет по лабораторной работе: Диалоговое окно макрокоманд: Определение клавиши макрокоманды автоматизированное формирование: Определение клавиши макрокоманды запись вручную: Открыть таблицу...
23341. Генератор прикладных программ 290 KB
  Задание на лабораторную работу: Перед началом работы создать отдельный каталог для файлов приложения. Выполните генерацию стандартного приложения создавая или указывая базу данных на шаге 1. Проверьте работу стандартного приложения: стандартный экран форма ввода кнопки управления; меню стандартного приложения. Отчет по лабораторной работе: Проектирование приложения: Результат работы генератора: Результат работы кнопки New Knopka ввести новую запись: Контрольные вопросы: Структурные элементы стандартного приложения.
23342. Интегрированная cреда FoxPro 49 KB
  Лабораторная работа №1: Интегрированная cреда FoxPro. Цель работы: знакомство с возможностями среды СУБД FoxPro for Windows. Задание: Создайте на диске Х: каталог под именем FOXPRO для хранения примеров. Войдите в среду FoxPro.
23343. Создание структуры базы данных в СУБД FoxPro 118.5 KB
  Лабораторная работа №2: Создание структуры базы данных в СУБД FoxPro По дисциплине: Базы данных. Цели работы: изучить типы данных FoxPro; научиться создавать структуру базы данных; заполнить таблицы данными. Задание: Создайте структуру базы данных в соответствии с вашей темой расчетнографического задания. Изучите возможности среды СУБД FoxPro for Windows для создания структуры базы данных.
23344. Сортировка и индексирование баз данных 87 KB
  Лабораторная работа №3: Сортировка и индексирование баз данных По дисциплине: Базы данных. Задание: Выполните сортировку по одному полю базы данных содержащей не менее 15 записей. Повторите сортировку для полей содержащих разные типы данных. Просмотрите результат сортировки в новой базе данных.
23345. рогнозирование периодичности технического обслуживания (межремонтной цикла tM ) для ансамбля однотипных мащин 44 KB
  16 ТМ 93 98 102 Данные для расчетов: Варианты 1 2 3 tk время измерения выходного параметра час 10 10 10 up предельное значение 100 150 200 u1 измеренные значения 9.5 155 21 u2 измеренные значения 12 165 19 u3 измеренные значения 11 14 23 u4 измеренные значения 105 145 22 u5 измеренные значения 85 15 17 u6 измеренные значения 9 15 20 u7 измеренные значения 95 135 21 u8 измеренные значения 10 157 15 u9 измеренные значения 105 153 24 u10 измеренные значения 95 15 18.
23346. Прогнозирование параметра технического состояния конкретного элемента по его реализации 78 KB
  Устинова Основы эксплуатации техники ЛАБОРАТОРНАЯ РАБОТА № 5 Прогнозирование параметра технического состояния конкретного элемента по его реализации Выполнил: Студент группы ВЕ187 Устюжанцев А. Этап 1 Аппроксимация изменения параметра степенной функцией вида: u0t = v0 t 1 Построить графики опытных данных и усредненной аппроксимирующей кривых Указание: Использовать метод МНК реализованный в Excel Этап 2 Определение...