Грамматикаларды құру әдістері

Қазақстан Республикасы білім және ғылым министрлігі
Семей қаласының Шәкәрім атындағы мемлекеттік университеті
                  3 деңгейдегі СМК құжаты
                                       
                                   ПОӘК
                                       
ПОӘК 042.39.1.146/01-2013
                                       
                                   ПОӘК
                      Оқытушыға арналған
<<Автоматтар теориясы және тілдер>>пәні бойынша оқу жұмыс бағдарламасы
                                 01.09.2010 ж
                              №1 басылым
                                 02.09.2013 ж
                              №2 басылым
                                       
                                       
                                       
                                       
                                       
                                       
                                       








        <<Автоматтар теориясы және тілдер>>
                                       
            пәнін оқыту-әдістемелік кешен
                                       
5В060200 - <<Информатика>> мамандығына арналған
                                       
                                       
                             оқу  кешені
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                  Семей,
                                     2013
                                       
                                       
                                       
                                       
МАЗМҰНЫ
                                       
* 
Глоссарий
* 
Дәрістер
* 
Зертханалық жұмыстар
* 
Студенттердің өздік жұмыстарының  жоспары


































Дәріс №1 Формалдық грамматика мен тілдер анықтамасы

Түрлі ұлттар қарым-қатынас жасайтын табиғи тілден жасанды тілдің ерекшелігі  -  олар жазба мәтіндерді құру үшін қолданылатыны белгілі. Бұндай тілдер жасанды тілдерден қида жеңіл болып табылады, себебі бұл тілде көп мағыналық  пен синоним жоқ,, синтаксис  пен семантика жеңілдетілген, сондай-ақ айтарлықтай мәтіндік бағыныңқылық төмендетілген. Жасанды мәтіндердің негізгі қызметі -ақпаратты компьютерлер мен басқару құрылғыларына беру.
 Мәтін компьютер немесе басқару құрылғылары орындау қажет тапсырма болып табылады. Бұндай тапсырманың мәтінін адам құрғандықтан, кіріс тілі деп аталатын мәтінді жазу тілі қолданатын адамдар қолданысына ыңғайлы және түсінікті болу керек. Адамға бағытталған тіл әдетте компьютер орындайтын команда түрлерімен біртектес болмайды. Компьютерге түсінікті командалар артынан кіріс тілінде мәтіннің өзгертілуін орындау үшін транслятор деп аталатын арнайы құрылғы немесе бағдарламалар қолданылады. 
Трансляторды құру тапсырмасы айтарлықтай қиын және жауапты іс. Оның шешім қабылдау сапасына  өзгертуді орындауға қажет ресурстар байланысты болады. Және бұнымен қатар кіріс тілінде жазылған мәтін мазмұнын дәлме-дәл жеткізу трансляторға қойылатын негізгі талап болып табылады. Ондай өзгертулерді іске қосу үшін тіл синтаксисі деп аталатын кіріс мәтіндерінің құрылу ережелерінің дәлме-дәл суреттелуі мен тіл семантикасы деп аталатын мәтін мазмұнын баяндайтын талдау ережелері қажет. 
Синтаксис пен семантиканы мазмұндау үшін түрлі құралдар қолданылады. Осылайша тіл синтаксисін формалдық грамматика, ал семантиканы атрибуттық грамматика көмегімен мазмұндауға болады. 
Бұл бөлімде тек қана синтаксисті мазмұндаумен байланысты мәселелер ғана қарастырылады. Табиғи тілдік аналогиялармен қолдана отырып формалды тілді нақты ережелер бойынша құрылған көптеген сөйлемдер ретінде көрсетуге болады. Формалды тіл мен құру ережелерінің ұсыныстарын құру тәсілі формалдық грамматика көмегімен анықталуы мүмкін. Бұнымен қатар құру ережелерінің жиыны грамматика кестесі деп аталады, ал құру реті шығару түсінігінің көмегімен анықталады. Грамматика ережелерінің көмегімен тіл сөйлемдерінің ережесі болып табылатын түрлі шығарулар құруға болатыны белгілі. Сондықтан формалдық грамматика көп жағдайларда тудыру грамматикасы, ал шығару  -  тудыру үрдісі деп аталады. 
Бұл бөлімде алфавит, шынжыр, грамматика, шығару, тіл және т.б. базалық түсініктер анықтамалары беріледі. Содан соң формалдық грамматиканың мүмкін классификацияларының бірі  -  Хомс бойынша классификациялау қарастырылады. Бұл классификация бағдарламалау тілін тәжірибеде мазмұндау үшін қолданылатын грамматика типін көрсетуге мүмкіндік береді. Бөлімнің соңында бағдарламалау тілінің кейбір конструкцияларына арналған жай грамматикаларды құру мысалдары қарастырылады. 
Формалдық тіл мен грамматиканы анықтауға қажет алғашқы және ең жай түсінік болып алфавит пен алфавиттегі сөздер табылады. 
Символдардың бұл қарастыруда бөлінбейтін соңғы жиыны сөздік немесе алфавит деп, ал жиынға жататын символдар - алфавит әріптері деп аталады. 
Мысалы, әрбіреуі екі символдан тұратын  алфавиті 5 әріпті құрайды, ал алфавиті 4 әріпті құрайды. 
Алфавит әріптерінің реті бұл алфавиттегі сөз немесе шынжыр деп аталады. Сөздегі әріптер саны  жиынының ұзындығы деп аталады. Бос шынжыр  -  бұл бірді-бір әріпі жоқ шынжыр. Оң жақтан немесе сол жақтан  шынжырына кез келген бос шынжырдың қосылуы  шынжырын өзгертпейді 
 алфавитінің символдарынан құрылған барлық мүмкін шынжыр жиындарын анықтау үшін  белгісі қолданылады. 
 формалды грамматика деп келесі төрт объектінің жиынтығы аталады:  мұнда - терминалдық алфавит (сөздік); бұл алфавиттің әріптерін терминалдық символ дейді; олардан грамматиканы тудыратын шынжыр құрылады; терминалдық сөздік немесе терминалдық символ әріптерін белгілеуді әрі қарай латын алфавитінің әріптерімен белгілейтінімізді атап кетейік;
  -  терминалдық емес, көмекші алфавит (сөздік); бұл алфавиттің әріптері шынжыр құруда қолданыла алады; олар аралық шынжырға кіре алады,  бірақ құру нәтижесіне кіргізілмейді; терминалдық емес символдарды белгілеу үшін латын алфавитінің жазба әріптерінен тұратын және бұрыштық жақшаларға алынған идентификаторларды қолданатынымызды атап кетейік; - грамматикасының  бастапқы символы немесе аксиомасы- .
  	 - шығару ережелерінің жиыны немесе түрінің ережелерін тудыру жиыны, бұнда   және ,  алфавитінің әріптерінен құрылған шынжырлар6 олар  грамматикасының толық алфавиті (сөздік) деп аталады. 
Грамматика ережелерінің жиынына сондай-ақ түрінің оң жағы бос ережелер де кіреді. Ереженің оң жағы бос болғандықтан, қателік тудырмау үшін бос шынжыр символын   түрінде белгілейміз. 
Грамматиканы шығару ережесі шынжыр құру үшін қолданылады. 
- грамматикасының ережесі және    -  символдар шынжыры,  оған қоса. Онда    шынжыры  (яғни -де  шынжырын  ауыстыру) ережесінің көмегімен шынжырдан алынуы мүмкін.  Бұл жағдайда   шынжырынан тікелей шығарылған және  білдіреді. 
Егер  шынжырының жиынтығы берілгенде келесі шығадыонда мұндай реттік қатарды   грамматикасында   - дан шығару деп атап,  белгілейді. 
 грамматикасының  терминалдық алфавитінің соңғы шынжыр жиынын алғашқы  символынан шығарамыз, ол  грамматикасынан түған тіл деп аталып, былайша   белгіленеді. 
                                       
                                       
                                       
Келтірілген грамматика кестесінде үш ереже бар. Екінші ереже ереженің оң жақ және сол жағында да  терминалдық емес символы бар. Мұндай ережелер рекурсивтік деп аталады. Бұл ережені  терминалы жоқ шынжырға пайдалану,  қайта енетін жаңа шынжырдың тууына әкеледі. Осылайша қайталай отырып ұзын шынжыр құруға болады. Рекурсивтік ереже көмегімен шығару шексіз болмау үшін грамматика кестесінде оң жақта  символымен бір болсын ереже болу керек. 
Бұндай ереже шығарылатын шынжырдан  шығара отырып рекурсияны аяқтайды. Қарастырылатын грамматикада шығаруды аяқтау үшін  ережесі қолданылады.  грамматика ережесінің көмегімен шығару қатарын қарастырайық. Бірінші және үшінші ережені қолданып келесіні аламыз: 

                                       
                                       
Бірінші, екінші одан кейін үшінші ережелерді қолданып келесіні аламыз:
                                       
                                       
 	1.2 Формалдық грамматика типтері

Формалдық грамматика теориясында 4 тіл түрі сәйкес келетін грамматиканың 4 түрі ерекшеленеді. Бұл грамматикалар грамматика ережелеріне шектеу қою жолымен анықталады.
	Жалпы түр грамматикасы деп айтылатын 0 түріндегі грамматикалар тудыру ережелеріне ешқандай шектеу қоймайды. Кез келген  ережесі  еркін шынжырындық көмегімен құрылуы мүмкін.
	Мәнмәтінді  -  бағыныңқылы грамматика деп аталатын 1 түріндегі грамматикалар кез келген ережені қолдануға жол бермейді.
 Бұндай грамматикаларда шығару ережесі келесі түрде болуы керек:

                                      
                                       
бұнда -  жиынынан мүмкін бос шынжырлар,  символ және  шынжыр.  және шынжырлары ережені қолданғанда өзгермейді, сондықтан оларды мәнмәтін (яғни сәйкесінше оң жақ және сол жақ), ал грамматиканы  -  мәнмәтінді бағыныңқылы деп атайды.
	1 түріндегі грамматика 0 түріндегі грамматикаға қарағанда көбірек қолданылады, себебі ереженің оң жағында кейбір синтаксистік түсініктермен байланысты болатын терминалды емес бір ғана символ өзгертіледі, ал 0 түріндегі грамматикада бірден бірнеше символ, соның ішінде терминалды да өзгертуге болады. 
Мысалы, 
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
грамматикасы мәтіндік-бағыныңқылы болып табылады, себебі екінші және алтыншы ережелер бос емес оң жақты мәнмәтінді, ал үшінші және бесінші ереже екі мәнмәтінді де ұстайды. Бұндай грамматикада шығару төмендегідей болуы мүмкін:
                                       
                                       
                                       
	2 түріндегі грамматиканы мәнмәтінді  -  бос және мәнмәтінсіз грамматика (-грамматика немесе  грамматика) деп атайды. бұндай грамматикаларды шығару ережесі келесідей болады: 
                                       
                                   және 
                                       
	Яғни бұл ережелер  шарты бойынша 1 түріндегі грамматика ережесінен пайда болады. Мәнмәтіндік шарттар болмағандықтан, 1 түріндегі грамматика ережесіне қарағанда МБ  -  грамматика ережесі жеңілдірек алынады. Яғни, нақты осындай грамматикалар бағдарлама тілдерін мазмұндау үшін қолданылады.   -  грамматикаға мысал ретінде төмендегі грамматиканы келтіруге болады:

                                       
                                       
                                       
Бұл грамматика  шынжыры немесе  шынжырының айналы көрінісінің әрбіреуі екі бөлігінен тұратын шынжырдан тұратын тілді тудырады. 

                                       
                                       
бұнда - бұл  бос шынжырсыз жиыны. Бұл грамматика көмегімен мысалға келесі шынжыр құруға болады: 
                                       
                                       
                                       
3 түріндегі грамматика автоматты грамматика (-грамматика) деп аталады. Бұндай грамматикаларда шығару ережелері келесі түрде болады:
                                       
                          немесе  немесе 
бұнда  және  және грамматика тек қана - оң жақ ереже немесе  -  сол жақты ереже түріндегі ережесі болуы мүмкін. 
Бұл грамматикалар бір тілді тудырады.  
Тіл классификациясы тілді тудыратын грамматика түрлеріне сәйкес құрылуы мүмкін. Бір тіл екі түрлі грамматика болатын түрлі грамматикалармен берілуі мүмкін. Сондықтан тіл түрін  түріндегі грамматика беруі мүмкін грамматика түрімен анықталады.
                                       
1.3 Шығару ағашы. Сол жақты және оң жақты шығарулар

Формалды грамматикалар нақты ережелер бойынша құрылған шынжыр жиындарын өкіл ететін тілдерді тапсыруға мүмкіндік береді.
 Бұл қолданылатын беру тәсілі тілге жататын кез келген шынжырды құруға мүмкіндік береді. Шығару деп аталатын құру үрдісін көріктендіру үшін оны графа түрінде, дәлірек айтсақ синтакс ағаш немесе шығару ағашы деп аталатын ағаш түрінде бейнелейді.
Берілген грамматика тудыратын, тілге қатысты болатын кез келген тілдің шынжырының шығаруы символдан басталуы керек болғандықтан, ағашты құру ережесін келесідей айту қажет:
*  Бастапқы шың немесе ағаш тамыры ретінде грамматикалық бастапқы символымен белгілейтін шыңды алайық; бұл шың ағаштың нөлдік қабатын құрайды.
*  Егер шынжырды шығару кезінің келесі адымында  терминал емес болып белгіленген,  нөмірімен қабатта орналасқан  грамматика ережесі немесе шың қолданылса, онда құрылған ағашқа шынжырында неше символ болса, сонша шың қосу керек және бұл шыңдарды  қабатына орналастырып, шынжырының символдарымен белгілеп, бұл шынжырларды  шыңымен доға көмегімен байланыстыру. Соңғы түйіндер  -  жапырақтар жиыны шығару қорытындысы болып келеді де, ағашты қарастыру кезінде солдан  -  астына  -  оңға  -  үстіне деп көрсетіледі.
 грамматика ереже нөмірінің реті  шыңның синтакситік талдауы деп аталады. Егер шығаруды құру үрдісінде бірнеше терминалды емес символы бар аралық шынжырлар пайда болса, онда шығаруды кез келгенін ауыстыра отырып жалғастыруға болады. Одан келіп шығатын анықтама, яғни шығару кезінде шынжырларды кез келген ретпен қолдануға болады. 
1.4 Көпмағыналы грамматикалар
Түрлі шығарулардың көмегімен шынжыр пайда болған грамматикалар бар. Мысалы:  грамматикаларда  шынжыры екі түрлі шығару көмегімен пайда болуы мүмкін және оған екі түрлі синтаксистік ағаш сәйкес келеді. 

                                       
                                       
                                       
 	Бұл шынжырдың бірінші шығаруы келесі түрде болады:
                                       
                                       
                                       
ал екіншісін былай алуға болады:
                                       
                                        
                                       
Келесі грамматика да түрлі синтаксистік ағашы бар түрлі шығарулар арқылы шынжыр құруға мүмкіндік береді. 
                                       
                                       
                                       
                                       
Бұл грамматикалық шынжыр тудыратын екі шығаруы келесі түрде көрсетіледі: 

                                       
                                       
Грамматиканың қарастырылған қасиеті көп мағыналық деп аталады. Ол келесі тәсіл арқылы анықталуы мүмкін.  тілінің шынжыры егер оны шығару үшін біреуден артық синтаксистік ағаш бар болса көп мағыналы деп аталады. Егер грамматикасы көпмағыналы шынжыр тудырса, онда ол көп мағыналы деп аталады.
	Көп мағыналық тек қана жасанды тілде болуы мүмкін емес. Яғни табиғи тілде де көп мағынасы бар сөйлемдер болуы мүмкін.
 Мысалы: <<Пальто испачкало окно>> бұл сөйлемде бастауыш қайсы, толықтауыш қайсысы екені түсініксіз. Ал ағылшынның "They are flying planes" сөйлемі екі түрлі түсіндірілуі мүмкін, яғни : "Они пилотируют самолет" немесе <<Это летящие самолеты". Көп мағыналық жасанды тілге өте жағымсыз қасиет болып саналады, себебі көп мағыналық шынжырдың бірнеше мағынасы бар және ол шығару ағашын бір мағына тәсілімен құруға мүмкіндік бермейді.
 Бұдан келіп шығатын қағида, яғни тәжірибеде бір мағыналы грамматикаларды қолдану қажет. Қарастырылып жатқан грамматика көп мағыналы екеніне көз жеткізу үшін бұл грамматика тудыратын түрлі шығарулар көмегімен құрылуы мүмкін шынжырды табу жеткілікті. Бірақ бұл жерде туатын қиындық көп мағыналы шынжырды тауып алуда  арнайы алгоритмнің жоқтығы. Бұл қағида формалды тілдер теориясында дәлелденген.
Егер   және  грамматикалары бір тілді  тудырса, онда олар эквивалентті деп аталады. 
Жалпы жағдайда екі берілген грамматика эквивалентті екенін тексеруге мүмкіндік беретін алгоритм жоқ екені дәлелденген. Бірақ көп мағыналық мәселесі жалпы түрде шешілмейді және кейбір жағдайларда, мысалы -грамматикасы үшін грамматика кестесінде грамматиканы көп мағыналы ететін ережелер түрі анықталған. Бұған келесі түрдегі ережелер мысал бола алады: 
                                       
                                       
                                       
Грамматика кестесінде бұл ережелердің біреуі болсын болуы грамматиканың көп мағыналы екенін көрсетеді. Алайда бұл ереженің грамматика кестесінде болмауы грамматиканың көп мағыналы еместігіне кепілдік бере алмайды.

 	1.5 Грамматика кестелерін беру тәсілдері

Грамматика кестесінде тілдің синтаксисін анықтайтын шығару ережесі және басқаша айтқанда туатын тілдің мүмкін компоненттері мен шынжыр конструкциялары болады. Ережелерді тапсыру үшін түрлі атап айтсақ, олар: рәміздік (символдық), Наур-Бэкус формасы, итерациондық форма және синтаксистік диаграммалар. 
Грамматиканың жалпы қасиеттерін қарастырумен байланысты жұмыстарда әдетте ережені тапсырудың символдық формасын қолданады. Ол элемент ретінде бөлек символдардың терминал емес сөздігі мен ереженің оң және сол жағын бөлуші ретінде  -  жебені қолдану алдын-ала қарастырылады.
Бағдарламалау нақты тілдің синтаксисін мазмұндауда көп мөлшерде терминалды емес символдар енгізуге тура келеді және осыдан жазылымның символдық формасы өз көрнекілігінен айрылады. Бұл жағдайда бұрыштық жақшаларға алынған терминалды емес символдар ретінде табиғи тілдің сөздер комбинациясын алдын ала қолдануды қарастыратын Наур-Бэкус формасын, ал бөлгіш ретінде екі қос нүкте мен теңдіктен тұратын арнайы белгі қолданылады. 
Мысалы, егер  немесе  ережелері символдық формада жазылған болса және   символы  "тізім", -"тізім элементі" түсінігіне сәйкес келсе, оларды Наур-Бэкус формасында төмендегідей көрсетуге болады: <тізім >:=<тізім элементі >< тізім , <тізім:=<тізім элементі>.
Грамматика кестесін мазмұндауда қысқарту үшін, БНФ-да тік сызықпен бөлінген оң жақ бөлігі біріктірілген ережелердің оң жағын енгізу қажет сол жағы бірдей болып келетін ережелерді бір ережеге біріктіру рұқсат етіледі. Қарастырылып жатқан мысалға ережелердің біріктірілуін пайдалана отырып келесі көріністі аламыз: 
<тізім>:=<тізім элементі><тізім>|<тізім элементі>.
Синтаксистік шағын мазмұндауын алу үшін мазмұнның итерациондық формасын қолданады. Бұл форма арнайы итерация деп аталатын және қос фигуралық жақша мен жұлдызшамен белгіленетін операцияны енгізуді қажет етеді. түріндегі итерация жиын ретінде анықталады да өзінің құрамында  а символы мен бос шынжырды пайдаланып құрылған мүмкін ұзындықтағы шынжырды ұстайды
                                       
                                       
                                       
Символдың ережелермен берілетін шынжыр жиындарын мазмұндау үшін итерацияны пайдаланып, келесі түзілуді аламыз:

                                        
                                       
Мазмұндаудың итерациялық формаларында итерациялық жақшалармен қатар жиі олардың ішіне алынған шынжырдың жоқтығына көрсететін тік жақшаларға алу кездеседі. Бұндай жақшалардың көмегімен 

                                   және 
ережесі төмендегідей жазылуы мүмкін:
                                       
                                       
                                       
Көзбен көріп қабылдауды жақсарту және күрделі синтаксистік мазмұндау түсініктерін жеңілдету үшін синтаксистік диаграмма түріндегі грамматика ережелерін көрсетуді қолданады. Синтаксистік грамматика грамматиканың әрбір ережесіне бағытталған граф ретінде көрсетіледі. Бұндай диаграммалардың құрылу ережесін келесі түрде тұжырамдауға болады: 
* Әрбір  түріндегі ережеге құрылымы ереженің оң жағымен анықталатын диаграммаға сәйкес қойылады. 
*  шынжырдағы терминалды  символының көрінуі  символы   жазылған доға мен дөңгелек диаграммасында бейнеленеді.
*   шыңжырында  терминалды емес символдың әрбір көрінуі  символы жазылған доға мен тік бұрыш диаграммаларда бейнеленген.
*   түрі бар грамматиканың тудыру ережесі.
*   түрі бар грамматиканың тудыру ережесі.
* Егер ереже  итерация түрінде берілсе, оған диаграмма сәйкес келеді.
Грамматиканың берілген кестесі үшін құруға болатын синтаксистік диаграммалар саны ереже санымен анықталады. Диаграммалар санын азайту үшін оларды біріктіріп, оларға арналып құрылған диаграммаларға енетін термин емес символдарға ауыстырылады. 
3-6 ережелері біріктірілген диаграммада  шынжыры ретінде бұл шынжырдарға арналған диаграммалар қолданылуы мүмкін деп болжайды. Мысал ретінде  бастапқы символды келесі грамматиканы қарастырайық: 
                                       
                                       
                                        

1.6 Грамматикаларды құру әдістері

Формалдық грамматикаларды құру тапсырмалары табиғи тілде соңғы шынжырлар жиынын мазмұндау үшін формалды грамматика құруды қажет етеді.  Бұл грамматика шынжыр жиынын тудыруды қажет және де терминдік сөздік берілген жиын құрамына кіретін шынжыр құруда қолданылатын барлық символдарды өз құрамында ұстауы қажет. Ал тапсырманың шешуі терминді емес сөздік немесе грамматика кестесі болуы керек. грамматика ережесін құру негізі болып берілген шынжыр жиынының құрылымын ерекшелендіру тәсілі табылады. Бұл тәсіл берілген жиынға енетін шынжырлардың қайталанатын жерлерін алып тастауға негізделген. 
Әрбір аланып тастаған құрылым элементіне белгі берейік.
 Бұндай белгілердің көбі кейбір грамматиканың терминді емес символдық сөздігінің негізін құрайды. Құраудың келесі адымы құрылым элементтері берілген шынжыр құрамынан алынып тасталуы.
 Бұндай реттер грамматика ережесін құруға негіз болып табылады. Шынжыр құрылымы грамматика ережесінде қалай көрінетінін қату үшін келесі мысалдарды қарастырамыз:
*  берілген символдарынан тұратын шынжыр  ережесіне сәйкес келеді.
*  берілген символдан басталатын шынжыр  ережесіне сәйкес келеді.
*  берілген символдан аяқталатын шынжыр  ережесіне сәйкес келеді.
*  берілген символ басталатын және аяқталатын шынжыр  ережесіне сәйкес келеді.
*  символы ортасында келетін шынжыр  ережесіне сәйкес келеді.
* l =2 ұзындығы ретінде берілген шынжыр  және  ережесіне сәйкес келеді.
*  символы қайталанатын шынжыр рекурсивтік ережемен  және  рекурсиясын анықтайтын ережеге сәйкес келеді.
*  және  символдарының кезектесіп қайталануынан құрылған шынжыр  және  ережесіне сәйкес келеді.
Алдымен символдың реттілігі мен бөлгіштері бар символдың реттілігі үшін грамматикаларды ретіне қою мысалдарын қарастырамыз. мұндай реттілікті жиі тізім деп айтады. 
Реттілік элементінің  деп белгілейік. Жай реттілік бір ғана  элемент тұра алады. Барлық басқа реттіліктер бұған дейінгі құрылған реттілікке тағы да бір элементтің қосылуы арқылы алынады. егер реттіліктің құрылған бөлігін терминалды емес  символымен, ал реттілікті  символымен белгілесек, онда грамматиканың келесі түріндегі ережесін аламыз: 
                                       
Алдыңғы тапсырмада  тізімі кем дегенде бір элементті өз құрамында ұстауы көзделген еді. егер де грамматикалық ережелерден туған шынжыр жиыны өз құрамында бос символды енгізе алса, онда құрылған ережелерге тағы да бір   ережесін қосу қажет. Бұл жағдайда ережелер жиынтығы келесі түрде болады:
                                       
Элементтің арасында бөлгіштер тұру қажет тізім реттілігін қарастырайық. Бөлгіш ретінде үтірді таңдайық. Жай тізім алдындағы жағдайдағыдай бір элементтен тұрады, ал бірнеше элементтен құрылған тізім реттілігі тізім элементтері бар бөлгіш тізімінен құрылған бөлігіне қосып жазу арқылы орындалуы мүмкін. бұл реттілікке сәйкес келетін ереже келесі түрде болады:
                                       
Егер бөлгіштері бар тізім бос болса, онда жоғарыда келтірілген ережелер жиынтығын оң жағы бос тағы да бір ережемен толықтыру керек. Нәтижесінде  келесі шығады: 
                                       
Көп жағдайда егер өзі кейбір тілдерді өкілет ететін шынжырлар жиынын мазмұндалған және бұл шынжырлар жиынын тудыратын грамматиканы құру қажет болса, онда төменде келтірілшендей іс-әрекет жасау қажет:
* Берілген шынжырлар жиынынан бірнеше мысал жазып алу керек. 
* Шынжырлар құрылымын бастауы мен соңын, қайталанатын символдар және символдар тобын ерекшелеп алып, талдау.
* Символдар тобынан тұратын күрделі құрылымдарға белгі енгізу.
* Әрбір белгіленген құрылымға қайталану құрылымының рекурсивті ережелерін қолданып ереже құру.
* Барлық ережелерді біріктіру.
* Шығару көмегімен түрлі құрылымды шынжыр алу мүмкіндігін тексеру. 
Келтірілген нұсқаулардың қолданылуын келесі мысалдарда қарастырайық.  тіліне терминалды сөздігі , ал тілді құрайтын құрылымы: 
а) әр шынжыр * әрпіне басталып, * * әрпіне аяқталады. 
b) шынжырдың басы мен соңының арасында не бос таяқшалар реттігі, немесе * символымен бөлінген бірнеше реттіліктер болуы мүмкін грамматика құруды қажет етеді.
* Алдымен төменде келтірілетін түрде болатын берілген тілдің бірнеше шынжырын құрайық:

                                   * *|||**,
                                  * *|*|*|**,
                             * *||*||||*|||||** ,
                             * *|||*|*||*||||||** 
                                      * 
* Келтірілген шынжырларды қарастыра отырып, олардың келесі құрылымдық компоненттерін ерешелеуге болады: 
  + шынжыр бастауы (*символы),
  + шынжыр соңы (**символы),
  + таяқшалардың бос емес тобы,
  + жұлдызшалармен бөлінген таяқшалар тобының реттілігі.
* Таяқшалар тобын  символымен, ал таяқшалар тобының реттілігін  символымен белгілейміз.
* Ерекшеленген құрылымдарды тізім ретінде қарастыруға болады. Осылайша таяқшалар реттілігі элементі таяқша болып келетін бөлгіштерсіз тізімді білдіреді. Бұндай тізімді тапсыратын грамматика ережесі келесі түрде болады:
                                       
                                       
                                       
Жұлдызшалармен бөлінген таяқшалар тобының реттіліг бөлгіштері бар тізім болып келеді. бұндай тізімнің элементі болып  таяқшалар тобы, ал жұлдызша  -  бөлгіші саналады. бұндай тізімді тапсыратын грамматика ережесін төмендегідей жазуға болады: 
                                       
                                       
                                       
Әрбір тіл шынжырының басы мен аяғы болу керегін ескере келе және грамматиканың бастапқы символы ретінде  таңдай келе, шынжырдың жалпы түрін анықтайтын келесі ережені аламыз: 
                                       
                                       
                                       
* Құрылған ережелерді біріктіре келе, төмендегі түрдегідей нақты грамматикалық ізделіп отырған кестесін аламыз: 
                                       
                                       
                                       
* Құрылған грамматика ережесінің көмегімен келесі, мысалы:

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

1.7 Бағдарламалау тілінің жай конструкцияларын мазмұндайтын грамматикалар

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

                                       
                                       
Бұл грамматика кестесінде  грамматикасында анықталған терминал еместер қолданылады.
Толық және заттық ауыспалыларды мазмұндауға арналған грамматика құру қажет делік. Нақты түрдегі ауыспалыларды мазмұндау 'real' немесе 'int' типті көрсеткіштермен басталу қажет.
 Толық мәтінде нақты түрдегі ауыспалыларды мазмұндау қайталануы мүмкін. толық мазмұндау құрылымын бөлгіштері бар екі енгізілген тізім ретінде көрсетуге болады. сыртқы тізім элементі ретінде қарастырылатын ішкі тізім бір типті ауыспалыларды мазмұндау болып келеді. Ішкі тізім бөлгіш ретінде нүктелі үтірді қолданады. Қарастырылып отырған грамматика кестесі келесідей жазылуы мүмкін: 
                                       
                                       
                                       
Айтарлық иемдену операторын оң жағында  грамматикасы мазмұндайтын жақшасыз формула ғана қолданылуы мүмкін дейік. Операторлардың бөлгіші ретінде нүктелі үтірді қабылдайық.
Операторлар реті нүктелі үтірді бөлгіші ретінде пайдаланатын тізімге сәйкес және ертеде анықталған идентификаторлардың конструкцияларымен қолдана отырып жақшасыз анықтамаларды келесі түрдегі грамматика кестесін аламыз:

                                       
                                       
Айтарлықтай Паскаль тілінде 'if', 'then', 'else' бөлгіштерімен ұқсас шартты операторлар қарастырылып отыр делік. Шарт ретінде бұндай операторларда екі идентификатордан тұратын   және , белгілерімен байланыстырылған, ал оператор ретінде 'then' немесе 'else' оң жақтағы арифметикалық формулалармен иемдену операторларын қолдануға рұқсат беріледі. Бұндай оператордың құрылымы жазылып алынатын ұзындық ретінің түрлерімен анықталады да, оларды мазмұндауға жай ғана компоненттерді атап өтуге болады. Бірінші реттілік толық және қысқартылған шартты операторларды анықтайды, ал екінші-<<қарым-қатынас>> конструкциясын. Бұл реттіліктерді беретін грамматика кестесі келесідей болады:
                                       
                                       
                                       
Бұл грамматикада   грамматикасының кестесімен анықталады.
Енді Паскаль тілінде қолданылатын 'while', 'do', 'repeat', 'until' бөлгіштері тәріздес цикл операторларын мазмұндауды қарастырайық.
 Әр оператор жоғарыда құрылған  және  грамматикада анықталған терминал еместер қолданылатын жай ғана реттілік түрінде мазмұндалуы мүмкін тәжірибеде көбінесе ережелердің оң жағы терминалдық символмен басталатын грамматикамен жұмыс істеген тиімдірек жағдайлар жиі кездеседі. 
Мұндай грамматикаларды құру берілген тіл конструкциясына арнайы жеке ереже құрылатын әр терминалдық символ үшін грамматика құру қажеттілігіне әкеледі. Қарастырылып жатқан цикл операторларына анықталған терминал емес символдарды қолданған грамматика кестесі келесі түрде болады:
                                       
                                       
                                       
                                       
Бэкустер немесе синтаксистік диаграммалар.
Формалды грамматика құру міндетіне жиын шынжырын мазмұндау мен берілген терминалды алфавит үшін терминалды емес символдар алфавитін анықтау және грамматика кестесін құру қажеттілігі жатады. Тәжірибеде шешімді іздеу берілген шынжырдың құрылымдық талдауын қолданумен орындалады. Бұндай талдау нәтижесінде шынжырдың құрылымдық компоненттреі анықталады да, олар терминалды емес грамматика сөздігіне енеді, ал шынжырдағы ілесу компоненттерінің реті грамматика ережесін құру негізі болып келеді.

Дәріс №2 Мәнмәтінді-бос грамматикалар мен дүкендік автоматтар

2.1 Тудырмайтын, жетпейтін және пайдасыз символдарды анықтау

Грамматиканың төрт түрінің ішінде мәнмәтінді - бос грамматика бағдарламамлау тілдеріне қосымша мен компиляциялар көз қарасынан ең негізгі болып келеді.  - грамматика көмегімен бағдарламамлау тілі құрылымының үлкен бөлігін анықтауға болады.
 Бағдарлама тілінің конструкциясын беретін грамматикаларды құру кезінде олардың өзгеруіне сүйенуге жиі тура келеді, сондықтан алдымен  - грамматиканың жай, бірақ та негізгі бірнеше өзгерулерін қарастырайық. Өзгерудің бірінші түрі грамматикадан пайдасыз символдарды жоюмен байланысты. Символдар грамматикада пайдасыз болып қалуы келесі жағдайларда болады: 
а) егер символ шығару кезінде алына алмаса
б) егер символдан соңғы терминалды шынжыр алына алмаса. 
Алдымен соңғы шынжырды шығаруға мүмкін емес символдарды айқындау алгоритімін қарастырайық. Егер  символынан соңғы терминалды шынжыр шығарылмаса ол тудырылмайтын деп аталады. 
     	Грамматикалардың ережесін қарастырып отырғанда оң жақ символдарының барлығы тудыратын деген шешімге келсек, онда сол жақта тұрған символдар да тудыратын болып келеді. Ақырғы тұжырым тудырмайтын символдарды байқау процедурасын келесі түрде жазуға мүмкіндік береді: 
    	1 Оң жағы терминал еместерді құрамынды ұстайтын бір болсын ереже  табылатын терминал еместер тізімін құру.
    	2 Егер жоғарыда айтылған ереже табылатын болса, онда терминалдар емес тізіміне оның сол жақында тұрғандарды енгізу.
  	3 Егер 2 қадамда тізім толықтырылмаса, грамматиканың барлық тудыратын терминал емес тізімі алынады, ал оның құрамына енбеген барлық терминал еместер тудырмайтын болып келеді.
                                       
                                        
                                       
 грамматикасына сәйкес талдай келе бұнда  және  символдары тудырмайтын екеніне көз жеткіземіз. Тудырмайтын символдары құрамында бар ережелерді жойған соң аламыз. 
Егер  ешбір шығарылатын шынжырда болмаса, онда  -  грамматикада  символы жетпейтін деп аталады. 
Егер сол жақтағы терминал емес символы жететін болса, онда оң жақтағылар да сондай болатынына көз жеткіземіз. бұл ереже қасиеті жетпейтін символдарды анықтау процедурасының негізі болып келеді де, оны келесі түрде жазуға болады: Бастауыш символдан тұратын бір элементті тізім құру. 
* Егер сол жағы тізімге енгізілген болса, онда оның оң жағындағыларда тізімге енгізілетін ереже табылса. 
*  Егер 2  -  қадамда тізімге жаңа терминал еместер қосылмаса, онда барлық жеткен терминал еместер тізімі жетпейтін болып келеді. 
Грамматикалардың пайдасыз символын келесі әдіспен анықтауға болады:  жататын  символы  -грамматикасында жетпейтін немесе тудырмайтын болып келсе, онда ол пайдасыз деп аталады.
  	Пайдасыз символдарды алдымен тудырмайтын, ал содан соң жетпейтін символдары құрамында бар ережелерді грамматикадан жоя келе шығарып тастауға болады. Иллюстрация ретінде келтірілген ережелерге дәлел түрінде келесі грамматикалардағы өзгерулерден орындаймыз: 

                                       

Алдымен  және  тудырмайтын символ екенін байқап, тудырмайтын символдары бар ережелерді жоя келе  аламыз.
Алынған схемада  символы жетпейтін символ болып келеді. Бұл символды құрамында ұстайтын ережені шығара келе  аламыз.
Келтірілген грамматикалар.
Егер  - грамматикасының құрамында пайдасыз символдар болмаса, онда ол келтірілген деп аталады.
 түріндегі ереже оң жақты  рекурсивті, ал  түріндегі ереже  -  сол жақты рекурсивті деп аталады.

2.2 Сол жақты рекурсивті және шынжырлы ережелердің шығарылуы

 	Оң жақ рекурсивті ережесі бар әрбір   -  грамматикасы үшін сол жақ рекурсивті ережесі жоқ эквивалентті Г грамматикасын құруға болады. 
Эквивалентті грамматика құру тәсілі келесідей:
Айтылған тәсілмен сол жақты рекурсиялы  - де барлық ережелерді ауыстыра келе  грамматикасын аламыз және де  себебі  грамматикаларда шығарылған әрбір шынжыр  грамматикаларда құрылуы мүмкін.  және  - гі шығару реттерін қарастырайық.  грамматикаларда шынжырды шығару түрі келесідей: 

                                       
                                       
 -  грамматикаларда осы шынжыр былайша шығарылады: 
                                       
                                       
                                       
Өзгеру техникасын көрсету үшін мысал қарастырайық.  грамматикасын өзгерту қажет, ол 


кестесімен берілген. 
Мазмұндалған тәсілге сүйене келе  ережесін   және   ережесіне, ал  және   ережесіне өзгертеміз. Нәтижесінде келесі кестедегі  грамматикасын аламыз: 
                                       
                                       
                                       
және оның құрамында сол жақ рекурсивті ереже жоқ.
 болатын  түріндегі грамматика ережесі шынжырлы деп аталады.
Шынжырлы ережесі құрамында бар ,  - грамматикасы үшін оған эквивалентті шынжырлы ережесі жоқ грамматикасын құруға болады. Дәлелдеу ойы келесіде: егер грамматика схемасы  түрінде болса, онда ондай грамматика  түріндегі схемамен эквивалентті болады, себебі  шынжырындағы  схемалы грамматикадағы шығару  схемалы грамматикасында  ережесінің көмегімен алынады. 
Жалпы жағдайда ақырғы пайымдауды төменгіде келтірілгендей дәлелдеуге болады:  - ды екі  және , жиындарына бөлеміз және  құрамына барлық  түріндегі ережелер енеді.  барлық ережесі үшін  ереже жиындарын табамыз. Ал оларбылай құрылуы керек: егер  және  - де  ережесі бар (бұнда  сөздігінің шынжыры) болса, онда  - ға ережесін енгіземіз. , және барлық жат  жиындарын біріктіру тәсілімен жаңа  схемасын құрамыз. 
Сонда берілген грамматикаға эквивалентті және  түріндегі ережесі құрамында жоқ  грамматикасын аламыз.
Мысал ретінде  грамматикасынан төмендегі кестелі шынжыр ережелерін шығаруды орындаймыз:

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


2.3 Қысқартылмайтын грамматикалардың түрленуі

  түріндегі ереже жоюшы ереже деп аталады.
Ал грамматика қысқартылмайтын немесе жою ережелерінсіз грамматика деп келесі жағдайларда аталады: 
* егер грамматика кестесінде жою ережелері болмаса 
* немесе грамматика кестесінде  грамматикасының бастауыш символы және оң жағында кездесетін  түріндегі бір ғана ереже болса. 
Жою ережелері бар грамматикалар үшін келесі тұжырымдар дұрыс болады. 
Әрбір жою ережесінің құрамында бар   грамматикасы үшін оған эквивалентті  түріндегі қысқартылмайтын  грамматикасын құруға болады.
Қысқартылмайтын грамматиканы құру жою ережелерінде терминал еместерді шығару нәтижесінде алынған қосымша ережелерді құру жолымен берілген грамматика ережелер санының көбеюін көздейді. Қосымша ережелер құру үшін грамматиканың барлық ережелерінде жою терминал емес символдарды барлық мүмкін бос шынжырлармен алмастыру қажет. Егер грамматикада  түріндегі ереже мен грамматиканың басқа ережелерінің оң жағының құрамына енетін символы болса, онда бастапқы жаңа   символын енгізіп,  ережесін төмендегі екі жаңа ережемен алмастыру:  және .

2.4 Дүкендік автоматтар

-грамматика шынжыр құрылымын анықтайды және нақты тілдегі шынжырды құруға мүмкіндік береді.
Формалды тілдер және грамматикалармен байланысты жұмыстарда кіріс лентасынан, басқару құралы және көмекші лента ол дүкен немесе етек деп аталатын көмекші лентадан тұратын дүкендік автомат моделі қолданылады.
Кіріс лентасы торларға бөлініп, ол торларға кіріс алфавитінің символдарын жазуға болады. Кіріс лентасының бастауы (басы) бір жаққа қарай ғана  -  оңға немесе орнында, қозғалып тұрады. Ол тек оқып тұру қызметін ғана атқарады. Ал көмекші лента оқып оқып және жазып алу қызметтерін атқара алады. 
Қарастырылып жатқан кезде бүршік астындағы позицияны дүкен шыңы деп атайды.
 дүкендік автомат жеті  объектілерінің арақатынасымен анықталады. 
 функциясы  үштігін  екілігіне суреттейді, онда  және  - символ в вершине магазина, для детерминированного автомата или в множество падетерминалданған автоматтар немесе детерминалды емес автомат жиыны үшін дүкеннің шыңындағы  символ. 
Бұл функция дүкендік автоматтың жай-күйінің кіріс лентасынан және кіріс бүршігінің орын ауыстыруы кезінде болатын жағдайын мазмұндайды. Кейінгіде дүкендік автоматтарды құру кезінде кіріс бүршігінің орын ауыстыруынсыз өзгеретін орын ауыстыру функциясының екі түрі қажет болады:
1 орын ауыстыру функциясы бос символдар кіріс символы ретінде: , ол кіріс лентасының оқылып жатқан бүршігінің астындағы символға қарамастан дүкен шыңынан  символын оқып алып, автомат жай-күйін  және шыңдарын дүкенге жазып алып өзгертеді.  
2 орын ауыстыру функциясы нақты кіріс символымен: , ол шынжырдың жай-күйінің өзгеруі мен жазылуын дүкенге   символы кіріс бүршігінен оқылатын жағдайда, ал дүкен шыңында  символы тұратын болса, қосып жазады. 

2.5 Дүкендік автомат жұмысы

Автомат жұмысын мазмұндау үшін конфигурация түсінігін енгізу керек.  автоматының  конфигурациясы деп  үштігін атайды. Онда  - басқарылатын құрылғының ағымды жағдайы,  шынжырының қолданылмаған бөлігі, бұл шынжырдың нағыз сол жақты  символы бүршік астында болады. Егер  болса, онда кіріс шынжыр оқылады деп саналады. 
-дүкенде жазылған шынжыр,  ең оң жақты символ дүкен шыңы болып саналады. Егер  болса, дүкен бос. Автомат жұмысы конфигурацияны ауыстырушы ретінде көрсетілуі мүмкін: 
                                       
                                       
                                       
Сонымен, автомат жұмысы кезінде келесідей үш жағдай болуы мүмкін:  жұмыс такті анықталып, орындалуда,  анықталған жоқ, бірақ   функциясы анықталды және бос такт орындалуда.  және   функциялары анықталмаған жағдайда автомат жұмысын тоқтатады.
Бастауыш конфигурация деп  конфигурациясы аталады. Онда  - бастапқы жай-күйі және  - дүкен түбінің маркері, ал қорытынды деп  конфигурациясы аталады, онда . 
                                       
                                       
                                       
соңғы жай-күй жиынына жатады.
Егер конфигурация реттілігі сақталса, онда  шынжыры автоматы үшін рұқсат етілетін деп аталады. Яғни онда бірінші конфигурация шынжырымен бастауыш, ал ақырғы 
                                       
                                       
                                       
аяқтаушы болып келгенде, бұнда .
 автоматымен рұқсат етілетін шынжырлар жиыны автомат рұқсат беретін немесе анықтайтын тіл деп аталады да,  бейнеленеді  

                                       


Дәріс №3 Азаймалы (бәсеңдейтін) және өрмелі (жоғары көтерілуші) танушылар 

3.1 Азаймалы танушылар және  -грамматикалар
 	
Терминалданбаған дүкендік танушылар жұмысының модельденуі реттіліктің бастауыш жай-күйден соңғы жай-күйге ауысуын іздеумен байланысты. Іздеу жеке-жеке қадамдардан тұрады.
 Және олардың әрбіреуі сәтсіздікке және бастапқы жай-күйге әкелуі мүмкін. Бұндай іздеу уақытты көпалатындықтан тәжірибеде қайтымсыз жұмыс істейтін детерминалданған танушыларды қолданады. Бұл танушылар -тілдердің шектеулі кластарын ғана қолданысқа жібереді, бірақ олар бағдарламалау тілдерінің барлық синтаксистік жақтарын көрсетеді. 
Танушыларды азаймалы және өрмелі деп екі категорияға бөлуге болады.
Азаймалы танушылар ережелерді жоғарыдан төмен өңдейді, яғни жоғары ережелерді төменгілерден бұрын. Ал бұл уақытта кіріс анализаторлары төмендегі ережелерді жоғарыдағылардан бұрын қолданады. Детерминалданған автоматтардың мүмкіндіктері мен олардың тұрғызылу тәсілдерін көрсету үшін бұл бөлімде  түріндегі грамматикалар тудыратын азаймалы танушылар қарастырылады.   
  	 атауы Left сөзінен шыққан, себебі анализатор кіріс шынжырын солдан  -  оңға қарай көреді. Тәжірибеде көбінесе  грамматика класы қолданылады. Олар үшін ағымды позицияда орналасқан детерминалданған бір кіріс символды танушылар жұмыс істейді. Оқудың бірінші қадамы ретінде азаймалы танушылардың  грамматика кластары ішіндегі бір реттілікті қараймыз. 
Бөлінген ауыспалылар.
Құрамында жою ережелері жоқ мәнмәтінді-бос грамматика төмендегі келесі екі шартты орындаса ғана бөлінген немесе жай деп аталады:  
  + Әр ереженің оң жағы терминалмен басталса.
  + Егер екі ереженің сол жағы бірдей болса, онда бұл ережелердің оң жағы түрлі  терминалдық символдармен басталуы керек. 
Бөлінген грамматиканың негізгі қасиеттерінің бірі  -  олардың әрқасысына өрлемейтін детерминалданған танушы құруға болады. 

3.2 Детерминалданған азаймалы танушылардың тұрғызылуы

Тұрғызылу тәсілі грамматиканың әр ережесіне танушы командасын салыстыруды алдын ала ескереді. Алдыңғы бөлімде мазмұндалған -грамматика үшін танушыларды тұрғызудың жалпы тәсіліне сәйкес -толық сөздіктердің символдар шынжыры және а терминалды сөздікке жататын,  түріндегі грамматиканың әрбір ережесіне кіріс бүршігінің қозғалуынсыз жұмыс беретін және онда  шынжырының айналы көрінісі болып келетін
                                       
                                     (*) 
                                       
командасын сәйкесінше қою керек.  Нәтижесінде бұл команданың орындалуы а терминалы дүкен шыңында болатынын атап өтейік.
 Бөлінген грамматикада әрбір ереже терминалды символдан және бұл терминалдар қайталанбайтынын ескере отырып, (*) командасы кіріс бүршігінің астында  терминалы болғанда және одан кейін (**) командалы орындалу қажет. 
(**) түріндегі нақтылықты жою мен жұмыс тактілерінің санын азайту үшін, (*) және (**) түріндегі командаларды бір командаға біріктіреміз. Және терминалды символдар тек қана сол жақ позиция ереженің оң жақ бөлігінде орналасуы мүмкін екенін ескере өту жөн.
  Бұндай терминалдар үшін  түріндегі команда құру қажет. Соңғы күйге көшу үшін  ережесін қосамыз да, бастапқы танушы конфигурация ретінде  формуласын аламыз, бұнда -грамматиканың бастапқы символы, ал -берілген кіріс шынжыры. Жоғарыда келтірілген ережелерді қолдана отырып  бөлінген грамматикасы үшін танушы құрамыз. 
Нәтижесінде:
                                       
                                       
                                       
Құрылған автоматтың жұмысын bbabab шынжырының талдауы мысалымен көрсетуге болады: 
                                       
                                       
                                       
Келтірілген конфигурация реттілігі әрбір конфигурацияда бір ғана детерминалданған танушы командасы қолданыла алатынын көрсетеді. 

3.3 Нашар бөлінген грамматикалар. -грамматикалар
 	
Грамматиканың келесі детерминалданған тілдерді тудыратын класы жай бөлінген грамматикалар деп аталады. Бұл грамматиканың бөлінген грамматикадан ерекшелігі грамматика кестесінде жою ережелерін қолдануға болатындығы. Құрамында жою ережелері бар бөлінген грамматика жай бөлінген грамматикалар класына жата бермейді. Жай бөлінген және  грамматикаларды анықтайтын тәсілді құру үшін біз ТАҢДАУ жиыны, АЛҒАШҚЫ және КЕЛЕСІ функциялары сияқты жаңа түсініктер енгізуіміз керек.
ТАҢДАУ жиыны әрбір ереже үшін құрылады және пайда болған кезде оқылып жатқан танушы бүршігінің астында бұл ережені қолданатын терминалды символдарды өз құрамына енгізеді. 
ТАҢДАУ жиынын анықтауда АЛҒАШҚЫ және КЕЛЕСІ функциялары қолданылады. АЛҒАШҚЫ функциясының аргументі ретінде  толық сөздігінің кез келген шынжыры бола алады, ал АЛҒАШҚЫ  функциясының мағынасы ретінде терминалдық символдар жиыны болады. Және олар  шынжырынан шығарылатын шынжырдың бірінші орындарында тұра алады.  
АЛҒАШҚЫ  функциясының мағынасын келесі ережелерді қолданып анықтауға болады:
*  Егер  шынжыры терминалды символға басталса және түрінде болса, онда АЛҒАШҚЫ ()  функциясы -ға тең.
*  Егер  шынжыры  бос шынжыр болса, онда АЛҒ.
*  Егер  шынжыры терминалды емес  символына басталып,  түрінде болса және грамматика кестесінде ережесі бар болып, кез келген жерінде  символы тұра алса:  және де егер  тұжырымы болмаса, онда АЛҒ функциясы біріктірілген
                                       
 АЛҒАШҚЫ=АЛҒАШҚЫАЛҒАШҚЫАЛҒАШҚЫ 
                                       
жиынын көрсетеді.
*  Егер  шынжыры терминалды емес символға басталып  түрінде болса, грамматика кестесінде  түріндегі ережесі енеді және  жою терминал емес символы болып танылады, яғни   бар болса, онда функция келесідей:

АЛҒАШҚЫ=АЛҒАШҚЫАЛҒАШҚЫАЛҒАШҚЫ АЛҒАШҚЫ
                                       
КЕЛЕСІ функциясының аргументі ретінде терминалды емес, мысалы  символы табылады, ал КЕЛЕСІ функциясының мағынасы ретінде шынжырда  терминал емес символынан кейін жүре алатын терминалдар жиыны болады. КЕЛЕСІ функциясының мағынасы келесі ережелерге сәйкес орындалады:
1) Егер грамматика кестесінде келесі түрдегі 
                                       
және барлық шынжыры болса, онда 
                                       
         КЕЛЕСІ= АЛҒАШҚЫАЛҒАШҚЫ ...
                                       
Дүкендік автоматтардың ауысуын құру үшін қажет болатын ТАҢДАУ жиынын АЛҒАШҚЫ және КЕЛЕСІ функциялардың көмегімен келесідей анықтауға болады: , которое потребуется нам для построения переходов магазинных: 
1  Егер грамматика ережесі   түрінде болып,  жою шынжыры болмаса,яғни басқаша айтқанда  бар болған жағдайда: ТАҢДАУ=АЛҒАШҚЫ
2  түріндегі грамматиканың жоюшы ережелеріне таңдау жиыны келесідей анықталады:  

                           ТАҢДАУ=КЕЛЕСІ
                                       
3 Егер грамматика ережесі  түрінде болса және  жоюшы шынжыр болып табылса, онда  

                ТАҢДАУ= АЛҒАШҚЫКЕЛЕСІ
                                       
Енгізілген түсініктерді қолдана отырып жай бөлінген грамматика анықтамасын беруге болады. -грамматика төмендегі үш шарторындаған жай бөлінген деп аталады: 
* әр ереженің оң жағы  бос шынжыр болып келсе немесе терминалды символдан басталса  
* егер екі ереженің сол жағы бірдей болса, онда ережелердің оң жақтары әртүрлі символдармен басталуы керек  
*  сияқты терминал емес әрбір  үшін бастапқы символдар жиыны : 
                                       
                        АЛҒАШҚЫКЕЛЕСІ=
  	  	3.4 Дүкендік автоматтың тұрғызылуы

 шарттарына жауап беретін грамматика үшін келесі анықтама тән.
	Анықтама. Әрбір   грамматикасы үшін  грамматикасы тудыратын тілді қолданысқа жіберетін детерминалданған  дүкендік автоматын құруға болады.
Берілген грамматикасы үшін дүкендік автоматты құру міндеті келесі тәсілмен беріледі.  грамматикасы берілген және  автоматын анықтайтын объектілерді анықтау қажет. 
Автомат берілген грамматика тудыратын тілдер шынжырын жіберуі қажеттігін ескере отырып,  қабылдаймыз. Автоматты мазмұндауды жеңілдету үшін бастапқыда, аяқтаушыда, яғни  және  болып келетін , жай-күйінде болатын айтарлық.
 Дүкендік алфавит ретінде  қабылдайық.Функциялардың орын ауыстыруды берілген грамматика ережелерінің ТАҢДАУ жиынын қолданып келесі тәсілмен орындаймыз: 
*  Әрбір  түрінде терминалды символмен бастайтын грамматика ережесі үшін  автоматының командасын құрамыз, бұнда  -шынжырының айналық көрінісі болып табылады. 
* Әрбір  түріндегі терминалды емес символмен басталатын грамматика ережесіне үшін   автоматының командасын құрамыз, бұнда  -кіріс бүршігінің қозғалмауынсыз пайда болған автомат командасы, ал шынжырының айналық көрінісі. 
* Әрбір  түріндегі грамматика жоюшы ережесі үшін  автоматының командасын құраймыз.
* Әрбір грамматика ережелерінің оң жағының немесе ортасында орналасқан  терминалды символы үшін   командасын құрамыз.
* Аяқтаушы күйге көшу үшін   командасын құрамыз. 
Автоматтық бастапқы конфигурациясы ретінде келесі берілген кіріс  шынжырымен   формуласын қолданамыз.
Келтірілген ережелерді пайдаланып  , грамматикасы үшін төмендегі дүкендік автомат құрамыз: 
                                       
                                       
Алдымен әрбір ережеге ТАҢДАУ жиынын құрып, ол грамматика  грамматикасы бола алатындығын тексереміз: 

(1) ТАҢДАУ=АЛҒАШҚЫ=
(2) ТАҢДАУ=АЛҒАШҚЫ
(3) ТАҢДАУ=АЛҒАШҚЫ
(4) ТАҢДАУАЛҒАШҚЫ
(5) ТАҢДАУКЕЛЕСІ=КЕЛЕСІ

Сол жағында  символымен және сол жағында   символымен ережелері үшін ТАҢДАУ шынжырында бірдей элементтер жоқ, соған сәйкес қарастырылып жатқан грамматика  грамматика класына жатады. ТАҢДАУ функциясын пайдаланып ізделіп отырған автоматтарға сәйкес командалар құрамыз:
 
                                      (1)
                                      (2)
                                (3)      
                                      (4)
                                     (5) 

Жабылатын жақшалар  (2) ережесінің аяғында орналасқанын ескеріп  командасын құрамыз.
Сондай-ақ аятаушы соңғы күйге көшеді:  командасын құрамыз. автомат жұмысын . Кірісшынжыр мысалында тексереміз және конфигурация тізбегін аламыз: 
                                       
                                       
ол кіріс шынжырын құрылған автомат жіберетінін көрсетеді.
3.5 Өрлеме танушылар

Өрлеме танушы жұмысының негізінде оң жақ шығыс көмегімен алынған шынжырда қолданылатын, өрлеу немесе ұю операциясы жатыр. Бұл операция шығысқа қарама-қарсы болып келеді. Оның мәні ереженің оң жағы сол жағымен алмастырылатынында. Жұмыс кезінде кіріс танушы кіріс шынжырдың символдарын дүкенге ауыстырады және дүкенде кез келген ереженің оң жағы барып түскен кезде ұю операциясы орындалады. Бұл операцияны келесі тәсілмен анықтауға болады.
  	Анықтамаережесі мен  шынжыры кестесінде кездесетін  грамматикасы берілген дейік. Егер  ережесі шынжырының оң жағы шынжыр бөлігі болса, онда грамматиканың ережесінің оң жағын сол жақпен ауыстырып  шынжырын алуға болады. Бұл жағдайда  шынжыры  шынжырының оралуы әдісімен алынып, қолданылады
  	Анықтама. Шынжыр негізі деп қарастырылып жатқан оң жақтап шығару кезінде қолданылған ақырғы ереженің оң жағының кіруін айтады. Келтірілген шынжырды тануды орындайтын дүкендік автомат жұмысын келесі түрде көрсетуге болады:
 
Кесте 3.1 - -грамматикалары
                                  Дүкен
Кіре беріс
Іс-әрекет


ауысу


ауысу


ұю (1)


ауысу


ауысу


ұю (1)


ауысу


ұю (4)


ұю (3)


ұю (2)


жіберу

	Детерминалданған өрлеу танушылар кез келген -грамматикалары үшін емес, тек қана бұндай грамматикалардың нақты кластары үшін ғана құрылады. -грамматикасының ішіндегі ішінаралық ең тараған -грамматикалар. 
Бұл грамматикалар солдан оңға қарағанда шынжырды тануды қамтамасыз етеді. Ол туралы  (Left) әрібі айтып тұр.  (Right) әрібі оралу орындайтынын айтады. k параметрі шынжырдың оралуы үшін  k артық емес символ көруге болатынын көрсетеді. Жалпы жағдайда -грамматикасы өте күрделі болғандықтан тәжірибеде -грамматикалық ішіндегі кластары: , немесе  -жай (Simple)  кіріс танушыларын жайға тұрғызу мүмкіншілігін беретін грамматикалар қолданылады. 

3.6 Жою ережелерімен грамматикалар үшін өрмелі танушылар

Алдымен жою ережелері мен грамматикалары үшін өрмелі танушы ережелерін тудыруды тұжырымдамас бұрын, мысал қарастырамыз және танушы қандай қосымша кізметтер атқаруы қажет екенін анықтауға тырысамыз. 
Екі операция жақшасыз арифметикалық формуланы беретін төмендегі грамматика берілген дейік: 
                                       
                                       
                                       
 	Бұл грамматикалық төртінші ереженің оң жағы бос болғандықтан -танушыны тұрғызудың алғашқы төрт процедурасына әсер етпеуі керек. Ал жою ережесі келесі түрде болады: 
  
Кесте 3.2 - Орын ауыстырумен танушы іс-әрекеті кестесі
                                       1
                                       2
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
  	Шығару кезінде грамматиканың төртінші ережесі шығарылып жатқан шынжырдан терминал емес  символын алып тастауға мүмкіндік береді. Осыған сәйкес оралу кезінде бұл ережеге  символын дүкенге жазу операциясын теңестіру қажет. Бұл операцияны Ұю (4) немесе Ұю(4) деп белгілейміз. Бұл операция қандай жағдайда орындалу керегін анықтау үшін терминал емес  символы шығарылатын шынжырда қандай символдардан кейін жүретінін анықтау қажет. 
 артынан жүре алатын   символдар жиынын  символы КЕЙІНІРЕК жиынының қайсысына енетінін анықтап табуға болады. Бұл жиынды көшу кестесінде келісі тәсілмен табуға болады: символымен белгіленген бағананы, көшу кестесін аламыз да, бұл бағанамен қиылысқан жерлердегі барлық бос элемент бар жолдарды табамыз. 
Бұл  жолдарының белгілену жиыны  символы ере алатын грамматика жиыны болып табылады.   символының артынан КЕЛЕСІ жиынының символдары ере жүретінін ескере отырып,  және  параметрлеріне сәйкес келетін кестенің элементтеріне  операциясын жазу керектігіне көз жеткіземіз. Нәтижесінде берілген грамматика үшін 3.2-кестені мен кіріс танушысын беретін 3.3-кестені аламыз:
 
Кесте 3.3 - Грамматика
                                       3
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       

Кесте 3.4 -  түріндегі кіріс шынжыр үшін танушы жұмысын мазмұндайтын конфигурация реттілігі төмендегідей
                                   Дүкен
Кіре беріс
Іс-әрекет






























 	
Қарастырған мысал -танушылар өрлемелі ережелерін тұрғызуда берілген грамматикада жою ережелерінің санын есепке алып отыратын тағы да бір 1 пунктісімен толықтыру қажеттігін көрсетеді. Тұрғызудың бұл процедурасын келесі түрде жазамыз: 
1  нөмірлі  жою ережесі үшін іс-әрекет кестесін элементтермен толтыру келесі тәсілмен орындалады:  
 символы артынан ере алатын грамматикалық кірістер жиынын табу үшін  символымен белгіленген ауысым кестесінде бос емес элементтері  бар жолдарды белгілейміз. 
Бұл бағанада бос емес эелементтері бар жолдарды белгілейміз айтарлық бұл жолдар , символдарымен белгіленген. КЕЛЕСІ жиынын табамыз. Бұл  символының артынан еретін грамматикалық символдар жиыны. Әрбір  элементер жұбы үшін іс-әрекет кестесінде сәйкес торға ҰЮ операциясын жазамыз.  
Танушыларды тұрғызу процедурасы нәтижеге егер жою ережелері бар берілген грамматика  грамматикасына жатса ғана жете алады. Егер де тұрғызу үрдісінде қарсылықтар байқалса, онда ол берілген грамматика   грамматикасы класына жатпайтынын және оған арнап -танушы құруға болмайды дегенді білдіреді.
Дәріс №4 Ауысуды мазмұндау тәсілдері мен түрлендірушілер

4.1 Ауысуды мазмұндау тәсілдері мен түрлендірушілер

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


Бұндай тұрғызу нәтижесінде нақты мән кіріс және шығыс шынжыр ережелерінің арасындағы сәйкестікке келеді. 
Қарастырылып жатқан ауысу тәсілі -кестесі түсінігімен тұжырымдалып, келесі тәсілмен анықталады.  	Ауысудың синтаксистік басқару кестесі (-схемой) деп төмендегі бес объектінің жиынтығын атайды: 
                                       
                                       
                                       
бұнда  - терминалды емес символдар жиыны,  -  кіріс шынжырын құруда қолданылатын терминалды символдар жиыны. Келтірілген анықтамадан -кестенің әрбір ережесі өз құрамына кіріс алфавит пен терминалды емес символдардан құралған шынжырды енгізіпуі керектігін көреміз. 
  -  кестесінің көмегімен сәйкес шынжырлар жұбын құруға болады. Бұндай тұрғызылу -кестесінің шығысы деп, ал алынатын жұптар шығарылатын жұптар деп аталады. 
       	Шығарылатын жұптар түсінігі көмегімен -кестесі беретін ауысымды анықтауға болады. 
Бұл кесте кіріс сөздері нөлдер мен бірліктерден, ал шығыстары  әріптерінен тұратын ауысымды анықтайды. Кіріс шынжырының нөлдеріне  әрпі, ал бірліктерге шығыс шынжырдың  әрпі сәйкес келу керек. Және шығыс шынжыр әріптері кіріс шынжыр әріптерінің айналық көрінісі болу керек. -кестеде қарастырылып жатқан шығыс келесі түрде болуы мүмкін:

                                       
Шынжырлардың ауысуын жүзеге асыратын детирминалданған құрылғыларды құру үшін ережелер түріне қосымша шектеуліктермен келетін -кестелер қолданылады. Олар төмендегідей анықталады:
-кестесінің жай түрінің мысалы  ретінде постфикстік және оларға сәйкес инфикстік формула түрінде ауысуды беретін    -  кестесін келтіреміз: 
                                       
                                       
                                       
	Ең сол жақты терминал емес символдарды аралық шынжырлар ережесін қолдану арқылы орындалатын -кестеде шығару келесі түрде болады:
                                       
                                       
                                       
Жай -кестесі мысалы ретінде    -  кестесін қарастыруға болады. Ол инфикстік формулаларды постфинкстік поляк формулаларына ауысуды береді.
                                       
                                       
                                       
Келтірілген -кестедегі шығару келесі түрде болады:
                                       
                                       
                                       
Жалпы жағдайда -кестесінің берілген ауысуға тұрғызылуы екі грамматиканы тұрғызуға қарағанда күрделі болып келеді, себебі бұл грамматикалар арасындағы байланыс немесе сәйкестікті ескеру керек. 
Бірақ, жай -кестелері үшін тұрғызылулар кіріс және шығыс шынжыр ережелерінде терминал емес символдардың орналасуы бірдей болу керектігіне байланысты жеңілірек болады. Жай -кестені тұрғызуды кіріс тілін анықтайтын грамматикаларды тұрғызудан бастаған дұрысырақ болады. 
Бұндай грамматика ізделіп отырған -кестесінің кіріс грамматикасы болу керек. Шығыс грамматикасын тұрғызуды -кестесінің ережелерін тұрғызумен сәйкестіруге болады. 
Кіріс шынжырының терминал емес символдары шығыс шынжырда сол ретпен жүру керектігін ескере отырып барлық терминал емес символдарды кіріс шынжырдан шығыс шынжырға ауыстырып, онда шығыс терминалды символдарды қойып қоямыз. Және бұл жағдайда терминал емес символдардан ғана тұратын ережелер кіріс және шығыс грамматикаларда бірдей болып шығады.
 Мысал ретінде келесі формуланы қарастырамыз: 
                                       
                                        
                                       
                                       
      	Шығыс формулаларнда жақша болмау керегін ескере отырып,  табамыз. Грамматиканың бірінші ережесінде бір ғана кіріс терминал болғандықтан -кестесінің ережесін  түрінде жазуға болады.
Грамматиканың үшінші ережесінде терминал болмағандықтан  аламыз.
Бесінші ереже жоюшы болып келгендіктен шығыс  грамматикасында сақталуы қажет.
Екінші ережеде тұрғызу ережесіне сәйкес болмау керек жақшалар бар болғандықтан біз  аламыз.
-кестесінің ережесін грамматиканың төртінші ережесі бойынша құрған кезде постфикстік жазылымда қосу белгісі екінші опреанд артынан жүру керегін және ол формулаға терминал емес  символы болып енгізілетінін ескере отырып, -кесте ережесін  түрде аламыз.
Тұрғызылған ережелерді біріктіре отырып, ізделіп отырған -кестесінің ережесінің жиынтығын келесі түрде аламыз:
                                       
                                       
-кестесінің дұрыс құрылғандығына көз жеткізу үшін төмендегі мысалды қарастырамыз: 
                                       

  + Ауысу немесе трансляциялауды мазмұндау

Қарастырылып отырған кіріс шынжырына арналып құрылған постфикстік жазылым дұрыс екенін байқаймыз.
 	Трансляциялау грамматикасы (-грамматика) деп символдары іс-әрекет символы деп аталатын терминалдық символдар жиыны кіріс және шығыс символдар жиынына бөлінген -грамматика аталады. 
 -  грамматикасына мысал ретінде келесі грамматиканы келтіруге болады:  
                                       
                                       
                                       
Кіріс және шығыс алфавиттерінде бірдей символдарды қолданғанда шатаспау үшін шығыс символдарын фигуралық жақшалармен белгілейміз. Бұндай белгілеулермен қолданылатын  грамматикасының ережесі төмендегідей болады:
                                       
                                       
                                       
Трансляциялау грамматикаларында шшығулар басқа -грамматикаларда сияқты орындалады. 
Әрбір  - грамматикадан біреу  -  кіріс шынжырын, ал екіншісі  -  шығыс шынжырын құруға мүмкіншілік беретін екі грамматика алуға болады. 
Әрбір жай -кестелі  үшін трансляциялаушы  грамматикасын құруға болады және -кесте мен -грамматикасы тудыратын ауысымдар сәйкес келеді: .
Бұл формуланың айқындығын көрсету үшін -кестесі бойынша берілген -грамматикасының тұрғызылу тәсілін мазмұндайық. Айтарлық -кестелі  берілген және  -грамматикасын құру керек.
Бұны орындауға болады, себебі -кестесі жай және оның әр ережесі үнемі бір терминал емес символдарды бір ретпен қолданылады. әңгімеленген тұжырымды мысалмен толықтырайық: 


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

4.3 Жақшасыз формулалар

Күнделікті тәжірибеде қолданылатын және құрамында жақшасы бар арифметикалық формулалар инфикстік формула деп аталады, себебі операция белгісі операнд араларында орналасқан. Бұндай формулаларда іс-әрекеттің орындалу реті операциялардың жасы мен жақшаларына байланысты анықталады. 
Бұндай формулаларды есептеу мен компиляциясы операцияның орындалу ретін анықтау мақсатымен оларды алдын-ала талдауды көздейді. Жақшасыз арифметикалық формулаларды жазу формулалары бар. Оларда іс-әрекет реті формуладағы операциясы белгілерінің ретімен беріледі.
 Бұндай жазу формалары поляктік немесе жақшасыз жазылым деп аталады. Поляктік жазу операция белгісі операндтардан ілгерірек болатын префикстік және операция белгісі операндтан кейін жүретін постфикстік болады. Жақшасыз формулаларды есептеу мен компиляциясы жақшалы формулаларға қарағанда жеңілдеу, себебі операция мазмұндау ретімен орындалып, алдын-ала талдауды қажет етпейді.
Бұл анықтама берілген инфикстік формуланың ПрПЗ құру ретін анықтайды. Мысалы  формуласы үшін ПрПЗ тұрғызылуын келесідей орындауға болады. Бірінші орындалатын операция операндыларын белгілейік: 
                                       
                                    және 
                                       
Анықтамаға сәйкес  формуласының префикстік жазылымы бұл , бұнда ,  және  формулаларының префикстік жазылымдары. Бұл  формулаларына постфикстік жазылымды тұрғызуды орындай келе аяғында  түріндегі нәтижеге жетеміз.
ПрПЗ есептеуін келесі тәсілмен көрсетуге болады: 
1 формуланы солдан оңға қарай артынан екі операнд жүретін операция белгісін тапқанша қараймыз. 
2 операцияны орындаймыз және нәтижені таңдалған үштік орнына жазамыз.

4.4 Дүкендік түрлендірушілер
 	
Келтірілген префикстік жазылымдарды есептеу ережелері айтарлықтай жай, бірақ тәжірибеде бұндай формулаларды есептеу әдетте дүкендік қолданушымен іске асырылады. Постфикстік поляк жазылымын (ПоПЖ) келесідей анықтайық: 
1 Егер   инфикстік формуласы бір   операндын көрсетсе, онда ПоПЖ   формуласы бұл .
2 Егер   формуласында  *- операция белгісі, ,   -  операндтарға арналған инфикстік формула болса, онда бұл  ПоПЖ формуласы және бұнда  - нің постфикстік формуласы. 
3 Егер  инфикстік формула болса, онда бұл ереженің постфикстік жазылымы   постфикстік жазылым болады. Алдыңдағы мысалға  ПоПЗ формуласын құрамыз.
және  сыртқы операция операндыларын белгілей отырып,   және  түріндегі операндтардың постфикстік жазылымын табамыз.табылған постфикстік  формуласына қойып, аяғында  аламыз.
Формуланың постфикстік жазылымын есептеуді келесі тәсілмен көрсетуге болады: 
* Формуланы солдан оңға қарай артынан екі операнд жүретін операция белгісін тапқанша қараймыз. 
* Операцияны орындаймыз және нәтижені таңдалған операндтар мен операциялар орнына жазамыз. 
* (1) пунктіні формула орнына бір ғана жалғыз нәтиже алғанша қайталаймыз. Құрылған постфикстік формула есептеуін келесі түрде көрсетуге болады: 
                                       
                                       
                                       
Тәжірибеде постфикстік формулаларды есептеуді іске асыру үшін дүкенді қолданумен орындаймыз. Бұл жағдайда есептеу келесі ережелер бойынша орындалады: 
1 Кіріс шынжырдың кезекті символын оқу. 
2 Егер кіріс символы  -  операнд болса, онда оны дүкенге жазу. 
3 Егер кіріс символы  -  оператор болса, онда дүкеннен екі операндты оқып, операцияны орындау және қортындыны операнд ретінде дүкенге енгізу. 
4 П.1 кіріс шынжырының барлық символдары оқылып бітпегенше қайталай беру.
  	Өткен бөлімде қарастырылған дүкендік автоматтар кірісте берілген шынжыр үшін автомат жіберетін тілге қатыстығын анықтауға мүмкіндік береді. Бұл бөлім дүкендік түрлендірушілер деп аталатын құрылғылар моделінің басқа типіне арналған. Бұндай құрылғылар берілген кіріс шынжырларына сәйкес келетін шығыс шынжырларын құруға мүмкіншілік береді. Ондай дүкендік түрлендірушілердің ауысымы немесе трансляция деп аталады.
 Түрлендірушіні құру үшін алдын-ала ол қандай ауысым жүргізетінін білу керек. Және түрлендірушіні кез келген ауысымға емес, ал жай -кестесінің көмегімен мазмұндалатын ауысымға ғана құруға болады.
 
Дәріс №5 Атрибуттық трансляциялау грамматикалары  мен түрлендірушілер

5.1 Атрибуттық трансляциялау грамматикалары мен түрлендірушілер

Синтаксистік-басқармалы кестелер мен трансляциялау грамматикалары ауысым деп аталатын кіріс және шығыс тілдер шынжырларының арасында сәйкетікті беруге мүмкіндік береді. 
Семантиканы тапсыру үшін түрлі тәсілдер қолданылады, яғни олар: -грамматикалар, вен метатілі, аксиоматикалық және  денотационды әдістер және  атрибуттық трансляциялау грамматикалары (-грамматикалары). 
Бұл бөлімде қарастырылатын -грамматикалары басқа трансляциялау грамматикаларынан грамматика символдарына семантикалық ақпаратты көрсететін атрибуттар, қосып жазылады, ал грамматика ережелеріне атрибут мәндерін  есептеу ережелері сәйкестіріледі. Атрибуттардың тағайындылығын талдау үшін бірнеше мысал келтірейік. Егер кіріс тілі  константын қолдануды көздесе, онда констант атрибуты ретінде оның мағынасын алуға болады.
 Констант мағынасын қисық сызықпен, мысалы  түрінде жазуды уәделесейік. Егер -грамматикада {қосу} операциялық символы қолданылса, онда бұндай символдардың атрибуты ретінде операнд мағынасы мен нәтижені алуға болады.  Атрибуттарды  символдарымен белгілей келе атрибуттары бар операциялық символдарды {қосу}  түрінде жазамыз. 
-грамматикада екі түрлі атрибуттар қолданылады: мұра етілуші және синтезделуші. Мұра етілуші атрибуттар мағынасы грамматика ережесінің сол жағында болатын шынжыр атрибуттарының мағынасы бойынша шығару қадамының орындалуы кезінде анықталады. 
Ал синтезделу атрибутының мағынасының есептелуі шығыс қадамының келесі қадамдары орындалған кезде анықталуы немесе қалдырылуы мүмкін. Жалпы түрде -грамматика қасиеті келесі тәсілмен тұжырымдалады. Трансляциялау грамматикасын атрибуттық грамматика немесе -грамматика деп келесі жағдайларда атайды:
  + Егер грамматика символдарына бір немесе бірнеше атрибуттар қосылып жазылған және әр атрибут үшін жіберілетін мағына жиыны анықталған болса.
  + Егер атрибуттар мұра етуші және синтезделуші болса. 
  + Әр грамматика ережесіне солда орналасқан атрибут мағынасын анықтайтын оң жақтағы иемдену функциясымен оператор түрінде атрибуттарды есептеу ережесі берілген болса. 
* Бастапқы символды мұра етілетін атрибут үшін бастапқы мағына берілген болса. 
* Іс-әрекет символдарының синтезделу атрибуттарының мағынасын есептейтін функциялар бұл символдың басқа атрибуттарына бағыныңқы болса. 
	Сол жақты шығарумен атрибут мағыналарын есептеуді көрсету
    	Егер атрибут мағынасы әлі анықталмаса және іс-әрекетті орындай алмаса, онда есептеу ережесін қойып қойған есептеулер тізіміне қосамыз. 
Егер атрибуттарды есптеу ережесін орындауға болып және нәтижесінде кейбір атрибуттар мағынасы анықталатын болса, онда қойып қойған ережелер тізімін қарастырып алынған мағына көмегімен есептеуге келетін барлық атрибуттар мағынасын табамыз. Жаңа мағыналар жаңа ережелерді табуға әкелуі мүмкін, сондықтан есептеу үрдісін мүмкін болғанша қайталай береміз және атрибуттарды есептеу ережелерін қолданған соң жоямыз. 
Берілген шығаруды келтірілген грамматикада орындауды  мағыналы констатары бар  шынжыры мысалында қарастырайық: 
Есептеуді қолдану алынып қойылған шығару ережелерінің нәтижелері тізімі

                                      * 
                                      * 
                                       
                                      * 
                                       
                                      * 
                                       ;
                                      * 
                                       
                                      * 
                                       
                                      * 
                                       
                                      * 
                                      * 
                                       
                                      * 
                                       
                                      * 
                                       
                                       
   жолдарында шынжырында құру кезінде атрибуттарды есептеу ережелері алынып қойылғандарады есептеу тізіміне енгізіледі.
 Шығару шынжырында бірінші константтың пайда болуы тізімдегі үш ереженің орындалуына әкеледі. Осыған ұқсас алынып қойылған есептеулер тізімінің қысқартылуы  және  жолдарда шынжырды жасағаннан кейін орындалады.  жолдағы   іс-әрекет символы алынған атрибут мағынасын шыға беріске жібереді. 

5.2 АТ-грамматикаларын қолданумен жасалған синтаксистік талдау. Синтаксистік талдау үрдісі

Айтарлық бұндай шынжырдың синтаксистік талдауының міндеті  жолы түрінде әрбір жады элементінің ауыспалысын ерекшелеу мен бұл жолдың көрсеткішін -ға енгізу делік. Бұл іс-әрекетті орындаудың шығыс мәліметі болып -ның бірінші бос элементіне көрсететін көрсеткіш табылады. Мазмұндауды өңдеп болған соң бұл көрсеткіш мағынаны ауыспалыларға жады бөлген соң -ның бірінші бос элементін анықтау керек. 
Қарастырылып жатқан түрдің шынжыр синтаксисі  бастапқы символы бар келесі грамматика беруі мүмкін:
                                       
                                       
                                       
Бастапқы  символына екі атрибутты береміз: бастапқы мағынасы -ның бірінші бос элементіне көрсететін түрдегі мұра ететін  атрибуты және ауыспалыларға жадыны шығарғаннан кейін -ның жаңа бос элементіне мағынасы көрсеткіш болатын синтездеу  атрибуты. Сондай-ақ тізімнің жалғасуын белгілейтін терминал емес  символына да екі атрибутты жазып қоямыз. Бір  атрибуты мұра етілуші болу керек. Ол -ға шығару кезінде келесі ережеге көрсеткіш мағынасын беру керек. Басқа  атрибуты  -  синтезделген. Ол көрсеткішке шыға берісті көрсету үшін қолданылуы қажет.

5.3  - атрибутты трансляциялау грамматикалары. Атрибутты түрлендірушілер 
    
Бұл бөлімде тек қана ауысымдардың атрибуттық мазмұндауларымен таныстық емес, сонымен қатар өрмелемейтін атрибуттық түрлендірушілермен де танысамыз. Олар атрибуттармен кіріс символдарды шын атрибутты кіріс символддарының шынжырын өңдеп, әрбір кіріс шынжырына оның ауысымы ретінде кіріс шынжырын құру немесе мүлдем кіріс тіліне жатпайтынын мойындап, бетін қайтаруы қажет. 
Бұндай құрылғылар өрлемейтін талдау кіре берісінде атрибуттарды есептеуді қамтамасыз ету керек. Кез келген -грамматика бұндай өңдеу мүмкіндігін бермейді, тек қана нақты талаптарға жауап беретін грамматикалар. Алдымен атрибут бағыныңқылығына шектеуліктері бар атрибутты трансляциялау грамматикаларын қарастырайық. Бұндай грамматикалар - атрибутты трансляциялау грамматикасы (-грамматикалар) деп аталады. 
 -грамматикасы - атрибутты трансляциялау грамматикасы болып келесі үш шартты орындаса ғана бола алады:
    	1 Грамматика ережесінің оң жағының әрбір мұра етілуші атрибут символы ереженің сол мұра етілуші атрибут символдарын қолданып, не атаулы символдың сол жағында орналасқан оң жақ ереженің еркін атрибут символдарын қолданумен есептелуі керек. 
    	2 Грамматика ережесінің сол жақтағы әрбір синтезделінетін символ атрибуты ереженің сол жағындағы мұра етілуші символ атрибуттарының немесе бұл ереженің оң жағындағы еркін символ атрибуттарын қолданып, есептелуі керек. 
    	3 Іс-әрекеттің әрбір синтезделінетін символ атрибуты бұл іс-әрекет символының мұра етілуші атрибуттары бойынша есептелуі керек.     	1-шарттың мәні грамматика ережесінде тек қана оның сол жағында орналасқан шама мұра етілуші атрибуттар бағыныңқылығын қамтамасыз етуінде. Бұл шарт атрибуттарды жоғарыдан төмен қарай өңдеуге мүмкіндік береді, себебі әрбір символ сол жағындағы символдар оқылғанға дейін өңделеді. 2 және 3-шарттар шеңбер бойынша айнала бағыныңқы болуынан айырылуын қамтамасыз етеді. Барлық бірге алынған үш шарт төмендегі келтірілген түрдегі атрибуттарды есептеу ретінде әкеледі
                                       
                                       
                                       
1 мұра етілушілер   атрибуттары2 мұра етілушілер  атрибуттары, 3 синтезделуші 	 атрибуттары, 4 мұра етілушілер  атрибуттары, 5 синтезделуші 	 атрибуттары, 6 синтезделуші  атрибуты.
    
-грамматикаларын жай иемдену формалары
    	Түрлендірушілерді тұрғызуға арналған -грамматикасына салынатын  шектеуліктердің екінші түрі болып атрибуттарды есептеу ережелерінде терминал емес символдарды және функционалды бағыныңқы іс-әрекеті символдарының кейбір атрибуттарын қолдануға тиым салу болып табылады. Бұл тиымды орындаған кезде атрибуттарды есептеу ережелері оң жақта қолданылған иемдену операторларының формасында болуы керек.
 Бұндай ережелі грамматика жай иемдену -грамматикасы деп аталады.     	Атрибуттарды есептеу ережелерінің санын азайту үшін бұндай грамматикаларда  иемдену жай операторлары түріндегі ережелерді ғана емес, бірнеше ауыспалыларға бір мағына берілетін көптік иемдену түріндегі  операторларды қолдануға рұқсат етіледі. Жай және көптік иемдену операторлары көшіруші ереже деп аталады. Бұндай ереженің оң жағын қайнар көзі, ал сол жақтың әрбір атрибутын қабылдағыш деп атайды. көшіруші ережелері жиыны егеменді деп бұл жиынның әр ережесінің қайнар көзі бұл жиынның басқа бірде бір ереже құрамына кірмеген жағдайда аталады.
 Егер көшірме ережелер бағыныңқы болып келсе, онда кейбір жағдайларда оларды бір ережеге біріктіруге болады. Мысалы:  және  ережелерін бір   ережесі түрінде жазуға болады, немесе   және  ережелерін сондай-ақ  түрінде жазуға болады, себебі  екінші ереженің қайнар көзі болып бірінші ережеге сәйкес  мағынасы беріледі. Егер көшіруші ережелер егеменді болса, онда олардыбіріктіруге болады.
 Көшіруші ережелердің егемендік түсінігін қолдана отырып, келесі анықтамаға келеміз: 
-грамматикасы жай иемдену формасына келесі шарттарды орындағанды келеді: 
а) іс-әрекеттің синтезделінетін символдарын есептеу ережелерінен басқа барлық атрибуттарды есептеу ережелері көшіруші болып табылады. 
б) грамматиканың әрбір ережесіне көшіруші ережелер жиыны егеменді болып табылады.
     -  атрибуттық және -грамматикасының жай иемдену қасиеті атрибутты ауысымды іске асыратын түрлендіруші тұрғызу үшін қажет болып табылады. 
Егер берілген   - грамматикасының жай  иемдену формасы болмаса, онда ол үшін жай иемдену формасындағы эквивалентті -грамматикасын құруға болады. 
Көшірмейтін ережелер түрленуінің реттілігін мазмұндамас бұрын, бұндай түрлену қалай болатынын көрсететін мысалды қарастырайық. Айтарлық көшірмейтін атрибуттық ереже келесі түрде берілген дейік:   

                                       
                                       
    	Алдымен  функциясының есептеуін көрсететін іс-әрекеттің жаңа символын енгіземіз. Іс-әрекет символын  түрінде белгілейміз де, оған үш атрибут береміз. Екі  мұра етуші атрибуттары функция аргументін беру үшін, ал бір синтезделінуші  атрибуты функция мағынасын алу үшін қажет. Нәтижесінде келесі іс-әрекет символының анықтамасына жетеміз: , бұнда  мағынасы   функциясы ретінде анықталады.  
    	Осыдан соң грамматика ережесіне іс-әрекеттің жаңа символын енгіземіз және  функциялы оң жақта болатын атрибутты есептеудің көшірмейтін ережесін іс-әрекеттің жаңа символы мен  функциясының аргументінің арасындағы байланысты тағайындау бірнеше көшірме ережелерімен ауыстырамыз. Аталған іс-әрекеттерді орындай келе келесі атрибуттың ережеге жетеміз:
                                       
                                       
                                       
Бұнда екі ережесі аргумент, ал біреуі нәтиже көшіретін тек қана көшіру ережелері бар. 
Грамматика ережесіне жаңа терминал емес символды жағу жерін таңдауда берілген грамматиканың  - атрибуттық қасиеті жойылмауы керек. Егер қарастырылып жатқан мысалға іс-әрекеттің алдынан терминал емес  жаңа символын енгізсек, онда  келесі ережені аламыз:
                                       
                                       
                                       
бұнда  мұра етілуші атрибутының мағынасы  -  атрибуттығының қасиетін бұзатын оның оң жағында орналасқан  синтезделуші атрибутымен анықталады. 
Егер де іс-әрекеттің жаңа символын  символынан кейін қойсақ, онда келесі ережені аламыз: 
                                       
                                       
                                       
бұнда  атрибуты  - атрибутының қасиетін жоятын, одан оңдау орналасқан с атрибуты бойынша анықталады. Осыдан қарастырылып жатқан мысалда іс-әрекеттің жаңа символының  - атрибутының қасиетінің бұзылмауы тек қана  және  терминал емес символды ережелерінің бір позицияларында ғана мүмкін. Егер бұл былай болса, онда мүмкін позициялардан ең солындағыны таңдау қажет, себебі кейбір жағдайларда нағыз іс-әрекеттің сол жақтағы символдар өңдеуді жүргізетін түрлендірушілер дүкеніне енгізбу керек. Ал егер де іс-әрекеттің жаңа символы орналасқан барлық позициялар жарамсыз және  - атрибут қасиетін жоятын болса, онда бұндай грамматиканы түрлендіру мүмкін емес. 
-грамматикасын жай иемдену формасындағы -грамматикасына түрлендіру
Жүргізілген талдау нәтижесі ретінде   -грамматикасын жай иемдену формасындағы -грамматикасына түрлендіру ретін мазмұндайық.
1 Грамматиканың кейбір ережелермен байланысты атрибуттарды есептеу ережелеріне енетін әрбір  функциясы  атрибуты бар іс-әрекеттің қосымша символын енгіземіз де оны  деп белгілеп,  түрінде анықтаймыз, бұнда  мағынасы  сияқты анықталады. 
2 Грамматиканың кейбір ережелерімен байланысты әрбір көшірмейтін  ережесі үшін грамматика ережесінің оң жағына  және  символдары грамматика ережесінде жоқ шығар деп  қосамыз да, көшірмейтін ережені  түріндегі  көшірме ережесіне ауыстырамыз: .
3  іс-әрекет символын жаққан кезде келесі шектеуліктерді сақтау қажет: 
а)  іс-әрекет символы  аргументінің біруі атрибуты болып келетін грамматика ережесінің оң жағындағы әрбір символдан оңдау орналасуы керек. 
б)  іс-әрекет символы  аргументінің біреуі атрибуты болып келетін грамматика ережесінің оң жағындағы әрбір символдан солдау орналасуы керек. 
в)  егер іс-әрекет символын орналастыру позициясының бірнеше түрі болса, онда мүмкін позициялардан сол жақтағысы таңдалуы керек. 
4 Егер грамматика ережесінің біреуінің қайнар көзі екіншісіне енетін болса,  онда грамматика ережесінің екі көшірме ережесін бір ережеге біріктіру керек. 
Бұл біріктіру бос қайнар көзі бар ережені жою жолымен іске асырылады. Параметрлерсіз оң жақта қолданылған процедуралар бағыныңқы ережелерді біріктірген кезде қауіптік сақтау керегін атап өтейік, себебі түрлі шақыру процедуралары түрлі мағына беретін болғандықтан қателік тууы мүмкін. 
    	Жай иемдену формасындағы  - грамматикалары атрибуттарға салынатын шектеуліктері атрибуттық түрлендірушілерді тұрғызу үшін мүмкіндік тудырады. 
Егер -грамматикаларының ережесінен барлық атрибуттарды жойсақ, онда трансляциялау грамматикасы шығады және оған өрлемейтін дүкендік түрлендіруші құрылуы мүмкін. 
Осыған -түрлендірушіні атрибуттарды өңдеумен байланысты іс-әрекетін толықтырылған дүкендік түрлендіруші түрінде құруға болады.
    	-грамматикада синтезделінетін атрибуттардың мағынасын анықтауда қойып қойған иемдену тууы мүмкін, сондықтан -түрлендіруші жұмысын жоспарлауда мағыналары әлі анықталмаған атрибуттарды сақтау мүмкіндігін ескеру қажет. 
Бұндай атрибуттарды сақтау үшін дүкен қолданылуы мүмкін. Атрибуттарды жай сақтау жеткіліксіз, себебі атрибут қандай мағына алуы қажет туралы мәліметтерді де сақтау керек. Жай иемдену формасында мағынаны анықтаудың бір ғана тәсілі қолданылатынын ескереотырып, иемдену операторының көмегімен иемдену мәліметтерін дүкенде көрсеткіш көмегімен көрсетуге болады. Ол үшін дүкеннің қайнар көзіне сәйкес келетін элементін қабылдағышқа сәйкес келетін элементіне көрсететін көрсеткішті жазуға болады.
 Бұндай көрсеткіштерді дүкенде оған грамматика ережесінің оң жағын жазған кезде орналастыруға болады.
 Бұл жағдайда алдымен қайнар көзі, ал одан кейін қабылдағыш анықталатын атрибут мағынасының анықталу реті қамтамасыз етілуі қажет. Бұндай реттіліктің есептеуінің орындалуы  - атрибуттық грамматика қасиетіне кепілдік береді. 
-грамматикасы үшін кеңейтілген шығару
    	Атрибуттарды өңдеудің мазмұндалған тәсілінің илюстрациясы ретінде  грамматикасындағы кеңейтілген  шығару көрінісін қарастырамыз.  
Бұндай шығаруға тек қана терминалды, терминалды емес және операциялық символдар ғана емес, сонымен қатар мағынасы әлі анықталмаған атрибуттар да енеді. Иемдену операцияларына сәйкес келетін атрибуттар арасындағы байланысты көрсету үшін желілік шығарумен қолданамыз. Бұндай шығару келесідей құрылады: 
- Атрибуттарды индекс позициясынан жолға ауыстырамыз да грамматиканың сәйкес келетін символына орналастырамыз.
- Қойып қойған есептеу қадамына сәйкес келетін әрбір көшіру ережесіне қайнар көзден қабылдағышқа бағытталған, қайнар көз бен қабылдағышты шығару шынжырына байланыстыратын доғаны сәйкесінше қоямыз..
- Көптік көшірме ережелеріне сәйкесінше қайнар көзді қабылдағышпен байланыстыратын шығару шынжырында доғалар ретін қоямыз.
- Егер шығару үрдісінде атрибут мағына алса, онда ол мағынаны атрибут есімінің орнына шығару шынжырына жазамыз, ал сәйкес доғаны жоямыз.
- Терминал емес символды ауыстырғанда ол шығару шынжырында жойылады, бірақ оның атрибуттары орындарында қалу керек.
Келтірілген шығаруда әрбір ауыстырылатын терминал емес символдардың атрибуты шығару шынжырында сақталуы қажет. 
Атрибуттық түрлендірушілер .
Алдыңғы бөлімде қарастырылған атрибуттық мазмұндау ауысымды мазмұндаудың синтаксистік бағытталған тәсілінің жалпыламасы болып табылады, ал бұл бөлімде қарастырылатын атрибуттың түрлендірушілердің тұрғызылуы мен жұмысының ережелері жасанды тілдер үшін компилярларды құру кезінде бұндай мазмұндауларды тәжірибеде қолдануға мүмкіндігін беруді көрсетеді.
 Қарастырылатын -лар өрмелемейтін символды түрлендірушілер негізінде құрылады, сондықтан оларды өрмелемейтін атрибуттық түрлендірушілер деп атайды. Бұндай түрлендірушілер жұмыс үрдісінде мысалы, аралық нәтижелерге жады бөлу, кесте мен өрістерді толтыру және мән мәтіндік шарттарды тексеру сияқты іс-әрекеттерді орындауға мүмкіндік береді. 
	5.4 -грамматика ережесін дүкенде көрсету
Қарастырылған  - грамматикасындағы шығарудың графикалық көрінісі атрибуттық түрлерінің бағдарламалық іске асырылуының негізі болып табылады. Түрлендірушіні тұрғызуды -грамматиканың әрбір ережелерінің оң жағын графикалық көрсетулер арасында ғы сәйкестігін орнатамыз және жады ретінде дүкен қолданылар деп ойлап оны жадыда көрсетеміз. Бұндай сәйкетікті беру үшін қор ретінде қағидалар қызмет етеді:
- әрбір терминал, терминал  емес және операциялық символ үшін сәйкес символды жазып қоятын, дүкенде жадының бір элементін ерекшелейміз,
- грамматика ережесіндегі әрбір атрибутқа егер ол анықталған борлса, атрибуттың кез келген мағынасы немесе егер әлі анықталмаған атрибут мағынасын жазу керек дүкен элементіне көрсететін дүкен жадының элементін келтіреміз,
- мағынасы анықталмаған атрибут үшін көрсеткіш үлкендігі жай иемдену формасындағы атрибуттарды есептеу ережелерімен анықталады да шығарудың графикалық көрінісіне нұсқарына сәйкес келеді. 
Сонымен, дүкенде  - грамматиканың сол жақты шығаруын тұрғызу үшін ережені әр қолданған сайын ереженің оң жағына сәйкес келетін дүкен үзіндіні құру және ауыстыру кезінде дүкен шыңының астында болатын оң жақ ереженің ауыстырылатын сол жақ ереженің атрибуттарымен байланысын табу керек. 
Байланыс нәтижесінде, дүкен элементтеріне мұра етілуші атрибуттардың мағынасын дүкен элементтеріне көрсеткіштер жазылып қойылу керек. Және бұнда бұл атрибуттың мәні, ал синтаксистік атрибутқа сәйкес келетін элементтерге дүкен элементіне көрсететін көрсеткіштер енгізілу керек. 
Атрибуттың грамматикада шығару атрибут мағынасын анықтаумен біріктіріледі. Егер грамматика жай иемдену пішінінде берілсе, онда атрибут мағынасын есептеу іс-әрекет символдарын орындағанда орындалады. 
Есептеу нәтижесінде алынған атрибут мағыналары дүкен элементінің берілген орнына енгізілуі керек, сондай-ақ онымен көрсеткіш шынжырымен байланыстырылған барлық элементтер, жоғарыдағы мазмұндалған атрибуттың грамматикада дүкенді қолдана отырып сол жақты шығаруды орындау кестеге негізделе отырып, трансляциялау грамматикасы бойынша тұрғызылуға түрлендірушімен салыстырғанда атрибуттың түрлендіруші қиыншылығы дүкенде атрибуттар үшін жады бөлу қажеттілігі мен көрсеткішпен жұмыс есесінен туатыны туралы қортынды жасауға болады. 
Дүкен фрагментін тұрғызумен байланысты іс-әрекеттерді -түрлендіруші ереженің оң жағын дүкенге жазу кезінде орындай алады. Фрагментті тұрғызу үшін қажет көрсеткіштерді қою мен атрибут мағынасын анақтауға қажет тапсырыстар алдын ала -түрлендірушілерін тұрғызу кезінде анықталып, мазмұндалуы мүмкін.
 Бұндай тапсырыстар атрибут түріне байланысты болады, яғни дүкенді пайдалану мен шығару кезінде шығару синтаксистік ағашының түбірі дүкен түбірінде орналасқан болса, ал ағаштың соңғы шыңдары жоғарыда болып шығады және бұдан былай синтезделінетін атрибуттар мағынасы ағаштың шындарынан түбіріне, ал мұра етілуші атрибуттардікі керісінше - түбірден соңғы шыңдарға бағыты бойынша берілуі керек. 
Белгіленген жағдайлар атрибут мағыналарын есептеу ережелерін келесі тәсілмен құруға мүмкіндік береді. 
1  Егер көшірме ереженің қайнар көзі ретінде синтезделінуші атрибут және терминалды символ атрибуты болса, онда қайнар көзге сәйкес келетін өрісте қайнар көзі анықталғаннан кейін мағынасын орналастыру қажет қабылдағыш өрісіне көрсететін көрсеткіш жазылады. 
2 Егер көшірме ереженің қайнар көзі ретінде мұра етілуші атрибут болса, онда қабылдағышқа сәйкес өрісте мағынасы алыну керек қайнар көз өрісіне көрсететін көрсеткіш жазылады. 
3 Егер көшірме ережесінің қайнар көзі ретінде константа болса, онда оның мағынасы қабылдағышқа сәйкес өріске енгізіледі. 
4 Егер көшірме ереженің қабылдағышы ретінде бірнеше атрибут  (көптік иемдену) болса, онда олар көрсеткіш шынжырымен байланыстырылады. 

	5.5  жұмысын мазмұндау
Жұмыс үрдісінде -түрлендіруші дүкен шыңындағы символды оқып, кіріс шынжырын тану мен шығыс шынжырын құрумен байланысты іс-әрекеттерді ғана емес, сонымен қатар төменде келтірілген ережелер түрінде мазмұндауға болатын атрибуттарды өңдеу іс-әрекеттерін де орындау керек. 
* Кіріс шынжырын өңдеу дүкенде грамматикалық бастапқы символы мен түбір маркері болғанда ғана басталады. Түрлендірушінің бірінші символы дүкенге грамматиканың бастапқы символын енгізіп, бастапқы символдың мұра етілуші символдарына бастапқы мағынаны беру керек. Және де синтезделінуші атрибуттарының өрістері бос көрсеткіштермен толтырылады. 
* Егер дүкен шыңында атрибуты бар кіріс символы тұрса, онда кіріс лентадан келетін символдар саналады да, бұл символдар өзара салыстырылады. Егер олар дәл келсе, онда лентадан кезекті кіріс символының атрибуты санау жүргізілуі жүргізіледі және қарастырылып жатқан кіріс символының атрибут өрісіне жазылған көрсеткіш сүйенетін шынжырды тудыратын дүкен торына жазылады. Одан кейін кіріс символы мен оның атрибуты дүкеннен жойылады да кіріс бүршігі жылжиды. 
* Егер дүкен шыңында атрибуты жоқ кіріс символы тұрса, онда кіріс лентасынан кезекті кіріс символы оқылады да бұл символдар салыстырылады. Егер олар дәл келсе, онда символ дүкеннен жойылып, кіріс бүршігі бір позицияға жылжиды. 
* Егер дүкен шыңында іс-әрекет символы тұрса, онда оның аргументтеріне сәйкес келетін атрибуттар оқылады, одан кейін синтезделінетін атрибуттар іс-әрекет символы функциясына сәйкес мағыналары табылады да, бұл мағыналар синтезделіну атрибут өрісінде көрсеткішке сүйенетін, көрсеткіш шынжырымен анықталатын барлық өрістерге орналастырылады. 
* Егер іс-әрекет символы шығысқа берілуі қажет болса, онда бұл символ мен оның атрибуттарын шығыс лентаға жазу іске асырылады. 
* Егер дүкен шыңында терминал емес символ тұрса, онда ол дүкеннен жойылады да  оның орнына дүкенде грамматика ережесінің оң жағына сәйкес келетін фрагмент құрылады және бұл фрагменттің тұдырылып жатқан фрагмен астында орналасқан жойылған символ атрибуттарымен байланысы табылады. Бұндай байланыстар фрагменті тұрғызу нұсқауларында анықталуы керек.  
* Егер дүкен шыңында мағынасы анықталған атрибут тұрса, онда ол дүкеннен жойылады.  
 	Детерминалданған атрибуттық түрлендірушіні тұрғызуда кіріс грамматикасы  грамматикасы класына қатысты жай иемдену пішініндегі кез келген -грамматикасы үшін орындауға болады. Түрлендірушіні тұрғызуды мүмкін екендігін анықтайтын фактор болып, жай иемдену пішінінің  -  атрибутының қасиеті табылады. 
 - атрибутының қасиеті өрлемейтін түрлендіруші жұмысы кезінде стектен атрибуттарды алып шығу реттілігіне сәйкес келетін атрибуттарды есептеу ретін қамтамасыз етеді. 
Тек қана көшірме ережелерінің атрибут мағыналарын есептеуді ереже ретінде қолдануды беретін жай иемдену пішінінің қасиеті атрибуттарды есептеуді мағынаны беру үрдісіне теңестіруге мүмкіндік береді. Бұл жағдайда қойып қойған иемдену туралы мәліметтер иемдену ретін анықтайтын көрсеткіш шынжыры түрінде сақталады. 
* Келтірілген тұжырымдарды қортындылай келе берілген жай иемдену пішініндегі -грамматикасы бойынша -түрлендірушісі тұрғызу ретін келесі тәсілмен мазмұндаймыз:
* Берілген -грамматика ережелерінен барлық атрибуттар мен оларды есептеу ережелерін жоямыз. Нәтижесінде трансляциялау грамматикасын аламыз. 
* Алынған трансляциялау грамматикасы үшін түрлендіруші құрамыз. Бұндай түрлендіруші кейін атрибуттармен жұмыста қолданылатынын ескеріп, оны құру ережесінде келесі өзгерістерді енгіземіз:          а) түрлендірушінің бірінші командасы грамматикалық алғашқы символының келесі реттегі алғашқы мағыналарын таба аласын десек, бастапқы ретінде (,<берілген шынжыр>,) түріндегі конфигурацияны аламыз. 
     	 б)  түріндегі ережелерге командаларды біріктіруден бас тартамыз, бұнда  атрибуты бар терминал, ал -терминалды және терминалды емес символдардан құрылған шынжыр. 
командасының орнына  екі командасын қолданамыз, себебі бір команданы орындағанда терминалды символ және оның сәйкес атрибуттары дүкенге жазылмайды. Ал ол жазылмағандықтан  терминалының атрибуты қолданылатын атрибутты есептеу ережесі үшін көрсеткіштің тудырылуына мүмкіндікті жояды.
Берілген -грамматиканың әрбір ережесі үшін оң жақ ережесін стекке жазу кезіндегі стек фрагментін тұрғызуды мазмұндайтын нұсқауды құрамыз. 
Нұсқауды нөмірлейміз де, нұсқаудың кезекті нөмірімен #  символы ретінде нұсқау белгілерін енгіземіз. Шынжырды стекқа жазуды орныдайтын құрылған түрлендірушілердің барлық крмандаларында атрибуттық шынжырды стекқа жазуды орындайтын сәйкес нұсқау шынжырларын белгілермен ауыстырамыз. Нәтижесінде ауысым функциясын келесі түрде аламыз:
     (,<кіріс символы>,<дүкен шыңындағы символ>)=(, <орындайтын нұсқау нөмірі>).
Бұл тәсілмен құрылған -түрлендіруші 1-6 ережелеріне сәйкес жұмыс істеу, нұсқауда жазылған іс-әрекеттерді орындау керек деп тұспалданады. 
*  грамматикасы үшін түрлендірушілер командасы келесі түрде болады: 
                                       
                                       
                                       
Дүкенге символдар шынжырын жазуды орныдайтын әр команда үшін, біздің жағдайда бұл (1)-(5) командалары көрсеткіш мағынасын анықтайтын нұсқау құрамыз. 
* Құрылған нұсқау белгілерін түрлендіруші командаларын енгізе отырып, және іс-әрекет символынан өңдеу  жұмысының ережесіне енгізіледі деп ескеріп, (7) - (12) командаларын команда тізімінен шығарып тастауға болады. Нәтижесінде келесі түрдегі командалар жүйесін аламыз: 

                                       
                                       
* Дүкен шыңында шығысқа берілу қажет операциялық символ бар, сондықтан түрлендіруші дүкеннен бұл символмен оның атрибутын оқиды және оларды шығыс лентесына жазады. 

  +  Өрлемелі атрибуттың түрлендірушілерді тұрғызуы

Детерминалданған атрибуттың түрлендірушімен тек қана өрлемейтін емес, сонымен қатар өрлемелі әдіс негізінде де, жұмыс істей алады. өрлемелі атрибуттың түрлендірушілерді тұрғызу процедурасының ерекшелігі бұндай түрлендірушілер іске асыратын ауысым төмендегі тәсілмен анықталатын -атрибуттың грамматика пішінінде берілуі керек. 
Терминалды емес символдардың барлық атрибуттары синтезделінетін атрибут болып табылатын жай иемдену пішініндегі -атрибутының грамматика -атрибуттық грамматика деп аталады. 
     	Тек қана синтезделінуші атрибуттарды қолдану қажеттілігі мұра етілуші атрибуттарды беру мүмкін болмайтын жапырақтан ағаштың түбіріне бағыты бойынша шығару ағашын құруға сәйкес келетін өрлемелі түрлендіруші жұмысының тәсілінен шығады. 
   	-атрибуттық грамматика қасиеті  терминал емес символды синтезделінуші атрибуттарды есептеу ережелерінде бұл символдың басқа синтезделінуші атрибуттары қолданданбайтынына және грамматика ережесінің оң жағындағы мұра етілуші атрибуттарды есептеу ережесінде тек қана атрибут қарастыратын символды солға қарай орналасқан грамматика ережелерінде орналасқан. 
      Егер -атрибуттық грамматика түрінде постфикстік трансляциялауной грамматикасы берілсе, және егер берілген трансляция грамматикасының кіріс грамматикасы детерминалды тілдерді тудыратын,  атап айтқанда мысалы  немесе  ішінаралық кластар, ішінаралық грамматикасы қатысты болса, онда ол үшін детерминалданған кіріс атрибуттың түрлендіруші құруға болады. 
Бұндай түрлендіруші кіріс грамматика шынжырының өрлемелі жанысуының кеңею жолымен құрылады. Атрибуттың грамматикалық трансляциялау грамматикасына терминалды, терминалды емес және операциялық символдары синтезделінуші немесе мұра етілуші атрибуттары барлығымен және грамматикалың әр ережесіне атрибуттарды есептеу ережелері қосылып жазылуымен ерекшеленеді. 
-грамматика ережесінің көмегімен шығаруды тұрғызуды атрибут мағынасын есептеумен біріктіреді.
-грамматикасы анықтайтын ауысымды іске қосатын түрлендірушіні құру кез келген -грамматикасы үшін мүмкін емес.
Ауысымды тек қана -атрибуттық грамматика шарттарын орындаған және жай иемдену пішінінде берілгендер ғана орныдай алады. Және грамматика ережесінің оң жағындағы грамматика -атрибуттық грамматика класына егер грамматика ережесінің оң жағында мұра етілуші атрибуттар сол жақтың мұра етілуші атрибуттар есесінен есептелінсе және егер іс-әрекет символының синтезделінуші атрибуттары олардың мұра етілуші атрибуттары бойынша есептелінсе ғана жатады. 
-грамматика егер атрибуттарды есептеудің әрбір ережесі идентификаторлы иемдену операторын көрсетсе немесе оң жақта константа болып табылған жағдайда жай иемдену пішінінде болады.
 -грамматикасын атрибут мағыналарын есептеу ереженің оң жағында қолданылатын функция мен операциялық символдарды ауыстыру және бұл символдарды грамматика ережелеріне енгізу жолымен жай иемдену пішініне түрлендіруге болады.
Өрлемейтін  -түрлендірушілер жұмыс үрдісінде трансляциялау грамматикалық ережесін құратын атрибуттарды символдарымен бірге дүкенде кіріс шынжырының сол жақ шығаруын құрады. Егер атрибут мағыналары дүкенге жазу кезінде аніқталмасы, онда олардың мағыналарының орнына бұл мағыналар орналасқан немесе бұл мағыналар алыну керек дүкен элементтеріне көрсеткіштер жазылады. 
Атрибут мағыналық жазылуы мен көрсеткіш тұжырымдары ережелерінің оң жағының дүкеніне жазумен біріктіріледі. Және бұл кезде грамматика ережелерінің оң жағына сәйкес келетін дүкен фрагментін тұрғызумен байланысты барлық іс-әрекеттер алдын ала түрлендірушілерді жобалау кезеңінде анықталып дүкенге ереженің оң жағын жазуды орныдайтын түрлендіруші командасымен байланысты болу керек нұсқау түрінде рәсімделуі керек. 
Әрбір такта түрлендіруші дүкен шыңында орналасқан символды оқиды және символға сәйкес жұмыс ережелері мен түрлендіруші  командаларымен жазылатын іс-әрекеттерді орындайды. 
Егер L-грамматика жай иемдену пішінінде берілген болса, онда түрлендірушіні тұрғызу берілген грамматикадан сәйкес трансляциялау грамматикасын, нұсқау құруды ерекшелеумен айналысады. Детерминалданған өрлемейтін -түрлендірушіні тұрғызу үшін берілген -грамматикасының негізінде жатқан трансляциялау грамматикасының кіріс грамматикасы -грамматикасы класына қатысты болу керек.
Өрлемелі  -түрлендірушісі -атрибуттық грамматикасының беретін ауысымды орныдайды. Ол өрлемелі танушы ауысымының таблицаларын жазатын іс-әрекет пен ауысымды орындайды. Танушы таблицалары берілген -атрибуттық  грамматикадан алынатын кіріс грамматикасы бойынша құрылады.
Егер кіріс грамматикасы  немесе  класына жатса, онда берілген грамматика үшін детерминалды -түрлендіруші құруға болады. Бұндай түрлендіруші атрибуттарымен жұмыс қажеттілігін ескеретін түйіршік және ауысым кеңейтілген оперцияларын қолданады. 

Дәріс №6 Автоматтардың құрылымдық синтезі

6.1 Автоматтардың құрылымдық синтезі

Автомат кестесін құру үрдісі әдетте екі қатысты бағыныңқы деңгейге: абстрактілі және құрылымдық синтез деп екіге бөлінеді.
 Абстрактілі синтез деңгейінде берілген жұмыс шарттарына сүйеніп, ауысым және автомат шығыстарының кестесін құру орындалады. 
Құрылымдық синтездің мәні автоматтық функционалды кесте құру. Құрылымдық синтез деңгейінің шығыс мәліметтері болып ауысым мен автомат шығыстарының таблицалары, логикалық элементтер жүйесі, жады элементінің типі, сондай-ақ кесте жұмысы мен сапасына қойылатын қосымша талаптар, мысалы: жұмыс уақыты, тәуекелдің жіберілуі, қоршаған ортамен байланыс шарты, құны және т.б. табылады. 
Шығыс мәліметтер мен құрылымдық синтез деңгейінде шешілетін сұрақтар шеңбері айтарлықтай өзгеруі мүмкін екенін атап өткен жөн. Мысалы құрылымдық синтезде кейбір жағдайларда ізделіп отырған кест енің таңдау міндетін шешеді.
Қарастырылып жатқан кесте екі бөліктен: комбинациялық кесте  мен жады элементтерінен  тұрады. Жады элементтерінің шығыс сигналдарына сәйкес келетін ауыспалылары автоматтың ішкі ауыспалылары деп аталады.  ауыспалылар кестеде жады элементтерінің жай-күйін өзгертетін кіріс сигналдарын ерекшелеу үшін қолданып, қоздыру функциясы деп аталады. Жады элементі ретінде тәжірибеде элементарлы автоматтар жиі қолданылады.
Келтірілген кестеде  кіріс ауыспалыларының мағына жиынтығы абстрактілі  автоматының кіріс алфавитінің әріптеріне,  шығыс ауыспалылар жиынтығы  шығыс алфавитінің әріптеріне, - абстрактілі автоматтың күіне сәйкес келеді.
      	Жалпы жағдайда келтірілген құрылымдық автомат кестесіндегі комбинациялық кесте түрлі міндеттерді шешуі мүмкін. Егер бұл кестені әрбіреуі жеке ішінаралық кестемен шешілетіндей екі ішінаралық кестеге бөліп тастасақ, онда автоматтық құрылымдық кестесі 2-суретте келтірілгендей түрде көрсетілуі мүмкін. Бұл кестеде комбинациялық кесте  шығыс функциясын өндіреді,  қоздырғыш функциясын, кодтарды түрлендіруші  - шығыс сигналдарын қайта кодтауға қолданылады, ал кодтарды түрлендіру  - шығыс сигналдарын түрлендіруге. 
 және  кодтарын түрлендірушілерін құрылымдық автомат кестесінде міндетті түрде болуы шарт емес, бірақ кейбір жағдайларда оларды кесте құрылымына енгізу қиындықты азайтуға жеткізіп, тұрғызу немесе автомат кестесінің жұмысын бақылау үрдісін жеңілдетеді.    
Құрылымдық синтездің негізгі кезеңдері.
      	Құрылымдық синтез процедурасын бір-бірімен байланысты бірнеше кезеңдерге бөліп қарастыру ыңғайлы.
* Автоматтың құрылымдық кестесін таңдау. Синтездің бұл кезеңі көбінесе кестенің тұрғызылу ретін анықтайды. Бұл кезеңнің негізгі қиыншылығы құрылымдық кесте таңдауда формалды критерилердің жоқтығында. Құрылымдық кестені таңдауды анықтайтын факторлардың негізгілерінің бірі жасаушының тәжірибесінде.
* Кіріс және шығыссигналдарын кодтау. Кіріс сигналдарын кодтау мәні абстрактілі автоматтың pi кіріс алфавитінің әрбір әрпінде бір мәнді тәсілмен  сәйкестіріледі.  Бұдан кіріс алфавитінің әріптер саны  түріндегі екілік ауыспалылар жиынтығының санынан аспайтыны, яғни кодтау біртекті екені анық. Осыдан шыға келе кіріс алфавитінің  әріптерін кодтау үшін қажет  екілік ауыспалылар санын шартынан анықтауға болады. 
	Шығыс сигналдарын кодтау дегеніміз абстрактілі автоматтың шығыс wi алфавитінің әріптеріне ұқсас тәсілмен шығыс ауыспалылар мәндерінің жиынтығы сәйкестіріледі. Кодтау нәтижелері әдетте кіріс және шығыс сигналдарын кодтау кестесіне енгізіледі.       Кіріс және шығыс сигналдарын кодтаудың кейбір тапсырмаларында абстрактілі синтез кезеңінде кесте жұмысының шарты негізінде беріледі. Бұндай жағдайларда автоматтың құрылымдық кестесіне кодтарды түрлендірушілер енгізілуі мүмкін.
	 Бұл кодтау кезінде  ауыспалылар әрбір мәндерінің жиынтығына сәйкес түрде  ауспалылар жиынтығы қойылады, ал әрбір ауыспалы   жиынтығына  ауыспалылар жиынтығы. Сондай-ақ, кіріс және шығыс сигналдарын кодтау кестесінің комбинациялық бөлігінің күрделілігіне автомат күйін кодтауға әсер еткендей әсер етеді.
*  Жады элементтерінің санын таңдау және автомат жай-күйін кодтау. Жай-күйді кодтау дегеніміз әрбір  жай-күйіне ішкі ауыспалы  жиынтығы сәйкестіріледі. Жай- күймен оларға сәйкес кодтар түрінде беріліп, автомат жай-күйін кодтау таблицасы депаталады.
* Қоздырғыш функциясын тұрғызу. Қоздырғыштың  функциясы автомат көшу қажет жай-күй кодын алу үшін жады элементінің   кірісіне қандай сигнал беретінін анықтайды.
 Құрылымдық синтездегі қоздырғыш функциясы абстрактілі автомат ауысымдарының функцияларына сәйкес келеді. Бұл сәйкестік автомат жай-күйін анықтайтын  ішкі ауыспалылар және бір уақытқа қатысты  кіріс ауыспалыларына қоздырғыш функциялары бағыныңқы болу керегін көрсетеді.
* Шығару функциясын тұрғызу. Мили автоматында әрбір шығару  функциясы шығыс сигналдар жиынтығының сәйкес компонентін анықтайды. Құрылымдық синтездегі шығыс функциясы абстрактілі автоматтың шығару функциясына сәйкес келеді. Олар y1, y2, ..., yh ішкі ауыспалылар мен    кіріс ауыспалыларға бағынышты. Бұдан  анықтайтын ауыспалылар мәні үнемі бір уақыт сәтіне қатысты болғандықтан, шығыс функциясы ауыстырып-қосқыш функция болып табылады:
  
                                       
                                       
Мур автоматының шығыс функциялары әр сәтте шығыс символдарының жиынтығын анықтайды: 
                                       
                                       


Дәріс № 7Асинхронды автоматтар
Асинхронды автоматтардың немесе дәлірек айтқанда автоматтың асинхрондық моделінің ерекшелігі кіріс сигналдарының қасиеттерімен анықталады. Бұндай автоматтың кіріс сигналдары импульстік түрдегі (6.1а суреті) сигналдарға ұқсас. Бұл кезде келесі шектеуліктер алынған болатын: 

                                       
Сурет 6.1 - Импульсивті  және потенциалды түріндегі сигналдар
                                       
- сигналдар автомат кірісіне  үнемі периодты СИ реттілігі беретін нақты бір уақытта ғана түсе алады;
-  кіріс сигналдарының ұзақтығы аз ;
- автомат кірісіндегі тактілейтін сигналдардың аралығындағы уақытта сигнал болмайды. Бұндай сигналдарға тұрғызылған автомат модельдері элементтерінде гальвандық байланысы жоқ импульстік типтегі сигналдармен жұмыс істейтін кестелерге сәйкес келеді.
Асинхронды автоматтың кіріс сигналдары потенциалды түрдегі сигналдарға (6.1б суреті) ұқсас. Бұндай сигналдарға келесі қасиеттер тән болу керек: - сигнал автомат кірісінде кез келген уақытта болады;
- кіріс сигналының ұзақтығына шектеулік қойылмайды және ол кейбір  минималды мөлшерінен асады; кіріс сигналдары кез келген уақытта өзгеруі мүмкін. 
Аталып өткен қасиеттер асинхрондық автомат үзіліссіз жұмыс істейді деп айтуға мүмкіндік береді. 
Синхрондық автоматқа сияқты екілік кіріс сигналдарын қарастырумен шектелеміз. Және бұл жағдайда асинхрондық автомат моделі потенциал түріндегі элементтерден құрылған кестелерді мазмұндау үшін қолданылуы мүмкін. Айтарлық  кіріс сигналының іс-әрекетінен  синхронды автомат  күйіне ауысады. Потенциалды түрдегі сигналдардың келтірілген қасиеттеріне сәйкес  автомат кірісінде болады және аяқталуы алдын ала белгілі болмайтын ауысым орындалған соң ғана. Осыған сәйкес бұндай ауысым орындалған соң автомат келесі кірісте сигнал өзгерісі болғанға дейін  күйінде қалу керек. Мазмұндалған жайды келесі анықтама түрінде қорытуға болады. Егер автомат күйінен  іс-әрекет астында  күйіне ауысым жасаса, яғни , және  іс-әрекеті астында  күйінде қалса, онда бұндай күй тұрақты деп аталады.
Асинхрондық автомат жұмысы да синхронды түрдегі автомат сияқты ауысым кестесі мен шығыс немесе граф көмегімен мазмұндалынады. Бірақ нөлдік емес ұзақтығы бар сигналдарға ауысу бұндай мазмұндауды қиындата түседі. Алдымен асинхрондық автоматты графты құру тәсілін берілген синхрондық автоматты графы бойынша құруға тоқталайық.
 (6.2а) суретінде графы келтірілген синхронды автомат берілген делік. Бұл графты құру кезінде кіріс сигналдарының ұзақтығы есептелген жоқ. Егер де шығысқа берілетін импульстік сигналдар соңғы ұзақтыққа ие болады деп санасақ, онда әр сигналдың іс-әрекеті кезінде автомат қандай күйде болу керектігін анықтай қажет.
 Бұны (6.2б) суретінде көрсетілгендей әр ауысымға берілген граф асинхронды автоматты анықтайды, себебі автоматың барлық жай-күйі ұрақты болып келеді.

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

Кесте 6.1 - Граф бойынша құрылған
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       -
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       -
                                       
                                       
                                       -
                                       
                                       
                                       
                                       
                                       -
                                       
                                       
                                       -
                                       
                                       
                                       
                                       -
                                       
                                       
                                       
                                       
                                       -
                                       
6.1-кестеде ауысым қалай орындалатынын мысал негізінде қарастырайық. Айтарлық автомат 00 кіріс сигналдарының іс-әрекетінің астында 3 күйінде делік. Ауысым таблицасына сәйкес бұл күй тұрақты болып келеді. Егер енді кіріс сигналдарының 10-ға өзгерсе, онда автомат қандай күйге өзгеретінін табу үшін 10 сигналдарымен белгіленген үшінші жол бойынша бағанаға көшуді орындау қажет. 
Бұл тәсілмен анықталған таблица торында автомат көшетін күйдің нөмірі бұл  күйі-орналасқан. Тігінен 10 бағанасында  жолына дейін жүре отырып бұл күйдің тұрақты екеніне көз жеткіземіз. Яғни бұл ауысым аяқталды деген сөз. 
Қарастырылған мысалда бір тұрақты күйден екіншіге ауысқанда автомат бір транзиттік күйден құтқарылады. Жалпы жағдайда автомат күйінің өзгеруі бірнеше транзиттік күйлерден өтіп ауысуы мүмкін, бірақ олар ауысым таблицасының бір бағанасында орналасуы керек. 
 
 


 

• Іс жүргізу
• Автоматтандыру, Техника
• Алғашқы әскери дайындық
• Астрономия
• Ауыл шаруашылығы
• Банк ісі
• Бизнесті бағалау
• Биология
• Бухгалтерлік іс
• Валеология
• Ветеринария
• География
• Геология, Геофизика, Геодезия
• Дін
• Ет, сүт, шарап өнімдері
• Жалпы тарих
• Жер кадастрі, Жылжымайтын мүлік
• Журналистика
• Информатика
• Кеден ісі
• Маркетинг
• Математика, Геометрия
• Медицина
• Мемлекеттік басқару
• Менеджмент
• Мұнай, Газ
• Мұрағат ісі
• Мәдениеттану
• ОБЖ (Основы безопасности жизнедеятельности)
• Педагогика
• Полиграфия
• Психология
• Салық
• Саясаттану
• Сақтандыру
• Сертификаттау, стандарттау
• Социология, Демография
• Спорт
• Статистика
• Тілтану, Филология
• Тарихи тұлғалар
• Тау-кен ісі
• Транспорт
• Туризм
• Физика
• Философия
• Халықаралық қатынастар
• Химия
• Экология, Қоршаған ортаны қорғау
• Экономика
• Экономикалық география
• Электротехника
• Қазақстан тарихы
• Қаржы
• Құрылыс
• Құқық, Криминалистика
• Әдебиет
• Өнер, музыка
• Өнеркәсіп, Өндіріс