«Соңғы автоматтар және формальдік тілдер теориясы»

Тілдер теориясын оқуды бастамастан бұрын тіл деген терминді қалай ұғатынымызды анықтап алуымыз керек. Тілдің энциклопедиялық “сөйлесудің маңызды құралы, әрі адамзат қоғамында өзара ой алмасып түсінушілік” деген анықтамасы математикада тіл теориясына жеткілікті анықтама емес. Сондықтан біз тілді абстрактілі түрде математикалық жүйе ретінде қарастырамыз. Бұл бізге формальді тілдерге қатаң анықтау беретін мүмкіндік, ол алдағы уақытта модельденеді. Осы оймен біз төмендегідей анықтама береміз.

Алфавитке бірнеше мысалдар: латын тілінде {A,B,…Z}; грек тілінде {α٫β‚…ώ}; бинарлық {0,1}.

АНЫҚТАМА 1.2. Сөйлем (жол, сөз) алфавит символдарынан тұратын кез келген шекті ұзындық бауы. Бірде бір символдан тұрмайтын сөйлем, бос сөйлем деп аталады. Ол грек әрпі мен анықталады. Егер V - кез келген алфавит, онда V^* - барлық сөйлемдердің жиынымен анықталады, V алфавит символдарынан құралған, бос сөйлемді де қосып алады.

V⁺ - пен анықтаймыз. Жиын V/{E}; Мысалы, егер V{0,1}, онда V^*={E,0,1,00,01,10,11,000,…}, a V^*={0,1,00,01,10,11,..}.

Егер х V^*, онда х баудың ұзындығын, х-ті, оны құратын символдар санын білдіреді. Бос баудың ұзындығы , 0-ге тең.

АНЫҚТАМА 1.3. Тіл кейбір алфавиттердегі кез келген сөйлем жиыны. Формальды түрде , егер V- алфавит, L-тіл, онда L V^*.

Әрине 3 сұрақ туады:

1) Тілді қалай ұсынамыз, тілді құрайтын ұсынысты қалай анықтаймыз?

2) Шекті ұсыныс әр тілде бар ма?

3) Шекті ұсынысы бар әрбір тіл класының құрамы қандай?

Егер тіл шекті болса, 1-сұраққа жауап беру оңай. Барлық ұсынысты санап олардың тізімін жасау керек. Екінші сұрақтың жауабы керісінше.

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

Ортақ әдісі - тілдегі сөйлемге “иә” деген жауаппен жұмысты аяқтайтын процедура беру, немесе аяқталмайды, тілдегі емес сөйлемге “жоқ” деген жауаппен аяқталады. Сондай алгоритммен процедура тілді анықтайды дейді. Алгоритм емес процедураның көмегімен анықтайтын тілдер бар.

Пайда болу. Тілді ұсынудың басқа тәсілі - жүйелік түрде тілдің сөйлемін белгілі бір тәртіппен тудыратын процедура беру.

Егер алгоритм мен процедура берілсе, онда ол V – алфавиттінде тілді анықтайды. Сонда алгоритм және процедура механизмі пайда болады. V^* көпшілігінің жүйелік генерациялануын тілдің және механизмнің көмегімен тексеруге болады. Бірақ егер қолданылған процедура алгоритмдегі қауіпті сезсе, онда бұл өзгеріс бірінші сөйлемдегі процедура орындалады. Осыған орай процедураны табу үшін оның қатесін тексеру керек. Оны келесі мүмкіндіктерден табуға болады. V- алфавитінде символдар болсын. V^*- сөйлеміндегі жиынды жүйедегі Р- санымен қосу бос сөйлемдегі Е арқылы қарастыруға болады. Енінің ұлғаюымен V^* сөйлемін тәртіппен нөмірлейміз. Мысалы: егер {a,b,c}, онда V^* сөйлемі төмендегідей нөмірленеді.

1.е 5.aa 9.bb

2.a 6.ab 10.bc

3.b 7.ac 11.ca

4.c 8.ba 12. …

Сонымен сөйлемдер жиынындағы V-алфавиті саналынды.

1. 
   Алфавиттер, тізбектер және тілдер?
   

1. 
   Программалау тілдерінің даму тарихы. Тілдерді өрнектеу.
   
2. 
   Синтаксис, семантика және программалау тілдерінің грамматикасы. Формализациялау проблемалары.
   

Дүниеде ғылымның әр түрлі саласына сай көптеген мыңдаған тілдер ойлап шығарылған.

Тілдердің даму кезеңдері:

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

Екінші кезең – оларға Ассемблер тілдері жатады, олармен жұмыс істеу машиналық тілге қарағанда жеңілірек болады. Оларда нақтылы командаларға арнайы сақтау әдістері қолданылды.

Үлкен көлемді жадылы, жылдам есептеуіш машиналардың пайда болуы, кодтау қиындықтарын соншама өсірді, олармен адамдардың жұмыс істеуі тиімсіз бола бастады.

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

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

Бұл қиындықтан шығудың жолы «жоғарғы деңгейлі» программалау тілдерінің жасалуына себепші болды.

Үшінші кезең – бұл тілдердің ең ауқымды кезеңі. Ол 1955 жылы Фортран (FORmula TRANslator – формулалар аудармашысы) тілінің пайда болуынан басталады. Бұл тілдің пайдаланылуы осы күнге дейін жалғасып келеді.

1960 жылы Алгол (ALGOritmic Language – алгоритмдік тіл ) тілі пайда болды. Ол да ұзақ уақыт бойы программалаушылар шеңберінде +белгілі танымдылықпен пайдаланылды.

1965 жылы және қазір де көпке таныымал – БЕЙСИК программалау тілі жасалынды (BASIC – Beginner’s Allpurpose Symbolic Instructions Code – тікелей аудармасы «үйренушілерге арналған көпмақсатты символдық коды») Қазіргі кезде тағы бір қуатты тіл – С программалау тілі кеңінен қолданылады.

Тілдерлің төртінші кезеңі – бұл программалық жабдықтарды басқару тілдері және оларды « программа генераторы» деп те атайды. Мысалы үшін Клипер, Супер Калк тілдерін жатқызуға болады.

Барлық тілдерге ресми болып табылатын « бесінші кезең» тіліне қарама-қарсы процедуралық болып табылады. Бұл кезеңнің негізгі тілдеріне: ЛИСИП, ПРОЛОГ тілдері жатады.

Мысалы. Программалау тілдерінің дамуына зор ықпал еткен келесі тілдерге тоқталайық:

1. 
   Фортран, ғылыми-техникалық тілдер бейнесі, 1955 жылы IBM фирмасының көмегімен жасалынды;
   
2. 
   Алгол, есептеуіш бейнелеу тілі, 1960 жылы Халықаралық оқымыстылар комитетімен құрылды;
   
3. 
   Бейсик, алғашқы бастаушыларға арналған қарапайым тіл, 1965 жылы Дортмундте құрылды;
   
4. 
   Паскаль, ғылыми және тәжірибиелік бейнелеу сапасы ретінде, 1969 жылы Цюрихте Н. Вирттің көмегімен құрылды;
   
5. 
   Си, қолдау сапасының тілі ретінде және OC UNIX бағдарламасына қатысты BELL (АҚШ, 1972 ж.) лабороториясында құрылды;
   
6. 
   Пролог, логикалы програмалау тілі, 1971-1973 жылдары Колмероэда құрылды;
   
7. 
   Питон (Пайтон), 1990 жылдардың басында Гвидо ван Россу негізін қалады және пайдаланушыларға кең, ауқымды қолданылатын қарапайым объектілі-бағдарланған тіл болып саналады;
   
8. 
   Java – интернеттің өрмегіне жіне WWW серверіне бағдарланған тіл;
   
9. 
   HTML, 1989 жылы WWW-құжаттарын қарастырған Тим Бернерс енгізді.
   

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

Трансляцияның екі негізгі басты әдісі бар: компиляция және интерпретация.

Интерпретация әдісі – жасанды тілдегі программаның әрбір әрекеті жеке алдын-ала аударылмастан, бірден машиналық тілде орындала бастайды.

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

Мысал. Бейсик тілі әртүрлі үлгідегі трансляторға ие. Мысалы, Turbo Basic (TBasic) ортасында – транслятор-интерпретатор, ал QuickBasic (QBasic) ортасында – транслятор-компилятор. TBasic ортасында программа цикл бойынша интерпретацияланады: «команданы енгізу – команданы ішкі машиналық тілге көшіру – берілгендерді енгізу берілген команда үшін орындау» Qbasic ортасында программа: «программаның барлық командаларының ішкі тілге көшірілуі – программада қателерді түзету – программа үшін берілгендерді енгізу – барлық командалардың орындалуы».

2. 
   Синтаксис, семантика және программалау тілдерінің грамматикасы. Формализациялау проблемалары.
   

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

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

Синтаксистік тілдің негізгі тапсырмасы – программа құрылымын талдау. Ереже сияқты құрылым ішінде ағаш түсіндіріледі, контексті еркін грамматикалық тілге сәйкес келетін. Қазіргі уақытта көбінесе LL(1)-талдау және LR(1)-талдау және оның варианты қлданылады. Рекурсивті жіберу көбінесе синтаксистік анализаторды қолмен программалағанда қолданылады, LR(1)-автоматты жүйе синтаксистік анализаторда қолдана отырып орындайды.

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

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

Бұл негізхгі байланыс «суреттеу - қолдану», объектіге анализ типі, облысты талдау түрлері, параиетрлер сәйкестігі, белгілер және тағы басқа. Контексті талдау объект таблицасы нәтижесінде объектіні суреттеу ақпаратты толықтырады.

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

Бұл таблицалар тура хеширлеу функциясын құрады, мнемониканы таблицадағы адрес жазуы жүзеге асырады.

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

Символ таблицасы динамикалы қалыптасады. 1-өткелдегі жұмыс нәтижесі. Сол таблицадағы іздеу 1-деңгей өткелде жүзеге асады.

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

Жаңа аттар таблицаға қосылады «бір-бірлеп», және әрбіруінің қосылғаннан кейін таблицфның реттелуі қалпына келтірілуі керек, алгоритмді сорттау қолдану, щығушы реттелген мәліметтер.

Бұл түсінік басқа таблицаға қатысы бар, жұмвс барысында Ассемблерде үлкен мүлшердегі таблица және сыртқы жадыға орналастыру және күрделі мтодтар оның организацясын қолданылады. Мысалы, -В+ ағаш.

Сөйлесу тілі төрт негізгі элемменттерден тұрады: Символдардан, сөздерден, сөз тізбектерінен және сөйлемдерден.

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

Программалау тілдері төмендегі элемменттерден тұрады:

1. 
   Символдар – бұл берілген тілдер программаның барлық мәтінін құрайтын негізгі бөлінбейтін белгілер. Барлық символдар жиыны тілдің алфавитін құрайды. Табиғи тілге қарағанда программалау тілдің алфавиті кеңірек. Ол латын әріптерін, арифметикалық амалдар белгілерін, ажыратқыш символдарды және басқа да арнайы символдарды қосады.
   
2. 
   Лексемдер - Өзіндік мағынасы бар алфавитің символдардың көрінбейтін тізбектері. Олар тілдің негізгі символдары арнқылы құралады. Бір символдан тұратын лексемдер бар болуы м үмкін, мысалы, амалдар белгілері. Кез-келген программалау тілдерінің кілттік сөздерінің нақты жинағы бар. Олар тілдің сөздігін құрайды.Программист нақты ережелер бойынша жеке меншік сөздер – идентификаторлар құрай алады. Табиғи тілде жазылғане алгоритім жазбасына қарағанда күрделірек түсіндіріледі. Лексемдер және олардың құрылу ережелері тілдің лексикасын құрайды.
   
3. 
   Өрнектер тілдің ережесіне сәйкес лексемдерден құралады. Олар кейбір мәндердің есептеу тәртібін береді. Өрнектер қарапайым тілдегі сөз тізбектеріндегі сияқты программалау тілдерінде де сол рөлді атқарады.
   
4. 
   Операторлар тілдің кейбір іс-әрекеттердің толық сипаттамасын береді. Күрделі әрекеттерді сипаттау үшін операторлар тобы керек. Бұл жағдайда операторлар құрамдас операторлар немесе блокқа біріктіріледі.
   

Программалау тілдерінің элементтерінің жазылу ережелерінің жүйесі оның синтаксисін құрайды.

Тілдің құру мағынасы - бұл оның семантикасы. Басқа сөзбен айтқанда,тілдің синтаксисі жеке құрастырушылардың сыртқы түрін анықтайды,ал семантика осы құрастырушылар арқылы компьютер орындайтын әрекеттерді талқылайды.Жоғарғы деңгейлі қазіргі тілдер симантикалары бойынша ұқсас,бірақ синтаксисте кейбір ерекшеліктері бар. Осыдан шығатын маңызды қортынды:программалауды алғаш меңгерушілер тілдің семантикасына көңіл аударуы қажет.Сапалы программаларды жазу тілдің синтаксисіне байланысты емес. Семантиканы соңына дейін түсіну күрделірек .Тілдің әрбір құрастырушысын жеке алгоритімдер жазуда міндеттері бойынша пайдалану одан сайын күрделірек.

Бұл жерде бұрынғы сыналған амалды компьютерде жұмыс, көптеген м ысалдарды өңдеу,есептерді шығаруды ұсынуға болады.

Табиғи тілден айырмашылығы әр программалау тілінің қатаң сипатталуы болады.Мұндай сипаттау не үшін керек? Бұл жерде компьютермен байланысу үшін арналған тіл туралы айтылып тұр. Яғни, аздаған екі ойлар қателікке соқтырады.

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

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

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

Қазіргі кезде тілдерді сипаттаудың бірнеше түрлері бар. Оларды программалау тілдеріне ажырату үшін оларды тілдердің белгілері деп атайды.

Бірдей мақсаттар үшін және өзара толық байланысқан әр түрлі екі тілдің белгілеріне сипаттама берейік:

1. 
   Бэкус-Наур (БНФ) қалыпты. Осы белгілі Algol тілін сипаттау үшін қолданылған, содан кейін әр түрлі программалау тілдерінің авторлары арқылы оларды қалыпты сипаттау үшін қолданылды. Қазіргі уақытты РБНФ деп аталатын кеңейтілген нұсқасы пайдаланылады.
   
2. 
   Вирттің синтаксистік диаграммалары. Тілдің негізгі құрастырушыларының графиктік бейнеленуі.
   

Барлық басқа түсініктер – терминалдар еместер – терминалдар бірте-бірте арнайы металингвистік формулалар көмегімен шығады. Ол формулаларда теңдік белгісінің орнына ::= қолданылады. Әр терминал емес бұрышты жақшаға алады. Мета символың мәні “немесе” (или) болады.

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