LL(1) - грамматикасы. 4 страница

Екілік және үштік кодты айыруға болады. Біріншісінің алфавиті 2 символмен шектелген (0,1), ал екіншісі 3-тік символдармен (-1,0,1). Кодты қарастыратын сигналдар келесідей сипатталады.

Ø Униполялы код.

Ø Полярлы код.

Ø Биполярлы код.

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

Дискретті ақпараттық әдістерін қарастырайық. Бірінші мысал болып Морзе алфавиті болып табылады. Онда латын әріптері және цифрлары кодталған олар нүктеден және сызықшадан тұрады. Кодталған элементтерді енгізу алфавитында символдар деп аталады. Символ деп ереже бойынша сандарды әріптерді, иероглифтерді пробел белгісін пунктуациялық белгілерді операциялық символдарды арнайы белгілерді ұғамыз.

Морзе кодының фрагменттері.

Кодталған элементтер енгізу алфавитында белгілер деп аталады. Енгізу алфавитіндегі әртүрлі белгілер санын белілік деп аталады. Кодталған символдар белгілерінің санын кодтың разрядталуы деп аталады. Соңғы кодта бірінен кейін бірі орындалады. Ал кейбір белгілер параллель біге орындалады. Морзе азбукасында:

Ø Символдар деп алфавит тілінің элементтерін және сандық алфабитті атайды.

Ø «Нүкте» және «Сызықша» белгілері бойынша (немесе «+» немесе «-» немесе «1» немесе «0»).

Ø Екі белгілеу бойынша Морзе азбукасы екі мағыналы болып келеді. (Болжарлық, екілік код) егер олар үшеу болса, онда біз үштік тернарлық үш мағыналы кодпен жұмыс атқарушы едік.

Ø Морзе азбукасы бірден беске дейінгі әріптермен және цифрлармен берілсе онда мұндағы код ауыстырылымдылы разрядты деп атлады. Егер белгілеулер бірінен кейін бірі берілсе онда Морзе азбукасы кезекті код деп аталады. Бірінші телеграф және радиобайланыс әдістері осы Морзе азбукасымен орындалған. Мұнда нүкте және сызықша түрінде импульс құрылғысы берілген. Олар телеграф лентасы арқылы XX ғасыр басында бес разрядты телеграф кодына айналды. Бірде сегіздік таблицасында белгілі кодтар тізбегі берілген. Олардың кейбіреуі ең басында байланыс үшін анықтамаларды кодтау үшін ЭВМ-да ақпаратты өңдеу үшін қолданылған.

Ø Бодо коды – бес разрядты код. Европалық стандартты телеграф байланысында қолданылған. (Екінші атауы IA-1- international alphabet # 1);

Ø М-2 немесе IA-2 телеграф коды ол бүкілхалықтық комитетпен телефон және телеграф байланысының және Бодо кодының орнына қолданылған.

Ø ASCII стандартты 7 биттік код. Ол 128 символдан тұрады, және бағанның символдары латынша сандары арнайы белгілеулермен және символдармен жазылған. Бұл кодқа ұлттық символдар 10 бинарлық комбинация құрылған.

Ø EBCDIC 8- разрядты код IBM фирмасымен ұсынылған. IBM/360-375 машина сериясына арналған.

Ø ASCII -8 -8 –разрядты код ішкі және сыртқы анықтамаларды беруде және жүйелерді орындауда қолданылады. Ол 128- симролдан тұрады, оның ұлттық кодтық таблицасы бар.

Ø Холлерита коды – ол ДК-ға ұсынылған. Содан ол ақпаратты енгізудің кодын ЭВМ перфокартында қолданылады. Ақырғы сөздерді өзгерісте жүйелерді символдың кодтауда универсалды код UNICODE қолданылады. Ол 16- разрядты кодтау символдарынан тұрады.

UNICODE стандартты техникалық комитеті екі үлкен фирмада өз жұмыстарын көрсеткен. Ол кодты анықтайды және әр түрлі символдарды, әріптерді, иероглифтерді, цифрларды идентификациялайды. Код 7-8 – биттік және ASCII орнына қолданылады. 16- разрядты UNICODE 65536 символдарды 128 ASCII кодының орнына кодталады.

Кейбір кодтың кестелік фрагменттері.

UNICODE 28000 әріптерді, белгілерді, тіркестерді, иерогливтерді дүние жүзі ұлттық тілдерін қамтамассыз етеді. UNICODE 30000 математикалық және техникалық символдарды құрайды.

Бірлік стандартты тілдік форматта ол халықаралық алфавиттерді кодтауды ретке келтіреді. Мұндағы тілдер иврит және араб тілдері. Мұнда мәтін оңнан солға қарай жазылады. Анықтамаларды беруде қалдық қодтар қолданылады. Оларға бірінші кезекпен қатені табатын кодтар жатады. Бұл кодтарды циклдің қалдық кодтары деп аталады. Бұл кодтың түрі барлығын нақты анықтайды. Бұл код берілген блокта және CRC циклдік қалдық кодында қатені табу үшін кеңінен қолданылады. Ол берілген блокта қайталанып орындалады. Егер нәтиже шығарылмаса онда мазмұнда қате бар деген сөз. Қатені түзеуде кодтар маңызды роль аталады. Бұл кодтарды қолдануда берілген қателерді анықтауға және түзетуге болады. (Хемминг коды берілген блоктағы қателерді түзейді).

Кодтау және сандарды түзеу.

Символдарды кодтаудан басқа ЭВМ-да сандарды кодтау беріледі. Біз заттарды ондық санаумен және 100-дік санаумен санауға т үйрендік, он бірлік ондықты құрайды. Он ондық жүздікті, он жүздік мыңдықты құрайды. Он ондық жүйелік санау болып табылады. Мысалы он екілік жүйелік санау немесе Римдік жүйелік санау бар. Ең қарапайым әдіс болып компьютерлік жүйе болып табылады. Санау жүйесі символдар көмегімен сандарды анықтайды, оның мағыналарын ашады. Жүйелік сандарды санауда келесі түрлерге бөлінеді:

Ø Позициялық емес;

Ø Позициялық;

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

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

1=I;

2=II;

5=IIIII;

10=IIIIIIIIII.

Келесі символдар санмен беріледі.

-1;

-6;

-12;

-24;

-60;

-365,

және ереже бойынша сандармен ол кез келген символдың комбинацмяларды жазуына және оның нәтижесін шығаруға болады. Мысалы 444 – үш әдіспен жазуға болады.

(365+60+2+6+1);

(6+1+365+60+12);

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

Мысалы:

23=2*10+3;

32=3*10+2;

және 23=32

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

VII;

VI;

IV.

V- бесті білдіреді, I- бірді білдіреді. Ал екінші жағынан цифрлардың бір – бірімен қалай орналасқаны маңызды.

VII=5+1+1=7;

VI=5+1=6;

IV=5-1=4.

Жүйелік санаудың негізі болып әртүрлі цифрлардың саны олардың позициялық жүйелік санауда қолданылады. Цифрлардың мағынасы 0-дан Р-1-ге санау жүйесі екі түрде беріледі.

^N=

Төменгі индекстер цифрда мыналарды анықтайды:

^Ø Индекстің мағынасының ондығы;

^Ø Бүтін мағынаның тірістігі;

Максималды бүтін сан a m разрядында берілген.

N =

Минималды бөлшек сан S разрядында берілген.

N =P

Екілік санау жүйесі Р=2 0 және 1 екі цифрының ақпаратын қолданады. Бірінші жүйелік санаудан екінші жүйеге көшу ережесі пайда болады. Мысалы екілік сан 101110,101 ондық санға 46,625-ке тең.

101110,101 =1*2 +0*2 +1*2 +1*2 +1*2 +0*2 +1*2 =46.625

Екілік санау жүйесін алгебралық қолданылуы.

Санның белгісі әдетте екілік цифрмен кодталады:

Ø код ноль «+» белгісін білдіреді.

Ø Код бір «-» белгісін білдіреді.

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

Ø Санның түзу коды.

Ø Қайтымды код.

Ø Қосымша код.

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

Санның түзу коды N

Егер N=a1,a2,a3,…am, онда

N>0, (N)пр=0,a1,a2,a3,…am;

N<0,(N)пр=1,a1,a2,a3,…am;

N=0 бірдей мағынада болмайды. (0)пр=0.0…=1.0….

Егер ЭВМ-да бірдей белгі берілсе, онда операция сол жолмен орындалады. Егер ол әртүрлі мағына берсе, онда абсолютті үлкен көлемде орындалады. Операциялық түзу кодқа бөлінуі және көбейтілуі қарапайым түрмен орындалады.

Кодқа операцияның саналуы теріс санмен беріледі, сондықтан ЭВМ-да түзу кодты қолданған кезде қиындықтар пайда болады.

Қайтымды код N санында белгілейік.

Егер N=a1,a2,a3,…,am және а инверсияны білдіреді, егер а=1 болса, онда а=0, және керісінше. Сонда N>0,(N)обр= 0,a1,a2,a3,…,am;

N<0,(N)обр=1,a1,a2,a3,…,am;

N=0 бірдей емес мағынаны білдіреді (0)обр=0.000…0=1.11…1.

Қайтымды кодты алу үшін цифрларды инверциялау керек. Оның белгісінің алдына бір санын қою керек және басқа разрядтағы нольді бір мен бірді нольмен ауыстыру керек.

Мысалы:

N=1011(N)обр=0.1011;

N=-1011(N)обр=1.0100.

Қосымша код N санын белгілейік. Жоғарыдағыдай N=a1,a2,a3,…,am және а биіктігін білдіреді, қайтымды а, егер а=1 болса, онда а=0, және керісінше.

Онда:N>=0,(N)доп=0.,a1,a2,a3,…,am;

N<=0,(N)доп=1,a1,a2,a3,…,am+0.00…1.

Қосымша кодты алу үшін барлық цифрларды инверциялау қажет. Содан соң ең төмен разрядқа 1-ді қосу керек.

Мысалы:

N=1011,(N)доп=0.1011;

N=-1100,(N)доп=1.0100;

N=-0000,(N)доп=10.0000=0.0000 (1 жоғалып кетеді)

Бір мағыналы емес бейнелеуде ноль жоқ. Эмперикалық ереже, қосымша кодты алу үшін теріс сандарды және барлығын инверциялау қажет.

Регистрлердің бөлінуі. Объект кодтың ықшамдылығы.

Адрестік регистрлер шапщаң жадтағы адрестерді сақтау үшін қолданылған. Бұл адресс арифметикалық және логикалық операциялық процессорларда қатысуы мүмкін. Көптеген қазіргі процессордағы регистрлердің бөлінуі адрестерде немесе регистрлерде шартты болуы мүмкін, ал АЛУ адрес пен сол шартты бірдей көреді, яғни екеуін бөлмейді. Алайда практикада программа айқын регистрлерге адрестерді бекітіп қояды. Көбінесе микропроцессорларда Motorola MC 680 XO сериясы тек қана адрестік регистрлерді операциялық адрестерінде қолданылады. Ал А7 регистрлерден функция стека шындары бекітілген.

Келесінде адрестік регистрлер қолданылады:

Базалық регистр (Base) – олар көрсетілген бастапқы адрестік объект үшін қызмет етеді.

Стек көрсеткіші (Stack Pointer) – процессорлармен, яғни жұмыс ұйымдар үшін қолданылады. Мұндай операциялар кейде мысалға айтқанда стека операциялық көшіру, әлде стекадан шығаруда, ішкі программаларда шақыру, әлде оларға келу; шақыру программалық өңдеудің үзілуі, үзілуден қайту, басқа тақырыпты қосу, деңгей ағымын жеңілдеттіру және т.б. да жұмыс істеу мүмкін. Микропроцессорларда ХР көрсеткіш стекада регистрдің SP – і қолданылады, сол стека шынын ағымдағы шығымға адрестейді. Микропроцессорларда Motorola сериясы MC 68 XO көрсеткіш стекасы адресті регистрді А7 қолданылады және көрсеткіш стеканың қолдануы.

Көрсеткіш базасы (Base Pointer) - стектің ыңғайлылығы үшін қолданылады, оның шынында болмайтын, мысалы ішкі программалардың параметрі.

Объектілік код – ең біріншіден өзін мәлім құрылым ретінде таныстырады. Объектілік кодтан шығару кодына көшіру не оны өзгерту мүмкін емес. Шек ойған көлемдерде программаның бір бөлігін тілге аудару мүмкін. Бұл белгілеуді кері өндіру үшін заң шығарушы мынадай термині `программалар ЭЕМ үшін қолданылады` қолданылады.Техникалық қабылдаудан қолдану облысына шек қойылады.

Техникада қолданылған аудан шектелген болады мысалға, әртүрлі тілде жазылған программалар бір немесе сол сияқты объектілік код болып шығады, сол сияқты шығару мәтіні нақты компьютерге бағынышты болады. Шығару мәтіндегі программ ереже бойынша құпияда сақталған. Сондай атақты программалар мысалға айтқанда Microsoft Word объектілік түрге жайылады. Оларды түсіну үшін біршама программаны мысалға келтірсе, координатада берілген екі нүктенің арасындағы арақашықтықты аламыз. Бұл программада шығу мәтіні бүгінгі күндегі үш атақты тіл программасында көрсетілген және оның объектілік коды әрбір компьютерге түсінікті Intel Pentium процессоры. Алдыға жылжу барысында тағы бір терминдік мәселені атау керек.

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

Объектілік кодқа келсек, ‘Бұл сол дақ’ арасындағы ең негізгісі – символдық кесте.

GCC ережесі

Сіз компиляцияны жабық компилятор кодымен бос программа құрылымы ретінде елестете аласыз ба? Сіздің орындалатын файлдарыңызда оның орындалатын қайдан білесіз? Ken Thompson, барлық уақытында компиляторды жазды. Және ‘login’ программасын қарады.

Басында...

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

# include < stdio.h>

Int main ()

Printf(‘Hello world!/n’);

Бұл фйлды game-ге сақтап қойыңыз. Сіз оны командадан өңдей аласыз.

Gcc game.c

Соңында, компилятор Си a.out атымне аталатын құрылған файл құрады. Сіз оны жібере аласыз, егер

a.out

Hello world

Әрқашанда сіз программаны өңдеген кезде, жаңа a.out алдыңғы программаны ескереді. Бірақ сіз программаның қайсысы программасын құрғанын айта алмаймыз. Біз бұл мәселені gcc ережесінің көмегімен шеше аламыз, біз орындалған файлды қалай атауымыз мүмкін, оны мына –о кілттің көмегімен. Біз бұл программаны game деп атаймыз,

G c c – o game game.c

Game

Hello world

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

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

# ifndef DECK – H #define DECK- H

# define DECKSIZE 52

Typedef struct deck-t

Int card [DECKSIZE];

/*number of cards used*/

Int dealt;

} deck –t;

#endif/* DECK-H*/

Бұл файлды Deck.h. секілді сақтаңыз. Сол сияқты.с файлы өңделгендіктен, біз game.c-ді өзгертуіміз керек. 2game.с файылында, # ihclude “deck.h”-ты жазамыз. Ал 5 жолда deck-t deck жазамыз. Оның ештеңесін сындырмағанымызға оған көз жеткізу үшін оны қайта өңдеңіз.

Gcc – o game game.c

Қате жоқ – онда жұмыста жоқ. Егер ол өңделмесе, онымен жұмыс істеңіз.

(Рre- compile)- Процессинг

Компилятор deck-t қандай тип екенін қайдан біледі? Өйткені ол процессинг кезінде “deck.h “ файлын “game.c” файлына көшіреді. Директивті процессор шығу кодына былай өзін көрсетеді: “#”. Сіз процессорда gcc-ндағы кілт –Е. Арқылы шақыры аламыз.

3.200 жолдың шығуы! Олар көбінесе бастапқы файлда stdioh құрылады, бірақ оларға қарасақ сіз сол біздің жазылуымызда көресіз. Егер сіз кілт арқылы – о шығу файлына ат еңбізбесеңіз, ол соңғы болып қала береді. Процессинг кодқа үлкен қасиет береді, егер ол мына 3 мақсатты орындаса.

1. “Өшіру (#include)” файлын өңдеу шығару файлына көшірсе.

2. “Анықталған (# define)” тексті нақты мәлімге ауыстырса.

3. Оларды шақыру кезіндегі жолдағы макросты ауыстырса.

Компиляция (Compile)

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

Біз автоматты түрде game.o. атты файлды құрамыз. Біз мұнда ең маңызды нүктеге тоқталамыз. Біз әртүрлі файлды юс алуымыз мүмкін жене одан объектілік код құруға болады. Бізжің мысалға келсек, карталық ойынды программаласақ және картаны deck-t секілді анықтадық, бізге енді функцияны жазу керек. Бұл функция көрсетілген картаны алып, оны орындайды. Ол “drawn” массив көмегімен картаға қарайды. Бұл массив DECKSIZE картаның қайталануын қадағалайды.

Бақылау сұрақтары:

1. Статикалық және динамикалық жады айырмашылықтарын атаңыз?

2. Компиляцияның уақыт адресі. Уақытша жады.

3. Кодтың генерациясы. Кодты құру.

4. Үш адресті код. Р – коды. Байт – коды. Машиналық кодты құруға тоқталыңыз?

Ұсынылған әдебиеттер:

1. Берн.Э.С. Вопросы теории поисковых систем. М. 1966 г

2. Брауэр В. Введение в теорию конечных автоматов. М. 1987 г

З Е Р Т Х А Н А Л Ы Қ

С А Б А Қ Т А Р Д Ы

О Р Ы Н Д А У

Ә Д І Т Е М ЕЛ І К

Н Ұ С Қ А У

Зертханалық жұмыс № 1 Толық автоматтардың эквиваленттілігі

Мазмұны: Формальдық тілдер мен грамматиканың типтерін айқындау. «алфавит», «тізбек», «формальдік грамматика», «эквиваленттілік грамматика» түсінігін бекіту. Формальді тілдердің типін, грамматикалардың эквиваленттілігі мен бірмәнділігін Хомский классификациясы бойынша туынды грамматикалардың иерархиясын құруды дағдыландыру.

Мақсаты: - «алфавит», «тізбек», «формалды грамма­тика» және «формалды тіл», «қорытынды тізбек», «эквивалентті грамма­тика» түсініктеріне шек қою;

- Хомский классификациясы эквивалентті грамматиканы құру кезінде іскерлік пен дағдыларды ұйымдастыру.

№ 1 зертханалық жұмысқа орындау тапсырмалары

Зертханалық жұмысты орындаған кезде келесі іс-әрекеттерді орындау қажет:

1) грамматикаларды құру, тудырушы формальды тілдер, берілген нұсқаларымен сәйкестігі;

2) Хомский классификацисясындағы формалды грамматика типтері мен тілдерді анықтау;

3) программалық құрылымды қамсыздандыру, Хомский классификациясындағы берілген өрістерді тану типі.

1.1 кесте - № 1 зертханалық жұмыстағы жеке тапсырма нұсқамасы

Нұсқа	Формалды тіл
	L(G)={anbmck	n, m, k>0}
	L(G)={(ab)n(cb)m	n, m≥
	L(G)={0n(10)m	n, m≥
	L(G)={wcwcw	w {a,b}+}
	L(G)={c2ndn	n>0}
	L(G)= {l+l-l	lG{a,b}+}
	L(G)={(10)n-1(01)n+1 n>0}
	L(G)={(ac)	n>0, a {b, d}, c {+, -}}
	Z(G)={ (010)w	n>0}
	L(G)={a1a2…anan…a2a1	ai {0, 1}}
	L(G)={a1a2…ana1a2…an	ai {c, d}}
	L(G)={ab.b	ai {+, -}, b { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+}

Әдістемелік әдебиеттер:

Не нашли, что искали? Воспользуйтесь поиском: