3.1 Азаймалы танушылар және -грамматикалар
Терминалданбаған дүкендік танушылар жұмысының модельденуі реттіліктің бастауыш жай-күйден соңғы жай-күйге ауысуын іздеумен байланысты. Іздеу жеке-жеке қадамдардан тұрады.
Және олардың әрбіреуі сәтсіздікке және бастапқы жай-күйге әкелуі мүмкін. Бұндай іздеу уақытты көпалатындықтан тәжірибеде қайтымсыз жұмыс істейтін детерминалданған танушыларды қолданады. Бұл танушылар -тілдердің шектеулі кластарын ғана қолданысқа жібереді, бірақ олар бағдарламалау тілдерінің барлық синтаксистік жақтарын көрсетеді.
Танушыларды азаймалы және өрмелі деп екі категорияға бөлуге болады.
Азаймалы танушылар ережелерді жоғарыдан төмен өңдейді, яғни жоғары ережелерді төменгілерден бұрын. Ал бұл уақытта кіріс анализаторлары төмендегі ережелерді жоғарыдағылардан бұрын қолданады. Детерминалданған автоматтардың мүмкіндіктері мен олардың тұрғызылу тәсілдерін көрсету үшін бұл бөлімде түріндегі грамматикалар тудыратын азаймалы танушылар қарастырылады.
атауы Left
сөзінен шыққан, себебі анализатор кіріс
шынжырын солдан – оңға қарай көреді.
Тәжірибеде көбінесе
грамматика класы қолданылады. Олар үшін
ағымды позицияда орналасқан детерминалданған
бір кіріс символды танушылар жұмыс
істейді. Оқудың бірінші қадамы ретінде
азаймалы танушылардың
грамматика кластары ішіндегі бір
реттілікті қараймыз.
Бөлінген ауыспалылар.
Құрамында жою ережелері жоқ мәнмәтінді-бос грамматика төмендегі келесі екі шартты орындаса ғана бөлінген немесе жай деп аталады:
Әр ереженің оң жағы терминалмен басталса.
Егер екі ереженің сол жағы бірдей болса, онда бұл ережелердің оң жағы түрлі терминалдық символдармен басталуы керек.
Бөлінген грамматиканың негізгі қасиеттерінің бірі – олардың әрқасысына өрлемейтін детерминалданған танушы құруға болады.
3.2 Детерминалданған азаймалы танушылардың тұрғызылуы
Тұрғызылу
тәсілі
грамматиканың
әр
ережесіне
танушы
командасын
салыстыруды
алдын
ала
ескереді.
Алдыңғы
бөлімде
мазмұндалған
-грамматика
үшін
танушыларды
тұрғызудың
жалпы
тәсіліне
сәйкес
-толық
сөздіктердің
символдар
шынжыры
және
а
терминалды
сөздікке
жататын,
түріндегі
грамматиканың
әрбір
ережесіне
кіріс
бүршігінің
қозғалуынсыз
жұмыс
беретін
және
онда
шынжырының
айналы
көрінісі
болып
келетін
(*) 
командасын сәйкесінше қою керек. Нәтижесінде бұл команданың орындалуы а терминалы дүкен шыңында болатынын атап өтейік.
Бөлінген грамматикада әрбір ереже терминалды символдан және бұл терминалдар қайталанбайтынын ескере отырып, (*) командасы кіріс бүршігінің астында терминалы болғанда және одан кейін (**) командалы орындалу қажет.
(**) түріндегі нақтылықты жою мен жұмыс тактілерінің санын азайту үшін, (*) және (**) түріндегі командаларды бір командаға біріктіреміз. Және терминалды символдар тек қана сол жақ позиция ереженің оң жақ бөлігінде орналасуы мүмкін екенін ескере өту жөн.
Бұндай
терминалдар
үшін
түріндегі
команда
құру
қажет.
Соңғы
күйге
көшу
үшін
ережесін
қосамыз
да,
бастапқы
танушы
конфигурация
ретінде
формуласын
аламыз,
бұнда
-грамматиканың
бастапқы
символы,
ал
-берілген
кіріс
шынжыры.
Жоғарыда
келтірілген
ережелерді
қолдана
отырып
бөлінген
грамматикасы
үшін
танушы
құрамыз.
Нәтижесінде:
Құрылған автоматтың жұмысын bbabab шынжырының талдауы мысалымен көрсетуге болады:
Келтірілген конфигурация реттілігі әрбір конфигурацияда бір ғана детерминалданған танушы командасы қолданыла алатынын көрсетеді.
3.3 Нашар бөлінген грамматикалар. -грамматикалар
Грамматиканың келесі детерминалданған тілдерді тудыратын класы жай бөлінген грамматикалар деп аталады. Бұл грамматиканың бөлінген грамматикадан ерекшелігі грамматика кестесінде жою ережелерін қолдануға болатындығы. Құрамында жою ережелері бар бөлінген грамматика жай бөлінген грамматикалар класына жата бермейді. Жай бөлінген және грамматикаларды анықтайтын тәсілді құру үшін біз ТАҢДАУ жиыны, АЛҒАШҚЫ және КЕЛЕСІ функциялары сияқты жаңа түсініктер енгізуіміз керек.
ТАҢДАУ жиыны әрбір ереже үшін құрылады және пайда болған кезде оқылып жатқан танушы бүршігінің астында бұл ережені қолданатын терминалды символдарды өз құрамына енгізеді.
ТАҢДАУ
жиынын
анықтауда
АЛҒАШҚЫ
және
КЕЛЕСІ
функциялары
қолданылады.
АЛҒАШҚЫ
функциясының
аргументі
ретінде
толық
сөздігінің
кез
келген
шынжыры
бола
алады,
ал
АЛҒАШҚЫ
функциясының
мағынасы
ретінде
терминалдық
символдар
жиыны
болады.
Және
олар
шынжырынан
шығарылатын
шынжырдың
бірінші
орындарында
тұра
алады.
АЛҒАШҚЫ функциясының мағынасын келесі ережелерді қолданып анықтауға болады:
Егер шынжыры терминалды символға басталса және
түрінде
болса,
онда
АЛҒАШҚЫ
() функциясы
-ға
тең.Егер шынжыры
бос шынжыр болса, онда АЛҒ
.Егер шынжыры терминалды емес символына басталып,
түрінде болса және
грамматика
кестесінде ережесі бар болып, кез келген
жерінде
символы тұра алса:
және де егер
тұжырымы болмаса, онда АЛҒ
функциясы біріктірілген
АЛҒАШҚЫ
=АЛҒАШҚЫ
АЛҒАШҚЫ
АЛҒАШҚЫ
жиынын көрсетеді.
Егер шынжыры терминалды емес символға басталып түрінде болса, грамматика кестесінде түріндегі ережесі енеді және жою терминал емес символы болып танылады, яғни бар болса, онда функция келесідей:
АЛҒАШҚЫ
=АЛҒАШҚЫ
АЛҒАШҚЫ
АЛҒАШҚЫ
АЛҒАШҚЫ
КЕЛЕСІ
функциясының
аргументі
ретінде
терминалды
емес,
мысалы
символы
табылады,
ал
КЕЛЕСІ
функциясының
мағынасы
ретінде
шынжырда
терминал
емес
символынан
кейін
жүре
алатын
терминалдар
жиыны
болады.
КЕЛЕСІ
функциясының
мағынасы
келесі
ережелерге
сәйкес
орындалады:
1) Егер грамматика кестесінде келесі түрдегі
және
барлық
шынжыры
болса, онда
КЕЛЕСІ
=
АЛҒАШҚЫ
АЛҒАШҚЫ
...
Дүкендік автоматтардың ауысуын құру үшін қажет болатын ТАҢДАУ жиынын АЛҒАШҚЫ және КЕЛЕСІ функциялардың көмегімен келесідей анықтауға болады: , которое потребуется нам для построения переходов магазинных:
1
Егер грамматика ережесі
түрінде болып,
жою шынжыры болмаса,яғни басқаша айтқанда
бар болған жағдайда: ТАҢДАУ
=АЛҒАШҚЫ
2 
түріндегі
грамматиканың жоюшы ережелеріне таңдау
жиыны келесідей анықталады:
ТАҢДАУ
=КЕЛЕСІ
3
Егер грамматика ережесі
түрінде болса және
жоюшы шынжыр болып табылса, онда
ТАҢДАУ
=
АЛҒАШҚЫ
КЕЛЕСІ
Енгізілген түсініктерді қолдана отырып жай бөлінген грамматика анықтамасын беруге болады. -грамматика төмендегі үш шарторындаған жай бөлінген деп аталады:
әр ереженің оң жағы
бос шынжыр болып келсе немесе терминалды
символдан басталса
егер екі ереженің сол жағы бірдей болса, онда ережелердің оң жақтары әртүрлі символдармен басталуы керек
сияқты
терминал емес әрбір
үшін бастапқы символдар жиыны
:
АЛҒАШҚЫ
КЕЛЕСІ
=