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

жүктеу 14,81 Mb.

бет	3/127
Дата	21.05.2018
өлшемі	14,81 Mb.
	#15467

1 2 3 4 5 6 7 8 9 ... 127

Дәріс №3 ФОРМАЛЬДІ ГРАММАТИКА Жоспар
1. Формальді грамматиканың негізгі түсінігі және классификациясы.

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

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

Дәріс №3 ФОРМАЛЬДІ ГРАММАТИКА
Жоспар:

Формальді грамматиканың негізгі түсінігі және классификациясы.
Грамматикаларды классификациялау: регулярлық, контексті-бос, контексті-тәуелді, жалпы көріністегі, атрибутты, программалық. Хомскийдің формальдық тілдер иерархиясы.

1. Формальді грамматиканың негізгі түсінігі және классификациясы.

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

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

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

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

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

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

Алфавит көмегімен анықталған тіл, Х={

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

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

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

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

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

“x mod y=0”.

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

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

Х – қандай да бір алфавит болсын, x={

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

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

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

G формалды грамматикасы: T={

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

N={

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

P={

} – бұл s

(x)  S(X) түрінің s

(x)  S(X)-ке ауыстыру системасы немесе s

(x) қарастырылып отырған s

(x) қатынасына ауыстырылуы.

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

жүктеу 14,81 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7 8 9 ... 127