Атрибуттық трансляциялау грамматикалары мен түрлендірушілер

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

Семантиканы тапсыру үшін түрлі тәсілдер қолданылады, яғни олар: - грамматикалар, вен метатілі, аксиоматикалық және денотационды әдістер және атрибуттық трансляциялау грамматикалары ( -грамматикалары).

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

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

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

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

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

- Егер атрибуттар мұра етуші және синтезделуші болса.

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

- Бастапқы символды мұра етілетін атрибут үшін бастапқы мағына берілген болса.

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

Сол жақты шығарумен атрибут мағыналарын есептеуді көрсету

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

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

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

Есептеуді қолдану алынып қойылған шығару ережелерінің нәтижелері тізімі

1

2

3

4

;

5

6

7

8

9

10

11

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

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

5.2 АТ-грамматикаларын қолданумен жасалған синтаксистік талдау. Синтаксистік талдау үрдісі

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

Қарастырылып жатқан түрдің шынжыр синтаксисі бастапқы символы бар келесі грамматика беруі мүмкін:

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

5.3 –атрибутты трансляциялау грамматикалары. Атрибутты түрлендірушілер

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

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

-грамматикасы - атрибутты трансляциялау грамматикасы болып келесі үш шартты орындаса ғана бола алады:

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

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

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

1 мұра етілушілер атрибуттары
2 мұра етілушілер атрибуттары,
3 синтезделуші атрибуттары,
4 мұра етілушілер атрибуттары,
5 синтезделуші атрибуттары,
6 синтезделуші атрибуты.

-грамматикаларын жай иемдену формалары

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

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

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

Көшіруші ережелердің егемендік түсінігін қолдана отырып, келесі анықтамаға келеміз:

- грамматикасы жай иемдену формасынакелесі шарттарды орындағанды келеді:

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

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

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

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

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

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

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

Бұнда екі ережесі аргумент, ал біреуі нәтиже көшіретін тек қана көшіру ережелері бар.

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

бұнда мұра етілуші атрибутының мағынасы – атрибуттығының қасиетін бұзатын оның оң жағында орналасқан синтезделуші атрибутымен анықталады.

Егер де іс-әрекеттің жаңа символын символынан кейін қойсақ, онда келесі ережені аламыз:

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

-грамматикасын жай иемдену формасындағы -грамматикасына түрлендіру

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

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

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

3 іс-әрекет символын жаққан кезде келесі шектеуліктерді сақтау қажет:

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

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

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

4 Егер грамматика ережесінің біреуінің қайнар көзі екіншісіне енетін болса, онда грамматика ережесінің екі көшірме ережесін бір ережеге біріктіру керек.

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

Жай иемдену формасындағы –грамматикалары атрибуттарға салынатын шектеуліктері атрибуттық түрлендірушілерді тұрғызу үшін мүмкіндік тудырады.

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

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

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

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

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

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

-грамматикасы үшін кеңейтілген шығару

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

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

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

- Қойып қойған есептеу қадамына сәйкес келетін әрбір көшіру ережесіне қайнар көзден қабылдағышқа бағытталған, қайнар көз бен қабылдағышты шығару шынжырына байланыстыратын доғаны сәйкесінше қоямыз..

- Көптік көшірме ережелеріне сәйкесінше қайнар көзді қабылдағышпен байланыстыратын шығару шынжырында доғалар ретін қоямыз.

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

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

Келтірілген шығаруда әрбір ауыстырылатын терминал емес символдардың атрибуты шығару шынжырында сақталуы қажет.

Атрибуттық түрлендірушілер .

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

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

Date: 2016-07-25; view: 483; Нарушение авторских прав