Studopediya

КАТЕГОРИЯ:


Астрономия- (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)

О вериги. Sentential форма. Заключение. O Chains




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

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

Класификация на граматики на Чомски

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

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

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

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

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

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

Техните правила структура няма ограничения: граматиката на формуляр G (T, N, P, S), V = нетен правила имат формата: a®b, където AIV +, BIV *.

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

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

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

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

Context-чувствителен граматика G (T, N, P, S), V = нетен имат вид на правила: a₁Aa₂®a₁ba₂, където a₁, а 2 IV *, Аин, BIV +.

Структурата на правилата за повреда - граматики е, че изграждането на изречения на езика, който са дали същото не-терминал символ може да се замени с определен низ от символи, в зависимост от контекста, в който това се случи. Ето защо тези граматики се наричат ​​"в зависимост от контекста." Вериги a₁ и a₂ в граматични правила представляват контекста (a - ляво контекста, и с 2 - десен контекст), по принцип, всеки един от тях (или и двете), може да бъде празно. Стойност на същия символ може да бъде различен в зависимост от контекста, в който се появява.



Не може да бъде съкратен граматика G (T, N, P, S), V = нетен правила са от вида: a®b, където, BIV +, | б | ≥ | а |.

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

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

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

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

Context-свободен (CF) граматика G (T, N, P, S); V = нетен има правила на формата: A®b, където Аин, BIV +. Такава граматика е също така понякога се нарича контекстно-свободен, не може да бъде съкратен (NCC) граматики (защото от дясната страна на правилата, те винаги трябва да бъде най-малко един символ).

Налице е също почти равностойни на своите граматика клас - съкращаване контекст-свободен (UKS) граматика G (T, N, P, S), V = нетен, правила, които могат да приемат формата на: A®b, където A Î VN, BIV *.

Разликата между тези два класа граматики е само в това, че празен низ (л) може да присъства в SMS граматики в дясната част на правилата, но граматики SAB - не. Език определено NCC - граматика, не може да съдържа празен низ. Доказано е, че тези два класа граматики е почти равностойни. По-късно, говорейки за CFG няма да бъде уточнено, клас граматики (UKS или NCC) има в предвид, ако възможността за присъствие на езика на празен низ не е критично.

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

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

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

Levolineynye граматика G (T, N, P, S), V = нетен може да има два вида правила: A®Bg или A®g, където A, BIN, gÎVT *.

Linear граматика G (T, N, P, S), V = нетен може да има правила, също два вида: A®gB или A®g, където A, BIN, GI VT *.

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

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

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

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

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

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

Тип 0, език израза структура

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

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

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

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

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

вина на компилатори - езици, които не са използвани като програмни езици имат по-опростена структура.

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

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

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

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

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

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

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

Фиг. 19 показва йерархията на езици и съответната йерархия на граматики и автомати разпознае устройството.


Фиг. 19. Йерархията на езици, граматики и автомати

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

Примери за някои от тези видове езици.

Граматиката за десетични число със знак

G ({0,1,2,3,4,5,6,7,8,9, -, +}, {S, T, F}, Р, S):

P:

S®T + T | -Т

T®F | TF

F® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Според структурата на своите правила на тази граматика G се отнася до контекста свободни граматики (тип 2). Тя може да се дължи на тип 0 и тип 1, но на възможния максимум е точно вида 2. Тип 3 не може да се счита тази граматика, защото T → F│TF ред съдържа правило T → TF, което е неприемливо за типа 3, и докато всички други правила на този вид отговаря на несъответствие е достатъчно.

Можете да се изгради и друг граматика G "за един и същ език (десетични число със знак) ({0,1,2,3,4,5,6,7,8,9, -, +}, {S, T }, Р, S):

P:

S®T | + T | -Т

T®0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0T | 1T | 2T | 3T | 4T | 5T | 6T | 7T | 8T | 9T

Според структурата на своите правила на граматиката G'yavlyaetsya pravolineynoy и тя може да се дължи на редовните граматики (тип 3).

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

P:

T® + | - | L

S® T0 | T1 | T2 | T3 | 4 | T5 | T6 | T7 | T8 | T9 | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9

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

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

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

Chain б = г 1 GD 2 се нарича пряко, извличани от веригата = г 1 ωd 2 граматика G (T, N, P, S), V = десет, г 1, г, г 2 IV *, ωÎV +, ако граматика G има едно правило: ω®g Î P. директно отчитане от веригата б верига се означава като: aÞb. Това е, б верига верига се извлича от това, ако аз може да отнеме няколко символа в низа на, да ги замени с други символи на някои правило на граматика и да получите верига б. Формалното определение за директно отчитане на всеки от веригите на г 1 и г 2 (или и двете вериги) може да бъде празно. В краен случай, цяла верига може да бъде заменен с верига от б, след това в граматиката G трябва да има едно правило: a®bÎP.

Веригата се нарича б изход от оковите на една (означен ATH * б) в случаите, когато едно от двете условия:

● б директно, извличани от (aÞb);

● $ г, така че: ж е, извличани от А и В са пряко извличани от г (ATH * г и gÞb).

Това рекурсивно определение люпимост верига. Същността му се състои в това, че веригата на б заключи от една верига, ако aÞb или ако е възможно да се изгради последователност директно на изхода на веригата от А до В от следния вид: aÞg 1-та ... THG аз та ... THG н THB, н ³ 1. В този всяка следваща верига последователност ж аз директно подразбират от предишната верига ж аз -1.

Такава последователност директно изходни вериги, наречени продукция или продукция верига. Всеки преход от една верига за директно изход следния изход във веригата се нарича изхода стъпка. Очевидно е, че изходните стъпки в изходния низ винаги има повече от междинни вериги. Ако веригата б директно подразбират от веригата: aÞb, тогава има само един изход стъпка.

Пример граматика за десетични число със знак

G ({0,1,2,3,4,5,6,7,8,9, -, +}, {S, T, F}, Р, S):

P:

S®T | + T |

T®F | TF

F®0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Ние го изгради малко произволно отнемане на вериги:

1. STH-TTH-TFÞ-TFFÞ-FFFÞ-4FFÞ-47FÞ-479

2. SÞTÞTFÞT8ÞF8Þ18

3. TÞTFÞT0ÞTF0ÞT50ÞF50Þ350

Имаме следните изводи:

1. STH * -479 или STH + -479 или SÞ7479

2. STH * 18 или 18 или STH + SÞ518

3. TTH * 350 или T Þ + 350 или TÞ6350

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





; Дата: 12.27.2014; ; Прегледи: 257; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



zdes-stroika.ru - Studopediya (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото допълнение , Al IP: 66.102.9.26
Page генерирана за: 0.052 сек.