Лекция Тақырыбы: Алфавиттер, тізбектер және тілдер

Лекция 1.

Тақырыбы: Алфавиттер, тізбектер және тілдер

1. Алфавит. Тізбектер

2. Тілдер

3. Тілдерді өрнектеу

Алдымен алфавит ұғымын енгізйік . Алфавит деп символдардың кез-келген жиынын атаймыз. Алфавит шекті болуы және санақты болуы міндетті емес, алайда практикада ол шекті болады. Алфавиттің екі мысалы: 26 үлкен және 26 кіші латын әріптері, екілік алфавит деп аталатын {0,1} жиыны.

Егер бірінен соң бірін орналастырып символдар қатарын жазып шықсақ онда бұл символдар тізбегі болады. Мысалы, 01011 – екілік {0,1}алфавиттегі тізбек. Сөз және қатар терминдері (кейде сөйлем) тізбек терминінінің синонимі ретінде жиі қолданылады.

Бос тізбек деп аталатын тізбек жиі кездеседі, сондықтан да оны арнайы е әрпімен белгілейді. Бос тізбекте ешқандай символ болмайды.
Анықтама. Е алфавитіндегі тізбек формальді түрде былай анықталады.:

1. 
   е – Е алфавитіндегі тізбек,
   
2. 
   егер х - Е алфавитіндегі тізбек болса және а символы Е-ге тиісті болса , онда ха – Е алфавитіндегі тізбек,
   
3. 
   у – Е алфавитіндегі тізбек бола алады, егер оған қатысты 1. немесе 2. пункттері дұрыс болса.
   

Кейінірек қажет болатыны үшін тізбекке қолданылатын амалдарды анықтайық. Егер х және у тізбектер болса, онда ху – х пен у –ң конкатенациясы деп аталады. Мысалы, х=аb, у=сd, онда xy=abcd. Кез-келген х тізбегі үшін хе = ех=х.

х Тізбектің айналуы деп (х^R деп белгілейміз) реті кері қарай жазылған х тізбегін атаймыз, яғни, егер х =а₁...а_n, болса, мұндағы а_і-ң барлығы символдар, онда х^R = а_n...а_1. Бұдан бөлек, е^R =е.

Айталық х, у, z – қайсыбір Е алфавитіндегі кез-келген тізбектер. ху тізбегінің префиксі (не басы) деп х-ті айтамыз, ал суффиксі (не аяғы) деп у-ті айтамыз. у-ті хуz тізбегінің ішкітізбегі деп атаймыз. Тізбектің префиксі және суффиксі оның ішкітізбектері боп табылады. Бос тізбек кез-келген тізбектің префиксі, суффиксі және ішкі тізбегі боп табылатындығын айта кетеміз.

Егер х≠у және х – у-ң префиксі (суффиксі) болса, онда у тізбегінің өз (өзінің) префиксі (суффиксі) деп аталады.

Тізбек ұзындығы – бұл ондағы символдар саны, яғни, егер х = а₁...а_n, мұндағы а_і –лер символдар, онда х тізбегінің ұзындығы n-ге тең.

х тізбегінің ұзындығын |x| -пен белгілейміз. Мысалы, |аав| =3 және |е| =0.
2. Тілдер
Анықтама. Е алфавитіндегі тіл деп Е-дегі тізбектер жиынын айтады. Кез-келген тіл ұғымы бұл анықтамаға дұрыс келеді, Фортран, Паскаль, тіпті ағылшын тілі де.
Мысал 10. Е алфавитіндегі қарапайым тілдерге мысал клтірейік. Бос жиын Ǿ - бұл да тіл. Бос тізбек қана тиісті болған жиыны да тіл боп саналады. Ǿ мен {е}-ң екі түрлі тілдер екенін ескертеміз.
Анықтама. Е^* арқылы Е алфавитіндегі барлық тізбектерді, соның ішінде е-ден құралған жиынды белгілейміз. Мысалы, егер Е екілік алфавит {0,1}болса, онда

Е^* ={е, 0,1, 00, 01, 10, 11, 000, 001, ...} болады.

Е алфавитіндегі әрбір тіл Е^* жиының ішкі жиыны болып табылады. Е алфавитіндегі е-ден басқа барлық тізбектер жиына Е¹ деп белгіленеді.
Мысал 11. L₁ тілі айталық, нөл не одан көп а символынан құралған тізбектерден тұрсын. Оны былай белгілеуге болады: {aⁱ | i≥0}. L₁ ={а}^* екендігі көрініп тұр.
Анықтама. Егер қайсыбір L тілдегі ешқандай тізбек осы тілдегі басқа ешқандай тізбектің өз префиксі (суффиксі) болып табылмаса, онда бұл L тілін префиксті қасиетке ие деп атайды.

Мысалы, {a}^* префиксті қасиетке ие емес, ал, {aⁱb | i≥0} бұл қасиетке ие.

Тіл дегеніміз жиын болғандықтан жиынға қолданылатын біріктіру, қиылысу, айырмасын табу, толықтыру амалдары тілдерге де қолданылады. Конкатенация амалын тізбектерге қолданған сияқты тілдерге де қолдануға болады.

1. 
   L⁰={e},
   
2. 
   Lⁿ=LL^n-1 , n≥1 үшін
   
3. 
   L^*=Lⁿ .
   

L тілінің позитивті итерациясы L⁺ деп Lⁿ тілін айтамыз. L⁺= LL^*= L^*L және L^*= L⁺{e} болатынын ескерте кетеміз.

Лекция 2.

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

1. Тілді анықтау мәселесі

2. Грамматиканы анықтау. Терминал және терминал емес белгілер. Шығару ережелері

3. Бэкустың нормаль формалары.

1. Тілді анықтау мәселесі

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

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

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

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

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

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

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

2. Грамматиканы анықтау. Терминал және терминал емес белгілер. Шығару ережелері

Грамматика келесі компоненттер арќылы аныќталады.

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

Грамматиканы бейнелеуді (баяндау) тілдік алфавиттік аныќтаудан бастау керек. Ол    т‰рінде болады. Б±л ережелер кµмегімен тілдіњ барлыќ тізбектері ќ±ралады ( туындайды). Б±л ережелердіњ оњ жєне ол жаќтарында арнайы терминал емес символдар кездесуді м‰мкін ; шыѓару барысында терминал емес символдар сєйкес ережелер кµмегімен терминалсимволдарѓа ауыстырылады. Грамматикаѓа б±лардан бµлек бастапќы символ не аксиома да ену керек. Тілдіњ барлыќ сµйлемдерді бастпќы символда баталады.

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

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

Мысалы А=  а, в, с  Онда А* =  е, а,в,с,аа,ав, ас,вв,вс,сс,...авс,...

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

АНЫЌТАМА : G граматика мына тµрттік арќылы аныќтлады : G = ( Vт, V_N , Р, S ) м±нда,

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}

3. Бэкустың нормаль формалары.

Қазіргі таңда информатикада формальді тілдерді тудыратын бірнеше граматиканы беру әдістері жасалынған. Қарапайым әдістердің бірі (әрі көп жерде қолданылатын) Бэкустің нормаль формалары деп аталатын әдіс.

Мысал арқылы қарастыралық. Айталық 2-лік цифр (0,1) және үтірден тұратын х алфавиті берілсін. Осы алфавит арқылы барлық рационал теріс емес екілік сандардан (бүтін, бөлшек) тұратын тіл құру керек. Мұндай тіл құру үшін Бэкус әдісінде мынандай екі (мета ұғым) ұғым беріледі.

“Сол жақ” Оң жақта келтірілген форма мәндерінің кез-келгенімен анықталады. n деген сөйлемді ынғайлылық үшін : : = белгісімен береміз.

<бүтін сан>: : =<0><1><0> <бүтін сан><1> <бүтін сан>

<екілік сан>: :=<бүтін сан> <,> <бүтін сан>

Мұнда  - немесе деген мағынаны білдіреді.

Жоғарыдағы анықтамаларға сәйкес дұрыс сөздер, яғни 2-лік сандар деп төмендегілерді айтуға болады: 01, 0010, 00.

жүктеу/скачать 1.44 Mb.

Достарыңызбен бөлісу: