Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Граматики передування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2008
Тип роботи:
Курсова робота
Предмет:
Дискретна математика
Група:
ПМ-31
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
кафедра прикладної математики
КУРСОВА РОБОТА
з курсу дискретна математика
на тему:
„Граматики передування”
Зміст
1. Вступ
2. Основні поняття граматики
3. Граматики передування (загальна характеристика)
4. Алгоритм типу «перенос-згортка»
5. Граматики простого передування
6. Граматики розширеного передування
7. Граматики слабкого передування
8. Список використаної літератури
Вступ
Для створення нових мов програмування необхідно описати правила згідно яких записуються слова мови. Також виникає проблема розпізнавання вхідних слів, а саме чи належать вони даній мові чи ні. Існує декілька методів перевірки належності стрічки до мови, одним з них є алгоритм типу «перенос – згортка».
Суть алгоритму полягає у використанні вхідної стрічки, читаючи її з ліва на право, і магазину. На основі того, що знаходиться в магазині і залишилось не опрацьованим на вході, функція f вирішує, перенести даний вхідний символ в магазин чи викликати процедуру згортки. Якщо виконується останнє рішення, то функція g вирішує, яку згортку зробити.
Основні поняття граматики
Граматика - це математична система, що визначає мову. Одночасно вона є пристроєм , що надає ланцюжкам мови корисну структуру.
У граматиці, що визначає мову L, використовуються дві кінцеві непересічні множини символів - множина нетермінальних символів (позначимо N) і множина термінальних символів (позначимо T). З термінальних символів утворюються слова (ланцюжки) обумовленої мови.
Основу граматики становить скінченна множина P правил виводу, які описують процес породження ланцюжків мови. Наприклад, правилом може бути пара (AB, CDE). Якщо вже встановлено, що деякий ланцюжок α породжується граматикою (або «виводиться » у ній) і α містить AB, тобто ліву частину цього правила, у якості свого підланцюжка, то можна утворити новий ланцюжок β, замінивши одне входження AB в α на CDE. Тоді говорять, що β виводиться у даній граматиці . Наприклад, якщо ланцюжок FGABH виведений, то FGCDEH теж виведений. Мова, обумовлена граматикою, - це множина ланцюжків, які складаються тільки з терміналів і виводяться, починаючи з одного особливого ланцюжка, що складається з одного виділеного символу, звичайно позначуваного S.
Означення.
Граматикою називається четвірка G=(N, T, P, S) , де
N - скінченна множина нетермінальних символів, або нетерміналів;
T - скінченна множина термінальних символів, або терміналів, яка не перетинається з N;
P - скінченна підмножина множин
()*N()*(()*.
S- виділений символ з N називаний початковим (або вихідним) символом.
Контекстно-вільною (надалі будем позначати КВ) називається граматика, якщо кожне правило з Р має вигляд А→α, де АN ,α()*;
Граматики передування (загальна характеристика)
Найпростіший клас алгоритмів типу "перенос - згортка " базується на так званих відношеннях передування. Для граматики передування межі основи праволінійного ланцюжка можна визначити за допомогою деяких відношень між символами, які входять в даний ланцюжок
Техніка розбору, орієнтована на відношеннях передування, використовувалась при побудові аналізаторів для мов програмування однієї з перших. З того часу в літературі появилося декілька видів граматик передування. Ми розглянемо оснований на відношеннях передування детермінований аналіз зліва на право, який проводить правий розбір. При цьому будуть введені граматики передування наступних типів:
Простого передування,
Розширеного передування,
Слабкого передування,
Змішаної стратегії передування,
Операторного передування.
Ключ для розуміння методу розбору по відношенням передування дає визначення відношення (≥) між символами граматики, які при перегляді зліва на право праволінійного ланцюжка αβω, де β - основа, вперше виявилось виконаним для останнього символу ланцюжка β,і першого символу ланцюжка ω.
Якщо для розбору використовується алгоритм типу «перенос – згортка», то кожний раз, коли між верхнім символом магазину і першим із неопрацьованих вхідних символів виконується відношення (≥) , приймається рішення про згортку; в протилежному випадку робиться перенос.
Таким чином за допомогою відношення (≥) локалізується правий кінець основи праволінійного ланцюжка. Локалізація лівого кінця основи і визначення необхідної згортки виконується різними способами, в залежності від використовуваного типу передування.
Техніка аналізу, яка базується на так званому «простому передуванні» використовує для виділення основи праволінійного ланцюжка αβω три відношення передування: (≤),(≥) ,(=), якщо β — основа, то між усіма суміжними символами ланцюжка α виконується відношення (≤) або (=).Між останнім символом ланцюжка α і першим символом ланцюжка β виконується відношення(≤), між суміжними символами основи – відношення (=) і між останнім символом ланцюжка β і першим символом ланцюжка ω – відношення (≥).
Таким чином, основу ланцюжка праволінійної граматики простого передування можна виділити, переглядаючи даний ланцюжок зліва на право доти, поки вперше не зустрінеться відношення (≥). Для знаходження лівого кінця основи необхідно повертатись назад, доки не зустрінеться відношення (≤) . Ланцюжок який знаходиться між відношеннями (≤) і (≥) буде основою. Якщо граматика допускається зворотною, то основу можна однозначно згорнути. Цей процес продовжується до тих пір, поки вхідна стрічка не згорнеться до першого символу.
Алгоритм типу «перенос-згортка»
Означення
Нехай G = (N,Т,P,S) - КВ - граматика, правила якої занумеровані числами від 1 до р. Алгоритмом типу " перенос - згортка " для граматики G назвемо пару функцій А = (f,g), де f називається функцією переносу, a g - функцією згортки. Функції f та g визначаються так:
(1) f відображає V*х(T{$})* в множину {перенос, згортка, помилка, допуск}, де V = {$} ,a$ - новий символ, кінцевий маркер.
(2) g відображає V*х(T{$})* в множину (1, 2, ..., p, помилка} при умові, що якщо g(α,ω) = i, то права частина i-го правила являється суфіксом ланцюжка α.
Алгоритм типу " перенос - згортка " використовує вхідну стрічку, читаючи її з ліва на право, і магазин. На основі того, що знаходиться в магазині і залишилось не опрацьованим на вході, функція f вирішує, перенести даний вхідний символ в магазин чи викликати процедуру згортки. Якщо виконується останнє рішення, то функція g вирішує, яку згортку зробити.
Роботу алгоритмом типу " перенос - згортка " можна розглядати в термінах конфігурацій трійок виду
), де
(1) - те що находиться в магазині, до того ж - верхній символ, Xі є N Т і $ служить маркером дна магазину.
- частина вхідної стрічки, яка залишилась неопрацьованою, -поточний вхідний символ, $- служить правим кінцевим маркером для входу.
(3) - ланцюжок правил, які використовуються при згортці початкової вхідної стрічки до стрічки .
Один крок алгоритму А можна описати за допомогою двох відношень │( А і │(А, визначених на конфігураціях (індекс А в цих позначеннях будемо опускати всюди де це буде можливо)
Якщо f(α,aω)= перенос, то (α,aω,π) │( (αa,ω,π) для α є V*, ω Є (Т{$})* і π є{1,...,р}*,
Якщо f(αβ,ω)= згортка, g(αβ,ω) = і і А →β - правило з номером і , то (αβ,ω,π)│( (аА,ω,πі),
Якщо f(α,ω) = допуск, то (α,ω,π) │( допуск
(4)В інших випадках (α,ω,π) │( помилка.
Визначимо відношення │(як об'єднання відношень │( і │(.
Для ωЄТ задамо А(ω) = π, якщо ($,ω$,е) │( ($S,ω$,π) ( допуск, і А(ω) = помилка, якщо такого π не існує.
Будемо називати алгоритм А коректним для граматики G , якщо:
L{G) = {ω | А{ω)≠ помилка},
π- правий розбір ланцюжка ω, якщо А(ω) = π .
Приклад (1).
Побудуємо алгоритм типу "перенос - згортка" А = (f,g) для граматики G з правилами
(1) S→SaSb
(2) S→е
Функцію переносу f задамо таким чином:для всіх α Є V* і хЄ(Т ($} )*
f(αS,cx)= перенос, якщо с є {а,b},
f(αс, dx) = згортка, якщо c є {а,b} і dє{a,b}, .;
f($, ах) = згортка,
f($,bx) = помилка,
f((αX,$) = помилка, для X є {S, α},
f(αb,$) = згортка,
f($S,$) =допуск,
f($,$) =помилка.
Функцію згортки g задамо таким чином: для всіх α Є V* і хЄ(Т($} )*
g($,aх) = 2,
g(αa, cx) = 2 для с є {a, b},
. (3) g($SaSb,cx)=1 для с є {a,$},
g(αaSaSb,cx) =1 для с є {a, b},
g(a,x) = помилка в усіх інших випадках.
Розберемо за допомогою алгоритму А вхідну стрічку aabb. Алгоритм приступає до виконання в початковій конфігурації ($,aabb$,e)
Перший крок визначається значенням f($,aabb$), яке з визначеним функції f дорівнює згортці. Про те, яку саме згортку робити нам покаже значення g($,aabb$) , яке дорівнює 2.
Тому першим кроком буде згортка
($, aabb$, е) │(($S, aabb$, 2)
Наступний крок визначається значенням f($S.aabb$)= перенос.
Таким чином, це крок переносу ($S, aabb$,2) │((SSa, abb$,2)
Продовжуючи таким чином алгоритм виконає таку послідовність кроків:
($,aabb$,e) │(($S,aabb$2)
│(($Sa,abb$,2)
│(($SaS,abb$,22)
│(($SaSa,bb$,22)
│(\$SaSaS,bb$,222)
│(($SaSaSb,b$,222)
│(($SaS,b$,2221)
│(($SaSb,$,2221) │(($S,$,22211)
│(допуск.
Таким чином A (aabb) =22211 (22211 - правий розбір стрічки aabb)
На практиці ми не хочемо на кожному кроці розглядати всю стрічку в магазині та всю неопрацьовану частину вхідної стрічки, щоб з'ясувати яким має бути наступний крок алгоритму розбору. Зазвичай нам хочеться, щоб функція переносу залежала тільки від невеликого числа верхніх символів магазину і від невеликого числа вхідних символів. Аналогічно хотілося б, щоб функція згортки залежала тільки від символів магазину, розташованих в ньому не нижче ніж на 1 чи 2 символи від основи, яку згортаю, і від одного чи двох наступних вхідних символів.
Узгодження. Якщо f і g- функції алгоритму розбору типу '"перенос - згортка" і значення f(α,ω) визначено , тоді f(βα,ωx) = f(α,ω),для всіх β і х, якщо немає домовленості про протилежне. Аналогічне твердження стосується і для функції g .
Граматики простого передування
Відношення передування Вірта-Вебера (≤),(=),(≥) для КВ-граматики G=(N,T,P,S) визначеної на множині наступним чином:
А) Х=Y,
якщо в Р існує правило A→αXYβ, де α,β- довільні ланцюжки, можливо порожні
Б) X≤Y,
якщо в Р існує таке правило A→αXDβ та вивід D=>Yz
В) X≥Y,
справджується тоді і тільки тоді, якщо існують правила
A→αСYβ і вивід С=>zX, або
A→αСDβ і вивід С=>zX, D=>Yw.
Зауважимо, що відношення передування залежить від порядку, в якому знаходяться символи. Наприклад, якщо X≤Y, то звідси не слідує, що Y≥X, а з Х=Y не випливає Y=X.
Аналізуючи вхідний ланцюжок(стрічку) методом передування, зручно додавати до неї лівий та правий кінцеві маркери. В якості такого маркера візьмемо символ $ і будемо вважати, що $≤X для всіх X, для яких S=>Xα, і Y≥$ для всіх Y, для яких S=>aY.
Означення:
КС- граматика G = (N,Т,P,S) називається граматикою передування, якщо вона приведена (не містить лівосторонньої рекурсії), не містить е- правил і для довільної пари символів з виконується не більш, ніж одне відношення передування Вірта – Вебера. Поворотна граматика передування називається граматикою простого передування.
Відношення передування для граматики G разом з додатковими відношеннями для кінцевих маркерів показані в вигляді матриці передування. Кожна комірка матриці містить відношення передування між символами, які позначають певний рядок, і символом який позначає стовпець. Пуста комірка інтерпретується як помилка. Всю важливу інформацію, яка міститься в матриці передування п х п, часто можна представити в вигляді двох n- вимірних векторів.
Приклад (2)
Граматика G складається з правил S→aSSb|c.
Відношення = визначається так: проглядаємо праві частини правил і бачимо a=S, S=S і S=b. Щоб визначити відношення ≤ будемо шукати в правих частинах правила суміжні символи ХС. Коли Х знаходиться у відношенні ≤ з кожним самим лівим символом ланцюжка, який нетривіально виводиться з С. В нашому випадку це aS та SS. Щоб визначити ≥ знову шукаємо в правих частинах правил пари суміжних символів виду СХ. Потім символи Y, які можуть бути на правому кінці ланцюжка , який виводимо з С за один або більше кроків і термінали d, які можуть бути на початку ланцюжка, який виводимо з Х. для даного прикладу прикладу це будуть SS, Sb.
L(G)
RG)
S
а,с
b,c
Таблиця відношення передування
S
а
b
с
$
S
=
≤
=
≤
а
=
≤
≤
b
≥
≥
≥
≥
с
≥
≥
≥
≥
$
≤
≤
Оскільки в кожній комірці записано не більше одного відношення передування, то G- грамати передування.
Лема (1).
Нехай G = (N,Т,P,S) - приведена КС- граматика без е- правил.
(1) Якщо X < А або X = А і А → Yα міститься в Р, то X < Y
(2) Якщо А < а, А = а або А > а і А → aY міститься в Р, то Y> а
Доведення. (2) Якщо А < а, тоді існує така права частина βABβ, що В=>ау для деякого ланцюжка у. Оскільки A=>+aY, то звідси отримуємо Y > а. Якщо А = а, то існує права частина βAαβ. Оскільки а => *α і A=>+aY, то звідси знову отримуємо Y < а. Якщо А > а, то існує права частина βBХβ, де В=>+уA і X => *aδ для деяких y і δ. Оскільки B=>+yaY, то ми отримуємо потрібний висновок.
Теорема (1).
Нехай G = (N,Т,P,S) - приведена КС- граматика без е- правил.
Якщо $S$ =>
=>rXpX...Xk+lX...Xar..a То (1). ХІ+1<Х або ХІ+1 = X, для р<і<к,
(2).Хк+1<Хк,
(3). ХІ+1=Х, для k>i≥1,
(4). Х > а.
Доведення. Доведення проведемо індукцією по n. Для n=0 маємо $S$ =>$X...Xl$ . Згідно означення відношень передування $ < Xк, Xl+l = Xt для к>і>1 і X1 > $. Зауважимо, що Хк...Х1 не може бути пустою стрічкою, оскільки G не має е - правил.
Для доведення кроку індукції припустимо, що теорема дійсна і для п. Розглянемо вивід
$S$ =>X…Хк+1Аа1...аq
=>Xp...Xk+1Xk...X1a1…a =>Xp...Xj+1Yr....Y1Х...Х1а1…a
в якому на останньому кроці Xj замінюється стрічкою Yr...Y1. Тому Х,...,Х1 - термінали, до того ж випадок j=1 не виключається.
По припущенню індукції Xj+1 < Xj або Xj+1 = Xj . Тому Xj+1 < Yr за мови леми(1). Крім того Xj знаходиться в одному з трьох відношень з символом справа від нього. Таким чином, Y1 > X j-1 або Y1 > а1 при j=1. Oскільки Yr...Y1- права частина правила, то Yr = Yr-1 =...= Y . На завершення Xі+1 <Xi , або Xi+1 = Xi для р< і <j згідно з припущенням індукції, отже теорему доведено.
Наслідок . Кожна граматика простого передування є однозначною.
Доведення . Зауважимо , що для довільного відмінного від S правовивідного ланцюжка β попередній ланцюжок, для якого α=>β, визначається однозначно. Основу ланцюжка β можна однозначно визначити розглянувши даний ланцюжок зліва на право, поки не зустрінеться відношення (>), а потім повертатися назад до найближчого (<). Основа буде лежати між ними. Оскільки граматика простого передування зворотня, то не термінал до якого потрібно згорнути основу знаходиться однозначно. Таким чином, α визначається по β однозначно.
Алгоритм (1) побудови алгоритму "перенос - згортка " для граматик простого передування.
Вхід.
Граматика простого передування G = (N,T.,P,S), в якій правила занумеровані
числами від 1 до р.
Вихід.
А = (f,g), алгоритм розбору типу "перенос - згортка" для граматики G
Метод.
(1). Алгоритм А використовує символ $ в якості маркеру дна магазину і правого кінцевого маркеру вхідної стрічки.
(2). Функція переносу f залежить від верхнього символу магазину і самого лівого символу неопрацьованої частини вхідної стрічки. Тому задамо на f тільки на (N T {$}) х (T {$}), за винятком одного правила(правило (в)):
(а) f(X, а) = перенос, якщо X <а або X = а,
(б) f(X, а) = згортка, якщо X > а,
(в) f($Х,$) = допуск,
(г) f(X,a) = помилка в інших випадках.
(3). Функція згортки g залежить від верхньої частини магазинної стрічки, яка включає в себе основу іще один символ нижче неї. Частина стрічки яка залишилась неопрацьованою не впливає на g. Тому задамо g тільки на ( ($})*:
(а) g(Xt+iXkXk_i...Xi,e) = і, якщо Хк+і<Хк,, ХІ+1=Х, для k>j>l і А → ХкХк-1...Х1- правило з номером i
(б) g(a,e) = помилка в інших випадках.
Приклад (3).
Побудувати алгоритм розбору типу "перенос - згортка" A=(f,g), для граматики G з правилами
S → aSSb
S → c
Відношення передування для граматики G виведені в попередньому прикладі . Функцію переносу f можна вирахувати за допомогою матриці передування. Функція g визначається так:
g(XaSSb) = 1, якщо X є {S,a,$},
g(Xc) = 2 , якщо X є {S,a,$},
g{a} - помилка в інших випадках.
Для вхідної стрічки accb алгоритм А зробить таку послідовність кроків:
($,accb$,е) │(($a,ccb$.e)
│(($ac,cb$,.e)
│—r($аS,сb$,2)
│(($aSc,b$,2)
│—r($aSS,b$,22)
│(($aSSb,$,22)
│—r($S,$,221)
В конфігурації ($ac,cb$,e), наприклад, буде f(с.с) = згортка і g(ac,e)= 2 . Тому
($ac,cb$,e)│— ($aS.cb$,2 )
Для перевірки правильності подивимося як поведеться алгоритм А на стрічці acb, яка не належить мові L(G). Для такої стрічки алгоритм А зробить таку послідовність кроків:
($,acb,e) │(($a,cb$,e)
│(($ас,Ь$,е)
│—r($aS,b$,2)
│(($aSb,$,2)
│( помилка
В конфігурації ($aSb,$,2) буде f(b,$)= згортка. Оскільки $<a і а = S = Ь,то згортку можна зробити тільки, якщо aSb - права частина якогось правила. Оскільки такого правила немає, тому g(aSb,e) = помилка.
Отже, алгоритм (1) будує коректний алгоритм розбору типу "перенос - згортка" для граматики простого передування.
Граматики розширеного передування.
Відношення передування Вірта - Вебера визначене для пар символів можна розширити на пару стрічок. Визначимо розширене відношення передування - між стрічками з т символів і стрічками з п символів. Наше визначення орієнтовано на деякий алгоритм "перенос-згортка". Для того, щоб зрозуміти мотиви введення розширеного передування згадаємо дві ролі, які грають відношення передування в алгоритмі типу "перенос - згортка".
1)Нехай аХ -це т верхніх символів магазину і аω- наступні п вхідних символів. Якщо аХ ≤ аω або аХ = аω, то а необхідно перенести в магазин. Якщо аХ≥ аω, тоді необхідно зробити згортку.
2)Припустимо, що X ...X2X1 - ланцюжок в магазині і а1..аq - неопрацьована частина вхідної стрічки в той момент, коли викликається процедура згортки. Якщо основою являється Хк ...X1, тоді нам потрібно щоб було
Xm+jXm+j-1...Xj+1:=XJXj-1...X1α...an-j для k>j≥l і
Xm+k…Х к+1≤Xk...X1а1...ап_к..
Таким чином, процедура обробки для поворотної граматики розширеного передування аналогічна процедурі розбору граматики простого передування Вірта – Вебера, за виключенням того, що відношення передування між символами X і Y визначається стрічками аХ і Yβ, де а складається з т-1 символів, розміщених зліва від X , а β - з n-1 символів, розміщених справа від Y .
Символи переносяться в магазин до тих пір, поки між стрічкою наверху магазину і неопрацьованою частиною вхідної стрічки не зустрінеться відношення (≥). Тоді повертаємось по магазину назад, проходячи відношення (=) , доки не зустрінемо відношення (≤). Між (≤) і (≥) лежить основа.
Означення.
Нехай G = (N,Т,P,S) - приведена КС- граматика без е- правил. Визначимо відношення (m,n)- передування (≤),(=),(≥) на множині ({$})x({$}). Нехай $S$=>rXnXp-l...Xk+1Aa1…aq
=>rXpXp_r..Xk+]Xk...Xla1..aq
- довільний правий вивід. Тоді
(1). а ≤β, якщо а складається з останніх т символів стрічки XрХр-1…Хк+1 і або
а) β складається з п символів стрічки Xк ...ХхаК ...aq, або
б) Хк –термінал і β є FIRSTn(Xk...Xtaj...aq);
(2). а = β для всіх k>j≥1, що а складається з останніх т символів стрічки XpXp_r..XJ+] а6o
а) β складається з п символів стрічки XjXj-1...ХІа1...аq або
б) Хj-термінал і β є FIRST(Xj,ХJ-1...Xla1...аq); (3). XmXm_1...X, ≥ a1…an
Будемо говорити, що G- граматика (m,n)- передування , якщо G - приведена КС- граматика без е- правил і відношення передування (≤),(=),(≥) попарно не перетинаються. З Леми (1) очевидно слідує, що G- граматика передування тоді і тільки тоді якщо вона граматика (1,1)- передування.
Алгоритм(2) побудови відношення (m,n)- передування.
Вхід.
Приведена КС- граматика G = (N,Т,P,S) без е- правил.
Вихід.
Відношення (m,n)- передування (≤),(=),(≥) для граматики G .
Метод.
Почнемо з побудови £ всіх підстрічок ( підланцюжків ) довжини m+n, які можуть зустрітися в такій - стрічці аβи, що $S$=>*r аА ω=>raβω і и= FIRST(ω). Це здійснюється так:
(1).Покладемо £ = {$S$, $S$}. Ці дів стрічки рахуються "нерозгляпутими".
(2). Якщо δ- нерозглянута стрічка із £ , "розглянемо" її викопавши наступні дві операції.
а)Якщо δ не має вигляду аАх, де │x│ ≤ п, тоді нічого не робимо
б) якщо δ = аАх, │x│ ≤ п і А є X , то добавити до £ , а якщо їх ще не має там, то стрічки γ, для яких в Р найдеться таке правило А →β, що γ - підстрічка довжини т+n стрічки аβ х. Зауважимо, що так як G- приведена граматика, то │аβ х│ ≥ т + п.
(3). Повторити дію (2), доки в £ не залишиться нерозглянутих стрічок. По множині £ побудуємо відношення (≤),(=),(≥)
(4). Для кожної стрічки аАγ з £ , для якої │а│ = m і для кожного правила А →β поставимо а <δ, де δ- перші п символів стрічки βγ.
(5). Для кожної стрічки аАγ з £ , для якої │а│ = m і для кожного правила А →βXYβ з Р покладемо δ =δ, де δ - останні т символів стрічки аβX, а δ-перші п символів стрічки Yβγ,
(6). Для кожної стрічки аАω з £, для якої │а│ = n і для кожного правила А →β з Р покладемо δ ≥ ω, де δ - останні т символів стрічки аβ .
Приклад (4).
Розглянемо граматику G з правилами S→0Sll|011
Таблиця відношень(1,1) передування для даної граматики
S
0
1
$
S
=
0
=
≤
=
1
≥,=
≥
$
≤
Як бачимо дана граматика не є граматикою передування.
За допомогою даного алгоритму порахуємо для G відношення передування. Почнемо з обрахунків £ . Спочатку £ = {$S$,$$S}. Розглянемо $S$ , додаючи до £ стрічки $0S, 0S1, SI І, 11$ (це всі підстрічки довжини 3 стрічки $0S11$) і $01, 011(підстрічки довжини З стрічки $0S11$). Розгляд стрічки $$S приводить до добавлення $$0, розгляд $0S, додає $00, 00S та 001, розгляд 0S1 додає 111, і розгляд 00S додає 000. Це всі елементи множини £ .
Щоб побудувати ≤, розглянемо стрічки з £ з S на правому кінці. Отримаємо $$≤0, $0≤ 0 і 00≤0. Для побудови = знов розглянемо такі ж стрічки і найдемо $0 = S, 0S = 1, SI = 1, $0 = 1, 0І = 1, 00 = S i 00 = 1.
Щоб побудувати ≥, розглянемо стрічки з £ в яких S в середині. З $S$ отримаємо 11 ≥$, а з 0SI отримаємо 11 ≥1.
Відношення (2,1) передування для граматики G наведенні нижче. Стрічки довжиною 2, які не належать області визначення відношень (≤),(=),(≥) тут опущено.
Таблиця відношень (2,1) передування
S
0
1
$
$ $
≤
$ 0
=
≤
=
0S
=
00
=
≤
=
01
=
S1
=
Оскільки конфліктів між відношеннями (2,1) передування немає ,годі G - граматика (2,1) передування 11
≥
≥
Оскільки конфліктів між відношеннями (2,1) передування немає ,годі G - граматика (2,1) передування.
Граматики слабкого передування
Багато граматик, які зустрічаються звісно не є граматиками простого передування, і спроби знайти для даної мови граматику простого передування часто приводять до появи досить незграбних граматик. Тому можна розширити клас граматик , які аналізуються методом передування, послабивши обмеження, що відношення (≤),( =) не повинні перетинатися.
Відношення (≥) як і раніше будемо використовувати для локалізації правого кінця основи. Тоді для локалізації лівого кінця можна використовувати праві частини правил, підшукуючи в них таку, яка співпаде з символами, які стоять безпосередньо зліва від правого кінця основи. Це не набагато важча робота, ніж розбір методом простого передування. Під час розбору для граматики простого передування після виділення основи все одно необхідно визначити, яке саме правило використати для згортки, так що ці символи все одно прийдеться розглядати.
Для того, щоб дана схема розбору працювала, необхідно вміти визначити, яке правило необхідно використати в тому випадку коли права частина одного правила являється суфіксом правої частини другого правила. Клас граматик для яких дане рішення виявляється правильним, утворюють клас граматик слабого передування.
Означення.
Нехай G = (N,Т,P,S) - приведена КС- граматика без е- правил. Назвемо G граматикою слабкого передування ,якщо:
1) відношення (≥) не перетинається з об’єднанням відношень ( ≤) і (=) .
2) для А → аХβ і В → β з Р , де X є , не виконується жодне з X≤B чи X = В.
Приклад (5)
Прикладом граматики слабкого передування може бути така граматика з правилами E→ E+T|+T|T
T →T*F |F
F→ (E)|а
Матриця передування для даної граматики
E
T
F
а
(
)
+
*
$
E
=
=
T
≥
≥
=
≥
F
≥
≥
≥
≥
а
≥
≥
≥
≥
(
≤,=
≤
≤
≤
≤
≤
)
≥
≥
≥
≥
+
≤,=
≤
≤
≤
*
≤
≤
$
≤
≤
≤
≤
≤
≤
Зауважимо, що суперечності виникають тільки між відношенням (≤) і (=), тому умова (1) визначення граматики слабкого передування задовольняється. Перевіримо тепер умову (2). Розглянемо три правла E→ E+T, E→+T і E→T. З матриці передування бачимо, що між E і E, а також між + і E немає жодного відношення передування. Отже ці три правила не суперечать умові (2). Решту правил, де одна права частина служить суфіксом іншій(T →T*F і T →F ), а між * і Т немає відношень передування, то і тут умова (2) не порушується. Отже, G- граматика слабкого передування.
Лема (2).
Нехай G — (N,T,P,S) - граматика слабкого передування і Р містить правило В →β. Нехай $S$=>rγCω=>rδXβω. Якщо існує правило A →αXβ, тоді останнім в даному виводі використовувалось не правило В →β.
Доведення. Доведення побудуємо від супротивного. Припустимо, що С = В і γ = δХ . Використавши теорему (1) до виводу S=>*yCω, отримаємо X <В а6о X = В. Це слідує з того, що основа стрічки уСω закінчується десь правіше символу С і це означає, що С - один із символів Xj теореми (1). Тоді зразу порушується умови слабого передування.
Лема (3).
Нехай G = (N,T,P,S) - граматика слабого передування і Р містить правило A →αXβ , граматика G поворотна. Якщо правило виводу виду A →αXβ не існує, тоді в виводі $S$=>rγCω=>rδXβω має бути правило С = В і γ = δX (тобто останнім використовується правило В →β).
Доведення. Очевидно, що на останньому кроці замінюється символ С. Лівий кінець основи стрічки δXβω не може бути лівіше символа X, оскільки не має правила A →αXβ . Якщо основа закінчується десь правіше першого символу стрічки β, то порушується лема(2), в якій В →β відіграє роль правила A →αXβ . Саме тому основа - стрічка β і потрібний результат слідує з поворотності граматики G .
Отже, сутність алгоритму розбору поворотних граматик слабого передування заключається в наступному. Ми продивляємось правовиводиму стрічку зліва на право доти, поки вперше не зустрінемо відношення (>) . Це відношення вказує на правий кінець основи. Потім по одному розглядаємо символи зліва від (>). Припустимо, що існує правило В →β і зліва від (>) знаходиться стрічка Хβ. Якщо правила А → аХβ не існує, тоді згідно з лемою(3) β- основа. Якщо ж таке правило існує, тоді згідно леми(2) правило В →β неможливо використати. Отже рішення про згортку β можна приймати зчитавши ії лише один символ зліва від β.
Алгоритм(3) побудови типу "перенос - згортка" для граматик слабкого передування.
Вхід.
Поворотна граматика слабого передування G = (N,T,P,S), правила якої занумеровані числами від 1 до р.
Вихід.
А = (f,g) алгоритм розбору типу "перенос - згортка" для граматики G.
Метод.
Побудова аналогічна тій, яка використовується в попередньому алгоритмі. Функція перенос f визначається відношенням передування:
f(X,a) = перенос, якщо X ≤а або X = а.
f(X,a) = згортка, якщо Х≥а.
f($X,$) =допуск,
f(X,a) = помилка, в усіх інших випадках.
Функція згортки g визначається так, щоб при згортці використовувалось саме найдовше з доступних правил:
(5) g(Xβ)=i, якщо В →β - правило з Р з номером і в Р не має правила виду А→аХβ,
(6) g(a) = помилка, в усіх інших випадках.
Припустимо, що в граматиці є конфлікт типу X = Y і X > Y. Так як X = Y , то в правій частині одного або декількох правил зустрічається під стрічка X Y, якщо в такому правилі замінній X новим нетерміналом А, то X = Y пропаде і тим самим конфлікт буде вичерпано. А для збереження еквівалентності граматик додамо до нової граматики правило А →Х. Якщо Х не являється правою частиною іншого правила, то зберігається поворотність граматики.
За допомогою деяких перетворень можна видалити з граматики конфлікти, які існують в ній між відношеннями передування. Такі перетворення дозволяють перетворити задану граматику, яка не володіє необхідними властивостями передування, в еквівалентну граматику (1,1) передування або граматику слабкого передування.
Припустимо, що в граматиці є конфлікт X = Y і X ≥Y. Так як X = Y , то в правій частині одного або декількох правил зустрічається підстрічка XY. Якщо в такому правилі замінити X новим нетерміналом А, то X = Y пропаде, чим конфлікт буде вичерпано. А для збереження еквівалентності граматик додамо до нової граматики правило А→Х. Якщо Х не являється правою частиною іншого правила то зберігається і поворотність граматики.
Приклад (6).
Розглянемо граматику G з правилами S→0S11| 011
В прикладі (4) ми побачили, що G не граматика простого передування тому, що 1 = 1 і 1≥1. Але, якщо в кожне правило замість правої одиниці поставити новbq нетермінал .A і додати правило А→1, то ми отримаємо граматику простого передування G' з правилами
S →0SA1|0A1
А →1
Тоді відношення передування для даної граматики матимуть такий вигляд
S
А
0
1
$
S
=
≤
А
=
0
=
=
≤
≤
1
≥
≥
$
≤
Аналогічними перетвореннями можна усувати конфлікти типу X≥Y,X≤Y.
Приклад(7).
Розглянемо граматику G з правилами
E→E+T|T
T→T*F| F
F→ a|(E) |a (L )
L→L, E|E
G не є граматикою слабкого передування, так як Е=) і Е≥). Можна було б усунути цей конфлікт замінивши Е в правилі F→ (E) на Е' і додавши правило Е'→ E. Але тоді виявилося би два правила з правою частиною Е. Якщо ж усунути з G правило F→ a (L ), зробивши підстановку замість L, то отримаємо еквівалентну граматику G з наступними правилами
E→E+T|T
T→T*F| F
F→ a|(E) |a (L, Е ) |a (L )
L→L, E|E
Так як L не зустрічається зліва від ), в цій граматиці уже немає Е≥). Отже G' – граматика слабкого передування.
Алгоритм(4) переходу від оборотного слабкого передування до простого передування.
Вхід
Поворотна граматика слабого передування G = (N,Т, P,S).
Вихід. Граматика простого передування G' для якої L(G')= L(G).
Метод.
(1) припустимо, що в найшлись такі X i Y, що X = Y і X ≤Y, для граматики G. Заберемо з Р кожне правило виду А→aXYβ і поміняємо його на А→aX[Yβ ], де [Yβ] - новий нетермінал.
(2)для кожного символу [Yβ] , введеного на кроці (1), поміняємо правило виду В → Yβ на В→[Yβ ] і додамо [Yβ →Yβ .
(3) повторяємо крок (1) стільки раз ,скільки він буде застосовуватись.
Приклад (8).
Прикладом граматики слабкого передування може послужити граматика G з правилами
E→ E+T|+T|T
T →T*F |F
F→ (E)|а
За допомогою алгоритму (4) ми можемо її перетворити і отримати граматику G' з такими правилами
E→ E+[T]|+[T]|[T]
T →T*F |F
F→ ([E)]|а
[T] →T
[E)]→E)
Тоді відношення передування для граматики G' буде мати вигляд
Е
Т
F
[T]
[E)]
a
(
)
+
*
$
E
=
=
T
≥
≥
=
≥
F
≥
≥
≥
≥
[Т]
≥
≥
≥
[Е)]
≥
≥
≥
≥
а
≥
≥
≥
≥
(
≤
≤
≤
≤
=
≤
≤
≤
)
≥
≥
≥
≥
+
≤
≤
=
≤
≤
*
=
≤
≤
$
≤
≤
≤
≤
≤
≤
≤
Отже граматика G' є граматикою простого передування Література
А. Ахо, Дж. Ульман. Теорія синтаксичного аналізу, переводу і компіляції, том 1,2. Москва «Мир», 1978.
В.Н. Лебедев Введение в системы программирования. Москва «Статистика», 1984.
Д. Грис. Конструирование компиляторов для цифровых вычеслительных машин.-1975.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора