Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Курсова робота
Предмет:
Математика
Група:
ПМ-31
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
кафедра прикладної математики
КУРСОВА РОБОТА
з курсу дискретної математики на тему:
«Граматики передування. Алгоритм типу «перенос-згортка». Граматики простого, розширеного та слабкого передування»
Анотація
У даній курсовій роботі розглянуто один з класів КВ – граматик, а саме – граматики передування. Дано загальну характеристику цього класу граматик, нижче розглянуто основні типи граматик передування, а саме – граматики простого, розширеного та слабкого передування.
Також розглянуто алгоритм типу «перенос-згортка», що дає можливість побудувати розпізнавач стрічок та встановити їх належність введеній граматиці. Крім того розглянуто відношення передувань Вірта-Вебера – що дають можливість зберігати інформацію про зв’язки між символами в граматиці, також показана різниця між граматиками простого, розширеного та слабкого передування, різниця в реалізації алгоритму «перенос-згортка» для кожного з цих типів.
На сам кінець – наведено реалізацію алгоритму «перенос-згортка» - код програми, що перевіряє належність вхідної стрічки до введеної граматики.
Зміст
Титульна сторінка 1
Анотація 2
Зміст 3
Вступ 4
Граматики. Основні характеристики. КВ – граматики 5
Граматики передування 6
Алгоритм «перенос-згортка» 8
Граматики простого передування 11
Алгоритм "перенос - згортка " для граматик простого передування 15
Граматики розширеного передування 17
Побудова відношень (m,n)- передування 19
Граматики слабкого передування 21
Алгоритм "перенос-згортка" для граматик слабкого передування. 24
Алгоритм переходу від оборотного слабкого передування до простого передування 26
Висновок 28
Додаток(текст програми) 29
Список використаної літератури 30
Вступ
У спілкуванні людини і машини (комп'ютера) існують природні труднощі. Машини оперують бітами і регістрами, а люди користуються природними мовами або користуються певною системою позначень (наприклад, мова математичних формул). Щоб спілкування з машиною стало можливим, людина одержує інструкцію для користувача, у якій пояснюються всі допустимі мовні конструкції та значення, а для комп'ютера розробляється програмне забезпечення, за допомогою якого він може сприймати послідовності бітів для позначення команд або програми, написані на деякій штучній мові, і перекладати їх у внутрішні бітові структури.
Програму для обчислювальної машини, що дозволяє їй «розуміти» директиви і речення вхідної мови, яку використовує програміст, будемо називати «мовним процесором». Розрізняють два типи мовних процесорів: інтерпретатори і транслятори. Різниця між ними полягає в тому, що інтерпретатор аналізуючи об’єкт програми – одночасно виконує відповідні дії, а транслятор – формує так званий об’єктний код, який пізніше виконується після остаточного формування.
Першим етапом трансляції вхідної програми є лексичний аналіз(сканування). Сканер проглядає літери вхідної програми зліва направо і будує символи (лексеми, слова, атоми) програми − цілі числа, ідентифікатори, службові слова, двосимвольні розділювачі. Символи передаються після цього на обробку фактичному аналізатору (синтаксичному).
Перед синтаксичним аналізатором стоять два основні завдання: перевірити правильність конструкцій програми, яка представляється у вигляді вже виділених слів вхідної мови, і перетворити її у вигляд, зручний для подальшої семантичної обробки і генерації коди. Іншими словами, на етапі синтаксичного аналізу потрібно встановити, чи має ланцюжок лексем структуру, задану синтаксисом мови, а також зафіксувати цю структуру. Отже, знову треба вирішувати задачу розбору: даний ланцюжок лексем, і треба визначити, чи виводиться вона в граматиці, що визначає синтаксис мови. Проте структура синтаксису мови, представленої у вигляді таких конструкцій як: вирази, описи, оператори і тому подібне, складніша, ніж структура лексем. Для опису синтаксису мов програмування використовують такі структури як граматики, а конкретніше один з класів – граматики передування, для яких існує досить ефективний алгоритм розбору під назвою «перенос-згортка» .
Граматики. Основні характеристики. КВ – граматики
Мова L – це множина рядків скінченої довжини у заданому скінченому алфавіті. Як описати мову в тому випадку, коли вона нескінченна. Якщо довжини всіх рядків обмежені, то L складається із скінченого числа рядків і можна скласти список всіх рядків з L. Однак для багатьох мов не можна або небажано встановити верхню границю припустимої довжини рядку мови. Такі мови не можна визначити переліком всіх рядків. Необхідний опис мови повинен бути скінченим, у той час, як мова може бути нескінченною. Відомо кілька таких способів опису мов. Один з них полягає у використанні системи, що називається граматикою.
Для кожної граматики визначають дві скінченні множини, що не перетинаються: множина T термінальних символів і множина N не термінальних символів.
З термінальних символів утворюються рядки мови, яка визначається, це означає, що множина термінальних символів складає алфавіт мови.
Не термінальні символи використовуються як допоміжні або проміжні у процедурах побудови рядків мови, але вони не входять до остаточного виразу.
Серцевину граматики складає скінчена множина продукцій.
Продукція – це упорядкована пара рядків, першим елементом якої є будь-який рядок, складений із символів алфавіту , причому цей рядок обов’язково містить хоча б один не термінальний символ. Другим елементом пари є будь-який рядок, що складений із символів алфавіту . Множина продукцій P описує процес породження рядків мови.
Граматикою називається структура G=(N, T, P, S), де
N – скінчена множина не термінальних символів;
T – неперетинна з N скінчена множина термінальних символів;
P – множина продукцій – скінченна підмножина множин ;
S – початковий символ з N.
Граматики можна класифікувати за виглядом їх продукцій. Така класифікація називається ієрархією Хомського.
Граматика називається контекстно вільною(КВ), якщо кожна продукція з P має вигляд , де .
Один з підкласів КВ – граматик є граматики передування.
Граматики передування
КВ-граматики діляться на класи відповідно до структури їх правил. У кожному з класів накладаються додаткові обмеження на допустимі правила граматики. Одним з таких класів є клас граматик передування.
Принцип організації розпізнавача вхідних ланцюжків мови, заданої граматикою передування, грунтується на тому, що для кожної впорядкованої пари символів в граматиці встановлюється деяке відношення, що називається відношенням передування. В процесі розбору вхідного ланцюжка порівнюється поточний символ вхідного ланцюжка з одним з символів, що знаходиться на верхівці стека. В процесі порівняння перевіряється, яке з можливих відношень передування існує між цими двома символами.
Залежно від знайденого відношення виконується або перенесення або згортка. За відсутності відношення передування між символами алгоритм сигналізує про помилку. Завдання полягає в тому, щоб мати можливість несуперечливим способом визначити відношення передування між символами граматики. Якщо це можливо, то граматика може бути віднесена до одного з класів граматик передування.
Ключ для розуміння методу розбору по відношеннях передування дає визначення відношення •> між символами граматики, які при перегляді зліва на право праволінійного ланцюжка αβω, де β - основа, вперше виявилось виконаним для останнього символу ланцюжка β,і першого символу ланцюжка ω.
Якщо для розбору використовується алгоритм типу «перенос – згортка», то кожний раз, коли між верхнім символом магазину і першим із неопрацьованих вхідних символів виконується відношення •>, приймається рішення про згортку; в протилежному випадку робиться перенос.
Таким чином за допомогою відношення •> локалізується правий кінець основи праволінійного ланцюжка. Локалізація лівого кінця основи і визначення необхідної згортки виконується різними способами, в залежності від використовуваного типу передування.
Техніка аналізу, яка базується на так званому «простому передуванні» використовує для виділення основи праволінійного ланцюжка αβω три відношення передування: <•, •>, =•, якщо β — основа, то між усіма суміжними символами ланцюжка α виконується відношення <• або =•.Між останнім символом ланцюжка α і першим символом ланцюжка β виконується відношення <•, між суміжними символами основи – відношення =• і між останнім символом ланцюжка β і першим символом ланцюжка ω – відношення •>.
Таким чином, основу ланцюжка праволінійної граматики передування можна виділити, переглядаючи даний ланцюжок зліва на право доти, поки вперше не зустрінеться відношення •>. Для знаходження лівого кінця основи необхідно повертатись назад, доки не зустрінеться відношення <• . Ланцюжок який знаходиться між відношеннями <• і •> буде основою. Якщо граматика допускається зворотною, то основу можна однозначно згорнути. Цей процес продовжується до тих пір, поки вхідна стрічка не згорнеться до першого символу.
Існує декілька видів граматик передування. Вони розрізняются по тому, які відношення передування в них визначені і між якими типами символів (термінальними або нетермінальними) можуть бути встановлені ці відношення. Крім того, можливі незначні модифікації функціонування самого алгоритму «перенос-згортка» в розпізнавачах для таких граматик (в основному на етапі вибору правила для виконання згортки, коли можливі неоднозначності).
Виділяють наступні види граматик передування:
простого передування;
розширеного передування;
слабкого передування;
змішаній стратегії передування;
операторного передування.
Алгоритм «перенос-згортка». Формальне визначення.
Нехай G = (N,Т,P,S) - КВ - граматика, правила якої занумеровані числами від 1 до р. Алгоритмом типу " перенос - згортка " для граматики G назвемо пару функцій , де f називається функцією переносу, a g - функцією згортки. Функції f та g визначаються так:
(1) f відображає в множину {перенос, згортка, помилка, допуск}, де ,a $ - новий символ, кінцевий маркер.
(2) g відображає в множину (1, 2, ..., p, помилка} при умові, що якщо , то права частина i-го правила являється суфіксом ланцюжка α.
Алгоритм типу " перенос - згортка " використовує вхідну стрічку, читаючи її з ліва на право, і магазин. На основі того, що знаходиться в магазині і залишилось не опрацьованим на вході, функція f вирішує, перенести даний вхідний символ в магазин чи викликати процедуру згортки. Якщо виконується останнє рішення, то функція g вирішує, яку згортку зробити.
Роботу алгоритмом типу " перенос - згортка " можна розглядати в термінах конфігурацій трійок виду
де
(1)- те що знаходиться в магазині, до того ж - верхній символ, і $ слугує маркером дна магазину.
(2) - частина вхідної стрічки, яка залишилась неопрацьованою, - поточний вхідний символ, $- служить правим кінцевим маркером для входу.
(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},
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)
Продовжуючи таким чином алгоритм A виконає таку послідовність кроків:
($,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 символі від основи, яку згортають, і від одного чи двох наступних вхідних символів.
Граматики простого передування
Граматикою простого передування називають таку приведену (без циклів, безплідних і недосяжних символів і ε-правил) КВ - граматику G(N, T, P, S), V=T(N, в якій:
1. Для кожної впорядкованої пари термінальних і нетермінальних символів виконується не більше ніж одне з трьох відношень передування:
Вi =• Вj (( Bi, Bj ( V), якщо і тільки якщо ( правило A(xBiBjy ( P, де A(N, x,y(V*;
Вi <• Вj (( Bi, Bj ( V), якщо і тільки якщо ( правило A(xBiDy ( P і вивід D(*Sjz, где A,D(N, x,y,z(V*;
Вi •> Bj (( Bi, Bj ( V), якщо і тільки якщо ( правило А(хСВjу ( P і вивід C(*zBi або ( правило A(xCDy ( P і виводи C(*zBi і D(*Bjw, де A,C,D(N, x,y,z,w(V*.
2. Різні правила в граматиці мають різні праві частини (тобто в граматиці не повинно бути двох різних правил з однією і тією ж правою частиною).
Аналізуючи вхідний ланцюжок(стрічку) методом передування, зручно додавати до неї лівий та правий кінцеві маркери. В якості такого маркера візьмемо символ $ і будемо вважати, що $<•X для всіх X, для яких S –>Xα, і Y•>$ для всіх Y, для яких S–>aY.
Відношення передування єдине для кожної впорядкованої пари символів. При цьому між якими-небудь двома символами може і не бути відношення передування - це означає, що вони не можуть знаходитися поряд ні в одному елементі розбору синтаксично правильного ланцюжка. Відношення передування залежать від порядку, в якому стоять символи, і в цьому сенсі їх не можна плутати із знаками математичних операцій - вони не володіють ні властивістю комутативності, ні властивістю асоціативності. Наприклад, якщо відомо, що Вi •> Bj, то не обов'язково виконується Bj <• Вi (тому знаки передування іноді позначають спеціальною крапкою: =•, <•, •>).
Для граматик простого передування відомі наступні корисні властивості:
всяка граматика простого передування є однозначною;
легко перевірити, є чи ні довільна КВ - граматика граматикою простого передування (для цього досить перевірити розглянуті вище властивості граматик простого передування або скористатися алгоритмом побудови матриці передування, який розглянутий далі).
Як і для багатьох інших класів граматик, для граматик простого передування не існує алгоритму, який би міг перетворити довільну КВ - граматику в граматику простого передування (або довести, що перетворення неможливе).
На підставі відношень передування будують матрицю передування граматики. Рядки матриці передування позначаються першими (лівими) символами, стовпці - другими (правими) символами відносин передування. У клітки матриці на перетині відповідного стовпця і рядка поміщаються знаки відносин. При цьому порожні клітки матриці говорять про те, що між даними символами немає жодного відношення передування.
Матрицю передування граматики складно побудувати, спираючись безпосередньо на визначення відносин передування. Зручніше скористатися двома додатковими множинами - множиною крайніх лівих і множиною крайніх правих символів щодо нетермінальних символів граматики G(N, T, P, S), V = T(N. Ці множини визначаються таким чином:
L(A) = {X | ( A(*Xz}, A(N, X(V, z(V* — множина крайніх лівих символів щодо нетермінального символу А (ланцюжок z може бути і порожнім ланцюжком);
R(A) = {X | ( A(*zX}, A(N, X(V, z(V* — множина крайніх правих символів щодо нетермінального символу А.
Іншими словами, множина крайніх лівих символів щодо нетермінального символу А - це множина всіх крайніх лівих символів в ланцюжках, які можуть бути виведені з символу А. Аналогічно, множина крайніх правих символів щодо нетермінального символу А - це множина всіх крайніх правих символів в ланцюжках, які можуть бути виведені з символу А. Тоді відношення передування можна визначити так:
Вi =• Bj (( Bi, Bj ( V), якщо ( правило A(xBiBjy ( Р, де A ( N, x,y(V*;
Вi <• Bj (( Bi, Bj ( V), якщо ( правило A(xBiDy ( Р и Bj ( L(D), де A,D(N, x,y(V*;
Вi •> Bj (( Bi, Bj ( V), якщо ( правило A(xCBjy ( Р и Bi(R(C) або ( правило A(xCDy ( Р і Bi(R(C), Bj(L(D), де A,C,D(N, x,y(V*.
Таке визначення відносин зручніше на практиці, оскільки не вимагає побудови виводів, а Таке визначення відносин зручніше на практиці, оскільки не вимагає побудови виводів, а множини L(A) та R(A) можуть бути побудовані для кожного нетермінального A(N граматики G(N, T, P, S), V = T(N по по дуже простому алгоритму.
Крок 1. ( A(N:
Ro(A) = {X | А(уХ, X(V, y(V*}, L0(A) = {X | A(Xy, X(V, y(V*}, i := 1.
Для кожного нетермінального символу А шукаємо всі правила, що містять А в лівій частині. У множину L(A) включаємо найлівіший символ з правої частини, а в множину R(A) - крайній правий символ з правої частини. Переходимо до кроку 2.
Крок 2. ( A(N:
Ri(A) = Ri-1(A) ( Ri-1(B), ( В ( (Ri-1(A) ( N),
Li(А) = Li-1(A) ( Li-1(B), ( В ( (Li-1(A) ( N).
Для кожного нетермінального символу А: якщо множина L(A) містить нетермінальні символи граматики А', А'', ..., то його треба доповнити символами, що входять у відповідну множину L(A'), L(A") ... і що не входять в L(A). Ту ж операцію треба виконати для R(A).
Крок 3. Якщо ( A(N: Ri(A) ( Ri-1(A) або Li(A) ( Li-1(A), то i:=i+l повернутись до кроку 2, інакше побудова закінчена: R(A) = Ri(A) и L(A) = Li(A).
Після побудови множин L(A) і R(A) за правилами граматики створюється матриця передування. Матрицю передування доповнюють символом $ (початок і кінець ланцюжка).
Матриця передування слугує основою для роботи розпізнавача мови, заданого граматикою простого передування.
Приклад (2)
Граматика G складається з правил S→aSSb|c.
L(G)
R(G)
S
а,с
b,c
Таблиця відношення передування
S
а
b
с
$
S
=•
<•
=•
<•
а
=•
<•
<•
b
•>
•>
•>
•>
с
•>
•>
•>
•>
$
<•
<•
Оскільки в кожній комірці записано не більше одного відношення передування, то G- граматика передування.
Лема (1).
Нехай G = (N,Т,P,S) - приведена КВ- граматика без е- правил.
Якщо X <• А або X =• А і А → Yα міститься в Р, то X <• Y
Якщо А <• а, А =• а або А •> а і А → aY міститься в Р, то Y•> а
Доведення. Якщо А < а, тоді існує така права частина β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 не має ε - правил. □
Для доведення кроку індукції припустимо, що теорема дійсна і для n. Розглянемо вивід
$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 згідно з припущенням індукції, отже теорему доведено.
Алгоритм "перенос - згортка " для граматик простого передування
Вхід.
Граматика простого передування 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(Xk+1XkXk-1...X1,e) = і, якщо Хк+1<•Хк,, Хj+1=• Хj, для k>j>l і А → ХкХк-1...Х1- правило з номером i. Зауважимо що функція згортки g виконується лише тоді коли Х1•> а;
(б) 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=•b,то згортку можна зробити тільки, якщо aSb - права частина якогось правила. Оскільки такого правила немає, тому g(aSb,e) = помилка.
Граматики розширеного передування
Відношення передування Вірта - Вебера визначене для пар символів можна розширити на пару стрічок. Визначимо розширене відношення передування - між стрічками з m символів і стрічками з n символів. Наше визначення орієнтовано на деякий алгоритм "перенос-згортка".
Для того, щоб зрозуміти мотиви введення розширеного передування згадаємо дві ролі, які грають відношення передування в алгоритмі типу "перенос - згортка".
(1) Нехай аХ -це m верхніх символів магазину і аω- наступні n вхідних символів. Якщо аХ <• аω або аХ =• аω, то а необхідно перенести в магазин. Якщо аХ•> аω, тоді необхідно зробити згортку.
(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β, де а складається з m-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). а <•β, якщо а складається з останніх m символів стрічки XрХр-1…Хк+1 і або β складається з n символів стрічки Xк ...ХхаК ...aq.
(2). а =•β для всіх k>j≥1, що а складається з останніх m символів стрічки XpXp_r..XJ+] абo β складається з n символів стрічки XjXj-1...ХІа1...аq.
(3). XmXm_1...X, •> a1…an.
Говоритимемо, що G- граматика (т, п) - передування, якщо G - приведена КВ-граматика без ε -правил і відношення <• =• і •> попарно не перетинаються. З леми попереднього розділу з очевидністю випливає, що G - граматика передування тоді і тільки тоді, коли вона - граматика (1,1) -передування. Деталі, пов'язані з кінцевими маркерами, легко встановлюються. При п - 1 умови 1 і 2 не дають нічого нового.
Відмітимо також, що якщо перетин відношень <• і =• непорожній тільки за рахунок умов 1 і 2, все одно для такої граматики розширеного передування знайдеться алгоритм розбору типу „перенесення - згортка".
Розглянемо тепер алгоритм, що обчислює відношення розширеного передування. Його, очевидно, можна застосовувати і для обчислення відношень передування Вірта - Вебера.
Побудова відношень (m,n)- передування
Вхід.
Приведена КС- граматика G = (N,Т,P,S) без е- правил.
Вихід.
Відношення (m,n)- передування <•,=•,•> для граматики G .
Метод.
Почнемо з побудови £ всіх підстрічок довжини m + n, які можуть зустрітися в такій - стрічці аβu, що $S$(*r аА ω(raβω. Це здійснюється так:
(1).Покладемо £ = {$S$, $S$}. Ці дів стрічки рахуються "нерозглянутими".
(2). Якщо δ- нерозглянута стрічка із £ , "розглянемо" її виконавши наступні дві операції.
а)Якщо δ не має вигляду аАх, де │x│ < n, тоді нічого не робимо
б) якщо δ = аАх, │x│ < n і А є X , то добавити до £ , а якщо їх ще не має там, то стрічки γ, для яких в Р найдеться таке правило А→β, що γ - підстрічка довжини m+n стрічки аβх. Зауважимо, що так як G- приведена граматика, то │аβх│ > m + n.
(3). Повторити дію (2), доки в £ не залишиться нерозглянутих стрічок. По множині £ побудуємо відношення <•,=•,•>
(4). Для кожної стрічки аАγ з £ , для якої │а│ = m і для кожного правила А →β поставимо а<•δ, де δ- перші n символів стрічки βγ.
(5). Для кожної стрічки аАγ з £ , для якої │а│ = m і для кожного правила А→βXYβ з Р покладемо δ=•δ, де δ - останні m символів стрічки аβX, а δ- перші n символів стрічки Yβγ.
(6). Для кожної стрічки аАω з £, для якої │w│ = n і для кожного правила А →β з Р покладемо δ•>ω, де δ - останні m символів стрічки аβ .
Приклад (4).
Розглянемо граматику G з правилами S→0Sll|011
Так як 1•>1 та 1=•1 то G не є граматикою передування.
За допомогою даного алгоритму порахуємо для G відношення передування. Почнемо з обрахунків £ . Спочатку £ = {$S$,$$S}. Розглянемо $S$ , додаючи до £ стрічки $0S, 0S1, S11, 11$ (це всі підстрічки довжини 3 стрічки $0S11$) і $01, 011(підстрічки довжини З стрічки $0S11$). Розгляд стрічки $$S приводить до добавлення $$0, розгляд $0S, додає $00, і,
S
0
1
$
S
=•
0
=•
<•
=
1
•>,=•
•>
$
<•
на кінець, розгляд 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) передування для граматики G приведені в таблиці нижче.
Оскільки конфліктів між відношеннями (2,1) передування немає ,тоді G - граматика (2,1) передування.
S
0
1
$
$ $
<•
$ 0
=•
<•
=•
0S
=•
00
=•
<•
=•
01
=•
S1
=•
11
•>
•>
Алгоритм розбору типу „перенос-згортка" для оборотних граматик розширеного передування повністю аналогічний алгоритму для граматик простого передування, так що варто тільки коротко сказати про нього.
Перші п необроблених вхідних символів можна зберігати вгорі магазина. Якщо такими символами є ах ... ап і безпосередньо під ними в магазині розташований ланцюжок Хm...Х1, причому Хm..Х1=•a1...ап або Хт...Х1<•a1...ап, то треба зробити перенесення. Якщо ж Хт...Х1•>a1...ап, то робиться згортка. Щоб зробити згортку, треба так само, як в алгоритмі для граматик простого передування, повернутися назад, проходячи через відношення •=, у пошуках відношення <•.
Граматики слабкого передування
Багато граматик, які зустрічаються звісно не є граматиками простого передування, і спроби знайти для даної мови граматику простого передування часто приводять до появи досить незграбних граматик. Тому можна розширити клас граматик , які аналізуються методом передування, послабивши обмеження, що відношення <•, =• не повинні перетинатися.
Відношення •> як і раніше будемо використовувати для локалізації правого кінця основи. Тоді для локалізації лівого кінця можна використовувати праві частини правил, підшукуючи в них таку, яка співпаде з символами, які стоять безпосередньо зліва від правого кінця основи. Це не набагато важча робота, ніж розбір методом простого передування. Під час розбору для граматики простого передування після виділення основи все одно необхідно визначити, яке саме правило використати для згортки, так що ці символи все одно прийдеться розглядати.
Для того, щоб дана схема розбору працювала, необхідно вміти визначити, яке правило необхідно використати в тому випадку коли права частина одного правила являється суфіксом правої частини другого правила. Клас граматик для яких дане рішення виявляється правильним, утворюють клас граматик слабкого передування.
Ми обмежимось застосуванням найдовшого з застосованих правил. Клас граматик, для яких такі рішення є правильним, створюють граматики слабкого передування.
Означення.
Нехай G = (N,Т,P,S) - приведена КВ- граматика без ε - правил. Назвемо G граматикою слабкого передування ,якщо:
1) відношення •> не перетинається з об’єднанням відношень <• і =•.
2) для А → аХβ і В → β з Р , де X є , не виконується жодне з X<•B чи X=•В.
Приклад (5)
Прикладом граматики слабкого передування може бути така граматика з правилами
E→E+T|+T|T
T→T*F|F
F→(E)|а
Матриця передування для граматики G.
E
T
F
а
(
)
+
*
$
E
=•
=•
T
•>
•>
=•
•>
F
•>
•>
•>
•>
а
•>
•>
•>
•>
(
<•,=•
<•
<•
<•
<•
•>
)
•>
•>
•>
•>
+
<•,=•
<•
<•
<•
*
<•
<•
$
<•
<•
<•
<•
<•
<•
Зауважимо, що суперечності виникають тільки між відношенням <• і =•, тому умова (1) визначення граматики слабкого передування задовольняється. Розглянемо три правла 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β не існує, тоді в виводі $S$(rγCω(rδXβω має бути правило С = В і γ = δX (тобто останнім використовується правило В →β).
Доведення. Очевидно, що на останньому кроці замінюється символ С. Лівий кінець основи стрічки δXβω не може бути лівіше символа X, оскільки не має правила A →αXβ . Якщо основа закінчується десь правіше першого символу стрічки β, то порушується лема(2), в якій В →β відіграє роль правила A→αXβ. Саме тому основа - стрічка β і потрібний результат слідує з поворотності граматики G .□
Отже, сутність алгоритму розбору поворотних граматик слабкого передування в наступному. Ми продивляємось правовиводиму стрічку зліва на право доти, поки вперше не зустрінемо відношення •>. Це відношення вказує на правий кінець основи. Потім по одному розглядаємо символи зліва від •>. Припустимо, що існує правило В→β і зліва від •> знаходиться стрічка Хβ. Якщо правила А→аХβ не існує, тоді згідно з лемою(3) β - основа. Якщо ж таке правило існує, тоді згідно леми(2) правило В→β неможливо використати. Отже рішення про згортку β можна приймати зчитавши лише один символ зліва від β.
Таким чином, для кожної оборотної граматики слабкого передування можна побудувати алгоритм розбору типу «перенос-згортка».
Алгоритм "перенос-згортка" для граматик слабкого передування.
Вхід.
Поворотна граматика слабкого передування 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) = помилка, в усіх інших випадках.
За допомогою деяких перетворень можна видалити з граматики конфлікти, які існують в ній між відношеннями передування. Такі перетворення дозволяють перетворити задану граматику, яка не володіє необхідними властивостями передування, в еквівалентну граматику (1,1) передування або граматику слабкого передування.
Припустимо, що в граматиці є конфлікт типу X=•Y і X•>Y. Так як X=•Y , то в правій частині одного або декількох правил зустрічається підстрічка XY, якщо в такому правилі замінити X новим нетерміналом А, то X=•Y пропаде і тим самим конфлікт буде вичерпано. А для збереження еквівалентності граматик додамо до нової граматики правило А →Х. Якщо Х не являється правою частиною іншого правила, то зберігається поворотність граматики.
Приклад (6).
Розглянемо граматику G з правилами S→0S11| 011
В прикладі (4) ми побачили, що G не граматика простого передування тому що 1 =•1 і 1•>1. Але, якщо в кожне правило замість правої одиниці поставити новий нетермінал .A
S
А
0
1
$
S
=•
<•
А
=•
0
=•
=•
<•
<•
1
•>
•>
$
<•
і додати правило А→1, то ми отримаємо граматику простого передування G' з правилами
S→0SA1|0A1
А→1
Аналогічними перетвореннями можна усувати конфлікти типу X•>Y,X<•Y.
Алгоритм переходу від оборотного слабкого передування до простого передування
Вхід
Поворотна граматика слабкого передування 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)
Е
Т
F
[T]
[E)]
a
(
)
+
*
$
E
=•
=•
T
•>
•>
=•
•>
F
•>
•>
•>
•>
[Т]
•>
•>
•>
[Е)]
•>
•>
•>
•>
а
•>
•>
•>
•>
(
<•
<•
<•
<•
=•
<•
<•
<•
)
•>
•>
•>
•>
+
<•
<•
=•
<•
<•
*
=•
<•
<•
$
<•
<•
<•
<•
<•
<•
<•
Отже граматика G' є граматикою простого передування
Висновок
При створенні компіляторів виникає проблема синтаксичного аналізу – розпізнавання тексту програми, а саме чи належить та чи інша стрічка даній мові чи ні. Існує декілька методів такої перевірки, одним з них є алгоритм типу «перенос – згортка», що базується на визначенні так званих відношень передування між символами мови.
В даній курсовій роботі було розглянуто граматики передування та їх основні класи, а саме – граматики простого, розширеного та слабкого передування. Було розглянуто особливості кожного з цих класів та різниця в реалізації алгоритму «перенос-згортка» для кожного з цих класів. Нижче наведено текст програми – розпізнавача вхідних стрічок. Програма аналізує введену граматику, визначає чи є граматика граматикою передування, формує матрицю відношень передування, а далі перевіряє введену стрічку на належність заданій граматиці за алгоритмом «перенос-згортка».
Додаток(текст програми)
/******************************************************************/
/* */
/* Dodatok do kyrsovoji robotu "Gramatuku peredyvannja". */
/* Programa realizyje algorutm 'perenos-zfortka' */
/* perevirjaje nalezhnist' vvedenoji */
/* stri4ku do zadanoji gramatuku. */
/* */
/* Vukonav: stydent grypu PM-31 */
/* Ostap4yk Jyrij */
/* Pereviruv: Demkiv L.I. */
/* */
/******************************************************************/
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <windows.h>
#include <string.h>
#define rozmir 200
/*******************OPUS ZMINNUH***********************/
char M_prav[rozmir][rozmir], //Masuv pravul
M_neterm[rozmir], //Masuv neterminaliv
M_term[rozmir], //Masuv terminaliv
M_nts[2 * rozmir + 1], //Masuv terminalu+neterminalu+$
DividedRules[rozmir][rozmir], //Masuv rozdilenuh pravul po sumvoly '|'
Zgortka[rozmir], //Osnova w4o zgortaet'sja
L[rozmir][rozmir], //Masuv livovuvodumuh sumvoliv
R[rozmir][rozmir], //Masuv pravovuvodumuh sumvoliv
M_Virt_Weber[rozmir][rozmir], //Matrucja vidnowen' Virta-Webera
Str[rozmir], //Stri4ka w4o vvodut'sja dlja perevirku
DivRule[rozmir][rozmir], //Masuv podilenogo pravula po sumvoly '|'
Magazun[rozmir], //Magazun
ch; //Dopomizhnuj sumvol
int N, //Kil'kist' neterminaliv
T, //Kil'kist' terminaliv
PrRozbir[rozmir]; //Masuv poslidovnosti rozbory
bool pr, //Praporec'
gram_pered = 0; //Praporec' - 4u je gramatuka - gramatukojy peredyvannja...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора