Лекция: 45 сағат С¤Ж: 45 саѓат обс¤Ж: 45 саѓат Барлыќ саѓат саны: 135 саѓ Ќорытынды баќылау: емтихан 2 семестр

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

Айталық, синтаксистік анализатор кірісіне мынадай өрнек берілсін:

<ид1> =(<ид2>+<ид3>)*<ид4> және”А=B+C*D” шығысында мыналарды аламыз:

1. 
   Ағаш.
   

Бірінші өрнек Екінші өрнек

+,<ид2>, <ид3>, T1 ,C,D,T1

,T2, <ид4>6, T2 +,B,T1,T2

=, T2, <ид1> =,T2,A.

(Т1, Т2 – компиляторқұрған уақытша айнымалылар).

2. 
   Поляк формасы.
   

Операндалар орналасу реті поляк формасында бастапқы инфексті өрнектегідей (авс= және вса= жазулары 2 түрлі мән береді). Поляк жазу формасын есептеу алгоритмі өте қарапайым: енуші тізбектің символдарынбіртіндеп қарап шығамыз. Егер кезектегі символ операнда болса (иденфикатор не константа) онда әрі қарай оқимыз. Егер символ бинорлық оператор болса, алдыңғы екі оператормен қоса операторды тізбектен бөліп аламыз. Операцияны орындап, нәтижені қайта символдар тізбегіне орналастырамыз.

Лекция 14

Тақырыбы: Формальді грамматика

1. 
   Тілді аныќтау мєселесі
   
2. 
   Грамматиканы аныќтау
   
3. 
   Грамматиканыњ кейбір ќасиеттері
   

1. Табиѓи не жасанды басылым кез – келген тілде ќарым – ќатынас жасау сµйлем арќылы ( дєлірегі фраза) ж‰зеге асады. Сµйлем осы тіл сµздерініњ шекті тізбегінен т±рады. Сµйлемді ќ±ра білу керек. Егер сµйлемді ќ±ру механизімі жєне оныњ д±рыстыѓын тексеретін механизім ( аныќтау, ( тану) механизімі) бар болса, онда осы тілдіњ ќайсыбір теоремасы бар болѓаны.

АНЫЌТАМА :  тілі - А алфавитінен т‰зілген ±зындыѓы шекті тізбектер жиыны.

Компиляция жасау барысында бірінші туындайтын мєселелердіњ бірі б±л ќарастырылатын програмалау тілін аныќтау. Тілді ќалай беруге болады ?

Біріншіден ( берілген ќандайда бір А алфавитінен т‰зілген) тізбектер саны шектеулі болатын тілдерді ќарастырѓан жаѓдайда барлыќ м‰мкін болѓан тізбектерді айќындап беруге болады.

Екіншіден тізбектіњ ±зындыѓына ешќандай шектеу ќоймайтын тілдер де бар. М±ндай жаѓдайда тілдіњ ќандайда бір шекті бейнесін тілді бейнелейтін шекті ережелер жиынына беруге болады. Жалпы тілдерді беруге ыњѓайлы т‰рлі математикалыќ формализмдер бар. Солардыњ ішінде кењ таралғаны – грамматика деп аталатын механизм.

Басќаша айтќанда грамматика – тілді бейнелейтін математикалыќ ж‰йе.

Грамматика ќайсыбір ережелер кµмегімен тілге тиісті барлыќ тізбектерді бере алады. Грамматиканы тілді беруге ѓана емес, тілді тану ‰шін де пайдалануға болады. Оныњ артыќшылыѓы да осында. Яѓни енуші ( беріліп отырѓан ) тізбектіњ аныќталып отырѓан тілге сєйкестігін ( тиістілігін) грамматика кµмегімен аныќтауѓа болаы.

• 
  Терминал символдар. ( алфавит)
  
• 
  Терминал емес символдар. (кейде ±ѓымдар деп те аталады)
  
• 
  Шыѓару ережесі (тудыру)
  
• 
  Бастапќы символ.
  

Енді грматиканыњ аныќтамасын формальді т‰рде жазып шыѓу ‰шін тµмендегі белгілеулер ќажет болады.

• 
  Егер А алфавит болса, онда А* арќылы А алфавитіне енген символдардан т‰зілген  тізбектер ( ќатар ) жиынын белгілейміз. Б±л жиынѓа бос тізбекте ( оны е арќылы белгілейміз ) енеді.
  

• 
  белгілейміз.
  

Vт – терминал символдардыњ шекті жиыны.

V_N – терминал емес символдардыњ шекті жиыны

Vт U V_N =  ( яѓни Vт мен V  ќиылыспайды, екеуініњ ортаќ символдары жоќ)

Р – ( , ) т‰ріндегі ережелердіњ шекті жиыны. М±нда,   V +,   V* ( V= Vт U V_N )

S – бастапќы символ, S υ VN

Мысалы. 1)[ 0n 1 n / n ≥ 0 ] тілді тудыратын грамматика былай белгіленеді.

Ġ=({ 0,1}, { S}, Р, S), м±нда Р = { S→0S1, S→e}

Лекция 15

Тақырыбы: Бэкус– Наур формасы.

1. 
   Бэкус– Наур формасы
   
2. 
   Кеңейтілген Бэкус – Наур формасы
   

1. Енді қазіргі кездегі праграммалау тілдерінің синтаксисін берудің кең тараған әдістерін қарастырамыз. Формальді грамматикалардың қандай– да бір түрі көбірек қолданылатыны табиғи. Бірақ формальді грамматика көмегімен тілдің контексті– тәуелсіз құрамдас бөлігі анықталады. Сондықтан жалпы жағдайда реалды (реальный) праграммалау тілдері үшін мұндай грамматика көмегімен алынған терминалдар синтаксисі дұрыс программа болады деп айта алмаймыз. Себебі дұрыс программа контекстті шарттарды да қанағаттандыруы қажет. Тіл синтаксисін бейнелеудің кең тараған әдісінің бірі – БЭКУС– НАУР формасы. Бұл әдіс АЛГОЛ– 60 тіл бейнелеу үшін дайындалған еді. Бірақ, кейінірек басқа да көптеген тілдер үшін қолданылды.

Грамматиканы БЭКУС– НАУР формасында жазу кезінде объекттердің 2 типі қолданылады:

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

• 
  металингвистикалық байланыстырушылар (связки) (::=,1)
  

МЫСАЛ :

2. 
   Кеңейтілген Бэкус– Наур формасы
   

• 
  Бейтерминалдар жеке сөздер ретінде жазылады.
  
• 
  Терминалдар тырнақшаға алынып жазылады, мысалы “ BEGIN”
  
• 
  Дөңгелек жақшалар топтау үшін қолданылады.
  
• 
  Вертикаль сызық, алдыңғыдай альтернативтерді анықтауға қолданылады. Квадрат жақшалар символ не символдар тобының мүмкін болған енулерін анықтау үшін паидалынады.
  
• 
  Фигуралы жақшалар символ не символдар тобының мүмкін болған қайталанулары үшін қолданылады.
  
• 
  Теңдік символы ::= символының орына қолданылады.
  
• 
  Нүкте символы ереженің соңын білдіру үшін қолданылады.
  
• 
  Түсініктемелер (комментарий) (*...*)символдары арасына жазылады.
  
• 
  – [ ] символымен де беріледі.
  

Integer= sign unsiged integer.

Unsgigned integer =digit {digit}.

Sign=[“ +”|”-“]

Didit =”0”|”1”| “2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".