Лекция: 45 сағат С¤Ж: 45 саѓат обс¤Ж: 45 саѓат Барлыќ саѓат саны: 135 саѓ Ќорытынды баќылау: емтихан 2 семестр

Лекция 14

Тақырыбы: Регуляр грамматика мен шекті автоматтардыњ эквиваленттілігі. Контексті бос грамматикалардыњ ќасиеті

 шекті автоматты тіл регумер грамматикамен аныќталуы

м‰мкін жєне керсінше. Сондыќтан,б±л формализмдермен

аныќталатын тілдер эвивалентті. Берілген шекті автоматќа сєйкес келетін регуляер грамматикалы ќ±растыру (конструирование) ‰шін б(q,a) =r т‰ріндегі барлыќ ауысулар жєне барлыќ аяќтаушылар P жаѓдалар ‰шін P→Е т‰рінде барлыќ ержелер ‰шін грамматикаѓа q→ar т‰ріндегі ержелі ендіру керек.Осылайша, регумер грамматикалармен берілетін тілдер классы компиляция мєселелерінде µте ќолайлы. ¤йкені оѓан ќарапайым танушы (шекті автомат ) сєйкес келеді. Б±л танушы ‰шін екі тілдіњ эвиваленттігі аныќталып отырѓан тілдіњ бостыѓы жєне берілген тілге енуші тізбектіњ тиістілігі тексеру сияќты мєселелер алгоритмді т‰рде шешім алады. Программалау тілдердіњ кµптеген " локал " ќасиеттерін - т±раќты, тіл сµздері жєне ќатарлар сияќтылар регуляр грамматика кµмегімен аныќталуы м‰мкін. Алайда регуляр грамматикалармен берілетін тілдер классы, ќазіргі уаќыттаѓы программалау тілдерініњ кµптеген ќасиеттерін бейнелеуге м‰мкіншілігі жетпейді. Мысалы, кµптеген программалау тілдерінде мынадай жаќшалар жєне айыру сµздері туралы келісіп алу ќажеттілігі туындайды begin –end, (),  , { }.

Б±л тілді бейнелейтін регуляр грамматиканыњ жоќ екендігі айќын. Алайда,б±л тілді келесі контексті -бос грамматика кµмегімен жазу оњай : S →(S), S→SS, S→E

Міне осы себепті, контексті бос граммтикалар ( регуляларѓа ќараѓанда ) компиляцияларда кењірек таралѓан. олардыњ кµмегімен, программалау тілдерініњ синтаксисініњ µте ‰лкен бµлігін беруге болады.
2. Контексті грамматикалар ќасиеті.Синтаксистік анализдіњ толыќ процессін ќысќартылѓан т‰рде енуші тізбектіњ берілген контексті -бос грамматикаѓа тиістілігін аныќтау ретінде ќарастыруѓа болады

..........

Мысалы, ќосу жєне кµбейтуі бар ќарапайым арифметикалыќ

µрнектерді бейнелейтін, жєне КБ -грамматикамен берілген G_o тілін келесі ережелер т‰рінде ќарастыруѓа болады :

Е →Е+Е⁄ Е Е │(Е) а. Б±л граммтика бір мєнді емес. ¤йткен м±нда а+а+а не а*а +а т‰ріндегі µрнектер ‰шін 2т‰рлі нєтиже (сол жаќта жєне оњ жаќта нєтиже ) бар

Біздіњ жаѓдайда бір мєнділік емес мєселесін G_jo грамматиканы эвивалентті G_o грамматика т‰рлендіру жолымен шешуге болады. G_o : Е→Е+Т │ Т, Т→Т,Т Т→(E) │a

Б±л грамматиканыњ да кемшіліктері бар : +жєне * амалдары бірдей приоритетке ие. Сондыќтан а +а*а µрнегі (a+a)*a сияќты орындалады. Амалдардыњ д±рыс орындалу ретін ќамтамасыз ету ‰шін грамматиканы таѓыда єрі ќарай т‰рлендіріп, келесі ережелер т‰ріне келтіреміз Е→Е+Т │Т, Т→Т*F │F, F →(E)│a
3. Грамматикаларды т‰рлендіру туралы жаѓдайлар байќаѓанымыздай кейде КБ грамматикаларынды т‰рлендіруге ќажеттілік туындайды.

¤кінішке орай, екі КБ грамматикаларымен берілген тілдердіњ тењ екендігін аныќтайтын алгоримтініњ жоќ екендігі сияќты, КБ грамматикалардыњ ќалаѓан т‰рге т‰рлендіріп келтірудіњ де жалпы алгоритмдік єдісі жоќ. Алайда, ќатысы жоќ символдарды жою сияќты бір ќатар т‰рлендірулер бізге белгілі. Олар грамматиканы єлде ќайда ыњѓайлы формаѓа келтіруге м‰мкіндік береді. Б±дан бµлек кез-келген КБ грамматиканы Хомский-њ нормал т‰ріне келтіруге болады. М±нда ережелер келесі т‰рлердіњ бірінде беріледі :

- А→ВС, м±нда А,В, С бейтерминалдар

- А →а, м±нда а -терминал,

- S→, егер  тілге тиісті болса, ал S бейтерминалы ережелердіњ оњ жаќтарында кездеспейтін болса.

Басќа бір кењ таралѓан КБ грамматикалардыњ стандартты т‰рі -Гейрбахтыњ нормал формасы болып табылады.

М±нда ережелердіњ оњ жаќтары терминалмен басталады..

Лекция 15

Тақырыбы: Магазинді автомат

1. 
   Магазинді автоматтар
   
2. 
   Детерминирлі магазинді автоматтар
   

1. Магазинді автоматтарды магазиндік жадысы бар автоматтар не МП автоматтар депте атайды. Ол формольді түрде былай анықталады:

Анықтама. МП- автомат Р═(Q, ∑‚ Г, , q₀, Z₀,F) жетілігімен анықталады. Мұндағы:

-Q- жағдайлардың шекті жиыны.

-∑- шекті енуші алфавит.

-Г- магазиндік символдардың шекті алфавиті.

-- ауысу функциясы, Q х (∑U{е})х Г жиынның QxГ ^* жиынының ішкі жиыныдарында бейнеленуі.

- q₀ €Q- басқару құрылғысының бастапқы жағдайы.

- Z₀ €Г- бастапқы моментте магазинде орналасқан символ (бастапқы символ)

- F Q- аяқтаушы символдар жиыны.

(q, ω,a) € QxΣ*хГ*, мұнда q –басқару құрылғысының ағымдағы жағдайы, ω-енушітізбектің пайдаланылмаған бөлігі.(Егер ω=, онда барлық енуші тізбек оқылған деп есептелінеді), а-магазин мәні (а-тізбегінің сол жақ бірінші символы магазиннің жоғарғы символы деп саналады; егер а= болса, онда магазин бос деп есептеледі.).

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

МП-автомат пен танылатын тілдер классы, дәлме-дәл КБ- грамматикалармен берілетін тілдер классымен сәйкес түседі. (мұны дәлелдеп отырмаймыз).

МП- автоматтқа мысал

{0ⁿ1^h I n≥0} тілік танитын МП –автоматтты қарастырамыз.

Айталық P=({ q_0, q_1, q₂ },{0,1},{Z, 0},, q₀, Z, {q₀} ), мұнда :

 (q_0, 0,Z)={(q₁, OZ)}

 (q_1,0, 0)={(q₁, O,O)}

 (q₁, 1,0)={(q₂, )}

 (q₂, ,z)={(q_0,, )}

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

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

Анықтама:МП-автомат P=(Q,,,Г,q_0,,,Z_0,,F) детерминирлі деп аталады, егер әрбір qQ және ZГ үшін келесі бекітімдердің біреуі дұрыс болатын болса:

-(q,a,z)-ң a және (q,e.z)= үшін біреуден артық элемменті жоқ.

-(q,a,z)-ң барлық а және (q,e,z)үшін біреуден артық элемменті жоқ.

Өкінішке орай,дитирмирирлі МП-автоматтар барлық КБ-тілдер классының ішкі жиынын ғана бейнелейді. Ол ішкі жиын детерминирлі КБ -тілдері деп аталады. Бұл тілдер классын LR(k)-грамматикалар деп те атайды, өйткені олар тізбекті солдан оңға

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

Детерминирлі КБ-тілдер, КБ-тілдердің толық классы сияқты, бұлармен анықталатын тілдің бостығын не берілген тізбектің тілге тиістілігін тексеруге мүмкіндік береді. Бірақ детерминирлі КБ-тілдер кейбір маңызды теориялық-жиындық қассиеттерге ие емес. Мысалы: детерминирлі КБ-тілдер қиылысу, толықтырылып не біріктіруге қатысты тұйықталмаған.

Бұған қарамастан, компиляция әдісі тұрғысыннан алғанда, LR(k)-грамматикалар классы үлкен маңызға ие. Өйткені, синтаксистік айқындау (разбор) құралдары осы грамматикаларға негізделген.

Ќазаќстан Республикасы Білім жєне ѓылым министрлігі

“Сырдария” университеті

“Жаратылыстану” факультеті

“Информатика” кафедрасы

“Тілдер теориясы және автоматтандыру” пєні бойынша

050602 мамандыѓыныњ студенттері ‰шін