Нашар бөлінген грамматикалар. -грамматикалар

Грамматиканың келесі детерминалданған тілдерді тудыратын класы жай бөлінген грамматикалар деп аталады. Бұл грамматиканың бөлінген грамматикадан ерекшелігі грамматика кестесінде жою ережелерін қолдануға болатындығы. Құрамында жою ережелері бар бөлінген грамматика жай бөлінген грамматикалар класына жата бермейді. Жай бөлінген және грамматикаларды анықтайтын тәсілді құру үшін біз ТАҢДАУ жиыны, АЛҒАШҚЫ және КЕЛЕСІ функциялары сияқты жаңа түсініктер енгізуіміз керек.

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

ТАҢДАУ жиынын анықтауда АЛҒАШҚЫ және КЕЛЕСІ функциялары қолданылады. АЛҒАШҚЫ функциясының аргументі ретінде толық сөздігінің кез келген шынжыры бола алады, ал АЛҒАШҚЫ функциясының мағынасы ретінде терминалдық символдар жиыны болады. Және олар шынжырынан шығарылатын шынжырдың бірінші орындарында тұра алады.

АЛҒАШҚЫ функциясының мағынасын келесі ережелерді қолданып анықтауға болады:

1 Егер шынжыры терминалды символға басталса және түрінде болса, онда АЛҒАШҚЫ () функциясы -ға тең.

2 Егер шынжыры бос шынжыр болса, онда АЛҒ .

3 Егер шынжыры терминалды емес символына басталып, түрінде болса және грамматика кестесінде ережесі бар болып, кез келген жерінде символы тұра алса: және де егер тұжырымы болмаса, онда АЛҒ функциясы біріктірілген

АЛҒАШҚЫ =АЛҒАШҚЫ АЛҒАШҚЫ АЛҒАШҚЫ

жиынын көрсетеді.

4 Егер шынжыры терминалды емес символға басталып түрінде болса, грамматика кестесінде түріндегі ережесі енеді және жою терминал емес символы болып танылады, яғни бар болса, онда функция келесідей:

АЛҒАШҚЫ =АЛҒАШҚЫ АЛҒАШҚЫ АЛҒАШҚЫ АЛҒАШҚЫ

КЕЛЕСІ функциясының аргументі ретінде терминалды емес, мысалы символы табылады, ал КЕЛЕСІ функциясының мағынасы ретінде шынжырда терминал емес символынан кейін жүре алатын терминалдар жиыны болады. КЕЛЕСІ функциясының мағынасы келесі ережелерге сәйкес орындалады:

1) Егер грамматика кестесінде келесі түрдегі

және барлық шынжыры болса, онда

КЕЛЕСІ = АЛҒАШҚЫ АЛҒАШҚЫ  ...

Дүкендік автоматтардың ауысуын құру үшін қажет болатын ТАҢДАУ жиынын АЛҒАШҚЫ және КЕЛЕСІ функциялардың көмегімен келесідей анықтауға болады: , которое потребуется нам для построения переходов магазинных:

1 Егер грамматика ережесі түрінде болып, жою шынжыры болмаса,яғни басқаша айтқанда  бар болған жағдайда: ТАҢДАУ =АЛҒАШҚЫ

2 түріндегі грамматиканың жоюшы ережелеріне таңдау жиыны келесідей анықталады:

ТАҢДАУ =КЕЛЕСІ

3 Егер грамматика ережесі түрінде болса және жоюшы шынжыр болып табылса, онда

ТАҢДАУ = АЛҒАШҚЫ КЕЛЕСІ

Енгізілген түсініктерді қолдана отырып жай бөлінген грамматика анықтамасын беруге болады. -грамматика төмендегі үш шарторындаған жай бөлінген деп аталады:

1 әр ереженің оң жағы бос шынжыр болып келсе немесе терминалды символдан басталса

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

3 сияқты терминал емес әрбір үшін бастапқы символдар жиыны :

АЛҒАШҚЫ КЕЛЕСІ =

Дәріс

Тақырып:Жылжыту-қайыру түріндегі төменнен жоғары қарай жіктеу.

Өрлеме танушы жұмысының негізінде оң жақ шығыс көмегімен алынған шынжырда қолданылатын, өрлеу немесе ұю операциясы жатыр. Бұл операция шығысқа қарама-қарсы болып келеді. Оның мәні ереженің оң жағы сол жағымен алмастырылатынында. Жұмыс кезінде кіріс танушы кіріс шынжырдың символдарын дүкенге ауыстырады және дүкенде кез келген ереженің оң жағы барып түскен кезде ұю операциясы орындалады. Бұл операцияны келесі тәсілмен анықтауға болады.

Анықтама ережесі мен шынжыры кестесінде кездесетін грамматикасы берілген дейік. Егер ережесі шынжырының оң жағы шынжыр бөлігі болса, онда грамматиканың ережесінің оң жағын сол жақпен ауыстырып шынжырын алуға болады. Бұл жағдайда шынжыры шынжырының оралуы әдісімен алынып, қолданылады

Анықтама.Шынжыр негізі деп қарастырылып жатқан оң жақтап шығару кезінде қолданылған ақырғы ереженің оң жағының кіруін айтады. Келтірілген шынжырды тануды орындайтын дүкендік автомат жұмысын келесі түрде көрсетуге болады:

Кесте 1 - -грамматикалары

Дүкен	Кіре беріс	Іс-әрекет
		ауысу
		ауысу
		ұю (1)
		ауысу
		ауысу
		ұю (1)
		ауысу
		ұю (4)
		ұю (3)
		ұю (2)
		жіберу

Детерминалданған өрлеу танушылар кез келген -грамматикалары үшін емес, тек қана бұндай грамматикалардың нақты кластары үшін ғана құрылады. -грамматикасының ішіндегі ішінаралық ең тараған -грамматикалар.

Бұл грамматикалар солдан оңға қарағанда шынжырды тануды қамтамасыз етеді. Ол туралы (Left) әрібі айтып тұр. (Right) әрібі оралу орындайтынын айтады. k параметрі шынжырдың оралуы үшін k артық емес символ көруге болатынын көрсетеді. Жалпы жағдайда -грамматикасы өте күрделі болғандықтан тәжірибеде -грамматикалық ішіндегі кластары: , немесе -жай (Simple) кіріс танушыларын жайға тұрғызу мүмкіншілігін беретін грамматикалар қолданылады.