Жою ережелерімен грамматикалар үшін өрмелі танушылар

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

Екі операция жақшасыз арифметикалық формуланы беретін төмендегі грамматика берілген дейік:

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

Кесте 2 - Орын ауыстырумен танушы іс-әрекеті кестесі

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

артынан жүре алатын символдар жиынын символы КЕЙІНІРЕК жиынының қайсысына енетінін анықтап табуға болады. Бұл жиынды көшу кестесінде келісі тәсілмен табуға болады: символымен белгіленген бағананы, көшу кестесін аламыз да, бұл бағанамен қиылысқан жерлердегі барлық бос элемент бар жолдарды табамыз.

Бұл жолдарының белгілену жиыны символы ере алатын грамматика жиыны болып табылады. символының артынан КЕЛЕСІ жиынының символдары ере жүретінін ескере отырып, және параметрлеріне сәйкес келетін кестенің элементтеріне операциясын жазу керектігіне көз жеткіземіз. Нәтижесінде берілген грамматика үшін 3.2-кестені мен кіріс танушысын беретін 3.3-кестені аламыз:

Кесте 3 - Грамматика

Кесте 4 - түріндегі кіріс шынжыр үшін танушы жұмысын мазмұндайтын конфигурация реттілігі төмендегідей

Дүкен	Кіре беріс	Іс-әрекет

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

1 нөмірлі жою ережесі үшін іс-әрекет кестесін элементтермен толтыру келесі тәсілмен орындалады:

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

Бұл бағанада бос емес эелементтері бар жолдарды белгілейміз айтарлық бұл жолдар , символдарымен белгіленген. КЕЛЕСІ жиынын табамыз. Бұл символының артынан еретін грамматикалық символдар жиыны. Әрбір элементер жұбы үшін іс-әрекет кестесінде сәйкес торға ҰЮ операциясын жазамыз.

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

Дәріс.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1

2

3

4

;

5

6

7

8

9

10

11

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

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