Ауысуды мазмұндау тәсілдері мен түрлендірушілер

Аз элементтер санымен берілген соңғы ауысуларды атап өту түрінде беруге болады. Бірақ, үлкен соңғы ауысулар мен аяқталмайтын ауысуларды беру үшін формалды тілдерге қажет сияқты құралдар керек. Кіріс шынжырларының жиынын ( ауысымының кіріс тілі) грамматикасының көмегімен және шығыс шынжыр жиының ( ауысымының шығыс тілі) грамматикасының көмегімен беруге болатын мысалдарды қарастырайық.
Бұл екеуін бір уақытта қолдана отырып келесі ережені аламыз:

Бұндай тұрғызу нәтижесінде нақты мән кіріс және шығыс шынжыр ережелерінің арасындағы сәйкестікке келеді.

Қарастырылып жатқан ауысу тәсілі -кестесі түсінігімен тұжырымдалып, келесі тәсілмен анықталады.
Ауысудың синтаксистік басқару кестесі ( -схемой) деп төмендегі бес объектінің жиынтығын атайды:

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

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

Шығарылатын жұптар түсінігі көмегімен -кестесі беретін ауысымды анықтауға болады.

Бұл кесте кіріс сөздері нөлдер мен бірліктерден, ал шығыстары әріптерінен тұратын ауысымды анықтайды. Кіріс шынжырының нөлдеріне әрпі, ал бірліктерге шығыс шынжырдың әрпі сәйкес келу керек. Және шығыс шынжыр әріптері кіріс шынжыр әріптерінің айналық көрінісі болу керек. -кестеде қарастырылып жатқан шығыс келесі түрде болуы мүмкін:

Шынжырлардың ауысуын жүзеге асыратын детирминалданған құрылғыларды құру үшін ережелер түріне қосымша шектеуліктермен келетін -кестелер қолданылады. Олар төмендегідей анықталады:

-кестесінің жай түрінің мысалы ретінде постфикстік және оларға сәйкес инфикстік формула түрінде ауысуды беретін – кестесін келтіреміз:

Ең сол жақты терминал емес символдарды аралық шынжырлар ережесін қолдану арқылы орындалатын -кестеде шығару келесі түрде болады:

Жай -кестесі мысалы ретінде – кестесін қарастыруға болады. Ол инфикстік формулаларды постфинкстік поляк формулаларына ауысуды береді.

Келтірілген -кестедегі шығару келесі түрде болады:

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

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

Бұндай грамматика ізделіп отырған -кестесінің кіріс грамматикасы болу керек. Шығыс грамматикасын тұрғызуды -кестесінің ережелерін тұрғызумен сәйкестіруге болады.

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

Мысал ретінде келесі формуланы қарастырамыз:

Шығыс формулаларнда жақша болмау керегін ескере отырып, табамыз. Грамматиканың бірінші ережесінде бір ғана кіріс терминал болғандықтан -кестесінің ережесін түрінде жазуға болады.

Грамматиканың үшінші ережесінде терминал болмағандықтан аламыз.

Бесінші ереже жоюшы болып келгендіктен шығыс грамматикасында сақталуы қажет.

Екінші ережеде тұрғызу ережесіне сәйкес болмау керек жақшалар бар болғандықтан біз аламыз.

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

Тұрғызылған ережелерді біріктіре отырып, ізделіп отырған -кестесінің ережесінің жиынтығын келесі түрде аламыз:

-кестесінің дұрыс құрылғандығына көз жеткізу үшін төмендегі мысалды қарастырамыз: