1. Төменге қарай айқындау әдісіне сипаттама
2. Төменге қарай айқындау әдісіне мысал
1. Төменге қарай және жоғарыға қарай әдістері адам іс-әрекетінің түрлі облыстарында кеңінен қолданылады. Әсіресе, жасанды жүйелердің анализі және синтезіне шектеуіне байланысты салаларда. Дербес жағдайда программалық қамтамасыздандыруды өңдеудің жоғарыдан төменге қарай, төменінен жоғары қарай әдістерін атап өтуге болады.
Төменге қарай айқындау ағашын ең түпкі, негізгі төбесінен бастап құру.
Айқындау бастапқы бейтерминал мен енуші тізбек символдары арасындағы аралық бастапқы бейтерминалдан келіп шығатын ережелермен толтырылып негізделген.
Негізгі төбе жапырақтардан құралған түйін болып табылады. Ал жапырақтар бастапқы бейтерминалдан келіп туындаған алтернативті ережелердің бірінің терминалдары мен бейтерминалдар тізбегі болып табылады. Қойылатын ереже жалпы жағдайда еркін түрде таңдалады. Жаңа бейтеминал төбелердің орнына олардың келіп шығатын ережелер қойылады. Бұл процесс ағаштың негізгі төбесін енуші тізбек символдарымен барлық байланыстары орнатылмайынша немесе ережелердің барлық мүмкін болған комбинациялары қарастырылып болмайынша жалғаса береді.
Айқындау ағашын құру енуші тізбектің берілген тілге тиістілігін тағайындайды.
Жалпы жағдайда сол бір енуші тізбек үшін бірнеше тілдің грамматикасы детерминирлі емес екендігін білдіреді.
2. Бұл пікірлерді келесі мысал жүзінде қарастырамыз.
Айталық G грамматикасы берілсін: G6 = ({S}, {a, +, *}, P, S),
Мұндағы Р былай анықталады:
-
S(p)a
-
S(p)S+S
-
S(p)S*S
Бұл грамматика тудыратын тізбектер “а” операндадан, “+” амалдарынан құралған өрнек түрінде болады.
Грамматиканың детерминирлі болмауы сол бір ғана терминал тізбекті әртүрлі жолдармен алуға мүмкіндік береді. Мысалы:
“a+a*a+a” өрнегін келесі жолдармен алуға болады:
-
S S+S a+S a+S*S a+ a*S a+a*S+S a+a*a+S a+a*a+a
-
S S+S S+a S*S+a S*a+a S+S*a+a S+a*a+a a+a*a+a (6.1)
-
S S*S S+S*S S+S*S+S a+ S*S+S a+a*S+S a+a*S+a a+a*a+a
Бұл мысалдағы өрнекті алудың жолдарын көптеп келтіруге болады, сондықтан бұл грамматиканы іс жүзінде қолдану туралы айтпаса да болады. Біздің жағдайымызда бұл мысал төменге қарай айқындау әдәсәнде түрлі ағаштарды қалай тудыратындығын көрсетуге мүмкіндік береді “a+a*a+a” өрнегін алудың келтірілген бір жолын ағаш құнды қадамдары арқылы көрсетелік.
  
Лекция 5 Тақырыбы: Грамматика класстары және оларды танушылар. Регуляр грамматика
-
Хомский иерархиясы
-
Грамматика класстарын танушылар
-
Р егуляр грамматика
1. Өткен сабақтардан грамматиканы G=(VT,VN,P,S) төрттігі түрінде анықталғаны белгілі. Мұндағы Р ережелердің ерекшеліктеріне қарай грамматикаларды 4 түрлі классқа бөледі. Грамматикаларды бұлайша классификациялау Хомський сирархиясы деп аталады. (Авторлық атымен аталған.)
-Егер Р-ғы ереже  Ах В не А х түрінде болса, онда оң жаққа қарай реттелген немесе регуляр грамматика деп. аталады. Мунда А,В- терминал емес, ал Х-терминал.(Бос болуыда мүмкін)
- Егер Р-ғы ереже Аα (мұнда А-терминал емес, α-терминал не терминал емес болуыда мүмкін) түрінде берілсе, онда грамматиканы контексті бос деп. аталады. 
-Егер Р-ғы барлық ережелер α→β болса, онда грамматиканы контексті тәуелді деп. аталады. Мунда │ά│≤│β│.(α,β –терминал емес не терминал.)
-Егер грамматика жоғарыда келтірілген 3шектеудің ешқайсысын да қанағаттандырмайтын болса, онда жалпы түрдей деп аталады.
Кей жерлерде жоғарыдағы грамматика класстарын 3-тен 0-ге дейін нөмерлеп, әр класты “n типті грамматика” деп. аталады.
Шартты түрде Хомський сирархиясын былайша бейнелеп көрсетуге болады:
Сонымен, грамматика класстары бірін-бірі өз іштеріне алады, яғни барлық контексті бос грамматикалар контексті тәуелді грамматикаларға жатады. Ал барлық контексті -тәуелді грамматикалар жалпы түрдегі грамматикалар болып есептеледі. Бұдан бөлек і типі не тиісті бірақ і+1 типіне тиісті болмайтын тілдерде бар.
Мысалы, G3 тілі контексті –тәуелді болып табылғанмен, контексті-бос емес, яғни бұл тілі тудыратын контексті –бос граматика жоқ.
-О типті грамматика –ең күрделісі, ережелер түріне ешқандай шектеу қойылмайды.
-1 типті грамматика –мұнда символ тізбегін ауыстыру мүмкіндігі оның контексі арқылы анықталады.
-2 типтегі граматика -ереженің сол жағындағы бейтерминалдар кез-келгеніне ауыстырылуы мүмкін.
-3 типтегі грамматика -ең шектелген, ең қарапайым грамматика.
2. Әр түрлі грамматика класстарын танушылар.
Әрбір классқа өз танушысы сәйкес қойылады:
-Шектеусіз грамматикамен берілген берілген тіл, Тьюринг машинасымен танылады.
-Контексті тәуелді грамматикамен берілген тіл, сызықты шектелген автоматтармен (контекстке сезімтал) танылады.
-Оң жақ сызықты (регуляр) тілдер шекті автоматтар арқылы танылады.
Танушы деп қайсыбір жиынды (біздің жағдайда- тіл) анықтауға мүмкіндік беретін жалпыланған алгоритм деп ұғамыз. Ол өзінің жұмысы барысында келесі компоненттерді пайдаланады: енуші лента, шектелген жадысы бар басқару құрылғысы және қосымша жады. Әдетте, басқару құрылғысы енуші лентада жазылған мәліметті оқып және енуші лента бойымен алға жылжиды. Кейде артқа да жылжуы мүмкін. Оқу кезекті символды көрсететін енуші тиек (головка) көмегімен жүзеге асады. Танушы жады жағдайында өзгерте алады. Жады стек түрінде (магазин деп те аталады.) не сызықты орналасқан ұяшықтарды шектелген тізімі (жиыны) түрінде ұйымдастырылуы мүмкін.
Егер енуші лентаға берілген тізбек танушы бірқатар қадамдарды орындауға мүмкіндік берсе, және танушы соңғы жағдайына келіп тоқтаса, онда тізбек берілген тілге тиісті деп есептеледі. Тіл осылай танылады.
3. Регуляр грамматикалар.
Грамматикалардың ең қарапайым әрі ең шектеген типі –регуляр грамматиканы қарастырамыз.
Кейбір мысалдар:
Идентификатор (БНФ формасында беріледі).
<идент>: : =<әріп> <идент>: : = <идент> <әріп> → <идент> : : =
= <идент> <цфр> <әріп> : : = а |b|...|= <цфр> : : 0|1|...|9
Арифметикалық өрнек.(жақшасыз)
G=(VT,VN, P,S) VT={S, E, OP, i } VN={, <идент>, +, -, *, /}
Р={ S→ iS→ i EE→ OPSop→+op→ -op→ *op→ /i→< сан>і→<идент> }
Осы жақшасыз өрнектер грамматикасын БНФ түрінде беруге болады.(бұл қатаң түрде болмаса да айтарлықтай көрнекті).
: : =< сан>|<идент >|: := : : = + | - | * | / <сан>: : =< цфр >
Z : : = UO |V1: : =Z1|1V : : =ZO|0
Бұл грамматика тудыратын тіл 01 не 10 жұптарынан түзілген қатарлардан тұрады, яғни
L(G)={Bh|h>0} мунда B={01¸10}
Жоғарыдағылардан сәл ғана күрделірек объектіде (мысалы, жақшасы бар арифметикалық өрнек) онда регуляр грамматикалардың өте шектелгендігі себепті →N ді қарастыра алмаймыз.
Мысал:
Арифметикалық өрнек (жақшасы бар)
G0=( { Е, Т, Ғ},{a,+, *, (, ),#}Р, Е)
Р={Е→Е+Т |Т Т →Т*F |F F→(Е)|a}
Бұл енді регуляр емес. Бұл контексті - бос грамматика.
Шектелгендігіне қарамастан регуляр грамматикалар компиляторлар теориясында маңызды орын иелейді. Олар компилятордың бірінші бөлігі-сканерді жүзеге асыру үшін жеткілікті. Өйткені, сканер идентификатор және константа (тұрақты сияқты қарапайым объектермен жұмыс істейді.
Сонымен, регуляр тілдердің фразаларын (сөйлемдерін) тудыра аламыз. Алайда біздің мақсатымыз тудыру емес, сөйлемдерді тану. Сондықтан, келесі сабақта тиімді танушы механизмдердің бірі – шекті автоматтармен танысамыз.
Достарыңызбен бөлісу: | 
