6. Өрлемелі атрибуттың түрлендірушілерді тұрғызуы

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

Терминалды емес символдардың барлық атрибуттары синтезделінетін атрибут болып табылатын жай иемдену пішініндегі -атрибутының грамматика -атрибуттық грамматика деп аталады.

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

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

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

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

-грамматика ережесінің көмегімен шығаруды тұрғызуды атрибут мағынасын есептеумен біріктіреді.

-грамматикасы анықтайтын ауысымды іске қосатын түрлендірушіні құру кез келген -грамматикасы үшін мүмкін емес.

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

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

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

Өрлемейтін -түрлендірушілер жұмыс үрдісінде трансляциялау грамматикалық ережесін құратын атрибуттарды символдарымен бірге дүкенде кіріс шынжырының сол жақ шығаруын құрады. Егер атрибут мағыналары дүкенге жазу кезінде аніқталмасы, онда олардың мағыналарының орнына бұл мағыналар орналасқан немесе бұл мағыналар алыну керек дүкен элементтеріне көрсеткіштер жазылады.

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

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

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

Өрлемелі -түрлендірушісі -атрибуттық грамматикасының беретін ауысымды орныдайды. Ол өрлемелі танушы ауысымының таблицаларын жазатын іс-әрекет пен ауысымды орындайды. Танушы таблицалары берілген -атрибуттық грамматикадан алынатын кіріс грамматикасы бойынша құрылады.

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

6-тақырып Автоматтардың құрылымдық синтезі

6.1 Автоматтардың құрылымдық синтезі

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

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

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

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

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

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

      Жалпы жағдайда келтірілген құрылымдық автомат кестесіндегі комбинациялық кесте түрлі міндеттерді шешуі мүмкін. Егер бұл кестені әрбіреуі жеке ішінаралық кестемен шешілетіндей екі ішінаралық кестеге бөліп тастасақ, онда автоматтық құрылымдық кестесі 2-суретте келтірілгендей түрде көрсетілуі мүмкін. Бұл кестеде комбинациялық кесте шығыс функциясын өндіреді, қоздырғыш функциясын, кодтарды түрлендіруші –шығыс сигналдарын қайта кодтауға қолданылады, ал кодтарды түрлендіру –шығыс сигналдарын түрлендіруге.

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

Құрылымдық синтездің негізгі кезеңдері.

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

• Автоматтың құрылымдық кестесін таңдау. Синтездің бұл кезеңі көбінесе кестенің тұрғызылу ретін анықтайды. Бұл кезеңнің негізгі қиыншылығы құрылымдық кесте таңдауда формалды критерилердің жоқтығында. Құрылымдық кестені таңдауды анықтайтын факторлардың негізгілерінің бірі жасаушының тәжірибесінде.

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

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

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

• Жады элементтерінің санын таңдау және автомат жай-күйін кодтау. Жай-күйді кодтау дегеніміз әрбір жай-күйіне ішкі ауыспалы жиынтығы сәйкестіріледі_. Жай- күймен оларға сәйкес кодтар түрінде беріліп, автомат жай-күйін кодтау таблицасы депаталады.

• Қоздырғыш функциясын тұрғызу. Қоздырғыштың функциясы автомат көшу қажет жай-күй кодын алу үшін жады элементінің кірісіне қандай сигнал беретінін анықтайды.

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

• Шығару функциясын тұрғызу. Мили автоматында әрбір шығару функциясы шығыс сигналдар жиынтығының сәйкес компонентін анықтайды. Құрылымдық синтездегі шығыс функциясы абстрактілі автоматтың шығару функциясына сәйкес келеді. Олар y₁, y₂, ..., y_h ішкі ауыспалылар мен   кіріс ауыспалыларға бағынышты. Бұдан анықтайтын ауыспалылар мәні үнемі бір уақыт сәтіне қатысты болғандықтан, шығыс функциясы ауыстырып-қосқыш функция болып табылады:

 

Мур автоматының шығыс функциялары әр сәтте шығыс символдарының жиынтығын анықтайды: