Формалды грамматика 5 страница

Вирттің синтаксистік диаграммалары – бұл түзу сызықтар мен біріктірілген блоктарды пайдаланып, тілді графикалық түрде сипаттау. Мұнда терминалдар дөңгелектер көмегі мен, ал терминал,еместер тікбұрыштар көмегі мен белгіленеді. Бэкус – Наурдың әр құрастырушысы үшін эквиваленттік синтаксисін диаграмма құруға болады

Өзін-өзі тексеру сұрақтары:

1. Программалау тілдерінің даму тарихы?

2. Тілдерді өрнектеу жолдары қандай?

3. Синтаксис, семантика және программалау тілдерінің грамматикасы түсініктеріне тоқталыңыз?

4. Формализациялау проблемалары қандай?

Ұсынылған әдебиеттер:

1. Б. Страуструп Язык программирования. 1991 г Москва

2. Ивани А. Элементы теоритического программирования. Учебное пособие для вузов. М. МГУ. 1985 Г

Дәріс 3. Граматика

Мақсаты: Студенттерді формальды граматика ұғымымен таныстыру, тілдің құрылымын көрсету

Жоспары:

· Формальді грамматика

· Тілдің құрылымы

Формальді грамматика - программалау тіліндегі синтаксисті жазу үшін математикалық аппараттар көптеп қолданылады. Тілдің құрылымы көптеп қолдануы, екінші жағынан, программалардың синтаксистік анализіндегі грамматикаларды алдын алу.

Формальді грамматика шекті көптік ережелер арқылы және екінші сөздік арқылы табылады. Олар генерациялардың процесіндегі тілдің тізбегін жазады.

Бірінші сөздік терминалды сөздік деп аталады және ол тілдің басты символдарынан тұрады, олар формальді грамматикалардың теориясында- терминальді символдар немесе терминальдар деп аталады. Терминальдарды латынның a, b, c,…t әріптерімен белгілейміз, терминальді сөздік ∑ символымен, терминальді символдар тізбегін латынның U, V, W, X, Y, Z,белгілейді.

Екінші сөздік грамматика- терминальді емес деп аталады және символдардың көмегімен қолданылады. Оны жазғанда латынның бас әріптерімен А, В, С,.......Т белгіленеді. Терминальді емес сөздікте N әріпімен аталады. N сөздікте терминальді емес ерекшеленеді, оны бастапқы символ грамматикасы деп атайды және соңынан S орындалады. Бастапқы символ грамматикада қиылысады көп жағдайда конструкция тілінде жазылады. Терминальді және терминальді емес сөздік грамматикалық сөздік мына формулада толығымен орындалады V=∑UN.

Ілім қатарын аксиомаландырған, олардың логикасын, ішкі құрылымын оқып үйрену – математиканың метатіл ғылымының дамуында математикалық логика маңызды роль атқарды.

Информатиканың, әсіресе оның мынандай бөлімдерінің: формальды тілдер теориясы, грамматикасы, құрылымы, алгоритмдік тілдері және трансляциялау әдісінің мәліметтер қоры және білім деңгейі және тағы басқаларының дамуы, ғылым салаларының дамуына, тереңдетілуіне, орындалуына және құрылымдауына әкеледі. Өз кезегінде, тілдің құрылымдарын модельдеу, формализациялау, байланысу тілдер қатарының құрылымдау, әр түрдегі мәтіндер мен сөздіктердің анализі жәе орналасуы, сонымен бірге, олардың автоматты түрде орналасуы.

Алфавит көмегімен анықталған тіл, Х={ } – бұл қандай да бір ауызша, дыбысты, жазбаша немесе х-ке тәуелді сөздердің берілу түрі, синтаксисті қосқанда, сөздерден және сөз тіркесінен алынатын құрылым тәртібі, семантиканы – дұрыстығын тексеретін ереже, мәнді біртектікті және лексемнен тұратын тілдің қалыбының синтаксистік орналасуы. Ауызша байланыс үшін фонетика – сөйлем мүшелерін дұрыс айту ережесі, яғни, фонем.

Тіл хабар алмасу құралы ретінде берілген алфавитке сай, сөздердің құрылымын анықтау сипаты болу керек. Сөздерден құралған сөйлемдердің грамматикалық тәртібі және синтаксистікәрі семантикалық ережелер бойынша аталатын осы сөйлемдердің сол құбылыстарға және процестерге сай келуі.

Мысал. «бүтін х саны у бүтін санына қалдықсыз бөлінеді» деген фактіні қысқа әрі нақты (дәл) жазайық. Математикалық тілде ол мына түрде беріледі:

«х саны у санынан кіші». х,у – бүтін, жоғарыда айтылғандай, яғни олар факт, аксиома қабылдайтындай, ол математикалық кіші мән.

Енді одан да қысқа әрі дәл түрде алгоритмдік Паскаль тілінде жазайық:

“x mod y=0”.

Мұнда кіші шарты аргументтің өзгеру облысы туралы айтпауға болады – олар Паскаль тілінде ресми жарияланған (mod операциясын айтуда және типтердің атағанда) пайдаланылады.

Табиғи тілдер болады, (мысалы, байланысу тілдері) және жасанды тілдер немесе формалды тілдер, адамдардың компьюермен байланысы үшін жасалынған не болмаса, білім алу үшін және оны атап көрсеті үшін.

Х – қандай да бір алфавит болсын, x={ }, ал S(x) – х алфавитінде сөздердің көптігі, онда S(x) – шексіз және сандық көпмүше.

L(x) формалды тілі - S(x) –тің қайталама көпмүшесі.

Бақылау сұрақтары:

1. Формальді грамматика деген не?

2. Бірінші, екінші сөздік деп нені атайды?

Ұсынылған әдебиеттер:

1. Женон Ф. Языки программирование М.Мир. 1972 г

2. Климова Л.М. Паскал. Практика программирования. М. 2000 г

Дәріс 4. Граматиканың классификациясы.

Мақсаты: Граматиканың түрлері және негізгі проблемаларын көрсету.

Жоспары:

Формалды грамматика

2. Грамматикаларды классификациялау: регулярлық, контексті

Формалды тіл табиғи тілді оған кіретін абстрактілі объектінің лексикалық қалыбы ретінде, метатіл немесе басқа тілдердің синтаксисін белгілеу үшін пайдаланылады. Метатілмен жазылған тіл, бұл жағдайда объектілі тіл деп аталады.

G формалды грамматикасы: T={ } – тілдің терминалдық символдарының көпшілігі немесе тілдің негізгі мағынасы тізбектерінен тұрады;

N={ } – бұл терминдік емес символдардың көптігі немесе көмекші ұғымдардың, нақты бір сөздің класын белгілеу, мысалы, етістіктерді немесе жалғауларды, және де N-де N-нің алғашқы символы n болады;

P={ } – бұл s (x) Ì S(X) түрінің s (x) Ì S(X)-ке ауыстыру системасы немесе s (x) қарастырылып отырған s (x) қатынасына ауыстырылуы.

S(x)-тің барлық сөздерін тудыруға мүмкіндік беретін тіл (көбіне сөзі) G(S) – тәртіп құрылымы грамматикасымен беріледі.

Грамматикалық анализ – терминдік емес немесе сөзге бәсеңдеу процесі.

Көпшілік W=N ÈT – G грамматикасының сөздігі. Шығару тәртібі – бұл f,gÎW болғанда f®g болатын тәртіп, ал “®” – бұл түрдің байланысы «сол жақты оңға ауыстыруға болады».

Егер, болғанда, сөзі сөзінен ережесінің көмегімен шығады.

Мысал. Табиғи, мысалы, формалды грамматика терминіндегі орыс тілінің элементтерін жазайық. X={А,а,Б,б,..., Я, я,.,,,:,;,,.,!,?, “, ”, (,)}, T={<түбірлер>, <рпиставкалар> және т.б.}, N={сөйлем, бастауыш, баяндауыш, етістік, пысықтауыш және т.б.}, n = “сөйлем”.

Операциялардың және операндтардың метатілде оң сандармен жазылған берілуі – тұрақты берілу деп аталады.

Формалды грамматикада үш негізгі проблемалар қарастырылады:

Енгізу проблемасы – берілген грамматикаға сай алгоритм құру және ол сол тілге сай келетінін мүмкіндік береді;

Анализдің проблемасы – әрбір сөз үшін грамматикаға сай алгоритм құру және оның мәнін шығару;

Бағалау проблемасы – алгоритм мәнінің дұрыстығын тексеру шарты.

Егер бірінші екі тапсырмалар көбіне грамматикалық сипатта болса, онда үшінші тапсырма, көбіне «алгоритмдік» сипатта болады.

Компьютердің пайда болуына байланысты, алгоритмнің нақты және құрылымына талаптар қойылады. Бұл мақсатты қанағаттандыру үшін алгоритмдік тілдер өндірілуде. Өзіне математикалық символиканы, мысалы, сандар, операциялы белгілері, айнымалы шамалар, берілулер және т.б. қосатындықтан, бұл формальды тіл, формальданған тіл болып саналады.

5. Грамматикаларды классификациялау: регулярлық, контексті

Грамматикада анықталған 3,2 разрядында a®b-ға шығу ережесінде екеуінің біреуі a тізбегінде терминальды емес болуы керек. Праграммалау тілінің сипаттамасы және оларды оқып білу көбінесе грамматика тілінде қызықты болады және шығару ережесі дәлелдеуді талап етеді

Формальды грамматиканың анықталу облысында [3, 6, 9, 34, 35,48] Хамаскидің классификациясы қабылдайды, грамматиканы ереже түріне байланысты 4 класқа бөледі:грамматиканың түрі және грамматиканың жалпы түрі G=(N, SP, S) бұл грамматика У шығу ережесінің түрінде a®b, ол a V*NV*,ab V*.

Грамматиканың жалпы түрі мәннің қызықтысын қабылдайды, олар тым бос, бұларды программалау тіліндегі синтаксисті жазуда қолдануға болады. Табиғи тілге арналған синтаксисте қолданылады. 0 грамматикалық түрдегі мысал G=({A, S}, {0,1}, P, S) программасына негіз болады және P={S®0A1, 0A® 00F1,A ®e}.

Бірінші грамматика түрі немесе конспект- тәуелді грамматика бұл G=(N, SP, S) граммтикасы шығу ережесі түрінің g1А g2®g1bg2 одан g1, g2 V,A N,ab V+. Конспект оң және сол жақ g1және g2 аталуы бойынша сәйкестендіріледі және тізбектеледі. Олар шығу ережесінің тапсырмасы бойынша шарт орындалады: конспект g1,g2 тізбектері әр уақытта терминальды емес грамматикада a және b тізбегімен ауыстырылады.

Конспект тәуелді грамматика тілде конспект тәуелді тіл деп те аталады. Грамматикада конспект тәуелді грамматика мен тіл кластарын сәйкестендіреді, оны [9] -бен дәлелдеуге де болады. Ол грамматикада қысқартылмайтын деп те аталады, шығару ережесінің a®b орындау кезінде мына шартты қанағаттандырады½a£½b½.

Демек бұл алгоритмде немесе шекті сандарды анықтау кезінде терминалды тілде не жатады немесе жатпайды. Қысқартылмаған грамматика мына мысалда көрсетілген: G=({B,C,S}), {a,b,c},P,S) P={S aS,B,C, S abc; CB BC, bB bb, bC bc, cC cc).

Екінші грамматикалық түрі немесе конспект бос грамматика – бұл G=(N, S,P,S) грамматика шығару ережесінің мынадай түрін береді. А®В, немесе АÎN,abÎV*.

Келесі тіл Конспект тәуелді грамматиканы жеңіл оқиды және толық тексереді, сосын тілден бос тізбек шығады. Шығу ережесін жазғанда Конспект тәуелді грамматикасы лингвистикалық формуламен сәйкес келеді. Нақтырақ айтсақ, конспект тәуелді грамматикада шығу ережесінің терминалды емес грамматикасының сол жақ бөлігі лингвистикалық грамматиканың сол жақ бөлік формасымен сәйкес келеді.

Қатынас (®) - метолингвистикалық байланыста былай белгіленеді: (::=) шығу ережесінің терминалды және терминалды емес тізбектерінің бөлігі – метолингвистикалық формулада екіге бөлінеді: математикалық қоңырау тізбегі және тілдің басты символдарының оң жақ бөлігі.

Үшінші грамматикалық түрі – автоматты және регулярлы грамматика бұл G=(N, S,P,S) шығару ережесінің түрі А®ab немесе А®a, онда А,ВÎN, aÎSU{E}.Автоматты грамматика тілде конспект тәуелді тілі немесе автоматты және регулярлы грамматика деп аталады

Бақылау сұрақтары:

1. Формальды граматика деп нені атаймыз және граматикалық анализ дегеніміз не?

2. Граматиканы жіктеу әдістері деген не?

Ұсынылған әдебиеттер:

1. Бурин Е.А. Введение в основы информатики Алматы-1989 г Мектеп

2. Козыров А.А. Информатика для вузов СПб 2002 г

Дәріс 5. Алгоритмдік проблемалар: бос, иденцификациялау, тілдердің эквивалентілігі

Мақсаты: Алгоритм заңдылықтарын, Тьюренг машинасы жұмысын, алгоритмдер теориясы ұғымдарын көрсету.

Жоспары:

· Граматика түрлері

· Келтірілген грамматикалар.

Алгоритмдер теориясында дәлелденгендей, алгоритмнің бір мәнді түсінілуі, ал оның қадамдары қарапайым және орындалатын болуы үшін осы талаптарды орындайтын машина болуы тиіс. Мұндай машиналардың бірі – абстрактілі (теория жүзіндегі) Тьюринг машинасы. Алгоритмнің қатаң заңдылықтарымен жұмыс істейтін Тьюринг машинасының құрылымы суретте көрсетілген (аі – енгізілген символдар, і = 1, 2, 3,...).
Машина құрамындағы таспа жеке ұяшықтардан тұрады (таспа шексіз болуы мүмкін). Әрбір ұяшыққа алфавитке сәйкес тек бір символ енгізіледі (суретте символ енгізілмеген ұяшық бос символ (<< >>) арқылы белгіленеді. Бастиек міндетті түрде бір ұяшықтың үстінде орналасулы тұрады. Ол символды оқи және енгізе алады, қажет болса оны өшіреді. Бастиектің ерекшелігі – ол таспа бойынша еркін жылжи алатын етіп орналастырылған.
БҚ таспа басқару құрылғысы
бастиек

Тьюринг машинасының негізгі құрылымдық бөлімдері
Тьюринг машинасының қарапайым бір қадамдық әрекеті мынадай іс-әрекеттерден тұрады:

• Бастиек бір тактілі уақытта өзі тұрған ұяшыққа енгзілген символды оқиды;
• Оқыған символ және бастиектің ағымдық орны басқару құрылғысының жағдайын (жаңа күйге өтуін, жаңа жазылатын символды, бастиектің жылжуын және т.с.с.) бір мәнбі анықтайды;
• Басқару құрылғысы машинаға берілген команданы орындайды және сақтайды;
• Автоматтың соңғы қалып-күйге өтуіне байланысты, машина өз жұмысын тоқтатады не алгоритм дұрыс құрылмаған болса, еш уақытта тоқтамайды.

Жұмыс басында бастиек таспа ұяшығына бір машиналық сөз жазады да, келесі ұяшықтың үстіне орналастырылып қойылады, т.с.с.
Алгоритмдер теориясында құрылған алгоритмдер өзінің мүмкіндігі бойынша Тьюринг машинасына және алгоритм ұғымын дәлелдейтін басқа үлгілерге (модельдерге) баламалы екені дәлелденген. Алгоритмнің мұндай ұғымы арқылы шешлмейтін проблемаларды алгоритмдеу мүмкін емес екені де дәлелденді. Яғни есепті Тьюринг машинасы арқылы шешуге мүмкін болмаса, оның алгоритмі шешімсіз.
Егер кейбір жалпы мәселені шешу үшін алгоритм белгілі Тъюринг машинасы деп аталатын айтылған машиналардың варианттарының бірін Тьюринг машинасының үш алфавиті бар:
1. Бос символмен берілген сыртқы алфавит – А((((.
2. Ішкі алфавит немесе жағдайлар алфавиті Q
3. Қозғалыстар алфавиті S = (-1, 0, +1(.
Машинаның құрылымына кіреді:
а) шексіз таспа (ұяшықтарға бөлінген). Әрбір ұяшыққа тек
б) оқып-жазушы құрылғы. Оқып-жазушы құрылғының шолу жасау,
г) машинаның бір конфигурациясынан басқасына өтулерін анықтайтын машинаның егер шолу жасалған ұяшық пен машинаның жағдайы белгілі машинаның программасы бұл әрбір (а, qi) қадам болып табылады.
Машинаның жұмыс істеу ережелері.
Машина дискретті түрде жұмыс істейді (қадам қадам машинаның жұмыстары машинаның қадамы q0 ға жеткенше жалғаса береді.
Машина мысалдары
Мысал 1. Келесі Тьюринг машинасы унарлық санақ жүйесінде
q1 q2 q3
| |q1+1 (q3-1 |q3-1
+ |q1+1
((q2-1
(q0+1
Мысал 2. Келесі Тьюринг машинасы унарлық санақ жүйесінде
q1 q2 q3
| (q1+1 |q2-1 |q3+1
(|q3+1 ((q2-1 (q0+1 |q2

Грамматиканың төрт түрінің ішінде мәнмәтінді–бос грамматика бағдарламамлау тілдеріне қосымша мен компиляциялар көз қарасынан ең негізгі болып келеді. –грамматика көмегімен бағдарламамлау тілі құрылымының үлкен бөлігін анықтауға болады.

Бағдарлама тілінің конструкциясын беретін грамматикаларды құру кезінде олардың өзгеруіне сүйенуге жиі тура келеді, сондықтан алдымен –грамматиканың жай, бірақ та негізгі бірнеше өзгерулерін қарастырайық. Өзгерудің бірінші түрі грамматикадан пайдасыз символдарды жоюмен байланысты. Символдар грамматикада пайдасыз болып қалуы келесі жағдайларда болады:

а) егер символ шығару кезінде алына алмаса

б) егер символдан соңғы терминалды шынжыр алына алмаса.

Алдымен соңғы шынжырды шығаруға мүмкін емес символдарды айқындау алгоритімін қарастырайық. Егер символынан соңғы терминалды шынжыр шығарылмаса ол тудырылмайтын деп аталады.

Грамматикалардың ережесін қарастырып отырғанда оң жақ символдарының барлығы тудыратын деген шешімге келсек, онда сол жақта тұрған символдар да тудыратын болып келеді. Ақырғы тұжырым тудырмайтын символдарды байқау процедурасын келесі түрде жазуға мүмкіндік береді:

1 Оң жағы терминал еместерді құрамынды ұстайтын бір болсын ереже табылатын терминал еместер тізімін құру.

2 Егер жоғарыда айтылған ереже табылатын болса, онда терминалдар емес тізіміне оның сол жақында тұрғандарды енгізу.

3 Егер 2 қадамда тізім толықтырылмаса, грамматиканың барлық тудыратын терминал емес тізімі алынады, ал оның құрамына енбеген барлық терминал еместер тудырмайтын болып келеді.

грамматикасына сәйкес талдай келе бұнда және символдары тудырмайтын екеніне көз жеткіземіз. Тудырмайтын символдары құрамында бар ережелерді жойған соң аламыз.

Егер ешбір шығарылатын шынжырда болмаса, онда – грамматикада символы жетпейтіндеп аталады.

Егер сол жақтағы терминал емес символы жететін болса, онда оң жақтағылар да сондай болатынына көз жеткіземіз. бұл ереже қасиеті жетпейтін символдарды анықтау процедурасының негізі болып келеді де, оны келесі түрде жазуға болады: Бастауыш символдан тұратын бір элементті тізім құру.

1. Егер сол жағы тізімге енгізілген болса, онда оның оң жағындағыларда тізімге енгізілетін ереже табылса.

2. Егер 2 – қадамда тізімге жаңа терминал еместер қосылмаса, онда барлық жеткен терминал еместер тізімі жетпейтін болып келеді.

Грамматикалардың пайдасыз символын келесі әдіспен анықтауға болады: жататын символы -грамматикасында жетпейтін немесе тудырмайтын болып келсе, онда ол пайдасыздеп аталады.

Пайдасыз символдарды алдымен тудырмайтын, ал содан соң жетпейтін символдары құрамында бар ережелерді грамматикадан жоя келе шығарып тастауға болады. Иллюстрация ретінде келтірілген ережелерге дәлел түрінде келесі грамматикалардағы өзгерулерден орындаймыз:

Алдымен және тудырмайтын символ екенін байқап, тудырмайтын символдары бар ережелерді жоя келе аламыз.

Алынған схемада символы жетпейтін символ болып келеді. Бұл символды құрамында ұстайтын ережені шығара келе аламыз.

Келтірілген грамматикалар.

Егер –грамматикасының құрамында пайдасыз символдар болмаса, онда ол келтірілген деп аталады.

түріндегі ереже оң жақты рекурсивті, ал түріндегі ереже – сол жақты рекурсивті деп аталады.

Бақылау сұрақтары:

1. Тьюренг машинасы құрамында не бар?

2. Граматикалар ережесі неден тұрады?

Ұсынылған әдебиеттер:

1. Симонович С.В. Базовый курс. Информатика. Питер. 2003 г

2. Ивани А. Элементы теоритического программаирования. М. 1985 г.

Дәріс 6. Автоматтар.

Мақсаты: Тілдер және автоматтар теориясы алғашқы ұғымымен таныстыру.

Жоспары:

· Автомат түсінігі