КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Четири вида граматики на Чомски




Формални граматики се класифицират в зависимост от структурата на техните правила. Ако всички без изключение граматични правила отговарят дадена структура, тя се отнася до конкретен вид. Достатъчно, за да има едно правило в граматиката, структурата не отговаря на изискванията на правилата, и тя вече не става за определения вид.

Според класификацията на Чомски четири вида граматики.

Тип А: граматика Фразата структура

По отношение на структурата на техните правила, няма ограничения: граматиката на Г формуляра (VT, VN, P, S), V - VNuVT правила имат форма A> Р, където AEV +, (3EV *.

Това е най-често срещаният тип на граматики. Тя обхваща всички, без изключение, официално граматика, но някои от тях, за общия радост, може да се дължи на други видове класификация. Фактът, че граматиката, която се прилага само за вида 0 и не може да се отдаде на други видове, най-сложните в структурата.

Практическа граматика заявление се отнася само за тип 0 не са.

Тип 1: в зависимост от контекста (късо съединение) и не може да бъде съкратен граматика

В този тип се състои от два основни класа граматика.

Context-чувствителен граматика G (VT, VN, P, S), V = VNuVT имат вид на правила: stsAskhg-Нх ^ ар, където 1, а 2 EV *, AeVN, (СЕП 4.

Не може да бъде съкратен граматика G (VT, VN, P, S), V = VNU VT имат вид на правила: а -> (3, където, (3EV +, | р |> | а |.

Структурата на правилата за виновен-граматични е, че изграждането на изречения на езика, който са дали същото не-терминал символ може да се замени с определен низ от символи, в зависимост от контекста, в който това се случи. Ето защо граматиката се нарича "в зависимост от контекста." 0ts верига и 2 означават граматиката правила контекст (VH - ляво контекст и с 2 - десен контекст), по принцип, всеки един от тях (или и двете), може да бъде празно. С други думи, стойност на същия символ може да бъде различен в зависимост от контекста, в който се появява.


Глава 9. Формални езици и граматики

не може да бъде съкратен граматични правила имат такава структура, че изграждането на изречения на езика, определен от граматиката, всеки символен низ може да бъде заменен с низ от знаци, не по-малка дължина. Следователно името "не може да бъде съкратен."

Доказано е, че тези два класа граматики са еквивалентни. Това означава, че за всеки език, като се има предвид в зависимост от контекста граматика, може да се изгради граматика не може да бъде съкратен, което е еквивалентно на настройката на езика, и обратно заместник: за всеки език, посочен граматика не може да бъде съкратен, че е възможно да се изгради в зависимост от контекста на граматиката, която е еквивалентна на определен език.

В изграждането на компилатори такива граматики не се прилагат, тъй като програмните езици, компилатори счита, че имат проста структура и може да бъде изградена чрез използване на други видове граматики.



Тип 2: Context-Free (COP) граматика

Context-свободен (CF) граматика G (VT, VN, P, S), V = VNuVT има правила на формата: A "р \ където AeVN, PEV +. Такава граматика е също така понякога се нарича контекстно-свободен, не може да бъде съкратен (NCC) граматики (ясно е, че дясната ръка на правило те винаги трябва да бъде най-малко един символ).

Налице е също почти еквивалентно на техния клас на граматики - съкращаване контекст-свободен (UKS) граматика G (VT, VN, P, S), V = VNuVT, правила, които могат да бъдат от вида: A "р \ където AeVN, PEV *.

Разликата между тези два класа граматики е само, че MSC-нищожна струнни граматики могат да присъстват в дясната ръка на правилата (AA), и в NCL-граматики - не. Следователно е ясно, че езикът е посочено NCC-граматика, не може да съдържа празен низ. Доказано е, че тези два класа граматики е почти равностойни. В бъдеще, когато би било контекст, без граматики, вече няма да бъдат актуализирани, клас граматика (MSC или NCC) има в предвид, ако възможността за присъствие на езика на празен низ не е критично.

CFG е широко използван, за да опише синтаксиса на езиците за програмиране. Синтаксис най-известен езици за програмиране се основава на контекстно-свободни граматики, така че това, разбира се, те са платили много внимание.

Вътре вида на контекстно-свободни граматики освен класове NCC и освобождаване UKS дори един куп различни класове граматики, и всички от тях са от тип 2. По-нататък, когато CFG и COP-език ще се счита за по-подробно на някои от тези класове на граматики и тяхната специфична ще бъде изготвен специално внимание.

Тип 3: редовен граматика

За редовен тип включва два еквивалентни граматика клас: levoliney-Nye и pravolineynye.


Класификация HjbiKOB и граматики.

Levolineynye граматика G (VT, VNJP, S), V - VNuVT може да има два вида правила: A 'или А-У ", от където A.BeVN, yeVT.

На свой ред, линейна граматика G (VT, VN, P, S), правила V = VNuVT също могат да бъдат два вида: A "YB или A 'Y, където A, BeVN, yeVT *.

Тези два класа граматики са равностойни и се отнасят до вида на редовни граматики.

Редовна граматика използва, за да опише най-простите езикови програмиране конструкции: .. идентификатори, константи, конци, коментари и т.н. Тези граматики са изключително прости и лесни за използване, така че съставителите на техните основни функции са изградени лексикален анализ на изходния език (принципите на изграждането им ще бъдат обсъдени по-късно ).

граматически видове са свързани помежду си по специален начин. От дефиницията на типа 2 и 3, които всяка редовна граматика е контекстно-свободна граматика, но не и обратно. Също така е очевидно, че всяка граматика може да се дължи на вида и 0, защото налага никакви ограничения по отношение на правилото. От друга страна, които не са, там са съкращаване CFG (тип 2) или в зависимост от контекста, или не може да бъде съкратен (тип 1), тъй като те могат да съдържат правилата на формата "A-> B>, неприемливо в тип 1. Най-общо можем да кажем, че сложността на граматиката е обратно пропорционална на максималния възможен брой на тип, които могат да бъдат приписани на граматиката. Граматика, която се прилага само за вида 0, е най-сложните и граматиката, които могат да бъдат приписани на вида 3 - най-проста.

Класификация на езиците

Езиците са класифицирани според вида на граматики, в която са установени. Освен това, тъй като един и същ език в общия случай може да се зададе произволно голям брой граматики, които могат да се отнасят до различни видове класифициране, тогава класифицирането на езика сред всичките му граматики граматика винаги се избира с възможно най-високата тип класификация. Например, ако на езика L може да се определи граматики G и G 2, свързана с тип 1 (в зависимост от контекста) граматика G 3, свързани с тип 2 (контекстно-свободен), и граматиката G 4, отнасящи се до вида 3 (редовна ), след това на езика трябва да се отдаде на тип 3 и е обикновен език.

От класификацията това зависи от вида на езика не само с помощта на които може да се изгради една граматика на езика офертата, но също така и степента, до която тези предложения са трудни за разпознаване. Признават оферти - означава да се изгради за разпознаване на езика (трети начин да се уточни език). Разпознаване на себе си, тяхната структура и класификация ще бъдат обсъдени по-късно, но тук можете да се уточни, че сложността на езика за разпознаване зависи от вида на класирането, до която на езика.

Сложността на език намалява с увеличаване на броя на типа на класификация на език. Най-трудно са езиците на тип 0, най-прости - тип 3 езика.

Според граматики класификация, има четири вида езици.


Глава 9. Формални езици и граматики

Тип А: език израза структура

Това е най-сложните език, които могат да бъдат определени само граматика, свързани с вида 0. За да се признае вериги такива езици изискват калкулатори, същата мощност машина Тюринг. Следователно, можем да кажем, че ако езикът на вида 0, след като е невъзможно да се изгради компилатор, който е гарантиран за извършване на анализ на изречения на езика за ограничен период от време въз основа на ограничени изчислителни ресурси.

За съжаление, почти всички от естествения език на общуване между хората, строго погледнато, тя е от този тип език. Фактът, че структурата и смисъла на естествен език фраза не може да зависи само от контекста на фразата, но също така и по отношение на съдържанието на този текст, където се среща фразата. Една и съща дума по естествен език не може да бъде само "с различно значение в зависимост от контекста, но също така и да играят различна роля в изречението. Ето защо толкова голяма трудност в автоматизиране на превода на текстове, написани на естествен език, както и липсва (и вероятно никога няма) компилатори, които ще възприемат програмата въз основа на тези езици.

Други езици израза структура няма да бъдат разглеждани.

Тип 1: контекстно-чувствителна (KZ) езици,

Тип 1 - вторият вид език трудност. Като цяло, по-време да се признае на езика на предложения, отнасящи се до вида 1, експоненциална функция на дължината на оригиналната поредица от букви.

Езици и граматика, свързани с вида 1 се прилагат при анализа и превод на текстове на естествен език. Преобразуватели, основани на тях, дават възможност да се анализират текстове, базирани на контекст зависимостта на в присъдите на изходния език (но те не вземат под внимание съдържанието на текста, така че в общия случай за точен превод от естествен език все още изисква човешка намеса). Въз основа на тези граматики може да работи автоматизиран превод от един естествен език на друг, те могат да използват функциите за обслужване на правописа и правописа в езикови процесори.

Съставителите на неизправности езици не са използвани като програмни езици имат проста структура, така че те не са разгледани подробно.

Тип 2: Context-Free (COP) езици

COP-езици са заложени в основата на синтактични конструкции на повечето съвременни езици за програмиране, въз основа на тях оперират някои доста сложни командни процесори, които позволяват на екипа за контрол контур и условия. Тези обстоятелства определят разпространението на този клас на езици.

Като цяло, по-време да се признае на езика на предложения, отнасящи се до вида 1, полином зависи от дължината на първоначалния низ от символи (в зависимост от езика класа е или кубична или квадратна зависимост).


Класификация на езици и граматики

Въпреки това, сред CF-езици, има много езикови курсове, за които тази зависимост е линейна. Много езици за програмиране могат да бъдат отнесени към една от тези класове.

Ченге езици разгледани подробно в глава "Context-свободен език" на този урок.

Тип 3: редовни езици

Редовни езици - най-прост вид език. Може би това е защо те са най-често срещаните и широко разпространеният тип на език в областта на компютърните системи. Време е да признаем редовни предложения езикови са линейно зависи от дължината на оригиналната поредица от букви.

Както бе споменато по-горе, редовните езици са на базата на най-простите езикови програмиране конструкции (лични карти, константи, и така нататък. П.), освен това, много мнемонични машинни инструкции (монтаж език) са изградени въз основа на тях, както и черупки, контрол характер команди и други подобни структури.

Редовни езика - много удобен инструмент. За да ги използвате, можете да използвате редовни набори и изрази, крайни автомати. Редовни езици са разгледани подробно в следващата глава на учебник.

Примери за езици и граматики класификация

Класификация на езици отива от прости до сложни. Ако ние се занимаваме с обикновен език, може да се твърди, че тя е и контекстно-свободен и контекстно-зависима, и дори на езика с фразеологични структура. В същото време е известно, че има COP езици, които не са редовни, и има късо съединение-езици, които не са нито редовно, нито контекст-свободен.

По-долу са примери за някои от тези видове езици.

Помислете като първи пример, същото граматика за десетични число със знак G ({0, л, 2,3,4,5.6,7,8,9, -, +}, {S, T, F} .P, S):

P:

S -> T | + T | T

T - »F | TF

F-> 0 | L | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Според структурата на своите правила на тази граматика G се отнася до контекста свободни граматики (тип 2). Разбира се, това може да се дължи на тип 0 и тип 1, но на възможния максимум е точно тип 2, тип 3, защото от тази граматика не може да се отдаде по някакъв начин: на низ T> ¥ \ TF съдържа норма T »TF, което е неприемливо за въведете 3, и докато всички други правила на този вид отговаря на несъответствие е достатъчно.

За същия език (десетични число със знак) могат да се изграждат и друга граматика G "({0,1.2,3,4.5,6,7,8,9, -, +}, {S, T}, P, S):


P:

S -> T | + T | T

T - * 0 | 1 | 2 | 3 | 4 | 5 | б | 7 | 8 | 9 | ОТ | IT | 2T | ST | 4T | 5T | 6T | 7T | 8T | 9T Според структурата на своите правила на граматиката G "е pravolineynoy и може да се дължи на редовните граматики (тип 3).

За един и същ език, можете да изгради еквивалент levolineinuyu граматика (тип 3) G "({0.1,2,3,4,5,6,7,8> 9, -, +}> {S , T}, P, S) :

P:

T -> * | - | X

S -> MOT | T1 | T2 | TK | T4 | T5 | TB! T7 | T8 | T9 | SO | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9

Следователно, езикът на десетичната число със знак, даден граматика G, G 'и G ", се отнася за редовна език (тип 3).

Като втори пример, помислете граматика G 2 ({0, L}, {A, S }, P, S) с правила P:

S - »0A1 ОА - 00A1 * A X

Тази граматика е тип 0. Това определя езика набор от предложения, които може да са били написани, както следва: L (G 2) = {0 п л н | п> 0}.

За същия език също може да се изгради според контекста граматика G 2 "({0, L}, {A, S }, P ', S) с правилата R":

S - »0A1 | 01

ОА -> 00A1 | 001

Въпреки това, за един и същ език може да се използва и контекстно-свободна граматика G 2 "({0, L}, {S}, P", S) с правила P ":

S -> 0S1 | 01

Вследствие на езика L = {0 п л н | п> 0} е контекстно-свободен (тип 2).

В трети пример, нека граматиката G 3 ({A, B, C} , {B, C, D, S}, P, S) правила P:

S -> BD

Б -> AVS | аб Ch - "LC CD -> Dc BDC -> Ск Абд -> ABC

Тази граматика е от тип 1. Очевидно е, че това не е да се съкрати-Ing. Той определя езика набор от предложения, които може да са били написани, както следва: L (G 3) = {а н б н в п | п> 0}. Известно е, че този език не е контекстно-свободен език, така че да не може да се изгради видове граматични 2 или 3 за него.

Език L - {а н б н в п | п> 0} е контекстно-зависими (тип 1).

Разбира се, за всеки език, даден граматика, като цяло,

случай е трудно да се лесно да идентифицират неговия вид. Това не винаги е така


цифров компютър

просто изгради възможно най-добрия вид на граматика за всеки език. Освен строгата дефиниция на необходима да покаже повече, че две граматика (първоначално съществуващи и новопостроени) вида са равностойни, и че там не е един и същ за голям тип граматика линия. Това не е тривиална задача, която не е толкова лесно да се реши. В продължение на много езици, и по-специално за COP-езиците и редовни език, там са специално формулирани изявления, които ви позволяват да се провери на езика, принадлежащи към определен тип. Такива изявления (лема) ще бъдат разгледани по-нататък в съответните глави на този урок. След това в продължение на произволен език достатъчно да се докаже твърдението на правото, а след това може да се каже със сигурност, че този език принадлежи към един или друг вид. не се изисква трансформация на граматики в този случай.

Въпреки това, понякога съществува проблемът за изграждане на съществуващата граматика за опростен вид от това. И дори и в случаите, когато видът на език вече е известно, този проблем е нетривиален в общия случай не е официално решение (проблемът за преобразуване на граматики се обсъжда по-късно).