Лекция 27. Тақырыбы: Орналастыру функциялары

Лекция 27.

Тақырыбы: Орналастыру функциялары

1. 
   Бастапқы орналастыру функциялары
   
2. 
   Конфликтті шешу әдістері
   

1. 
   Бастапқы орналастыру функциялары
   

Бастапқы функциялардың кең қолданылып жүргендерін айта кетеміз:

1. 
   Егер α машинада бірнеше сөзді иелейтін болса, α-ң бір ғана сөз түріндегікөрінісін алу үшін осы сөздердің арифметикалық (не логикалық) қосындысын есептеугше болады. Бұл сөзді енді санға айналдыруға, квадраттың түбірін тауып, h₀(α) ретінде нәтиженің орта log₂ n битін алуға болады. Өйткені, квадрат түбірдің орта биттері объекттің барлық символдарына байланысты әртүрлі объекттер орташа әртүрлі адрестер береді, және бұл объекттердің ортақ префикс не суффиксі болуына байланыссыз.
   
2. 
   α-ны білдіретін бір ғана сөзді бірдей ұзындықтағы (әдетте log₂ n бит ұзындық) бірнеше бөліктерге бөлуге болады. Бұдан соң осы бөліктерге қосып h₀(α) ретінде қосындының кіші log₂ n битін алуға болады.
   
3. 
   α-ны білдіретін бір ғана сөзді кесте көлеміне n-ге бөліп h₀(α) ретінде бөліндіден қалған қалдықты алуға болады (бұл жағдайда n жай сан болуы керек).
   

Енді конфликтті шешу әдістерін, яғни қосымша h₁, h₂, ..., h_m функцияларды құру әдістерін қарастырамыз. Ең алдымен, h_і(α) мәні h_j(α)-дан, барлық i≠j үшін, өзгеше болуы керек. h_і(α) конфликт бергенде h_і+r(α)-ны есептеп, талпыныс жасаудың мәні жоқ, егер h_і+r(α) = h_і(α) болса. Көп жағдайда m=n-1 болғанын қалаймыз. Өйткені әрдайым талицадан егер бар болса бос позицияны тапқымыз келеді. Жалпы жағдайда конфликтті шешу әдісі жадысы үлестірілген жүйенің тиімді болуына әсері күшті.

Қарапайым, әрі ең нашар h₁, h₂, ..., h_n-1 функциялары мынадай:

h_і(α) = (h₀(α)+i) mod n 1≤ i≤ n-1

мұнда r_і – псевдокездейсоқ сан. Бұл мақсат үшін 1-ден n-1 аралықтағы барлық сандарды бір мәртеден беретін кездейсоқ сандардың ең элементар генераторы да жеткілікті болады (10.1.8 жаттығу). Екіншілік функция қолданылған кезде әрдайым кездейсоқ сандар генераторы сол бір жағдайға орнатылады. Осылайша, әрдайым h қолдану кезінде сол бір r₁, r₂,.... тізбегі генерацияланады, сонымен «кездейсоқ» сандар генераторының әрекеті детерминант (анық) деуге болады.

ТАРАУ 6. Жадыны үлестіру және кодты генерациялау

Лекция 28

Тақырыбы: Компиляция фазалары

1. 
   Компилятор. Объектілі код. Лексикалық талдау
   
2. 
   Синтаксистік талдау
   
3. 
   Семантикалық талдау
   

1. Компилятор. Объектілі код. Лексикалық талдау

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

Бұл тарауда компиляторда қолданылатын адаруды дәл бейнелеу үшін қолднылатын формальді келісімдерді қарастырамыз. Бұдан соң осы формализмдермен анықталатынадарудың машиналық орындалу әдістерін қарастырамыз.

1. 
   абсолют машиналық командалар тізбегі
   
2. 
   жылжитын машиналық командалар тізбегі
   
3. 
   ассемблер тіліндегі программа
   
4. 
   қайсыбір басқа тілдегі программа
   

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

Лексикалық анализатордың жақсы моделі – бұл шекті түрлендіргіш.

2. Синтаксистік талдау

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

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

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

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

3. Семантикалық талдау

Компилятор енуші тілдің белгілі бір семантикалық келісімдері орындалғандығын тексеруі де керек. Мұндай келісімдерге мысал келтірейік:

1. 
   Нұсқау жасалынған әрбір операторлық белгі бастапқы программада нақты қайсыбір операторға белгі ретінде көрінуі керек;
   
2. 
   Ешқандай идентификатор бір мәртеден артық сипатталмауы керек;
   
3. 
   Барлық айнымалылар қолданылудан алдын сипататлуы керек;
   
4. 
   Функцияны шақыру кезінде аргументер саны мен олардың атрибуттары функция анықталуымен сәйкес болуы керек.
   

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

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

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

Кейбір компиляторларда код генерациясынан алдын оптимизация фазасы жүреді. Бұл фазада анағұрлым тиімді объектілі код алу мақсатында аралық программаға түрлендіру жүргізіледі.

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

Лекция 29, 30

Тақырыбы: Жадыны ұйымдастыру . Аралық программа көрінісі. Кодты генерациялау

2. Польдік жазба Жадыны ұйымдастыру.

3. Көпадресті код

4. Мысал қарастыру

5. Кодты генерациялау процессінің модельдері

5. 
   Аралық программа көріністері. Жадыны ұйымдастыру. Польдік жазба
   

Кодты оптимизациялау бойынша айтарлықтай жұмысты жүзеге асыратын компиляторлар бастапқы программаның орындалуын дәл бейнелейтін аралық програманың детальді көрінсін құрады. Басқа компиляторларда аралықө программаның көрінісі ретінде синтаксистік ағаштың польдік жазбаы сияқты қарапайым көрінісі қолданылады. Кодты азғана оптимизациялайтын кейбір компиляторлар объектілі кодты талдау барысында генерациялайды. Бұл жағдайда «аралық» программа талдау алгоритмінің қадамдары ретінде шартты түрде ғана болады.

Аралық программаның жалпы қабылданған бірнеше көріністері:

1. 
   постфиксті польдік жазба
   
2. 
   префиксті польдік жазба
   
3. 
   ағашты беретін байланысқан тізімдік құрылым
   
4. 
   нәтижелерінің атауы айқын берілетін көпадресті код
   
5. 
   нәтижелерінің атауы айқын берілмейтін көпадресті код
   

6. 
   Польдік жазба
   

берілген болсын:

A = B + C * -D (9.1.1)

Постфиксті польдік жазбадағы түрі:

ABCD-*+=

Префиксті польдік жазбадағы түрі:

=A+B*C-D

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

Польдік өрнектің 2 түрі де өрнектің 9.1 суретте көрсетілген синтаксистік ағашының сызықты түрі болып табылады. Бұл ағаш өрнектің синтаксистік құрылымын беінелейді. Осы ағашты байланысқан тізімдік құрылым түрінде кодтап, аралық программа ретінде алуға болады.

Cурет 9.1. Синтаксистік ағаш

7. 
   Көпадресті код
   

Т₁← -D

Т₂← *C Т₁

Т₃← +B Т₂

A← T

A←ӨВ₁...В_r түріндегі оператор (Ө - бұл +, -, *,т.б.) r-орынды оператор Ө-ны В₁...В_r айнымалылардың ағымдағы мәніне қолдану, ал алынған нәтижені А айнымалыға меншіктеу керектігін білдіреді.

1: -D

3: +B(2)

Мұнда жақша ішіндегі сан осы санмен белгіленген өрнек мәнін білдіреді.

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

8. 
   Мысал қарастыру
   

If i=j then S₁ else S₂

мұнда S₁, S₂ еркін алынған операторлар.

Бұл оператордың постфиксті польдік көрінісін былай жазуға болады:

IJ EQUAL? L₂ JFALSE S₁’ l JUMP S₂’

Мұндағы

• 
  S₁’ және S₂’ – S₁ және S₂ үшін постфиксті көрініс,
  
• 
  EQUAL? – егер екі аргумент тең болса АҚИҚАТ мәнін береді, кері жағдайда ЖАЛҒАН мәнін беретін бинарлық амал.
  
• 
  JFALSE – егер бірінші аргумент мәні жалған болса екінші аргументкөрсеткен орынға өтуді білдіретін, егер бірінші аргумент мәні ақиқат болса ешқандай әрекет орындамайтын бинарлық амал.
  
• 
  JUMP – аргумент көрсеткен орынға ауысуды білдіретін унарлық амал.
  

Осы шығару ағашында берліген мәліметтің маңыздысын 9.3 суреттегі синтаксистік ағаш түрінде беруге болады. Бұл ағаштағы S₁’ және S₂’ – S₁ және S₂-ң синтаксистік ағаштары.

Синтаксистік анализатор 9.1.2 өрнегін 9.2 суреттегі ағашқа қарай отырып талдаған болар еді, бірақ оның шығысы яғни, аралық программа 9.3 суреттегі синтаксистік ағашты құру командаларының тізбегі болар еді.Синтаксистік ағашта ішкі төбелер операцияны (амалды) білдіреді. Ал сол операцияның операндалары болып оның тікелей ұрпақтары саналады. Ситаксистік ағаштың жапырақтары идтификаторларға сәйкес келеді. Іс жүзінде жапырақтар атау кестесіне көрсеткіштер және сәйкес идентификатордың атрибуттары болып табылады.

I J

Cурет 9.3 Синтаксистік ағаш

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

INTEGER I

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

9. 
   Кодты генерациялау процессінің модельдері
   

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

А ← +ВС

түріндегі меншіктеу операторы 3 машиналық командаға бейнеленуі мүмкін:

LOAD B

ADD C

Бұл жерде біз бірпроцессорлы машина пайдаланылып отыр деп есептедік. Бұл машинада LOAD B командасы В ұяшығының мәнін сумматорға орналастырады, ADD C командасы С ұяшығының мәнін сумматор мәнімен қосады. Ал, STORE A сумматор мәнін өзгерпейді.