Контекстно-вільна граматика (скорочено КВ-граматика) — формальна граматика типу 2 в ієрархії Чомскі.
Визначення
Контекстно-вільна граматика — це четвірка :
- та — скінченні множини, що не перетинаються
- — скінченна підмножина
Використовують такі назви: — множина нетермінальних символів, — множина термінальних символів, — множина правил виводу, — початковий символ. Правила записують як .
У лівій частині правила виводу має міститися одна змінна (нетермінальний символ). Формально має виконуватись: , де .
Розширенням КВ-граматик є стохастичні КВ-граматики. Правилам виведення співставляють ймовірність використання: де
Нормальні форми
Для КВ-граматик визначено різні нормальні форми. В нормальних формах Чомскі (НФЧ) скорочуюють праву частину правил виводу, тобто права частина може складатись або з одного термінального символу, або з двох нетермінальних. Якщо в лівій частині міститься початковий символ, права частина може породжувати порожнє слово. Існує алгоритм, який переводить довільну КВ-граматику в НФЧ.
Контекстно-вільна граматика визначена в (НФГ), якщо вона не породжує порожнього слова та права частина правил виводу починається з щонайбільше одного термінального символу, слідом за яким йдуть нетермінальні символи. Кожна КВ-граматика, яка не породжує порожнє слово, може бути перетворена в НФГ алгоритмом.
Породжена мова
Контекстно-вільні граматики породжують контекстно-вільні мови, тобто кожна КВ-граматика породжує КВ-мову, і для кожної КВ-мови існує КВ-граматика, що її породжує.
Контекстно-вільну мову , породжену КВ- граматикою , позначають , де:
Символом позначають послідовність правил виводу граматики , унаслідок застосування якої отримують слово мови . Також .
Контекстно-вільні мови можна розпізнати недетермінованим автоматом з магазинною пам'яттю. Якщо існує детермінований автомат, здатний розпізнати мову, її називають . Ця підмножина КВ-мов утворює теоретичну основу для синтаксиса багатьох мов програмування.
Контекстно-вільні мови можуть містити порожнє слово, наприклад, через правило виводу .
Властивості
Належність слова
Задача визначення належності слова КВ-мові, або визначення можливості породження слова КВ-граматикою, алгоритмічно розв'язна. Під час розв'язання цієї задачі можна побудувати дерево виводу. Його також називають деревом синтаксичного аналізу, а програму, яка його будує, — синтаксичним аналізатором. Для кожної КВ-граматики можна автоматично побудувати синтаксичний аналізатор (див. також та ). Часова складність для найгіршого випадку синтаксичного аналізу довільної КВ-граматики O. Для детермінованих КВ-граматик можна побудувати синтаксичний аналізатор, час роботи якого . Типовим прикладом застосування ефективних синтаксичних аналізаторів з лінійним часом роботи є синтаксичний аналіз вихідних текстів програм в компіляторі.
Якщо слово мови () в граматиці може бути отримане кількома різними способами, то таку граматику називають багатозначною. Синтаксичний аналізатор для багатозначної граматики може побудувати кілька різних дерев синтаксичного аналізу. Багатозначність не важлива для розв'язання задачі належності слова, але якщо різним деревам співставляють різне значення, то той самий текст може мати різні значення. Наприклад, однозначність граматики важлива для процесу компіляції, аби отримати правильний код.
Багатозначність
Задача розпізнавання багатозначності серед КВ-граматик алгоритмічно не розв'язна.. Однак існують способи перевірки на багатозначність або однозначність для деяких окремих випадків КВ-граматик.
Еквівалентність
Задача визначення еквівалентності граматик та , або породження ідентичних мов , алгоритмічно нерозв'язна.
Підмножина
Задача визначення чи породжена КВ-граматикою мова також може бути породжена іншою КВ-граматикою , тобто чи , алгоритмічно нерозв'язна.
Об'єднання
Об'єднання двох КВ-граматик () також КВ-граматика. Тобто, .
Перетин
Задача визначення належності перетину двох КВ-граматик до класу КВ-граматик алгоритмічно не розв'язувана.
Доповнення
Доповнення КВ-граматики не контекстно-вільне.
Приклади
Нехай — КВ-граматика
- складається з чотирьох правил виводу:
в граматиці можна отримати такою послідовністю застосування правил виводу:
, тут — дерево виведення. Корінь дерева та проміжні вузли позначені нетермінальними символами, а листи дерева позначені термінальними символами.
Таким чином, .
Слово де не належить до мови , оскільки нетермінальний символ не початковий, а всі слова утворені від початкового мають розташовуватися посеред термінальних та . Формально це записують:
Граматика не багатозначна.
Приклад багатозначності
Як приклад багатозначної граматики можна навести: .
- містить такі правила виводу:
До можна застосувати правила , та . Таким чином, — багатозначна.
Див. також
Посилання
- Schöning, 2001, S.21
- Alfred V. Aho and Jeffrey D. Ullman. The Theory of Parsing, Translation, and Compiling. Volume 1: Parsing. — Prentice-Hall, 1972. — .
- H. J. S. Basten. Ambiguity Detection Methods for Context-Free Grammars.
- Schöning, 2001, S.137
Література
- Uwe Schöning. Theoretische Informatik - kurzgefasst. — 4. — Spektrum Akademischer Verlag, 2001. — С. 13, 51. — .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Kontekstno vilna gramatika skorocheno KV gramatika formalna gramatika tipu 2 v iyerarhiyi Chomski Zmist 1 Viznachennya 2 Normalni formi 3 Porodzhena mova 4 Vlastivosti 4 1 Nalezhnist slova 4 2 Bagatoznachnist 4 3 Ekvivalentnist 4 4 Pidmnozhina 4 5 Ob yednannya 4 6 Peretin 4 7 Dopovnennya 5 Prikladi 5 1 Priklad bagatoznachnosti 6 Div takozh 7 Posilannya 8 LiteraturaViznachennyared Kontekstno vilna gramatika G displaystyle G nbsp ce chetvirka N T P S displaystyle N T P S nbsp S N displaystyle S in N nbsp N displaystyle N nbsp ta T displaystyle T nbsp skinchenni mnozhini sho ne peretinayutsya P displaystyle P nbsp skinchenna pidmnozhina N N T displaystyle N times N cup T nbsp Vikoristovuyut taki nazvi N displaystyle N nbsp mnozhina neterminalnih simvoliv T displaystyle T nbsp mnozhina terminalnih simvoliv P displaystyle P nbsp mnozhina pravil vivodu S displaystyle S nbsp pochatkovij simvol Pravila a b P displaystyle alpha beta in P nbsp zapisuyut yak a b displaystyle alpha rightarrow beta nbsp U livij chastini pravila vivodu maye mistitisya odna zminna neterminalnij simvol Formalno maye vikonuvatis a N b N T displaystyle alpha in N beta in N cup T nbsp de b 1 displaystyle beta geq 1 nbsp Rozshirennyam KV gramatik ye stohastichni KV gramatiki Pravilam vivedennya spivstavlyayut jmovirnist vikoristannya r P R displaystyle rho P rightarrow mathbb R nbsp de p r P r r p r 1 displaystyle sum p r in P r rho p r 1 nbsp Normalni formired Dlya KV gramatik viznacheno rizni normalni formi V normalnih formah Chomski NFCh skorochuyuyut pravu chastinu pravil vivodu tobto prava chastina mozhe skladatis abo z odnogo terminalnogo simvolu abo z dvoh neterminalnih Yaksho v livij chastini mistitsya pochatkovij simvol prava chastina mozhe porodzhuvati porozhnye slovo Isnuye algoritm yakij perevodit dovilnu KV gramatiku v NFCh Kontekstno vilna gramatika viznachena v normalnij formi Grejbah NFG yaksho vona ne porodzhuye porozhnogo slova ta prava chastina pravil vivodu pochinayetsya z shonajbilshe odnogo terminalnogo simvolu slidom za yakim jdut neterminalni simvoli Kozhna KV gramatika yaka ne porodzhuye porozhnye slovo mozhe buti peretvorena v NFG algoritmom Porodzhena movared Kontekstno vilni gramatiki porodzhuyut kontekstno vilni movi tobto kozhna KV gramatika porodzhuye KV movu i dlya kozhnoyi KV movi isnuye KV gramatika sho yiyi porodzhuye Kontekstno vilnu movu L displaystyle L nbsp porodzhenu KV gramatikoyu G displaystyle G nbsp poznachayut L G displaystyle L G nbsp de L G w w T S G w displaystyle L G w w in T S rightarrow G w nbsp Simvolom G displaystyle rightarrow G nbsp poznachayut poslidovnist pravil vivodu gramatiki G displaystyle G nbsp unaslidok zastosuvannya yakoyi otrimuyut slovo w displaystyle w nbsp movi L G displaystyle L G nbsp Takozh L G T displaystyle L G subset T nbsp Kontekstno vilni movi mozhna rozpiznati nedeterminovanim avtomatom z magazinnoyu pam yattyu Yaksho isnuye determinovanij avtomat zdatnij rozpiznati movu yiyi nazivayut determinovanoyu KV movoyu Cya pidmnozhina KV mov utvoryuye teoretichnu osnovu dlya sintaksisa bagatoh mov programuvannya Kontekstno vilni movi mozhut mistiti porozhnye slovo napriklad cherez pravilo vivodu S e displaystyle S rightarrow varepsilon nbsp Vlastivostired Nalezhnist slovared Zadacha viznachennya nalezhnosti slova KV movi abo viznachennya mozhlivosti porodzhennya slova w displaystyle w nbsp KV gramatikoyu algoritmichno rozv yazna 1 Pid chas rozv yazannya ciyeyi zadachi mozhna pobuduvati derevo vivodu Jogo takozh nazivayut derevom sintaksichnogo analizu a programu yaka jogo buduye sintaksichnim analizatorom Dlya kozhnoyi KV gramatiki mozhna avtomatichno pobuduvati sintaksichnij analizator div takozh generator sintaksichnih analizatoriv ta CYK algoritm Chasova skladnist dlya najgirshogo vipadku sintaksichnogo analizu dovilnoyi KV gramatiki O n 3 displaystyle n 3 nbsp Dlya determinovanih KV gramatik mozhna pobuduvati sintaksichnij analizator chas roboti yakogo O n displaystyle O n nbsp Tipovim prikladom zastosuvannya efektivnih sintaksichnih analizatoriv z linijnim chasom roboti ye sintaksichnij analiz vihidnih tekstiv program v kompilyatori Yaksho slovo w displaystyle w nbsp movi L displaystyle L nbsp w L G displaystyle w in L G nbsp v gramatici G displaystyle G nbsp mozhe buti otrimane kilkoma riznimi sposobami to taku gramatiku nazivayut bagatoznachnoyu Sintaksichnij analizator dlya bagatoznachnoyi gramatiki mozhe pobuduvati kilka riznih derev sintaksichnogo analizu Bagatoznachnist ne vazhliva dlya rozv yazannya zadachi nalezhnosti slova ale yaksho riznim derevam spivstavlyayut rizne znachennya to toj samij tekst mozhe mati rizni znachennya Napriklad odnoznachnist gramatiki vazhliva dlya procesu kompilyaciyi abi otrimati pravilnij kod Bagatoznachnistred Zadacha rozpiznavannya bagatoznachnosti sered KV gramatik algoritmichno ne rozv yazna 2 Odnak isnuyut sposobi perevirki na bagatoznachnist abo odnoznachnist dlya deyakih okremih vipadkiv KV gramatik 3 Ekvivalentnistred Zadacha viznachennya ekvivalentnosti gramatik G 1 displaystyle G 1 nbsp ta G 2 displaystyle G 2 nbsp abo porodzhennya identichnih mov L G 1 L G 2 displaystyle L G 1 L G 2 nbsp algoritmichno nerozv yazna 4 Pidmnozhinared Zadacha viznachennya chi porodzhena KV gramatikoyu G 1 displaystyle G 1 nbsp mova takozh mozhe buti porodzhena inshoyu KV gramatikoyu G 2 displaystyle G 2 nbsp tobto chi L G 1 L G 2 displaystyle L G 1 subseteq L G 2 nbsp algoritmichno nerozv yazna 4 Ob yednannyared Ob yednannya G displaystyle G nbsp dvoh KV gramatik G 1 N 1 T 1 P 1 S 1 G 2 N 2 T 2 P 2 S 2 displaystyle G 1 N 1 T 1 P 1 S 1 G 2 N 2 T 2 P 2 S 2 nbsp G G 1 G 2 displaystyle G G 1 cup G 2 nbsp takozh KV gramatika Tobto G N 1 N 2 T 1 T 2 P 1 P 2 S S 1 S S 2 S displaystyle G N 1 cup N 2 T 1 cup T 2 P 1 cup P 2 cup S rightarrow S 1 S rightarrow S 2 S nbsp Peretinred Zadacha viznachennya nalezhnosti peretinu dvoh KV gramatik G 1 G 2 displaystyle G 1 G 2 nbsp do klasu KV gramatik algoritmichno ne rozv yazuvana 4 Dopovnennyared Dopovnennya KV gramatiki ne kontekstno vilne Prikladired Nehaj G N T P S displaystyle G N T P S nbsp KV gramatika T x y z displaystyle T x y z nbsp N S A B displaystyle N S A B nbsp P displaystyle P nbsp skladayetsya z chotiroh pravil vivodu S A A x A y A x B y B z displaystyle begin aligned S amp rightarrow amp A A amp rightarrow amp xAy A amp rightarrow amp xBy B amp rightarrow amp z end aligned nbsp w 1 x x z y y displaystyle w 1 xxzyy nbsp v gramatici G displaystyle G nbsp mozhna otrimati takoyu poslidovnistyu zastosuvannya pravil vivodu t w 1 S A x A x B z y y displaystyle t w 1 S A x A x B z y y nbsp tut t w 1 displaystyle t w 1 nbsp derevo vivedennya Korin dereva ta promizhni vuzli poznacheni neterminalnimi simvolami a listi dereva poznacheni terminalnimi simvolami Takim chinom w 1 L G displaystyle w 1 in L G nbsp Slovo w 2 displaystyle w 2 nbsp de w 2 z displaystyle w 2 z nbsp ne nalezhit do movi L G displaystyle L G nbsp oskilki neterminalnij simvol B displaystyle B nbsp ne pochatkovij a vsi slova utvoreni vid pochatkovogo mayut roztashovuvatisya posered terminalnih x displaystyle x nbsp ta y displaystyle y nbsp Formalno ce zapisuyut w 2 L G displaystyle w 2 notin L G nbsp Gramatika G displaystyle G nbsp ne bagatoznachna Priklad bagatoznachnostired Yak priklad bagatoznachnoyi gramatiki mozhna navesti G 2 N 2 T 2 P 2 S 2 displaystyle G 2 N 2 T 2 P 2 S 2 nbsp T 2 x y displaystyle T 2 x y nbsp N 2 S 2 A displaystyle N 2 S 2 A nbsp P 2 displaystyle P 2 nbsp mistit taki pravila vivodu S 2 A A A A A x A y A e displaystyle begin aligned S 2 amp rightarrow amp A A amp rightarrow amp AA A amp rightarrow amp xAy A amp rightarrow amp varepsilon end aligned nbsp Do w 3 x y displaystyle w 3 xy nbsp mozhna zastosuvati pravila S A x A e y displaystyle S A x A varepsilon y nbsp S A e A x A e y displaystyle S A varepsilon A x A varepsilon y nbsp ta S A x A e y A e displaystyle S A x A varepsilon y A varepsilon nbsp Takim chinom G 2 displaystyle G 2 nbsp bagatoznachna Div takozhred nbsp Portal Matematika Notaciya Bekusa Naura Normalna forma ChomskiPosilannyared Schoning 2001 S 21 Alfred V Aho and Jeffrey D Ullman The Theory of Parsing Translation and Compiling Volume 1 Parsing Prentice Hall 1972 ISBN 0 13 914556 7 H J S Basten Ambiguity Detection Methods for Context Free Grammars a b v Schoning 2001 S 137Literaturared Uwe Schoning Theoretische Informatik kurzgefasst 4 Spektrum Akademischer Verlag 2001 S 13 51 ISBN 3 8274 1099 1 Otrimano z https uk wikipedia org w index php title Kontekstno vilna gramatika amp oldid 33478989