ТАРАУ 5. Семантикалық талдау Лекция 25

ТАРАУ 5. Семантикалық талдау

Лекция 25

Тақырыбы: Белгілер кестесін ұйымдастыру

2. Лексемаға тиісті мәліметтерді сақтау

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

1. Атаулар кестесі

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

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

Мысалы Берілгенннің типін (нақты, бүтін, қатарлық, т.б.); оның белгі не процедура атауы, не процедураның формальді параметрі екендігін; оның статикалық не динамикалық жады облысында сақталынатындығын, идентификатордың құрылымға ие не ие емес екендігін (мысалы, массив), егер ие болса ол қандай құрылым екендігін (мысалы, массив өлшемі) білу қажет болуы мүмкін.
2. Лексемалар туралы мәліметті сақтау

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

GOTO LOOP

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

А = В+С

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

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

Мысал2. Айтлық, масивті жариялау төмендегі ережелермен анықтаатын қайсыбір тілден компилытор жасақталуда:

<массив операторы> → массив <массивтер тізімі>

<массивтер тізімі > → <массив анықталуы>, <массивтертізімі> | <массив анықталуы>

<массив анықталуы>→ <идентификатор> (<бүтін сан>)
Бұл тілде массивті жариялау мысалы төмендегіше

массив АВ(10), CD(20)

Қарапайымдылық үшін массив бұл жерде бір өлшемді (10.1.1) операторы үшін талдау ағашы (дерево разбора) төменде көрсетілген. Мұнда идентификатор – АВ, СD, ал бүтін – 10,20.

Бұл талдау ағашындағы <идентификатор>₁,<идентификатор>₂, <бүтін>₁ және <бүтін>₂ сәйкесінше мыналарды білдіреді: А,В,СD, 10 және 20.

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


<массив анықтамасы>

<массивтер тізімі>

<массив анықтамасы>

<идентификатор>₁ ( <бүтін>₁ )

Сурет Массив операторын талдау ағашы.

Лекция 26.

Тақырыбы: Орналастыру кестелері

1. 
   Орналастыру кестесі. Орналастыру механизмі
   
2. 
   Орналастыру кестесінің адресін есептеп шығару
   

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

		Атау	Көрсеткіш
	0
α объект	1
	. . . .				α жөніндегі мәліметтер
h	h(α)	α
орналастыру функциясы	. . .

Сурет Орналастыруды пайдаланған жады схемасы: а – орналастыру кестесі, б – берілгендер кестесі

Берілгендер кестесі физикалық тұрғыдан орналастыру кестесімен сәйкес түсуі мүмкін. Мысалы егер әрбір объект үшін k сөзден тұратын мәлімет керек болса, онда k_n –өлшемді орналастыру кестесін пайдалануға болады. Орналастыру кестесінде сақталынған әрбір объект k сөздер тізбегінің бір бөлігін иелейтін болар еді. Орналастыру кестесіндегі α объектіне сәйкес келетін ұяшықты α үшін орналастыру адресі h(α)-ны k-ға көбейтіп табу оңай және алынған адресті α-ға қатысты сөздер тізбегінің бірінші ұяшығы ретінде аламыз.

h орналастыру функциясы – бұл h₀, h₁,..., h_m функциялар тізбегі. Бұлардың әрқайсысы {0,1,…,n-1} бүтін сандар жиынындағы объекттер жиынтығын бейнелейді: h₀ функциясын орналастырудың бастапқы функциясы деп аталады. Жаңа α объекті кездескенде, h(α)-ны есептеу үшін келесі алгоритмді қолдануға болады. Егер объект алдын кездескен болса, онда h(α) – орналастыру кестесіндегі α сақталынған ұяшық. Егер α объекті алдын кездеспеген болса, онда h(α) - α-ны сақтап қоюға болатын бос ұяшық.

2. Орналастыру кестесінің адресін есептеп шығару

Алгоритм 10.2. Орналастыру кестесінің адрестерін есептеп шығару

Кірісі. α объекті, h₀, h₁, ..., h_m функциялар тізбегінен тұратын орналастыру функциясы h. (олардың әрқайсысы {0, 1, ..., n-1} бүтін сандар жиынында объекттер жиынтығын бейнелейді) және h ұяшықты орналастыру кестесі (бос болуы шарт емес).

Шығысы. h(α) орналастыру адресі және α-ң кездескен не кездеспегендігі жөнінде көрсетпе. Егер α орналастыру кестесінде бар болған болса, онда h(α) – α-ға берілген ұяшық. Егер α объекті алдын кездеспеген болса, онда h(α) – бос ұяшық, оған α сақталынады.

Тәсіл.

1. 
   Кезекпен h₀(α), h₁(α), ..., h_m(α) функцияларын «конфликт» туғанша 2-ші қадамды орындай отырып есептейміз. Егер h_m(α) конфликт берсе тоқтап, сәтсіздік жайында хабарлаймыз.
   
2. 
   h_і(α)-ны есептейміз:
   
   1. 
      егер орналастыру кестесіндегі h_і(α) ұяшығы бос болса h(α) = h_i(α) деп алып, α объекті алдын кездеспегендігін хабарлап, тоқтаймыз.
      
   2. 
      Егер h_і(α) бос болмаса оның атау өрісін тексереміз. Егер атау α болып шықса, онда h(α) = h_i(α) деп, α объектінің алдын бар болғандығын хабарлап тоқтаймыз. Егер атау α еме басқа болып шықса, онда конфликт туды; 2.-қадамды басқа адресті есептеу үшін қайталаймыз.
      

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

Идеал жағдайда бастпқы h₀ орналастыру функциясының кез-келген екі әртүрлі объект үшін орналастыру кестесінен әртүрлі орын бергенін қалар едік. Әрине, жалпы бұл мүмкін емес, өйткені мүмкін объекттердің барлық саны әдетте кестедегі орындар санынан n көп болады.

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

Дәл осылайша, α туралы мәліметті табу үшін h(α)-ны 10.2 алгоритмі бойынша есептеуге болады. Берілгендер кестесі жадысындағы α-ға тиісті мәліметті локализациялау (бөліктеу) үшін көрсеткіш өрісіндегі көрсеткіш пайдаланылады.

(ОБСӨЖ-ге)

h_і(α)-ны 0≤ j≤ 9 үшін (CODE (α) +j) mod 10) ретінде анықтаймыз. Орналастыру кестесіне A, W, EF объекттерін енгізейік.

h₀(α)-ны есептейміз: h₀(α) = (1 mod 10) = 1. Демек А-ны 1-ші орынға (позицияға) орналастырамыз. W объектін3 орыға енгіземіз. объекті үшін h₀(EF) = (5+6) mod 10 = 1 болады. 1-орын иеленіп қойғандықтан, тағы талпыныс жасаймыз h₁(EF) = (5+6+1) mod 10 = 2. Осылайша EF үшін 2-ші орын беріледі.

	Атау	Көрсеткіш
0				А-ң берілгендері
1	А
2	EF			W -ң берілгендері
3	W
4				EF-ң берілгендері
5
6				. . . .
7
8
9

Сурет Орналастыру кестедегі мәндер
Айталық, кестеде НХ объектінің бар-жоқтығын тексерейік. h₀(HX) = 2-ні табамыз. 10.2 алгоритмі көмегімен 2-орынды тексереміз. Конфликт туындайды, өйткені бұл орынды басқа объект иелеп тұр. Бұдан соң, h₁(HX) = 3-ші орынды тексереміз. Тағы да конфликт туады. h₂(HX) = 3 деп есептеп, 4-орын бос екендігін көреміз. Осылайша, кестеде НХ объекті жоқ деген қорытындыға келеміз.