Тьюринг машинасы, фон Нейман автоматы.

2. Бір қалыпты өрнек бойынша детерминант емес шекті автомат құру.

Тьюринг машинасы

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

Алан Матисон Тьюринг (1954-1954) ағылшын инженері әрі математигі. Оның ғылыми еңбектері, көбінесе, математикалық логика мен есептегіш машина жұмысының негіздемелік мәселелерін зерттеуге және уағыздауға арналған. Кибернетика ғылымы мен электронды есептегіш машиналар теориясының негізін алғаш қалаушы Норберт Виннер (1894- 1964): «Тьюринг расында, ғалымдардың ішіндегі ойша тәжірибе жүргізу арқылы машиналардың логикалық мүмкіндігін тұңғыш зерттнген адам болды.

Тьюринг машинасы дәлді математикалық ұғым болып табылады. Оны ешұқашан кездеспейтін және ұшы қиыақырсыз жады бар механикалық құрылым деп қарастырады.

Анықтама: Тьюринг машинасы (ТМ) деп ұзындықтары бірдей шаршы ұяларға бөлінген ақырсыз таспамен және уақыттың әрбір моментінде таспаның мазмұнын есепке алатын жаңа белгілеменіжазатын және таспаны жылжытатын Д тетіктен жабдықталған А ақырсыз автоматты айтады.

Тьюринг машинасы соңғы автоматтандырудың жай моделі болып табылады.

Қарастырайық, Тьюринг машинасы мен жай модельдік автоматтың айырмашылығын.

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

Функционалдық автоматты бейнелеуді оның программасы ретінде санауға блады: онда 4 – тік санау жүйесі қолданылады < s, a, p, y> - бұл өткен қалып, а – келесі енгізілген сигнал, р – келесі қалып және у – кезекті шығару сигналы. Соңғы автомат программасы аргуметерді санайды, және функцияның нәтижесін шығарады: S*X – S*Y

Соңғы автомат пен Тьюринг машинасын салыстыру.

СОҢҒЫ АВТОМАТ ТЬЮРИНГ МАШИНАСЫ

Енгізу лентасы

Басыныңың

Басының қозғалысы қозғалысы

Шығару лентасы MT = (S, X, Y,

А = (S,X, Y, O) Г = (L, R, H)

&: S*X S*Y &: S*X S*Y*Г

Программа: Программа

1. (s, a) (p, y) 1. (s, a) (p, y, l)

2. (q, b) (s, z) 2. (q, b) (s, z, R)

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

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

Тьюрингтің айтуы бойынша формальдық модельдің соңғы автоматтан айырмашылығы ол – 2 аспект бойынша орындалады.

1. Ол шексіз жұмыс лентасын қамтамасыз етеді, онымен ол символдарды қайда жазуды және оқуды біледі.

2. Жазудың басы онымен ол жұмыс лентасында кез – келген жаққа қозғалуы мүмкін.

Тьюринг машинасы такт бойынша жұмыс атқарады. Әрбір такта ол символдарды оқиды және жұмыс лентасында ұяшықтарды құрады. Функционалдау бейнесін, оның программасы ретінде санауға блоады. Ол бестік жиынмен беріледі. <S, A, P, Y, D>ұндағы: S,A,P және У – сол мағынаны береді, ол Д жұмыс лентасының басын қозғалтуды қамтамасыз етеді. Ол 3 мағынада айтылады. L – солға, R- оңға, және Н – орында қалу. Екінші сөзбен айтқанда бұл программа соңғы бестің тізбегі. Тьюринг машинасы бірінші соңғы жұмыстық Х алфавитін емденеді, онда енгізу және шығару символы ол лентада теріледі, машина келесі такт бойынша оқиды. Ыңғайына қарай Х элементі бос символдарды құрайды.

Қарастырайық: ТЬЮРИНГ машинасы қалай жұмыс істеитінін.

Тьюринг машинасының конфигурациясын оның өткен қалпы деп атайды. Программаны атқаруда тактта конфигурация өзгереді.

Тьюринг машинасының тоқтаған кезінде енгізу тізбегінде өңдеу нәтижесі шығады. Осыған орай программа автомвтты символдық тізбек болып табылады. Тьюринг машинасы көптеген тізбектерді түсіндіруіде мүмкін. Бұл программада арнаиы қалыптар беріледі немесе «!» және программа түсіндіруші ретінде берілсе енгізу лентасы бос болады.

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

Тьюринг машиналарының қасиеттері.

Тьюринг машиналарының бірнеше қасиеттерін қарастырайық.

Теорема. Әрбір Тьюринг машиналарына эквиваленция орындалу керек.

Дәлелдеуі: Тьюринг машинасының шығаруында эквиваленттік ережелер орындалады.

Теорема. Әрбір Тьюринг машинасына орта шексіз лента эквиваленциясы орындалады.

Дәлелдеуі: Бұл теорема конструктивтік, біз оған алгоритм берейік. Ол Тьюринг машинасы бойынша құрылады. 1-ден жұмыс летентасында ұяшықтарды нөмірлейік

Содан кейін ұяшыққа «*» символын берейік

Тьюринг машинасын қарастыру

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

Мысалы Тьюринг машинасының программасының басы мына түрлерді ұсынады.

00: егер а, 0,2; /* егер бастапқы қалыпта а символы оқылса онда 02*/командасына

01: өту, 0,5; /* егер жоқ болса басқа символ*/

02: басу, а

03: жылжыту, солға;

04: көшу, 00; /*бастапқы қалыпқа көшу*/

05: егер, в 07; /* егер бастапқы қалыпта в символы оқылса, онда 07*/командасына

06: көшу, /* егер жоқ болса басқа символға */

07: басу, в;

08: қозғалту солға;

09:.........

Бұл мысалдан келесі нәтижені шығаруға болады. Автоматты есептеу құрылғысы кез келген алгоритмді орындай алады. Тьюринг машинасының енгізу лентасының шексіз аналогы ретінде 5 операция орындалады. Оның мағынасы универсалды есептеу машинасы болып табылады.

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

Универсалды Тьюринг машинасын қарастыру оқырманға жаттығулар арқылы беріледі.

2. Бір қалыпты өрнек бойынша детерминант емес шеткі автомат құру.

Детерминант емес шекті автоматтар – есептеу теориясында қолданылатын модель.

Жай шеткі автоматтар.

Шеткі автоматтардың үш түрі болады. Олар: Мур шеткі автоматтары, Милдің шеткі автоматтар және жай шеткі автоматтар.

Сонымен, детерминант шеткі автомат деп келесі параметрге сәйкес келетін құрылғы болады:

• Q – мағынаның көптік шеткісі.
• Σ – кіру символдарының көптік шеткісі.
• δ – өту функциясы. Аргументтер – күй – жағдай және кіру символы, күй - жағдай – нәтижесі.
• q₀ – бастапқы күй - жағдайы, Q да болады.
• F – жиын күй – жағдайының кіру рұқсаты, Q жиын асты болады.

Келесі түрде құрылған:

• q₀ мағынасында автомат жұмыс істей бастайды..
• Егер автомат q_i, мағынасында болса, ал кіруге b кірсе, онда автомат δ(q_i, b) мағынасына өтеді.

Детерминант шеткі автоматтардың жұмысы символдар бауларын айырып тануда болады, Σ жиынына жататын. Егер, бауды өңдегенде, автомат кіру рұқсатындағы күй- жағдайда болса, онда бау кіру рұқсаты болады, ал егер олай болмаса, онда орындалмайды. Сайып келгенде, ДША кейбір тілге сұрау қояды – онымен рұқсат етілген бау жиыны, бұл тілдің алфавиті болады – Σ жиыны.

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

Детерминант емеске келтірейік.

Детерминант емес шеткі автоматты анықтау, жоғарыда көрсетілген детерминант шеткі автоматты анықтауға ұқсас болады, тек екі айырмашылығы болады:

• δ – өту функциясы. Аргументтер – мағына және кіру символы, нәтижесінде – мағынаның көптігі (бос – болуы мүмкін).
• Егер автомат q_i жағдайында болса,ал кіруге b символы енгізіледі, онда автомат δ (q_i, b) жиын мағынасының жағдайына өтеді. Егер автомат жиын {q_i}, жағдайында болса, онда ол жиын жағдайға өтеді.

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

2 – ші суретте жай детерминант емес шеткі автомат көрсетілген, 0 ден және 1 тізіміне рұқсат беретін бау көрсетілген және ол 00 аяқталады.

Тура осы автомат кесте түрінде:

Кесте 2. Тура осы детерминант емес шеткі автомат.

Оның жұмысын қарастырайық.

Мысалға, автомат кірісіне «100100» тізбек келіп тұрсын делік.

Кесте 3. 100100 тізімінің өңделуі.

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

1. Тюринг машинасы, фон Нейман автоматы

2. Детерминант емес шекті автомат бойынша детерминант автоматының айырмашылығы?

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

1. Мелихов А.Н. Теория алгоритмов и формальнызх языков. Таганрог1983

2. Кузнецов О.П. Дискретная математика для инженеров. М. 1988 г

Дәріс № 9. Анық емес граматика, автоматтар және тілдер

Мақсаты: Тілдер граматикасына түсінік беру.Тізбектер мен тілдерді ұғындыру

Жоспары:

Алфавиттер

2. Тізбектер

3. Тілдер.

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

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

АНЫҚТАМА 1.1. Алфавит және сөздік шекті символдар жиыны. Символ дегеніміз не - анықталмайды, қалай анықталмайды, мысалы геометриядағы нүкте сияқты.

Алфавитке бірнеше мысалдар: латын тілінде {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) Тілді қалай ұсынамыз, тілді құрайтын ұсынысты қалай анықтаймыз?

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

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

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

1. Крючкова Е.Н. Теория алгоритмов. Барнаул. 1995г

2. Любимский Э.З. Программирование М.Наука. 1980 г

Дәріс 10. Синтаксистік анализаторлар

Мақсат: Синтаксистік талдау әдісінің жіктелуін түсіндіру

Жоспар:

 Синтаксисті талдауды тағайындау.

 Синтаксистік талдаудың әдістерінің классификациясы.

Синтаксистік талдау синтаксистік анализдің бірінші этапы болып табылады. Синтаксистік талдаудың орындалуы танытушылар арқылы жүзеге асырылады.

Синтаксистік талдаудың әдістерінің классификациясы:

Үстіңгі деңгейде бөлектеніп тұрғандар:

1. талдау әдістері

2. талдау тізбегі

3. алдыңғы жақты көру мүмкіндігі

4. қайтуларды қолдану

Талдаулар кезінде әр түрлі бұтақтардың пайда болатынын суреттерден

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

Сондықтан, грамматикада символдар тізбегі бірдей болып басталатын

альтернативтіережелер кездесуі мүмкін.

Резюме.

 программалау тілінің синтаксисі неғұрлым күрделі болса, оның

грамматикасы соғұрлым күрделі болып келеді.

 грамматика неғұрлым күрделі болса, талдау әдісінің

универсалдығымен күрделілігі басым болады.

 талдаудың уиверсалды әістері оның орындалуына әлде қайда тежейді.

Классификация категориясы

Талдау әдістері

Талдау тізбегі

Алдыңғы жақты көру

Қайтаруларды қолдану кірітін шығатын аралас

Солдан оңға

Оңнан солға

Кез-келген 1 символға алдыға

N символға бар жоқ

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

1. Синтаксистік талдауды тағайындау?

2. Синтаксистік талдаудың нәтижесі не болып табылады?

3. Синтаксистік талдаудың классификациясының критерийлерін атаңыз.

4. Қандай талдау әдістері бар?

5. Кіру тізбегін шығару мен талдау әдәстерінің арасындағы байланыс.

6. Төмен қарай аралатын талдаудың қандай ерекшеліктері бар?

7. Өсетін талдаудың қандай ерекшеліктері бар?

8. Аралас талдаудың ерекшеліктері неде?

9. Талдаудың қандай тізбектері бар?

10. Талдау тізбегі мен әдістерінің арасындағы байланыс.

11. Алдын көру мүмкіндігі бар талаудың ерекшеліктері.

12. Комплексті бос грамматиканың қосымша классификациясы.

13. Қайтулары бар талдаудың ерекшеліктері.

14. Тілдің күрделілігі мен трансляциясы арасындағы байланыс.

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

1. Успенский В.А. Теория алгоритмов. М. Наука. 1987 г.

2. Касаткин В.Н. Информация. Алгоритмы ЭВМ. Радио и связь. 1986 г

Дәріс 11. Спецификация тілдері. Трансляция әдісі

Мақсат: Формальді грамматика мен тілдер теориясының негіздері мен

байланысты білімді ұсыну.

Жоспар:

 Пәннің мақсаты мен есебі.

 Негізгі ұғымдар және анықтамалар.

 Программалау және трансляторлар тілінің жалпы ерекшеліктері.

 Транслятордың жалпыланған құылымы.

 Транслятордың блоктарының нұсқалары.

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

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

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

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

Эмулятор – берілген ЭЕМ-нен өзгеше болатын және берілген ЭЕМ-де

программаны өзгертпей орындауға мүмкіндікті қамтамасыз ететін

программа.

Код түрлендіруші – бір ЭЕМ-де берілген машиналық тілдегі

программаны екінші машиналық тілдегі программаға түрлендіретің

программа немесе құрылғы.

Макропроцессор – бір тізбектің симвлодарын басқамен ауыстыруды

қамтамасыз ететін программа.

Синтаксис – қандай-да бір тілдің элементтерін формалауды анықтайтын ережелердің бірігуі.

Семантика – тілдің элементтері мен оның мағыналық мәндерінің арасындағы қатынасты анықтайтын ереже немесе шарт.

Синтаксистік анализатор – синтаксистік ережелер және берілген

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

Трансляторлар мен программалау тілдерінің ортақ ерекшеліктері.

Программалау тілдері бір-бірінен айырмашылқтары жеткілікті түрде үлкен болып келеді: Құрылымы жағынан, күрделілігі жағынан.

1. Программалау тілдері программалауды жеңілдетуге арналған. Сондықтан олардың берілгендер операторлары мен құрылымдары

машиналар тіліне қарағанда әлдеқайда қуатты.

2. Программалаудың көрнектілігін арттыру үшін адамдарға

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

3. Кез-келген тіл үшін анықталатындар:

 Дұрыс программаларды жазуда қолдануға болатын көптеген символдар.

 Дұрыс программалаудың ережелер жиыны.

 Әрбір дұрыс программаның «мағынасы».

Программалау тілімен мен программа құрылымы арасындағы байланыс -синтаксистік бейнелеу деп аталады. Транслятордың жалпыланған құрылымы.

Әрбір программалау тілінің ортақ қасиеттері мен заңдылықтары болатыны сияқты, осы тілдердің трансляторларына да қатысты болады. Оларда бастапқы мәтіннің түрлендіруінің ұқсас процестері ағып жатады. Компилятор мен интерпретатордың жалпыланған құрылымы:

 Лексикалық анализатор тізбек;

 Синтаксистік анализатор;

 Код генераторы;

 Қателер анализаторы;

 Қателер жайлы мәліметтер;

 Программаның аралық көрсетілуі;

 Объектілі код;

 Бастапқы программаның мәтінін көрсететін, символдар тізбегі.

Программалау тілдері бір-бірінен айырмашылқтары жеткілікті түрде үлкен болып келеді: құрылымы жағынан, күрделілігі жағынан.

1. Программалау тілдері программалауды жеңілдетуге арналған. Сондықтан олардың берілгендер операторлары мен құрылымдары машиналар тіліне қарағанда әлдеқайда қуатты.

2. Программалаудың көрнектілігін арттыру үшін адамдарға қабылдауға әлдеқайда ыңғайлы болуы үшін сандық кодттар орнына тілдің құрылымы символикалық және графикалық түрлері қолданылады.

3. Кез-келген тіл үшін анықталатындар:
■Дұрыс программаларды жазуда қолдануға болатын көптеген символдар.
■ дұ рыс программалаудың ережелер жиыны.
■ Ә рбір дұрыс программаның «мағынасы».
Программалау тілімен мен программа құрылымы арасындағы байланыс - синтаксистік бейнелеу деп аталады. Әрбір программалау тілінің ортақ қасиеттері мен заңдылықтары болатыны сияқты, осы тілдердіңтрансляторларына да қатысты болады. Оларда бастапқы мәтіннің түрлендіруінің ұқсас процестері ағып жатады. Компилятор мен интерпретатордың жалпыланған құрылымы:
ережелер жиынықұрылым
Сурет -1 Транслятор құрылымы
Лексикалық анализ-трансляция процесінің бірінші фазасы, Лексема деп аталатын кіру тізбегінің символдарын әлдеқайда Үлкен конструкцияларға топтау. Әрбір лексемамен 2 ұғым байланысты:
1.Лексема класы;
2.Лексема мәні;
Транслитератор деп әрбір бөлек символдарға кластарды сәй-кестендіруді жүзеге асыратын құрылғы. Символдар класының қарапайым түріне жататындар:
1.Әріп -әріптер жиынына сәйкес қойылатын класс;бұл әріптердің бір алфавиттен болуы шарт емес.
2.Сан-көбінесе 0 ден 9-ға дейінгі сандарға қатысты символдар жиыны;
3.Бөлектегіш-пробел,жолды ауыстыру.
4.Ескерту-тілдің алфавитіне тиісті емес символдар.
5.Басқалар-белгілі категориялардың ешбіріне жатпайтын символдар.
Әмбебап программалық жасақтың дамуының арқасында күрделі біріктірілген жүйелер (интегралданған) жасалып жатыр. Олар бірыңғай командалар жүйесі арқылы бір форматгы пайдалана отырып мәтін редакторын, электрондық кестелерді, графикалық редакгорды, мәліметгер базасын басқаружүйесін, калъкуляторды және тағы басқаларды біріктіріп, бір интерфейс арқылы осылардың барлығын да пайдалану мүмкіндігін береді.
Әмбебап программалык, жасақ дербес компьютерлермен жабдыкталган өртүрлі мамандьгқ иелерінің жүмыс орыңцарът автоматгандыруды іске асырады. Мұдай жүйелерге, мысалы, конструкторлық жобалауды, электрондық тақшалар жасап дайындауды, экономикалық және бухгалтерлік жүмыстарды автоматтандыру істерін жатқызуға болады.
Қоғамды дербес компьютерлермен, ЭЕМ желілерімен және информациялық қорлармен толық қамтамасыз ету бұрынғы "қағаздағы" мәлімегерді қолдану жұмыстарын толықтыра отырып, информация алу, тарату, пайдалану жұмыстарын ұйымдастыруды жаңа белеске көтерді. Мүны өзі қоғамымызды информацияландыру процестерін дамытудың негізі болады деп толығынан айта аламыз.
Қолданбалы програмалар арасындағы ерекше топқа "қосымша" программаларды даярлаудың аспаптық қүралдары (инструментальные средства) жатады.
Программалау жүйелері шыққанға дейін өр адам өзі қолданатын программа мәтінін программалау тілінде жазып, оны ЭЕМ-ге арнаулы мәтін редакторы арқылы енгізіп, сонан соң тағы бір арнайы ирограмма - компилятор (транслятор) көмегімен өз мэтінін машина тіліне аударатын. Ен соңында үшінші бір арнаулы жинақтаушы программаның арқасында бөлек модульдерден орындалатын программалық файл алынатын.
Қазіргі кезде жасалынып жатқан программалар теледидар, тоңазытқыш, шаңсоргыш тәрізді ондірістік онімдер санатына кіреді. Бүл программаларды жасау мен тарату — өндірісті жүргізу зандылықтарымен бірдей деңгейде болады деген сөз.

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

1. Мыналардың айырмашылықтарын атаңыз:

 Компилятордың интерпритатордан айырмашылығы;

 Компилятордың ассемблерден айырмашылығы;

 Эмулятордың интерпретатордан айырмашылығы;

 Синтаксистiң семантикадан айырмашылығы;

Программалау тiлiнiң соңғы шығарылған қандай белгiлi түрiн бiлесiз.

1. Аталған тiлдердiң негiзгi сипаттамасын айтыңыз;

2. Программалау тiлiмен байланысы жоқ трансляция әдістерін

облыстарда қолданылуын нақты мысалдарын келтіріңіз;

3. Программалау тiлдерін компиляциялауға нақты мысалдар келтіріңіз;

4. Программалаудың интерпретациялау тiлiне мысалдар келтiрiңiз;

5. Компиляторларыда, интерпретаторлары да бар болатын программалау

тiлiне нақты мысал келтiрiңiз;

6. Компилятордың негiзгi қасиеттерi мен кемшiлiктерi;

7. Интерпретатордың негiзгi қасиеттерi мен кемшiлiктерi;

8. Өзіңізге белгiлi екi программалау тiлдерiнiң синтаксистерiнiң негiзгi

айырмашылықтарын айтыңыз;

9. Өзіңізге белгiлi екi программалау тiлдерiнiн семантикаларының

негiзгi айырмашылықтарын айтыңыз;

10. Трансляция процесiнiң негiзгi фазаларын атаңыз.

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

1. Рейуорд-Смит В.Дж. Теория формальных языков. М. Мир. 1988 г.

2. Касаткин В.Н. Информация. Алгоритмы. М.Радио и связь. 1986 г

Дәріс 12. Лексикалық анализаторлар

Мақсаты: Лексикалық талдау, транслитератор түсінігімен таныстыру.

Жоспар:

1 Лексикалық анализдің фазасының қажеттілігі;

Транслитератор;

3 Лексикалық анализдің әдістері мен грамматикасы.

4 Белгілерді оқу. Лексикалық анализдерді программалау.

5 LEX лексикалық анализаторының құрылымы.

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

Әрбір лексемамен 2 ұғым байланысты:

1. Лексема класы;

2. Лексема мәні.

Транслитератор.

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

1. Әріп-әріптер жиынына сәйкес қойылатын класс, бұл әріптердің бір

алфавиттен болуы шарт емес.

2. Сан-көбінесе 0 ден 9-ға дейінгі сандарға қатысты символдар жиыны;

3. Бөлектегіш - пробел, жолды ауыстыру;

4. Ескерту-тілдің алфавитіне тиісті емес символдар;

5. Басқалар-белгілі категориялардың ешбіріне жатпайтын символдар.

Символдар. Лексикалық анализдің грамматикасы. Лексикалық анализаторлар көбінесе элементар конструкцияларды тану үшін қолданылады. Вирт диаграммасымен ақырлы автомат арасындағы байланыс ақырлы автоматты құрастыру үшін Вирт диаграммасын жәнес ол

жақтың рекурссиялы грамматикалар қатарын қолдануға болады. Ережежелерді сипаттауда олар анағұрлым көрнекті. Сонымен бірге Вирт

диаграммасымен ақырлы автоматтар арасында бір мәнді сәйкестік бар.

Терминалдардан ғана тұратын Вирт диаграммасына эквивалентті ақырлы

автомат мынадай түрде құралады:

1. Диаграмманың бастапқы доғасы арқылы автоматтың бастапқы жағдайына түрленеді.

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

3. Ақырлы автоматтың құралуын идентификатордың сипаттау мысалында көруге болады.

Вирт диаграммасымен оң сызықты диаграммалар арасындағы байланыс, оң жақ рекурсияны итерацияға түрлендіру. Оң сызықты грамматика болған жағдайда ақырғы автомат құрамай-ақ, бастапқы грамматиканы Вирт диаграммасына түрлендіруге болатыны туралы айта аламыз.

А) Қарапайым грамматиканы түрлендіру:

Вирт диаграммасымен сол жақ рекурсияның грамматикасы арасындағы

байланыс. Сол жақ рекурсияны итерацияға түрлендіру. Құрамында сол жақ рекурсиясы бар ережелер үшін итерацияға түрлендіруге болады:

1) Рекурсивті анықталатын терминал емес тен шығатын доға, цикл құру

арқылы ереженің ең соңын әкеліп қосылады.

2) Адресаты жоқ терминал еместер сызылып тасталынады, ал оған

кіретін доға алынып тасталады.

Лексикалық талдау.

Программаның берілуі текстік шығаруда компилятор жұмысына өте ыңғайлы сондықтан программа анализінің уақытында кезегі пайда болады немесе лексема пайда болады. Лексемалардың көпшілігі лексикалық класстарға өтеді. Лексемалар бір лексикалық класқа көшеді. Егер олар синтаксистік анализаторда болса. Мысалы: синтаксистік анализ уақытында барлық идентификаторлардыбірдей деп санауға болады. Лексикалық класстардың көлемі өте алуан түрлі. Мысалы: лексикалық класс идентификатордан өте шексіз. Басқа жағынан, лексикалық класстар бар, олар бір ғана лексемадан тұрады. Мысалы көпшілік ішінде if лексемасынан тұрады.

Программалау тілінің көпшілігінде келесі лексикалық класстар бар:

* негізгі сөздер

*идентификаторлар

*жолдық интегралдар

*сандық константтар

Барлық көпшілік ішіне кейбір сандар беріледі. Олардың лексикалық класстың идентификаторы немесе лексикалық класс деп аталады.

Мысалы: const pi = 3.1416.

Паскаль тілінің операиторын қарастырайық. Бұл оператор келесі лексемалардан тұрады:

- Const – лексикалық класс, const LS

- Pi лексикалық класс Identifier LS

- =- лексикалық класс Relation LS

- 3.1416- блексикалық класс Number LS

-; - лексикалық класс Semicolon LS

Программалау тілінің әртүрлі лексикалық талдауы.

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

Алгол 98 немесе Фортран пробелдері жолдық интегралдарға байланысты.

Мысалы: ДО5= 1,25 операторында ДО кілті сөздің 10- дық нүктесінен анықтауға болады. Басқа жағынан, ДО 5=1,25 операторында біз лексеманы табамыз.

Кілтті сөз ДО нұсқа5, идентификатор 1, оператор =, констант 1, үтір және констант 25. Сондықтан, үтірді кездестіргенше, бізДО – кілтті сөздің деңгейін береді. Бұл жағдайды шешу үшін, FORTRAN 77 әрбір үтірде нұсқа мен индекспен ДО операторында орындалады. Мұндай үтірдің қолданылуы ДО операторын анықтап береді. Қазіргі кезде прогрммалау тілдерінде кілтті сөз анықталмайды. Егер кілтті сөз анықталмаса, онда лексикалық талдау кілтті сөзді анықтайды. Шын мәнінде, нгер лексикалық талдау, мысалы, PL/I келесі операторда толық болады.

If then then then = else; else; else =then;

Лексикалық анализатордың тағайындалуы.

Лексикалық анализаторды қарастырғанға дейін, лексема не екенін біліп алуымыз керек.

Лексема (тілдің лексикалық бірлігі) – бұл тілдің құрылымдық бірлігі, ол қарапайым тілдердің символдарынан тұрады және құрамында басқа тілдердің құрылымдық бірліктері болмайды.

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

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

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

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

• лексикалық анализатор шығу программасының синтаксистік қадамындағы мәтінмен жұмысты жеңілдетеді және өңделетін ақпараттың өлшемін қысқартады.

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

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

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

Қарапайым түрде лексикалық және синтаксистік анализдер компилятормен орындала алады. Бірақ көптеген программалау тілдеріне, лексикалық анализдің қадамына ақпарат жеткіліксіз болуы мүмкін. Осындай жағдайдың мысалы болып, FORTRAN тіліндегі оператор программасы бола алады. Егер мәтін бойынша DO 10 I=1 оператордың типін анықтауға болмайды.

Басқа тағы мысал бола алатын С тілінің операторы. Оның сыртқы пішіні мынадай болады: k = i+++++j; Бұл оператордың тек бір ғана түсіндірмесі бар: k = i++ + ++j; Оның лексикалық анализаторын табу үшін, барлық операторды аяғына дейін қарап шығу керек. Қате нұсқалары тек семантикалық анализдің қадамында байқалуы мүмкін. (Мысалы, k = (i++)+++j; нұсқасы синтаксистік жағынан дұрыс болады, бірақ С тілінің семантикасымен рұқсат етілмейді). Бұл конструкция дұрыс болу үшін, оған кіретін және операндалар бейнеленуі керек және тілінің операциясына рұқсат беру керек.

Сондықтан көптеген компиляторларда лексикалық және синтаксистік анализаторлар – бұл бір – бірімен байланысты бөліктер.

Лексикалық және синтаксистік анализаторлар арасындағы байланыстардың екі түрлі әдісі бар:

• жүйелік

• параллельдік

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

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

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

... Begin

For i: = 1 to N do

Fg: = fg *0.5

...

2. Лексикалық анализатордың құрылу принциптері.

Лексикалық анализатор тұрақтылар және идентификатор сияқты объектілермен қарым қатынаста болады. Тұрақтылар және идентификаторлар тілі – көп жағдайда қайталанбас болады және қайталанбас грамматикаларының көмегімен жазылуы мүмкін. Қайталанбас тілдердің анықтамасы соңғы автоматтар болады. Мынадай ережелер болады, осы ережелер арқылы кез келген қайталанбас грамматика үшін детерминировалданған емес соңғы автомат құрылуы мүмкін. Әрбір кіру тізбегінің тілі үшін соңғы автомат сұраққа жауап қайтарады.

Сканер келесі іс - әрекеттерді орындау керек:

• лексеманың шекарасын толық анықтауы керек, олар шығу мәтінінде берілмеген;

• ақпаратты сақтау үшін, белгілі бір іс - әрекеттерді орындауы керек.

Лексемалардың шекараларын анықтау.

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

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

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

Мысалы, жоғарыда көрсетілген С тілінің жолы k = i +++++ j; лексемаларға келесі түрде бөлінеді:

K = I ++ ++ +j; - және бұл бөлу дұрыс емес, компилятор қолданушыға қате туралы хабарлама жібереді.

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

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

Лексикалық анализатордың құрылуы.

Енді сканерлердің практикалық орындалуын қарастыруға болады: Компилятордың құрамында бір емес, бірнеше лексикалық анализатор болуы мүмкін. Олардың әрқайсысы анықталған лексеманың типін тексеру және таңдау үшін арналған.

Сонымен қарапайым лексикалық анализатордың компиляторда жұмысын келесі түрде бейнелеуге болады:

• кіру ағымынан бір символ таңдалады, ол қандай сканер іске қосылатынына байланысты (символ қате болуы мүмкін);

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

• белгіленген лексема туралы анықтаманың табысты анықталуы лексема кестелерін және идентификаторлар кестесіне енгізіледі, алгоритм бірінші қадамға қайтады және кіру ағымының символдарын қарастыруға жалғастырады. Жалғасы сканерлер тоқталған жерден басталады;

• егер танылу дұрыс орындалмаса қате туралы хабарлама келеді, ал қалғаны сканердің жұмысына байланысты болады – оның жұмысы тоқтатылады немесе келесі лексеманы орындайды. (алгоритмнің бірінші қадамына өту жүріп жатыр).

Лексикалық анализатордың құрылу автоматизациясы (LEX программасы).

Лексикалық танушылар (сканерлер) – бұл компилятордың маңызды бөлігі ғана емес. Сонымен қатар лексикалық анализ басқа да облыстарда қолданылады, мысалға компьютерде мәтіндік ақпаратты өңдеумен байланысты. Ең алдымен, лексикалық анализ барлық командалық процессорларды және утилиттерді талап етеді. Сонымен қатар, енгізілу мәтінінің лексикалық анализін барлық мәтіндік редакторлар және мәтіндік процессорлар қолданады.

Лексикалық анализаторды құруға арналған көптеген программалар бар. Олардың арасынан ең танымалысы LEX программасы.

LEX – сканерлерді генерациялауға арналған прграмма (лексикалық анализатордың).

LEX программасының нәтижесі, программалау тілінің кейбіреуінде болады, ол ену файлын оқиды және одан берілген айтылуларды белгілеп алады.

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

Қазіргі кезде кез келген OC үшін LEX программасының көптеген түрлері бар.

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

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

1. Лексикалық анализатор не үшін қажет?

2. Лексикалық анализатордың не туғызады?

3. Сканердің көмегіне жүгінбей-ақ қоюға бола ма?

4. Транслитератордың тағайындалуы?

5. Сканер мен ақырғы автомат арасында қандай айырмашылық бар?

6. Вирт диаграммасымен ақырғы автомат арасында қандай

айырмашылық бар?

7. Лексикалық анализдің негізгі әдістерін атаңыз

8. Тура емес лексикалық анализдің жалпыланған түріне мысал

келтіріңіз.

9. Тура лексикалық анализдің жалпыланған түріне мысал келтіріңіз.

10. Лексикалық анализдерді программалау жолдары қандай?

11. LEX лексикалық анализаторының құрылымын атаңыз?

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

1. Гросс М. Теория формальных граматик. М.Мир. 1971 г.

2. Саломаа А. Жемчужины теории формальных языков. М.Мир. 1987 г.

Дәріс № 13 СИНТАКСИСТІК АНАЛИЗАТОРЛАР

Мақсаты: Синтаксистік талдау түсінігін, синтаксистік талдауды құру және қолдану кестесін түсіндіру.

Жоспары:

3. Шығарылған синтаксистік талдау.

Не нашли, что искали? Воспользуйтесь поиском: