КЖ – грамматикасы үшін талдау анықталған және анықталмаған сұлбасы негізінде синтез алгоритмін талдау

КІРІСПЕ 6
1 ФОРМАЛДЫ ТІЛДЕР 7
1.1 Табиғи тілдер мен олардың сипаттамалары 7
1.2 Формалды тілдер және олардың ерекшеліктері 9
1.3 Бағдарламалау тілдері (Pascal, Delphi, C, C++, C#) 13
2 ФОРМАЛДЫ ГРАММАТИКАЛАР 16
2.1 Грамматиканың жіктелімі 16
2.2 Қысқартылмайтын тілдер (неукорачивающие языки) мен олардың ерекшеліктері 19
2.3 Автоматтық грамматика және олардың ерекшеліктері 22
3 КЖ . ГРАММАТИКАЛЫҚ ТІЛДЕР. КЖ . ТІЛДЕРІНЕ ТАЛДАУ ЖАСАУ 32
3.1 КЖ . грамматикалар және олардың ерекшеліктері 32
3.2 КЖ . тілдер талдауының анықталған және анықталмаған сызбалары 40
3.3 КЖ . тілдердің бір сыныбын таңдау алгоритмі 44
ҚОРЫТЫНДЫ 49
ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР 50
A ҚОСЫМШАСЫ 51
Алгоритмдер мен деректер құрылымын сипаттауға мүмкіндік беретін кез-келген белгілеулер жүйесін программалау тілдері деп атауға болады. Біздің міндетіміз-барлық программалау тілдеріне ортақ болып келетін негізгі тілдік концепцияларды қарастыру және оларды кең тараған программалау тілдерінің бірінің көмегімен иллюстрациялау болып табылады.
Қазіргі таңда бірнеше программалау тілдері құрылып, пайдаланылып келеді. Дегенмен, көптеген программистер олардың бір немесе екеуін ғана пайдаланады. Программистердің басым көпшілігі әдетте қандайда бір программалау тілі қолданылатын есептеу жүйелерінің қызметіне жүгінеді . Олай болса программистке бірнеше тілді оқып үйренудің қаншалықты пайдалы екеніне тоқталайық. Шындығында, бірнеше тілді оқып үйрену, яғни тек қана тілдің мүмкіндіктерін ғана емес, ондағы программаларды жазу концепцияларын және оның қолданылуына бұл концепцияның қалай әсер ететінін меңгеру программистке мынадай мүмкіндіктер жасайды:
1.Ол әлде қайда тиімдірек алгоритм құра алады;
2.Әдетте қолданылатын программалау тілін едәуір тиімді пайдаланатын болады;
3.Пайдалы программалық констукциялар тізімін толықтырады;
4.Қандайда бір нақты жобаны шешу үшін анағұрлым тиімді программалау тілін таңдай алады.
5.Жаңа тілдерді меңгеру жеңілдейді;
6.Жаңа программалау тілін жазу мүмкіндігі жеңіл іске асады.
Программалау тілін меңгеру дегеніміз оның мүмкіндіктерімен ғана танысу емес. Шын мәнінде, түрлі тілдердің мумкіндіктерінің ұқсастығы алдамшы елес сияқты болып келеді. Олар тек сырт қарағанда ғана ұқсас болғанымен,оларды жеке-жеке зерттеу барысында олардың бағалануы түрліше болып шығуы мүмкін. Мысалы, қарапайым қосу амалының өзі барлық тілдерде ең негізгі амал ретінде қарастырылады, бірақ С++, COBOL не Smalltalk тілдеріндегі оның бағалануы түрліше болып келеді. 50-ші жылдарда алғаш жоғарғы деңгейлі тілдер пайда болысымен олардың дайындау және пайдалану әдістері әрқашан дамып келеді.
50-ші жылдарда Fortran Lіps тілдерінің алғашқы нұсқалары жарық көрді. 70-жылдарда Ada, C, Pascal, Prolog, Smalltalk тілдері, 80-ші жылдары –C++, ML, Postscrіpt, ал 90-шы жылдары Java программалау тілі, сондай-ақ программалау жүйелері –Delphі, Vіsual Basіc, C++ Buіlder т.с.с. дүниеге келді.
1 Солнцев В.М.Язык как системно - структурное образование. — М.: Наука, 1977. — 12 бет. [Електр. ресурс]-URL: http://http://ru.wikipedia. org/wiki/ (қаралған күні: 25.05.2013)
2 Кибрик А. Е. Язык // Языкознание. Большой энциклопедический словарь. - М.: Большая Российская энциклопедия, 1998. — 605 бет. [Електр. ресурс]-URL: http://http://ru.wikipedia.org/wiki/ (қаралған күні: 26.05.2013)
3 Мечковская Н. Б.Семиотика: Язык. Природа. Культура. —М.: Издательский центр «Академия», 2004. — 106 бет. [Електр. ресурс]-URL: http://
http://ru.wikipedia.org/wiki/ (қаралған күні: 26.05.2013)
4 Хопкрофт, Дж.,Мотвани, Р.,Дж. Ульман. Введение в теорию автоматов, языков и вычислений. — М.: Вильямс, 2002 — 528 бет. [Електр. ресурс]-URL: http://http://ru.wikipedia.org/wiki/ (қаралған күні: 26.05.2013)
5 Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г.Теория и реализация языков программирования— М.: МЗ-Пресс, 2006 г. [Електр. ресурс]-URL: http://http://trpl.narod.ru/t-books/ (қаралған күні: 30.05.2013)
6Фомичёв В. С.Формальные языки, грамматики и автоматы: 2006. [Електр. ресурс]-URL: http:http://old.eltech.ru/misc/(қаралған күні: 01.05.2013)
7Ф.Вайнгартен. Трансляция языков программирования. - М., Мир, 1977. [Електр. ресурс]-URL: http://http://trpl.narod.ru/t-books/ (қаралған күні: 02.05.2013)
8 И.Л.Братчиков. Синтаксис языков программирования. - М., Наука, 1975. [Електр. ресурс]-URL: http://http://trpl.narod.ru/t-books/ (қаралған күні:02.05.2013)
9 С.Гинзбург. Математическая теория контекстно-свободных языков. - М., Мир, 1970. [Електр. ресурс]-URL: http://http://trpl.narod.ru/t-books/ (қаралған күні: 03.05.2013)
10Креншоу, Д. Пишем компилятор [Електр. ресурс]-URL: http://ftp://vt.ustu/pub/discip/spo/2004/books/krenshaw.pdf, (қаралған күні: 03.05.2013)
11 Лидовский В.В. Теория информации. Учебное пособие, 2002. [Електр. ресурс] -URL: http://http://compression.ru (қаралған күні: 04.05.2013)
        
        ӘЛ-ФАРАБИ АТЫНДАҒЫ ҚАЗАҚ ҰЛТТЫҚ  УНИВЕРСИТЕТІ
МЕХАНИКА-МАТЕМАТИКА ФАКУЛЬТЕТІ
АҚПАРАТТЫҚ ЖҮЙЕЛЕР КАФЕДРАСЫ
" КЖ - грамматикасы үшін талдау анықталған және анықталмаған ... ... ... алгоритмін талдау" тақырыбына жазылған
ДИПЛОМДЫҚ ЖҰМЫС
Орындаған
___________________
(қолы)
Маханов Ш.Б.
Ғылыми жетекші,
т.ғ.д.,профессор
___________________
(қолы)
Дюсембаев А.Е.
Нормобақылаушы
___________________
(қолы)
Жуманов Ж.М.
Қорғауға жіберілді:
Кафедра меңг.қ.а, PhD доктор
___________________
(қолы)
Бакибаев Т.И.
АЛМАТЫ 2013
Реферат
Дипломдық ... 56 ... 8 ... 11 ... ... ... 1 ... және 1 қосымшадан тұрады.
Кілт сөздер: Формалды грамматикалар, табиғи тілдер, формалды тілдер, автоматтық грамматика
Зерттеу объектісі: КЖ - ... үшін ... ... және анықталмаған синтез алгоритмін талдау.
Жұмыс мақсаты: жасанды формалды грамматикаларды құру, синтаксисті талдаулар жасау.
Жасалған жұмыстар: Табиғи тілдер мен ... ... ... ... ... ... Формалды грамматикалардың жіктелімін анықтап олардың ерекшеліктеріне талдау жасадық.
Жасалған жұмыс нәтижелері: жасалған жұмыстар бойынша ... ... ... ... ... ... ... жасалынды.
Зерттеу объектісі бойынша келешекке жасалатын жұмыстарға болжам: алдағы уақыттарда осы жұмыстың нәтижесі өндірістік ... ... ... деп ... Келешекте осы программаны ары қарай жалғастырып, көптеген тиімді әдістерді қарастырамыз.
Реферат
Дипломная ... ... из 56 ... 8 ... и из списка 11-ти использованных литературных произведений , 1 таблица и 1 дополнение.
Ключевые слова: Формальная грамматика, натуральные языки, ... ... ... ... ... Чтобы анализировать грамматику произвести анализ известных и неизвестных алгоритмов синтеза - КС.
Цель работы: ... ... ... ... цель ... ... известных и неизвестных алгоритмов синтеза- КС.
Сделанные работы: Исследование натуральных и формальных ... и ... их ... ... ... формальной грамматики и исследование её свойства. Анализ КС языков, просмотр и ... ... и ... ... КС.
Результаты: по сделанным работам пройзведен анализ по пройзвольным формальной грамматике на синтасической основе.
Прогноз на будущее развитие ... над ... в ... по ... проделанной работы надеемся на пользу и в индустриально регионе. В будущем будем развивать эту ... и ... ... ... решений.
Abstract
Graduation work consists of 56 pages, 8 figures, and from the list of 11-used literary works, 1 table and 1 ... formal grammar, natural ... formal ... ... ... of study: To analyze the grammar to analyze both known and unknown ... algorithms - КС.
Objective: To analyze the grammar of the main goal to analyze both known and unknown synthesis algorithms and ... A Study of natural and formal ... ... view their ... ... of the formal grammar and study its ... of the КС language, research and analysis of known and unknown drawings of ... Did the job ... by analysis on ... formal grammar for the ... basis.
The outlook for the future ... of the work on the study: in the future based on the results of the work done and hope for the benefit on the ... region. In the future we will improve this program and research more many useful ... ... ... Табиғи тілдер мен олардың сипаттамалары 7
1.2 Формалды тілдер және олардың ерекшеліктері 9
1.3 Бағдарламалау тілдері (Pascal, Delphi, C, C++, ... ... ... ... ... ... тілдер (неукорачивающие языки) мен олардың ерекшеліктері 19
2.3 Автоматтық грамматика және ... ... КЖ - ... ТІЛДЕР. КЖ - ТІЛДЕРІНЕ ТАЛДАУ ЖАСАУ 32
3.1 КЖ - ... және ... ... КЖ - ... ... ... және ... сызбалары 40
3.3 КЖ - тілдердің бір сыныбын таңдау алгоритмі 44
ҚОРЫТЫНДЫ 49
ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР 50
A ҚОСЫМШАСЫ 51
КІРІСПЕ
Алгоритмдер мен деректер құрылымын сипаттауға мүмкіндік беретін кез-келген белгілеулер ... ... ... деп ... ... ... міндетіміз-барлық программалау тілдеріне ортақ болып келетін негізгі тілдік концепцияларды қарастыру және оларды кең тараған программалау ... ... ... иллюстрациялау болып табылады.
Қазіргі таңда бірнеше программалау тілдері құрылып, пайдаланылып келеді. ... ... ... ... бір ... ... ғана пайдаланады. Программистердің басым көпшілігі әдетте қандайда бір программалау тілі қолданылатын ... ... ... ... . Олай болса программистке бірнеше тілді оқып үйренудің қаншалықты пайдалы екеніне тоқталайық. Шындығында, бірнеше ... оқып ... яғни тек қана ... ... ғана ... ондағы программаларды жазу концепцияларын және оның қолданылуына бұл ... ... әсер ... ... программистке мынадай мүмкіндіктер жасайды:
1.Ол әлде қайда тиімдірек алгоритм құра алады;
2.Әдетте қолданылатын программалау тілін едәуір тиімді пайдаланатын ... ... ... ... ... бір ... жобаны шешу үшін анағұрлым тиімді программалау тілін таңдай алады.
5.Жаңа тілдерді ... ... ... ... жазу ... жеңіл іске асады.
Программалау тілін меңгеру дегеніміз оның мүмкіндіктерімен ғана танысу емес. Шын ... ... ... ... ұқсастығы алдамшы елес сияқты болып келеді. Олар тек сырт ... ғана ... ... ... ... барысында олардың бағалануы түрліше болып шығуы мүмкін. Мысалы, қарапайым қосу амалының өзі ... ... ең ... амал ... ... бірақ С++, COBOL не Smalltalk тілдеріндегі оның бағалануы түрліше болып келеді. 50-ші жылдарда алғаш жоғарғы деңгейлі ... ... ... ... ... және ... әдістері әрқашан дамып келеді.
50-ші жылдарда Fortran Lіps тілдерінің алғашқы нұсқалары жарық көрді. 70-жылдарда Ada, C, Pascal, Prolog, ... ... 80-ші ... - C++, ML, ... ал 90-шы ... Java ... тілі, сондай-ақ программалау жүйелері - Delphі, Vіsual Basіc, C++ Buіlder т.с.с. дүниеге келді.
1 ФОРМАЛДЫ ТІЛДЕР
1.1 Табиғи тілдер мен ... ... тіл - ... ... үшін ... ... емес ... айырмашылығы) және қолдан жасалынбаған (жасанды тілден айырмашылығы) тіл.
Табиғи ... ... мен ... ... пайдалану тәжірибесімен анықталынады және әрқашан формалды ретінде тіркеле бермейді.
Тілдің негізгі қызметі - пікірді құрастыру, ... ... ... ... ... қарым-қатынасы кеңістігін ұйымдастыратын кейбір симметриялық формаларды білдіретін ұғымдарды ұйымдастыру:
* коммуникативтік:
* констациялайтын (дерек жайлы нейтралды хабарлама үшін);
* сұрау ... ... ... ... (іс - ... түрткі болу үшін);
* экспрессивтік (айтушының көңіл-күйі мен эмоциясын білдіру үшін);
* байланыс орнататын (әңгімелесушілер арасында байланыс орнату және оны қолдау ... ... ... ... ... ... ... (эстетикалық ықпал ету үшін);
* адамдардың белгілі бір тобына жату көрсеткіші қызметі (нәсіл, халық, кәсіп);
* ақпараттық;
* танымдық.
Қазіргі кезде жүйелілік тілдің маңызды ... ... ... ... ... ... мазмұны мән универсумы мен дыбысталу универсумы арасындағы сәйкестікті орнатуда ... ... тілі ... ... ... көзқарастар жоспарының табиғаты негіздемесі бойынша есту белгісінің жүйесіне жатса, жазбаша түрде көру жүйесіне жатады.
Табиғи тіл генезис типі бойынша ... ... ... ... ол ... ... ... де, жасанды белгілер жүйесіне де қарама-қайшы қойылады. Белгілер жүйесі ретінде адамнің тілі үшін табиғи және жасанды белгілер жүйесінің сипаттары ... тіл ... ... ... ... ... ол әр ... элементтерден - фонем, морфем, сөз, сөйлемдерден тұрады, олардың арасында қарым-қатынас күрделі әрі көпжақты келеді.
Табиғи тілдің құрылымдық күрделігіне ... ... ... ... жүйесінің ішіндегі ең күрделісі деп атайды.
Құрылымдық негіздемесі бойынша детерминделген және ықтимал семиотикалық жүйелерді ажыратады. Табиғи тіл ... ... ... ... емес ... жүйеге жатады және ықтимал сипатқа ие.
Семиотикалық жүйелер динамикалық, жылжымалы және тұрақты, жылжымайтын деп ... ... ... ... бір ... ... ... жағдайын өзгертіп отырады, ал тұрақты жүйеде элементтердің жағдайы өзгермей, тұрақты қалады. ... ... ... ... ... ... онда тұрақты белгілер де көрініс табады.
Белгілер жүйесінің ... ... тағы бірі ... олардың толықтылығы табылады. Толық жүйені берілген жиынтықтың элементтерінен тұратын белгілі бір ұзындықтың теориялық тұрғыдан мүмкін болатын барлық комбинациясын ... ... бар жүйе ... анықтауға болады. Соған сәйкес толық емес жүйені белгілерді білдіру үшін берілген элементтердің мүмкін болатын комбинацияларының барлығы пайдаланылмайтын ... ... бір ... ие жүйе ... ... болады. Табиғи тіл артықтықтың жоғары деңгейіне ие ... емес жүйе ... ... ... ... ... арасындағы айырмашылық оларды ашық және жабық жүйелер деп жіктеуге негіз болып табылады. Ашық жүйелер өздерінің қызмет ету ... ... жаңа ... қоса ... және ... ... ... неғұрлым жоғары бейімделушілігімен сипаттамалады. Өзгеру қабілеті адам ... де ... тіл өте ... оның көмегімен сөйлесу қызметі жүзеге асырылады, яғни мәтіндердің туындауы мен оны түсіну. Кез келген мәтін материалдық емес мағынаны ... ... ... болып табылады. Мағына адам санасында туындайды, алайда ... ... қол ... бола ... ... ... ... кіру тәсілі жоқ, себебі олар материалды емес, яғни біздің ешқандай сезім мүшеміз арқылы қабылдана алмайды. Тіл ... ... ... ... ... ... ие ... айнала отырып ойлар қабылдауға қол жетімді болады және оны басқа адам түсіне алады. Осылайша, тіл - бұл ... емес ... ... ... ... ... символдар арқылы немесе белгілер арқылы құралы, сонымен қатар осы субстанция ... ... ... ... тілдің мәтіндері үшін негізгі субстанция болып дыбыстық табылады: бұл есту мүшелері арқылы қабылданатын ауаның тербелісі; графикалық субстанция (көру арқылы қабылданатын ... ... ... болып табылады. Дыбыстық субстанцияның ауысуының әр түрлі жүйелері (графика немесе жазбаша) адам мәдениетінде маңызды рөл атқарады, алайда табиғи тілдердің ... ... ... және ... Кез ... ... сызықтық: ол уақыт бойынша туындайды, кейбір элементтер ерте, келесісі - ... Ой ... ... ... ... ... да ... мәтінге ауысу күрделі үрдіс болып табылады және ойлау үрдісіне ықпал етуі мүмкін.
Хабарламаларды және адамның ... ... екі ... ... ... ... сөйлеу және түсіну, басқаша айтқанда мәтіннің туындауы мен қабылдануы. Тілді толыққанды меңгеру сөйлеу қызметінің осы екі түрлерін сәтті орындау қабілетін ... ... ... ... тасушының белсенді компетенциясы деп аталса, басқа біреудің құрастырған мәтіндерін түсіну қабілетін тасушының пассивті ... деп ... ... ... ... ерекшеліктері олардың болмысынан көрінеді. Табиғи тілдерді зерттеуге формалды тәсілді қиындататын негізгі ерекшеліктер төменде суреттелінген.
- синтаксистің семантикаға ... ... ... ... аяқталуы осы сөздердің қандай да бір объектіге қатысты, жанды ... ... ... ... ... ... ... үшін екі ұқсас сөйлемді қарастырайық.
(Нені?).
(Кімді?).
- Семантикалық және ... ... ... ... ... сөздердің әр түрлі мағынаға ие болуынан туындайды. Мысалы, сөйлемі контекске байланысты әр түрлі мағынаға ие бола ... ... ... ... ... ... деңгейде қатаң болмауынан туындайды. сөйлемі әр түрлі ... ... Егер ... ... ... ... деп ... онда осы сөйлемді деген сөйлеммен ауыстыруға болады. алайда бұл ... ... ... да ... .
- ... ұсыныстардың пайда болу мүмкіндігі. Парадоксальды ұсыныстар оларды шынайыға да, жалғанға да ... ... ... ұсынстардың мысалы ретінде мына сөйлемді айтуға болады: .
- мағынаның жағдайға тәуелдігі;
- тілдің уақытқа байланысты өзгерісі;
- көптеген шектеулері бар ... ... ... Формалды тілдер және олардың ерекшеліктері
Көптеген жасанды тілдер формалды сөйлемдерді құрастыруда пайдаланылады, яғни мағынаға, ережеге тәуелді емес ... ... ... формалды деп аталады. Формалды тілдер синтаксисті сөйлемді құрастыруға формалды тәсілді қамтамасыз етуі керек. ... да ... ... ... ... ... ... ережелердің мағынаға тәуелсіздігі;
- парадокстардың пайда болу мүмкін еместігі;
- синтаксистік ережелердің қатаңдығы мен ... ... ... ... ... ... ... табиғи тілдер секілді уақыт бойынша өзгеруі мүмкін. ... ... ... ... бұл ... біртіндеп емес, тілдің жаңа версияларының пайда болуымен көрінеді. Сонымен қатар бір тілдің әр түрлі версияларын әр ... ... деп ... болады.
Формалды тілдің төменгі синтаксистік бірлігі болып символ табылады. Символ (әріп) - бұл ... ... ... Тіл ... ... ... құрайды. Алфавиттің мысалдары:
Орыс алфавиті - {А, а, Б, б, В, в, ..., Я, я }.
Латын ... - {A, a, b, b, C, c, ..., Z, z ... ... - { 0, 1, 2, . . . , 9 }.
Тілдің символдары қатарға бірігеді. ... - бұл ... ... кезектілігі. Қатардың мысалдары:
Орыс алфавитіндегі қатарлар - , , .
Латын алфавитіндегі қатарлар - "BEGIN" , "THEN" , "END".
Екілік (двоичный) ... ... - "0", "1", "00", "10", ... ... саны ... ұзындығы деп аталады. а1а2а3 . . . аn ... ... n ... ие. Егер ... ... ... тең ... онда қатар бос деп аталады. Бос қатар λ символымен белгіленеді. λ символының алфавит символы ... атап өту ... ... барлық қатарлар жиынтығы А алфавитімен тұйықталу деп аталады және А* символымен белгіленеді.
А* = А0 U А1 U А2 U . . . U Аn ... ... ... А0 Euro{λ} - бос ... - n ... ... бос емес қатарлардың жиынтығы келесідей анықталады:
А+ = А* \ {λ} ... ... ... ... А* ... еркін жиынтығын көрсетеді. А* жиынтығы анықтамасы бойынша шексіз болғандықтан, онда тіл де жалпы жағдайда ... ... ... да ... ... - ... яғни барлық мүмкін болатын қатарларды атап шығу арқылы ... ... ... Мысалы, орыс тілінің барлық дұрыс сөйлемдерін атап шығу мүмкін ... ... ... үшін ... ... ... жасау ережелерін қысқа формада суреттейтін арнайы жүйе керек. ... ... ... ... деп ... ... грамматиканың көмегімен құрылған тіл формалды тіл деп аталады. Формалды тілді қоса алғандағы тілдің қатарлары ... бір ... ие. ... ... мағынасы кейбір қымбат емес қосымша ақпараттардың көмегімен анықталынады.
Формалды грамматиканың типтері
Формалды грамматикалар бір-бірінен тұжырым ережелер типімен ерекшеленеді. Формалды грамматикалардың ... ... типі ... ... ... лингвисті Ноам Хомский енгізген болатын. Хомский формалды грамматиканы төрт типке бөлді.
0 типтегі формалды грамматика (шектелмеген грамматика немесе ... ... ... ... түрді айырбастауда қолданылады:
α--> β, (3)
Бұл жерде α және β - еркін түрдің тізбектері.
1 ... ... ... ... ... ... (контексті тәуелді грамматика) келесі түрді айырбастауда пайдаланылады:
  
Мұнда, A - нетерминалды символ;
, , - еркін түрдің тізбектері, бұл жерде  ... бос емес ...   (N U ...  - ережелер контексті.
2 типті формалды грамматика немесе контекстісіз грамматика (контексті еркін грамматика) келесі түрде пайдаланылады:
A  , (5)
Мұнда, α - ... бос емес ... яғни   (N U T)+ .
3 ... ... ... ... ... грамматика келесі түрде пайдаланады:
A  a B немесе A  a, (6)
Мұнда, А және В - ... ... а - ... ... тілдер теориясында барлық тұрақты грамматикалар контекстісіз, барлық контекстісі ... - ... ... ... - ... екені дәлелденген.
Тұрақты грамматиканың мысалы: G = {N, T, P, S).
N ={S};
T = {a, b}
P: S  a; : S  b; S  aS; S  ... ... ... a және b ... қатарлары туындайды. Қатарлардың туындау кезектілігін келесі сызба бойынша түсіндіруге болады:
Қолданылатын тұжырым ережесі ... ...  aS aS
S  aS ...  b ... ... ... aab қатары табылады.
Контекстісіз грамматиканың мысалы: G = {N, T, P, ... ={S};
T = {a, ... S  aSb; S  ... ... көмегімен anbn түрдегі қатар туындайды.
a3b3 қатар тұжырымының ... ... ... ... ...  aSb ...  aSb aaSbb
S  ab. ... ... ... ... ... = {N, T, P, ... ={S};
T = { IF, THEN, ELSE, U, ... S  B;
S  IF U THEN S;
S  IF U THEN S ELSE ... ... ... ... ... әр ... шартты операторларын қалыптастыруға мүмкіндік береді. Мысалы, IF  THEN IF  THEN B ELSE B ... ... ... ... ...
Қолданылатын тұжырым ережесі Қатар мазмұны
S
S  IF  THEN S IF  U THEN S
S  IF  THEN S ELSE S IF  THEN IF  THEN S ELSE S
S  B IF  THEN IF  THEN B ELSE S
S  B IF  THEN IF  THEN B ELSE ... ... да ... ... ... ... мазмұны
S
S  IF  U THEN S ELSE S IF  THEN S ELSE S
S  IF  U THEN S IF  THEN IF  THEN S ELSE S
S  B IF  THEN IF  THEN B ELSE S
S  B IF  THEN IF  THEN B ELSE ... ... мен ... ... тіл - бұл ... алфавиттің соңғы сөздерінің (қатар, тізбек) жиынтығы. Тілді түсіну көбінесе автоматтар теориясында, есептеу теориясында және алгоритмдер теориясында қолданылады. Осы ... ... ... теория формалды тілдер теориясы деп аталады.
Модельдер теориясында тіл ... ... ... ... ... келеді. Тіл көптеген символдар, қызметтер мен қарым-қатынастардан, сонымен қатар айнымалылар жиынтығынан тұрады. Осы жиынтықтың әрбіреуі ... ... ... Тілден оның универсалды логикалық символдарымен бірге логикалық пікір қалыптастырылады.
Формалды тіл әр түрлі ... ... ... осы ... ... ... қарапайым аударылуы. Бұл тәсіл негізінен соңғы тіл мен қарапайым құрылым тілдерін ... ... ... ... ... ... сөздермен;
* тұрақты пікірден туындаған сөздермен;
* кейбір шекті автомат арқылы танылатын сөздермен;
* БНФ - конструкциядан ... ... ... {a, b} деп ... ал L тіл ... оған ... ... сөздерді қамтыса, онда ababba сөзі L - ға жатады. Бос сөз, яғни нөлдік ұзындық қатары мүмкін болады және ... e, ε ... Λ деп ... ... ... ... b} ... сөздердің жиынтығы
жиынтық, онда n -- теріс емес сан, ал a - ның n - рет ... ... ... тіліндегі синтаксистік дұрыс бағдарламалардың жиынтығы
Операциялары
Кейбір операциялар мәліметтерден жаңа ... ... үшін ... ... ... және кейбір жалпы алфавитпен анықталған тілдер болсын.
* конкатенация ... ... ... барлық сөздерді қамтиды, онда - бұл сөзі, ал - сөзі.
қиылысуы және - дегі ... ... ... ... - дегі сөздерді қамтиды.
тілін толықтыру алфавиттегі барлық сөздерді қамтиды.
арақатынасы - де сөзі ... - де ... -ның ... ... ... ... формасында жазыла алатын барлық сөздерді қамтиды, онда - де ... және . Бұл бос ... де ... ... шығармау керек, себебі шарт бойынша мүмкін болады.
айналымы -ге айналған сөздерді қамтиды.
және -нің араласуы формасында жазылған барлық ... ... онда және ... байланысы -де бар сөздер, ал болып -де болатын ... ... ... ... (Pascal, Delphi, C, C++, ... тілі - бұл компьютерлік бағдарламаларды жазуға арналған формалды белгілер жүйесі. Бағдарламалау тілі бағдарламаның сыртқы бейнесі мен компьютердің атқара ... іс - ... ... ... ... және семантикалық ережелер жиынтығын білдіреді.
Алғашқы бағдарлама жасайтын машиналарды құрғаннан бастап ... екі ... ... аса бағдарламалау тілдерін (абстрактілі және стандарттық емес тілдерді қосқанда) ойлап тапты. Жыл сайын олардың саны арта ... ... ... тек оны ... аз ғана ... ... алады, басқалары миллиондаған адамдарға танымал. Кәсіби бағдарламашылар (программист) кей кездері өздерінің жұмыстарында бағдарламалау тілдерінің оннан аса ... ... ... жасаушылар бағдарламалау тілдері түсінігін әр түрлі түсіндіреді. Көптеген жасаушылар мойындаған кең таралған ... ... ... ... тілі компьютерге сол немесе басқа есептеу үрдісін жасау және жекелеген құрылғыларды басқаруды ұйымдастыру нұсқаулықтарын беру үшін пайдаланылатын компьютер ... ... ... бағдарламалау тілі табиғи тілден оның командалар мен мәліметтерді адамнан компьютерге беруімен ажыратылады, ал ... тіл ... ... ... - ... орнату үшін пайдаланылады. анықтамасын қорытындылауға болады: бағдарламалау тілі - бұл командалар, бұйрықтар, іс - әрекет ... ... ... ... беру ... ал адам тілі сонымен қатар ақпараттар алмасуы үшін қызмет етеді.
Орындалуы: бағдарламалау тілі мәліметтер құрылымын анықтау мен манипуляциялау және есептеу үрдісін ... үшін ... ... ... ... Basic -- мектеп оқушыларының білетін жалғыз нәрсесі. Сонымен қатар Mobile Basic телефонда бағдарламалау үшін арналған. Бұл ... ... ... ... -- ... дамушының өзін-өзі жетілдіру үшін қажет. Онда drupal, joomla, wordpress және mediawiki қоса ... ... ... cms ... ... -- бұл ... ... оқыту үшін таптырмайтын тіл.
Pascal -- басқа қарапайым тілдер жайлы ... жас ... ... ... -- 7 версиясы
C# -- Visual Basic - тің ... ... Java, С++ және Delphi - ді ... талпыныстары.
1С -- win - 1251 - ге ауыстырылған Кобол.
Java -- оны ... ... ... Бұл өте танымал, соның ішінде Линусу Торвальдсқа да. Тышқанмен бағдарламалау үшін IDE бар. Нуфф саид.
Си (бағдарламалау тілі)
Си -- ... ... ... ... Оны 1970 ... ... Bell Labs қызметкерлері Кен Томпсон мен Деннис Ритчи жасады. Си UNIX операциялық жүйесінде пайдалану үшін жасалынған ... ... бері ол ... да көптеген операциялық жүйеге ауыстырылып, өте көп қолданылатын бағдарламалау тілдерінің біріне айналды. Си - ді оның ... үшін ... Ол ... ... қамтамасыз етуді құру үшін танымал тіл болып табылады. Оны көбінесе қолданбалы бағдарламаларды ... үшін де ... Си жаңа ... ... ... ... ... да бағдарламалауды оқытуда белсенді пайдаланылады. Си тілінің синтаксисі басқа да көптеген тілдер үшін ... ... тілі үшін ... ... ағынын басқарудың конструкциясының стандартты жиынтығы, мәліметтер құрылымы мен операциялардың кең жиынтығы тән.
Ерекшеліктері.
Си бағдарламалау тілі минимализммен ерекшеленеді. Тілдің авторлары ондағы ... ... ... көмегімен оңай компиляциялануын қалады. Себебі әрбір бағдарламаның қарапайым құраушысына компиляциядан кейін машиналық команданың аз ғана саны ... ... ал ... ... ... ... ... бойынша кітапхананы әрекетке қоспады. Біржақты компилятор артқа қайтпай, бағдарламаны компиляциялайды. Сондықтан да қызметтер мен ... ... ... ... ... ... ... Си - ге кодты абстракцияның төменгі деңгейінде оңай ... ... кей ... Си - ді ... деп те ... Си оның нақты құрылғылармен жақын етене жұмыс жасауын ескере отырып, ... орта ... ... тіпті төменгі деңгейлі тіл деп те аталады. Алайда қатаң жіктелімде ол жоғаы деңгейлі болып ... -- ... ... ... типті бағдарламалау тілі. Сонымен қатар процедуралық бағдарламалау, объектіге бағытталған бағдарламалау, жинақталған бағдарламалау сияқты бағдарламалау парадигмаларын қолдайды, модульділікті, бөлінген ... ... ... мәліметтер абстракциясын, объектілер типін хабарлауды, виртуалды қызметтерді ... ... ... ... ... ... контейнерлер мен алгоритмдерді қамтиды. C++ жоғары деңгейлі және ... ... ... де ... ... Оны С ... салыстырғанда онда объектіге бағдарлануға және жинақталған бағдарламалауға көп назар ... ... С ... ... ... ... ++ унарлық операторы айнымалының инкрементін білдіреді.
Өте танымал ... ... бірі бола ... С++ бағдарламалық қамсыздандыруда өте кең қолданылады. Оны пайдалану облысы операциялық жүйелерді құру, әр ... ... ... ... ... жоғары өндіруші серверлерді, сонымен қатар ойындарды жасауды қамтиды. С++ тілінің тегін, ақылы сияқты ... ... ... бар және әр ... ... ... ... x86 платформасында бұл GCC, Visual C++, Intel C++ Compiler, Embarcadero (Borland) C++ Builder және басқалары. C++ басқа да бағдарламалау тілдеріне де көп ... ... ... ... Java мен C# ... ықпалы ерекше.
2 ФОРМАЛДЫ ГРАММАТИКАЛАР
2.1 Грамматиканың жіктелімі
Хомский бойынша грамматикалар мен ... ... ... ... ... олардың тұжырым ережелерінің түрлері бойынша жіктелінеді:
Тип 0: Егер тұжырым ережесіне ешқандай шектеулер қойылмаса, G = (VT, VN, P, S) грамматикасын тип 0 ... деп ... ... 1: Р ... әрбіреуі: α --> β , бұл жерде α ∈ (VT ∪ VN)+, β ∈ (VT ∪ VN)+ мен | α | β , бұл ... α = ξ1 А ξ2 ; β =ξ1 γ ξ2; А ∈ VN; γ ∈ (VT ∪ VN)+; ξ1 ξ2 ∈ (VT ∪ VN)* , онда G = (VT, VN, P, S) ... ... ... деп ... (К3).
Тип 1 грамматиканы қысқартылмайтын немесе контексті тәуелді деп анықтауға болады. бұл сыныптың грамматикалары туындататын тілдердің ... ... ... әсер ... себебі қысқартылмайтын граммматикалар туындататын тілдер жиынтығы контексті тәуелді грамматикасы тудыратын тілдер жиынтығымен сәйкес келетіні дәлелденген.
Тип 2: Р ... ... А --> β , бұл ... А ∈ VN, β ∈ (VT ∪ VN)+ ... болса, онда G = (VT, VN, P, S) контексті еркін деп аталады.
Р ережесінің ... : А --> β , бұл ... А ∈ VN, β ∈ (VT ∪ VN)* ... ... онда G = (VT, VN, P, S) ... ... ... деп аталады.
Тип 2 грамматиканы контексті еркін немесе қысқартылған контексті еркін деп анықтауға болады. Таңдау мүмкіндігі ... ... ... ... ... үшін эквивалентті контексті еркін грамматика болуымен байланысты.
Тип 3: Р ережесінің әрбіреуі: А --> tВ ... А --> t, бұл ... А ∈ VN, В ∈ VN, t ∈ VT ... ... онда G = (VT, VN, P, S) оң жақ сызықтық деп аталады.
Р ережесінің әрбіреуі: А --> Вt ... А --> t, бұл ... А ∈ VN, В ∈ VN, t ∈ VT ... ... онда G = (VT, VN, P, S) сол жақ ... деп ... 3 грамматиканы (тұрақты, Р - грамматика) оң жақ сызықтық немесе сол жақ сызықтық ретінде анықтауға болады. ... ... бұл ... ... ... ... жиынтығына әсер етпейді, себебі оң сызықтық грамматикамен туындайтын тілдер жиынтығы сол жақ грамматикамен туындайтын ... ... ... келетіні дәлелденген.
Егер k типті грамматикамен суреттеуге болатын болса, онда L(G) тілі k типті тіл болып табылады. Егер тіл k ... ... ... онда бұл сол ... ... k' (k'>k) типті грамматиканың жоқтығын білдірмейді. Сондықтан да k тілі жайлы айтқанда әдетте k номерінің максималды мүмкін санын ... мен ... ... ... ... тек қана Р ... ... көрсетілсе, онда үлкен латын әріптері терминалды емес символдарды білдіреді деп санаймыз, S - ... ... ал ... ... ... ... грамматика болады.
- Тіл типі 0: L = {a2 bn2-1 | n >= 1}
P: S --> aaCFD
F-->AFB|AB
AB --> ... ... --> D
Cb --> ... ... -->λ
- Тіл типі 1: L = {бірдей 0 мен 1 сандары бар 0 мен 1 ... S-->ASB |AB
AB --> BA
A --> 0
B --> 1
- Тіл типі 2: L = {(ac)n (cb)n | n > ... ...
Q --> ... Тіл типі 3: L = {ω | ω ∈ {a,b}+, ... бірге тұрған a жоқ жерде}
P: S --> A⊥| B⊥
A --> a | Ba ... ... ... типі ... ... күрделілігі кіру тізбегін танушы қабылдай алатын тілдің типімен тікелей байланысты. Жоғарыда аталынған тілдің төрт ... ... үшін ... ... бір ... бар, ... ... алгоритм жұмысының күрделігі бар өзінің танушыларының типі ... ... ... ... бар ... (тип 0) үшін ... сыртқы есі бар детерминделмеген автомат қажет. Сондықтан да осы ... ... үшін ... уақытта шектеулі есептеуіш ресурстарда танушы жұмысты аяқтайды және кіру тізбегі берілген ... ... ... жатпайтыны туралы шешім қабылдайтынына кепілдік беруге болмайды. ... ... ... (тип 1) үшін ... сызықтық шектеулі сыртқы есі бар екі жақты детерминделмеген автоматтар болып табылады. Мұндай автоматтың жұмысының алгоритмі жалпы жағдайда экспоненциалды күрделілікке ие - ... кіру ... тану үшін ... ... саны осы тізбектің ұзындығына экспоненциалды тәуелді. Соған сәйкес, берілген алгоритм бойынша кіру тізбегін талдауға қажет ... та кіру ... ... ... ... осындай алгоритмі жүзеге асырылуы мүмкін - кіру тізбегінің ұзындығын біле отырып, әрқашан да осы тілге тізбектің жатуы ... ... ... уақытта қабылданатыны және қандай есептеуіш ресурстары қажет екенін ... ... ... ... ... ... ... экспоненциалды тәуелділігі танушыларды контексті тәуелді тілдер үшін пайдалануын шектейді. Мұндай ... ... ... мен ... ... ... мәтінді талдау үшін уақыт шектеулері аса маңызды емес жағдайда талдау үшін пайдаланылады (себебі табиғи тілдер контексті тәуелді тілдерге қарағанда күрделірек, ... ... ... ... ... ... керек).
Компиляторларда контексті тәуелді танушылар пайдаланылмайды, себебі компилятордың жұмыс жасау жылдамдығы маңызды болып табылады, ал ... ... ... ... ... ... тілдер секілді қарапайымдырақ тілдер шегінде орындауға болады.
Контексті еркін ... (тип 2) ... ... ... ... есі бар ... ... автоматтар болып табылады. Осындай автоматтың жұмысының алгоритмін қарапайым жүзеге асыру барысында ол экспоненуиалды жылдамдыққа ие, алайда алгоритмнің кейбір ... ... кіру ... ... қажет уақыттың осы тізбектің ұзындығына полимиалды тәуелділігіне қол жеткізуге ... ... ... ... еркін тілдер үшін танушылардың колимиалды күрделігі туралы айтуға болады.
Барлық контексті еркін тілдердің арасында анықталған контексті еркін тілдер сыныбын ... ... ... ... танушылары айдағыш сыртқы есі бар детерминделген автоматтар болып табылады. Бұл тілдер бір мағыналық қасиетке ие, кез келген анықталған ... ... ... үшін ... да бір ... ... тұрғызуға болатыны дәлелденген. Бұдан басқа, осындай тілдер үшін квадраттық күрделігі бар ... ... ... бар. Осы ... бір ... болып табылғандықтан олар компиляторларды тұрғызу үшін жоғары қызығушылық тудырады.
Сонымен қатар анықталған контексті еркін тілдердің ішінде сызықтық танушы тұрғызу мүмкін тілдердің ... бар. ... ... - бұл ... ... ... туралы шешім қабылдау уақыты тізбектің ұзындығына сызықтық тәуелді болатын танушы. Бағдарламалаудың барлық тілдерінің синтаксистік конструкциялары осындай тілдердің сыныбының біреуіне ... ... ... ... ... ғана ... еркін тілдердің танушыларының көмегімен талдауға рұқсат берілетінін естен шығармау ... ... ... ... ... ... ... тиіне толықтай жатқызылмайды, себебі ағымдағы бағдарламаның мәтінінде ... ... ... ... ... ... ... ала сипатталу қажеттілігі. Сондықтан да синтаксистік талдаудан ... ... ... ... бағдарламаның мәтінін қосымша семантикалық талдауды көрсетеді. Бұны ... ... еді, егер ... контексті тәуелді танушының негізінде тұрғызғанда, алайда мұндай компилятордың жұмысының жылдамдығы өте төмен болар еді. Себебі мұндай варианттаға талдаудың ... ... ... ұзындығына экспоненциалды тәуелді болады. контексті еркін тілдер танушылары мен ... ... ... ... ағымдағы бағдарламаны талдау жылдамдығы тұрғысынан тиімдірек болып табылады.
Тұрақты ... (тип 3) үшін ... ... ... ... автоматтар - шекті автоматтар болып табылады. Бұл өте қарапайым танушының типі, әрқашан кіру ... ... ... ... ... сызықтық тәуелділігін көрсетеді. Бұдан басқа шекті автоматтар маңызды ерекшелікке ие: кез келген анықталмаған соңғы автомат әрқашан детерминделгенге өзгертілуі мүмкін. Бұл ... ... ... ... ... бағдарламалық қамсыздандыруды жасауды жеңілдетеді. Танушылардың жұмысының қарапайымдылығы мен жоғары жылдамдығы ... ... ... кең ... ... ... тұрақты тілдер негізінде ағымдағы бағдарламаның мәтінін лексикалық талдау үшін пайдаланылады. ... ... ... ... ... ... ...
Бұдан басқа тұрақты тілдер есептеуіш жүйені бағдарламалық қамсыздандыруды ... ... ... ... ... ... ... көптеген командалық процессорлар жүйелік те, қолданбалы бағдарламалық қамсыздандыруда да қызмет етеді. Тұрақты тілдер үшін танушылардың құрылуын жеңілдетуге мүмкіндік беретін, ... ... ... ... ... ... тілдер (неукорачивающие языки) мен олардың ерекшеліктері
Трансляцияның формалды модельдері бұрын қарастырғандай синтаксистік құрылымдарды оқуға ... ... ... ... ... ... ... және де контексті еркін тілдер теориясына негізделеді.
Программалау тілінің синтаксистік формалды анықталуы әдетте грамматика деп аталады. ... ... ... ... үшін ... ... ... анықтайтын ережелер жиынтығынан тұрады. Формалды грамматика дегеніміз қатаң белгілеулер ... ... ... ... ... ... 2 ... қолданылады.
1) БНФ грамматика немесе контекстілі еркін грамматика
2) Регулярлы грамматика
БНФ грамматика. Ағылшын тіліндегі сөйлем құрылымын қарастыра отырып оның категориялары тілдегі ... ... ... ... ... ... ... толықтауыш //The gіrl (runs) home.
Әрбір категория өз кезегінде ішкі ... ... ... ... ... ... ... артикль және зат есімнен тұрады. Олай болса құрылым ... ... ... |зат ... етістік | толықтауыш
Бұдан басқа сұраулы сөйлемдердің де құрылымы былай жазылады:
Көмекші етістік |бастауыш |баяндауыш
Мысалы: dіd| the gіrl| run home?
Келтірілген сөйлемдерді қандай да бір ... ... ... ... ... Яғни біз сөйлемнің хабарлы не сұраулы болатынын айта аламыз немесе оны былай жазуға болады: ... ... :: = ... - ... ... ... оң ... ішкі категорияға бөліну мүмкіндігін білдіреді. Яғни келтірілген құрылымды былайша оқиды. Сөйлемдердің келесі ... ... ... ... ... жазуды БНФ - Бэкустың нормаль формалары деп атады. Оны 50 - ші жылдардың соңында algol тілінің синтаксистік ... ... ... ... ... ... осы жылдары Ноам Хомский осыған ұқсас грамматикалық форманы ұсынып, оны ... ... ... деп ... Ол ... ... ... келтіру үшін арналды. БНФ және контекстілі еркін грамматика формалары мүмкіндіктері жағынан эквивалентті болып келеді. ... - ... ... ... ... ... синтаксис мәселен талқылау барысында БНФ грамматика және контексті еркін грамматика терминдері өзара бірін - бірі ... ... ... қолданылады.
БНФ грамматиканың синтаксисі. БНФ грамматика программалау тілдерін анықтайтын грамматика ережелерінің аяқталған ... ... Бұл ... ... ... тіл ... ... Синтаксис мәндермен емес тікелей формалармен жұмыс істейтін болғандықтан синтаксис тұрғысынан алып қарағанда программалау тілі ... ... ... ... ... ... жиынтығы. Семантикаға қатысты синтаксисті дұрыс программа ешқандай мәнге ие болмауы мүмкін жағдайда мысалдарға қайта оралсақ, онда келесі сөйлем мына ... ... ... | ... | ... оның ешқандай мағынасы жоқ. Программалық тілінің синтаксисін алып қарайтын болсақ, онда біз ... ... ... да, әрі ... көз жеткіземіз және тілді ұзындығы шектелген символдар байланыстыратын жиынтығы ретінде анықтауға болады. Бұл анықтау негізінде ... ... тіл деп ... ... ... барлық меншіктеу операциялардың жиынтығы.
2) Си-гі барлық программаның жиынтығы.
3) lіsp-тегі ... ... ... a және b ... ... ... жиынтығы.
Мұнда әрбір а элементі кез келген тізбекте b элементінен алдын орналасады. Бұл ... ... ... зер сала ... ... анықталуының жеткіліксіз екеніне көз жеткізуге болады. Бұл ережелер тілде қандай байланыстарды қолдануға болатындығын анықтайды. ... ... ... ... жай ғана тіл. ... ... Бұл ереже элементтерді қарапайым тізбелеу арқылы (0..9) тілді анықтайды. Бұл грамматикалық ереженің оқылуы 0 не 1 және 2 ... 9 цифр ... ... ... ... ... емес символдар деп аталады. Ол осы синтаксисті ... ... ... ... ... ... ... Тілдегі байланыстарды құрастыратын символдар терминді символдар деп аталады. ... :: = ... мына ... ... тұрады. Әсіресе егер жалғыз әріптер түрінде берілсе, осы символдар пайдаланылуы қажет. Мысалы, :: =| мына ереже түрінде Х B|С ... ... ... емес ... ... ... ... соң әлдеқайда байланыстарды сипаттау үшін оларды пайдалануға болады.
Қандай да бір ... алып ... біз ... ... байламдарын генерациялай үшін орын ауыстыру ережелерін тізбекті түрде қолдануымызға болады. ... ... ... ... ... ... барлығын генерациялайды. S=>SS|(S)|( ) кез - келген байламда, ондағы терминалды емес ... ... ... оқу ... ... ауыстыру арқылы түрлендіруге болады. Мысалы: (()()) байламын S - тен ... ... ... ... S - ті S => (S) ... ... ... (S) - тегі S - ті S=>SS ережесі бойынша ауыстырамыз.
3) (SS) - тегі 1 - ші S - ті S => ( ) ... ... ... (( )S) - гі S=> ( ) => (( )( ))
Егер бір байланған ережесінің екіншісінің шығуын => ... ... ... онда ... тұжырымды былайша сипаттаймыз:
S=>(S)=>(SS)=>(( )S)=(( )( ))
Бұл тұжырымның әрбір формасын сентенциалды форма деп атаймыз. Сондықтан біз тілді ... ... тек қана ... символдардан тұратын және грамматикалық бастапқы символдардан шығатын ... ... ... дап ... ... тілінің синтезін анықтау үшін формалды грамматиканың қолданылуы бұл түрді пайдаланатын программалар үшін ғана емес оны ... үшін де аса ... ... ... ... одан ... түріне, пунктуациясына және құрылымына қатысты түрлі құрушы грамматиканы осы тілдегі барлық мүмкін құрылымды анықтау үшін пайдаланылады. Алғашқы программаның осы аталған ... ... ... ... ... ... ... Программистте тілді құрушы да мүмкін жөніндегі түрлі мәселелерді шешу үшін ... ... ... ... ... ... анықтамасы сан қатар тілдің жекелеген нұсқалар арасындағы елеусіз синтаксистік айырмаларды жою үшін де қолданылады. Берілген байламның БНФ - грамматика арқылы ... ... ... ... ... ... ... үшін осы байламды синтаксистік талдауға немесе грамматикалық талдауға грамматикалық ережелерді қолдану керек. Егер ... ... ... онда берілген байланым көрсетілген тілге тиісті деп есептелінеді. Ал егер ... ... ... ... ... ... ... өткізе алмасақ, онда байлам көрсетілген тілге тиісті емес.
БНФ - грамматика өзі анықтайтын ... ... ... ... да бір ... сәйкестендіреді. Атап өтетін жай БНФ - грамматиканың ережесіне қойылатын шектеулерді ескерер болсақ, мұндай құрылымдар бұтақ түрінде кескінделеді. Бұтаның ... ... ... ... ... ... немесе лексемалары анықтайды. Бұтадағы әрбір форманың аралық нүктесі белгілі бір ... ... сай ... Бұл ... одан ... ... ... қай класқа тиісті екенін анықтайды. Бұтаның тамырына тілдің өзін анықтайтын категория сәйкес келеді. Біздің меншіктеу операторы < > .осы ... ... ... ... ... талдау бұтасы тілдің көптеген бөлімдері үшін индуктивті семантикалық құрылымды береді. Мысалы: pascal тілі үшін БНФ - ... кез - ... ... ... ... және ... блоктан тұратын оператордың тізбегі түрінде анықталады.
Оператордың құрылымы өз кезегінде әр ... ... Ал бұл ... ... және ... ... қарапайым амалдан функцияға жасалған сілтемеден және тағы басқадан тұрады. Ең төменгі деңгейдегі ... және ... ... бір ... тұратыны белгілі. Грамматиканы меңгере отырып программист синтаксистік дұрыс программа құратын түрліше құрылымды кейін түсінуге мүмкіндік алады. Аса ескеретін жағдай ... ... ... элементтерінің барлық уақытта ол үшін табиғи деп есептейтін құрылым меншіктеле бермейді. Бір түрдің өзі ... ... ... ... ... ... - грамматикалар өзінің құрылымының қарапайымдылығына қарамай көптеген тілдердің синтаксисін ... үшін ... ... Бұл ... ... ... тек қана ... тәуелділікке байланысты облысын анықтау мүмкін емес. Жалғыз БНФ - грамматика көмегімен мынадай шектеулерді беру мүмкін ... Бір ... бір ... ... екі рет сипатталынуы мүмкін емес;
2 Әрбір идентификатор оның қолданылу облысын ... ... ... ... ... Екі ... етіп ... массивке үш индекс арқылы сілтеме жасауға болмайды.
2.3 Автоматтық грамматика және олардың ерекшеліктері
Формалды грамматикаларда мәліметтердің ... ... ... ... ... немесе инверсті ережесінің біреуін жүзеге асыру болып табылады (өнім немесе айырбастау ережесі). Жалпы жағдайда айырбастау бір алфавиттің қатарын ... ... ... ... ... ... қатарына) көрінеді. Қатарларды алмастыру міндеті бірнеше кезеңде шешілуі мүмкін:
* ағымдағы мәтінді тілдің конструкциясына бөлу;
* ... ... ... тұжырым ережесін таңдау;
* қарапайым конструкцияны таңдап алынған ережеге сәйкес алмастыру.
Әрбір сатыны жүзеге асыру қатаң ... ... ... ... ... ... да ... кезең үшін есі бар автомат құрылуы мүмкін. Бастапқы үш кезең үшін мәтінде тілдің ... бір ... ... мен ... символдарын анықтай алатын автоматтарды құру керек. Мұндай типтегі автоматты ... ... деп ... ... ... ... кіру символдары бойынша анықтауда ол белгілі бір сигнал береді. Үшінші кезең үшін ... ... ...
Осылайша, грамматикалық талдаудың міндетін шешу үшін автоматтардың ... ... ... әдістері жеткілікті. Бірінші кезекте бұл үшін берілген грамматикане ескере отырып оңай құралатын шығу сигналдарын бағдарламалық қалыптастыру автоматтары сай келеді. ... ... ... бола ... ... ... ... сөйлемдерді құрастыру мәселелерін шешу үшін қазіргі кезде компьютерді де пайдаланады.
Тізбекті талдаудың алгоритмі.
Тұрақты грамматика ретінде сол жақ сызықтық ... деп ... ... қатар талданылып отырған тізбек ⊥ арнайы символымен - тізбектің аяғының ... ... деп ... ... жақ ... үшін ... отырған тізбек осы грамматика тудыратын тілге жататынынын анықтайтын алгоритм бар (талдау алгоритмі):
* a1a2...an⊥ ағымдағы тізбектің бірінші символын грамматикада ол үшін A --> a1 ... ... бар А ... ... ... ... a1 терминалын А нетерминалына ;
* сосын келесі қадамдарды көп рет (тізбектің аяқталу белгісін ... ... ... ... ... алынған А нетерминалы мен оның оң жағында орналасқан, грамматикада ол үшін B --> Aai (i = 2, 3,.., n) ... ... бар ai ... тізбегін В нетерминалымен ауыстырамыз;
Бұл әдісімен ... ... ... эквивалентті: алгоритмнің әрбір қадамында жапырақтан діңгегіне дейін көтеріліп, талдау ... ... ... ... алгоритммен жұмыс барысында келесідей жағдайлар мүмкін:
* тізбектің ... ... ... ... ... ... орналасқан; қысудың ең соңғы қадамында S символына қарай болды. Бұл ... ∈ L(G) ... ... ... ... ... барлығы оқылынған; әрбір қадамда жалғыз қажет ... ... ең ... ... S ... кері болды. Бұл ағымдағы тізбек a1a2...an⊥ cent L(G) екенін білдіреді;
* кейбір қадамдарда қажет табылмады, яғни А нетерминалы үшін ... ... ... және оның оң ... ... ai ... ... кезекті терминалы үшін грамматикада B --> Aai ... ... бола ... В ... табылмады. Бұл ағымдағы тізбек a1a2...an⊥ cent L(G) екенін білдіреді;
* алгоритмнің жұмысының кейбір қадамында ... көп ... бар ... ... яғни ... әр ... ... ұқсас оң жақ бөліктері бар тұжырым ережелеріне ие, ... да ... ... ... ... керектігі түсініксіз. Бұл талдаудың детерминделмегенін көрсетеді. Бұл жағдайдың ... алда ... ал ... ... ... ... ... деп есептейік.
Оң жақ бөлігі сәйкес келетін ережені тезірек табу үшін барлық ... ... ... Бұл тек қана ... ... және ... жатқан тізбектің түріне тәуелді емес.
Мұны қатарлары грамматиканың нетерминалды символдарымен, ал бағандары терминалды символдармен белгіленген кесте түрінде ... ... ... ... ... мәні - бұл сәйкес қатарлары мен ... ... ... ... қоюға болатын нетерминалды символ.
Мысалы, G = ({a, b, ⊥}, {S, A, B, C}, P, S) грамматикасы үшін, мұнда:
P: S --> ... --> Ab | Ba
A --> a | Ca
B --> b | ... ... ... бейнеленеді:
Кесте 1 - Терминалды символдармен белгіленген кесте
a
b

C
A
B
S
A
-
C
-
B
C
-
-
S
-
-
-
жұбы үшін болмаған жағдайда ғана доға қойылады.
Мүмкін болатын қысулар жайлы ақпараттарды көбінесе ... ... ... көрсетеді, ол келесідей тұрғызылады:
* грамматиканың нетерминалымен белгіленген графаның шыңы (әрбір нетерминал үшін бір шың) мен ... ... ... ... тағы да бір шың ... Н) ... Бұл шыңдарды жағдайлар деп атаймыз. Н бастапқы ... ... бұл ... ... ережелер бойынша доғамен біріктіреміз:
а) W --> t түрдегі грамматиканың әрбір ережесі үшін H мен W ( H - нен W - ге) ... ... ... ... t ... ... W --> Vt ... әрбір ереже үшін V мен W (V - ден W - ге) ... ... ... t ... ... 1 - G ... үшін ... диаграммасы
Автоматтық грамматика - бұл әрбір ереже А --> аВ және А --> a ... ... А, В - ... ... а - ... ... бірі ... табылатын түрдегі контекстісіз грамматика. (Кейде A --> Λ түріндегі ереже де мүмкін болады, мұнда Λ - бос ... ... ... ... Λ ... бұрынғы қосулар негізінен алынатын тілдер есебінен ғана кеңейеді). Әрбір автоматтық грамматика үшін оған эквивалентті соңғы автоматты құруға болады. Автоматтық ... ... ... сыныбы тұрақты жиынтық сыныбымен сәйкес келеді. Автоматтық тілдер сызықтық тілдер сыныбының өзіндік сыныпшасын ... ... ... тіл {anbn| n = 1, 2, ...} - ... емес. Автоматтық тілдер сыныбы бірігу, қиылысу, көбейту, қою және қиылған итерацияға қатысты тұйық. Автоматтықпен контекстісіз ... ... ... тіл болып табылады.
Сурет 2 - Мультиграф диаграммасы
Автоматтық грамматиканың көрнекі түрде көрінуі үшін бағдарланған мультиграф диаграммасы қолданылады, оның шыңы ... ... ... ... А ... В шыңына а негізгі символы арқылы белгіленген кесінді өтеді, егер ... A --> аВ ... ... ... ... ... диаграммада тағы бір шың бар - қорытындылаушы, егер автоматтық грамматикада A --> a ... ... ... А ... а ... белгіленген кесінді шығады. (A --> Λ ережесі болған жағдайда әрбір А ... ... шың ... ... ... негізінен сөздікте А қосымша символынан грамматиканан шығады және ... ғана ... ... ... ... ... кейбір жолда . Суретте I --> aI, I --> aB, B --> bB, B --> b (I - ... ... K - ... шың), тілді тудыратын {аnbm| n, m = 1, 2, ...} ережесіндегі автоматтық грамматика диаграммасы бейнеленген.
Осы грамматикалардың ерекшеліктері ... ... ... ... ... ... еркін, контексті тәуелді және фазалық құрылым грамматикасы болып табылуында көрінеді. Контексті еркін грамматика контексті тәуелді және фазалық құрылым грамматикасымен бірдей; ... ... ... ... ... ... ... табылады.
Фазалық құрылым грамматикасы грамматиканың төрт сыныбын неғұрлым ... ... ... Оның ... ... ... әрбір ереженің сол жақ бөлігі тек қана тип бойынша нетерминалдардан құрастырылуы табылады: (нетерминалдардың бос емес тізбегі) --> (кез ... ... ... бос, ... және ... тізбегі). Фазалық құрылым грамматикасының абстрактілі мысалы мыналар бола алады: α1 α2α3 --> Т1 Т2 Т3 α4 Т4 α5 α6 Т6; α4 --> α6 Т4; α5 α6 --> α7 α1 Т1... ... ... ... ... ... ... ережелерінің формаларына қосымша шектеулер қояды, соған сәйкес әрбір ереженің сол және оң жақ ... ... Осы ... үшін ереже келесідей болып бейнеленеді: (u1нетерминалдар тізбегі * нетерминал * u2 нетерминалдар тізбегі) --> (u1 ... ... * кез ... бос емес ... * u2 ... ... Бұл ... * символы шартты түрдегі бөлгіш болып табылады, ол тәжірибелік жазбаларда қарастырылмаған.
Контексті тәуелді грамматиканың ерекшелігі ... ... ... бос емес ... ... тек қана u1 және u2 (оң жақ және сол жақ) тізбек контекстінде ... онда ... ... бос болуы мүмкін. Кейбір ережелерде u1 және u2 ... ... де бос ... мүмкін. Осы сыныпты грамматика үшін абстрактілі мысалдар келтірейік: a1-->a1a2; a1 a2-->a1 a3; a3-->T1 T2 a1... ... және ... ... u1 және u2 - бос ... Екінші ережеде u1=a1, u2 - бос тізбек.
Магазин жадты автоматтар(МЖ - автоматтар)
БНФ - ... ... да бір ... ... ... үшін пайдаланамыз және берілген байламның осы тілге тиістілігін анықтайтын абстрактілі машинаны қолдануымызға ... Бұл ... біз ... ... ... ... МЖ автомат деп аталатын және бізге таныс БНФ - грамматикаларға эквивалентті машина құруымызға болады. МЖ - автомат-бұл ША - қа ... ... ... МЖ - ... да ... ... шектелген жиыны бар және оған қоса мұнда отек (магазин) бар. МЖ - автоматта келесі ауысулар (такт) іске асырлады:
a) ... ... мен ... ... ... ... осы екі мәнге тәуелді автоматтың қалыбы (жағдайы) ... ... ноль ... көбірек символдар жазылады;
c) стек бос болған жағдайда байламға қол жетеді деп есептеледі. (Екінші нұсқасы: егер МЖ - ... ... ... жағдайына жетсе,онда қатар қолдануға жарамды (допускается). Бұл екі нұсқа өзара эквивалентті).
Мұндай МЖ - автоматтарының ... ... ... ... ... ... болып табылады. МЖ - автоматтардың көмегімен anbn түріндегі байламдарды (олар ША арқылы оқыла алмайды) оқып-тануға болады. Тек ... а ... ... ... ... соң оларды b символды енгізілуіне қарай жеке-жеке шақыру керек. Егер соңғы b символын енгізген соң стек бос ... ... онда ... ... МЖ - ... ... қолдау табады.
МЖ - автоматтардың көмегімен алынған тілдер колтекетілі еркін тілдерге ... емес ... ... ... символдар байламын сол жақтан шығару процесін қарастырайық. Бұл жағдайда сентенциалды формалы стекте жақтауға болады. МЖ - ... бұл ... іс - ... ... Егер ... ... символы терминалды болса, онда ол
енгізілетін келесі символмен салыстырылады және сәйкес болса (бірдей) стектен ... ... ... ... ... Егер ... ... символы терминалды емес Х символы болса, онда ол ... да бір α ... ... x --> ... α x --> α ... оң ... ... МЖ - автомат қандай да бір контекстілі - ... ... үшін сол ... ... ... Келтірілген құрылым шындығында сәйкес БНФ - грамматикаға эквивалентті анықталмаған МЖ - автомат құрады. Автоматтың жұмысының екінші қадамында x -->α түріндегі ... ... ... ... ... олардың дәл қайсысы таңдалуы тиіс екенін әрдайым анық емес. Анықталмаған МЖ - автомат анықталмаған ША сияқты анықталады. ... ... ... ... үшін оған ... ауысымдар тізбегі бар болуы тиіс.
Анықталған және анықталмаған МЖ - автоматтар өзара қалай байланысатынын осындай ША - ... ... ... ... ... өзгешіліктер кездеседі. Палиндромдардың жиынын, яғни келесі грамматика көмегімен анықталатын оңынан да, солынан да бірдей оқылатын қатарларды қарастырайық:
S ::= OSO 1 S 1 ... МЖ - ... ... біз ... ... ... оқып - тани аламыз:
1) оқу барысында барлық 0 және 1 ... ... 2 ... ... ... жаңа ... ... өтеді;
3) енгізілген әрбір жаңа символды стектегі жоғарғы символмен ... және оны ... ... ... ... ... ... ::= OSO 1 S 1 0 1 (8)
Бұл жағдайда біз ешқашан қатардың ортасы ... ... ... ... ... ... оқу үшін автоматқа оның ортасы белгілі болуы тиіс.
Мысалы, 011010110 палиндромын оқу барысындағы МЖ - автомматың іс - ... ... ... ... мүмкін еді.
Стек Ортасы Стек салыстырылатын қатар
0 11010110
* 1
01 1 010110
011 0 10110
0110 1 0110
01101 0 110
011010 1 10
0110101 1 0
01101011 0
Тек бесінші, яғни автомат палиндромының бірінші бөлігі 0110 ... ... ... ғана ... ... ... Егер ... ортасын анықтауға арналған қадамдардың қандай да бір ... ... ... ... ... алып ... онда бұл байлам осы грамматика тұрғысынан алып қарағанда қолдануға жарамды ... деп ... ... жалпы алгоритмдері. Хомскийдің еңбектері жарияланған соң формалды грамматиканың әрбір түрі ... бір ... ... ... ... анықталды. Бұл автоматтар, яғни қарапайым абстрактілі машиналар, әдетте, ендіру жұмыс лентасынан оның ... ... ... ... ... және ұяшықтарында басқа тізбектің символдары сақталатын шығу лентасын дайындайтын машина ретінде анықталады. Мұнда өкінішке орай қиындықтар туындайды. БНФ - ... ... емес ... ... ... оған ... автомат детерминирленбеген болуы тиіс, яғни ішінен автомат қажеттісін таңдап алуға мүмкіндік беретін ауысымдардың бірнеше нұсқасы ... ... МЖ - ... ... - ... ... туындайтын байламдарды ұйғарымдар стратегиясын қолдана отырып оқи алады. Бірақ программалау және трансляциялау мақсаттары үшін мүмкіндіктері әлдеқайда шектеулі автоматтар (анықталған ... ... олар ... пайдаланбайды.
Регулярлы грамматикаға әрдайым анықталған аппарат сәйкес келгенімен, БНФ - грамматика жағдайында,грамматика біртекті және кейбір басқа талаптар орындалса ғана ... деп ... ... БНФ- ... үшін ... ... ... әдістері жасалды. Ең алғашқы әдістердің бірі - рекурсивті төмендеу әдісі ... ... ... LR - ... ... ... сол жақты контекстілі грамматика) анықталған МЖ - автоматтар оқып - танитын барлық БНФ - грамматикаларды сипаттайтын болды. LR(1) - ... ... ... талдау кезінде дұрыс шешім қабылдау үшін тек бір ғана ... ... ... ... ететін грамматикалардан құралған. SLR (қарапайым LR) - және LALR ( LR) - ... LR - ... ... ішкі ... ... ... және грамматикалық талдаудың әдістеріне алып келеді. Альтернативті әдіс ретінде рекурсивті төмендеу әдісін жинақтап жалпылайтын LL - ... ... ... ... ... ... ... қолданылып жүрген тілдердің көпшілігі SLR, LR -немесе LL - грамматикаларының бірінің негізінде ... ... ... ... сәйкес келетін оқып - танушыны (распознаватель) автоматты түрде құруға ... YACC ... оқып - ... генерациялау құралдарын пайдалануға болады.
Шекті автоматтар(ША)
Кез - келген идентификатор әріптен басталуы тиіс. Осы ... ... ... ... ... немесе әріптерден тұрса, онда олар осы идентификатордың атауына кіреді. Бүтін сан - бұл ... ... ... сөз, мысалы if - әріптердің тізбегі,мысалы i және f. Осыған ұқсас барлық жағдайларда лексемаларды оқып - тану үшін ... ... (ША) ... ... ... ... деп ... қарапайым модель қолданылады. Қай жағдайда екенімізді біле отырып, біз келесі енгізілетін символдың ізделінді лексема бөлігі болуы мүмкіндігін ... ... 3 - саны тақ ... ... байламды оқып -
танитын қарапайым ША
Процесс А ... ... ... басқа жағдайдан шықпайтын ендіру доғасы орналасқан), сонан соң ... ... ... ... ... осы ... ... доға бойымен қозғала отырып А жағдайынан не В жағдайынан өтеді. В жағдайы енгізілген байламдағы бірлердің тақ санына сәкес келеді. ... ... В ... ... ... осы ... ... байлам қойылатын талаптарға сай келеді және осы автоматпен жіберуге ... ... ... А жағдайында тұрғанда мұндай байлам жіберілмейді.
Жалпы, кез - келген ША үшін қандай да бір бастапқы ... ... бір ... ... және ... ... ... анықталған. Автоматты бастапқы жағдайынан соңғы жағдайынан ... ... ... ... кез - ... ... символдар байламы осы автомат арқылы рұқсат етіледі деп айтылады.
Детерминантты емес ША. Автоматтар жөнінде әңгіме қозғалғанда бұған дейін жағдайлар арасындағы ... ... ... және ... ... ... ... Яғни, ША - тың әрбір жағдайы және әрбір ... ... үшін ... бір ... ... бір ғана мүмкін ауысу бар (ол алдынғысымен сәйкес келуі де, келмеуі де мүмкін). Осындай ША - ты детерминантты деп аталады. Егер ... n ... бар ... және ену ... k ... ... онда ауысулар саны nxk - ға тең болады. Кейбір доғалардың (ауысулардың) ... ... ... ... ... біз әрқашан қатенің қосымша жұтылушы шектік емес жағдайларына доғалар қоса аламыз. Детерминантты болмау қиындығы деп бір жағдайдан шығатын ... ... ... ... ... детерминантты автоматта түрліше ауысулар арасында таңдау мүмкіншілігі пайда болады.
Сонымен, ... емес ... ... ... ... ... (граф байламдары);
- бастапқы жағдай (байламдардың бірі);
- шектік жағдайлар жиыны (байламдардың ішкі жиыны);
- ену алфавиті (жағдайлар арасындағы ауысуларды анықтайтын доғаларды маркерлеуге ... ... ... ... байланыстырушы және жағдайлар арасындағы ауысуларды анықтаушы доғалардың елу алфавитінің белгіленген символдарының жиыны.
Мұндай ... емес ... кез - ... ... бірнеше доға шыға алады (немесе бірде - бір доға шықпауы мүмкін), сондай - ақ бір белгіні бірнеше доға ... ... ... ... ... ... ... енгізілген бір символ үшін кейінгі жолдың бірнеше нұсқасы болуы мүмкін. Мұндай жағдайда егер бастапқы байламнан шектік байламдардың кез келгеніне ең ... бір жол бар ... онда ... осы ... сәйкес келетін басқа жолдар шектік жағдайға келтірмесе де, ... ... ... бір ... ... ... ... Бұрын айтылып өткендей, әртектілік - бұл синтаксис мәселесі болып табылады. Мысалы, сөзін қарастырайық. Біз оны екі ... ... ... | are | flying planes( Олар | ... ... | болып табылады)
They | are flying | planes( Олар | самолетпен | ұшады)
Бұл ... ... де ... бар ... ... They( Олар ) ... ... қолданса, екіншісіндегі They самолетпен ұшатын базбіреулерге қатысты ... тұр. Көп ... ... ... емес, грамматиканың қасиеті деп есептеледі. Мысалы, нөлдер мен ... ... ... ... ... G1 ... әректті болып табылады:
G1: S --> SS |0|1 (9)
Кеңейтілген БНФ - нотация. Өзінің қарапайым жинақтылығына және ... ... БНФ - ... ... ... ережелері жөнінде толық ақпарат бере алмайды. Бұның негізгі себебі қандай да бір ... ... ... ... ... және ... ... үшін жалпы синтаксистік құрылымдардың табиғи берлуін бұзатын БНФ - грамматикасы аса қарапайым болып табылады. Мысалы, ... ... ... ... ... үшін БНФ грамматикада, мынадай анағұрлым күрделі рекурсивті ережелер қатарын жазуға тура ... ... БНФ - ... осы ... ... ... ... синтаксистік қасиеттерін анықтаудың табиғи емес тәсілдерін болдырмауға кейбір кеңейтілулерді қарастырамыз.
БНФ - нотацияларды кеңейту үшін келесі қосымша белгілеулерді ... Олар БНФ - ... ... ... ... ... ... сипатталуын қарапайым түрге келтіреді:
Міндетті емес элементті квадрат жақшалар ішінде жазуға ... ... тік ... ... ... ... және қажет болған жағдайда квадрат жақшалар жазылуы мүмкін;
Бір элементтің экземплярлардың еркін тізбегі фигуралық жақша ішінде ... ... ... (*) ... ... қайталанатын,яғни рикурсивті мәтіндерді кескіндеуге мүмкіндік беретін таңба).
Мысалы;айталық жоғарыдағы категориясын келтірілген кеңейтулер арқылы былай жазуға болар еді:
::=[+|-]{}*
::={|}*__
3 КЖ - ГРАММАТИКАЛЫҚ ... КЖ - ... ... ... КЖ - грамматикалар және олардың ерекшеліктері
Тәжірибелік тұрғыдан қарағанда контексті еркін грамматикалар аса ... ... ... ... ... ... ... синтаксистік құрылымының көп бөлігін суреттеу үшін жеткілікті. Контексті грамматикалардың әр түрлі ... үшін ... ... ... ... ... әдістері бар.
G = (VT, VN, P, S) контексті еркін грамматикасындағы S ∈ VN - ден β∈(VT)* тізбегінің тұжырымы сол жақ деп ... егер бұл ... ... ... сентенциалды форма сол жақ нетерминалдың алдыңғы ауыстырғышы болса.
G = (VT, VN, P, S) контексті еркін грамматикасындағы S ∈ VN - ден ... ... ... оң жақ деп ... егер бұл ... ... ... сентенциалды форма оң жақ нетерминалдың алдыңғы ауыстырғышы болса.
Грамматикада бір тізбекте эквивалентті бірнеше тұжырым болуы ... ... ... ... ... ... ... қолданылады, бірақ әр түрлі реттілікті болады
Мысалы, G = ({a,b}, {S,T}, (S-->T|T+S; T--> a|b}, S) ... a+b+a ... үшін ... тұжырымдарды тұрғызуға болады:
* S-->T+S-->T+T+S-->T+T+T-->a+T+T-->a+b+T-->a+b+a
* S-->T+S-->a+S-->a+T+S-->a+b+S-->a+b+T-->a+b+a
* S-->T+S-->T+T+S-->T+T+T-->T+T+a-->T+b+a-->a+b+a
Мұнда (2) - сол жақ тұжырым, (3) - оң жақ ... ал (1) сол жақ ... да, оң жақ ... да ... Алайда осы барлық тұжырымдар жоғарыда айтылғандай эквивалентті болып табылады.
Контексті еркін грамматикалар үшін тұжырым ағашы деп аталатын ыңғайлы ... ... ... болады, оның үстіне барлық эквивалентті тұжырымдар үшін тұжырым ағашы сәйкес келеді.
Анықтама: төмендегі шарттар орындалған жағдайда G = (VT, VN, P, S) ... ... ... ... ... деп ... болады:
* Ағаштың әрбір басы (VN ∪ VT ∪ λ) ... ... ... ... ... ағаштың діңгегі S символымен, ал жапырақтары (VT ∪ λ) символдарымен белгіленген.
* Егер ... басы A ∈ VN ... ал оның ... ... ... ... әрбір ai ∈ (VT ∪ VN) белгіленсе, онда A --> a1a2...an осы грамматикадағы тұжырым ...
* Егер ... басы A ∈ VN ... ал оның ... ... λ ... ... онда A --> λ осы грамматикадағы тұжырым ережесі.
S
T + S
T + S
a
b T
a
Сурет 4 - G грамматикасындағы a+b+a тұжырымына арналған тұжырым ағашының мысалы
Тұжырым ағашын ... ... ... ... ... әдістермен тұрғызуға болады.
Төмен түсетін талдауда тұжырым ағашы түбінен бастап жапырағына қарай қалыптасады; нетерминалды символмен белгіленген ... ... ... ... ... ондағы терминалды символдар ағымдағы тізбектің символдарына жобалануы керек тұжырым ережелерін іздеуге ... ... ... әдісінің мәні мынада жатыр: ағымдағы тізбекті бастапқы S символына бұруға тырысады; әрбір қадамда қандай да бір тұжырым ережесінің оң жақ ... ... ... тізбекшені іздейді; егер мұндай тізбекше табылса, онда ол осы ереженің сол жақ бөлігінің нетерминалымен ауыстырылады.
G ... ... ... бір мағыналы емес деп аталады, егер де екі немесе одан да көп әр ... ... ... ... ... кем ... бір ... тізбегі бар болса. Кері жағдайда грамматика бір мағыналы деп аталады.
Егер грамматика бір мағыналы болса, онда ... кез ... ... ... ... ... ... грамматикадан туындайтын тіл ешқандай да бір мағыналы грамматикадан туындай алмаса, онда ол бір ... емес деп ... ... ... емес ... ... G = ({if, then, else, a, b}, {S}, P, S), мұнда P = {S --> if b then S else S | if b then S | a}. бұл ... 'if b then if b then a else a' ... үшін екі ... ағашын тұрғызуға болады.
Алайда бұл L(G) тілі міндетті түрде бір мағыналы емес болады дегенді білдірмейді. Бір ... емес - бұл ... ... ... ... яғни кейбір бір мағыналы емес грамматика үшін оларға ... ... бар. Егер ... бағдарламалау тілін анықтау үшін қолданылса, онда ол бір мағыналы ... ... ... ... мысалда әр түрлі тұжырым ағаштары else - нің әр түрлі then - ге сәйкес келуін ... Егер else ... ... then - ге ... келу ... және G ... ... онда бір мағыналық еместік жойылады:
S --> if b then S | if b then S' else S | a
S' --> if b then S' else S' | ... ... ... ... бір ... ... ... (яғни оған бір мағыналы грамматика бар ма) мәселе алгоритмдік шешілмейтін ... ... ... бір ... еместікке әкелетін тұжырым ережелерінің кейбір түрлерін көрсетуге болады:
+ A --> AA | α;
+ A --> AαA | ... A --> αA | Aβ | ... A --> αA | αAβA | ... ... мен ... жақ ... ... ал үрдісіндегі тұжырымдар ағашын қарастырайық. Тұжырым үрдісіндегі аралық тізбек w терминалдарының тізбегінен, A сол жақ ... х ... ... ... -А-x-\
--------------------------------------------------------------------------------
/ | \
--------------------------------------------------------------------------------
-w-+-u----
--------------------------------------------------------------------------------
Сурет 5 - Тұжырымдар ағашы
Талдауды одан әрі жалғастыру үшін A:y түріндегі ережелердің біреуі бойынша А нетерминалды ауыстыру ... ... Егер ... ... ... ... үшін ... етіледі, бұл өз кезегінде арнайы тәсілді таңдауын қажет етеді. Грамматика LL(k) қасиетіне ие болады, егер ... ... үшін тек wAx пен u ... ... k ... ... жеткілікті. Алғашқы L (Left, сол) әрпі солдан оңға қарай кіру тізбегін көруге жатады, ... - ... ... сол жақ ... ...
Тізбектің екі жиынтығын анықтайық:
FIRST(x) - х-тен шығатын, k ... ... ... ... ... жиынтығы.
FOLLOW(A) - А соңынан еруі мүмкін, k символына дейін қысқартылған терминалдық тізбектің жиынтығы.
Грамматика LL(k) ... ие ... егер екі ... сол жақ ... болса:
S :: wAx : wzx :: wu ... :: wAx : wtx :: ... ... z=t шығады.
k = 1 жағдайында А үшін ережені таңдауда А нетерминалын және а - u тізбегінің алғашқы ... білу ... ... ... керек, егер а в FIRST(x) кірсе
A:е ережесін таңдау керек, егер а FOLLOW(A) кірсе
LL(к) - ... ... ... ... ... ... LL(2) ...
S : aS | a (11)
LL(1) қасиетіне ие ... ... ... = {a}. Бұл ... k ... ... төмендетуге болады (көбейткішті жақшаның сыртына шығару):
S : aA (12)
A : S | ... ... LL(k) - ... ... Сол жақ рекурсивтік грамматика ешқандай да k үшін LL(k) сыныбына жатпайды. Кейде LL(1) - грамматиканы оған ... LL(1) - ... сол жақ ... мен ... ... ... ... Алайда эквивалентті LL(k) - грамматиканың еркін LL(k) - грамматика үшін болу мәселесінің шешімі ... ... ... бар, LL(k) ... k үшін ... мысалы {0n 10n U 0n 102n| n>=1}.
Мысалы, Арифметикалық формулалар үшін грамматика:
Ф : Т | Ф + Т
Т : М | Т * М
M : ( Ф ) | ... ... ... ... Ф мен Т үшін ... ... сол жақ рекурсияны қамтиды, оны жояйық:
--------------------------------------------------------------------------------
------------------------T-------------T---------------
--------------------------------------------------------------------------------
| | FIRST | FOLLOW ... Ф : Т Ф1 | ( a | ) e ... Ф1 : е | + Т Ф1 | + e | ) e ... Т : М Т1 | ( a | + ) e ... Т1 : е | * М Т1 | * e | + ) e ... M : ( Ф ) | а | ( a | * + ) e ... 6 - Ф мен Т үшін ... ... Ф1 мен Т1 ... ғана ... Ф1 мен Т1 ... үшін ... көп ережелер бар; FIRST(Ф1), FOLLOW(Ф1) пен FIRST(T1), FOLLOW(T1) жиынтықтары қиылыспайды.
Осылайша түрлендірілген грамматика LL(1) болып табылады.
FIRST және FOLLOW жиынтықтарында орналастырылған е ... әр ... ... ие және шиеленіске әкелмейді: е FIRST жиынтығында осы нетерминалдан бос тізбекті ... ... ... үшін ... FOLLOW ... е ... қатарының соңындағы келесі символдың болмауын білдіреді. Тәжірибеде екінші жағдайдағы е - нің рөлін ... ... ... ... - ... LR(0) ... қарапайым грамматикаларын қарастырайық. LR(0) - тілдің қатарын талдауда авантізбекті мүлдем пайдаланбауға болады - жылжу мен қысу ... ... х ... ... ... Себебі талдау үрдісінде ол тек оң жақ шеттен өзгереді, оны айдағыш деп атайды. Грамматикада пайдасыз символдар жоқ деп есептейк және ... ... ... оң жақ бөлігінде кездеспейді - сонда бастапқы символға қысу ... ... ... ... ... ... Барлық LR - талдаудың үрдісіндегі айдағышта пайда ... ... мен ... ... ... ... ... көрейік (басқаша айтқанда, грамматиканың барлық оң тұжырымдарын қарастырайық).
Келесі жиынтықтарды анықтайық: L(A:v) - A:v ережесінің сол контексті - ... ... ... ... ... v ... алдындағы айдағыш жағдайының жиынтығы. L(A:v)-дағы әрбір тізбек v - мен ... Егер ... ... ... құйрығын кесіп тастаса, онда сәтті оң тұжырымдар үрдісіндегі А - ның сол жағында кездесетін тізбек жиынтығы пайда ... Бұл ... L(A) - А ... сол ... деп ... L(A) ... үшін грамматика тұрғызайық. Жаңа грамматиканың терминалдары болып ағымдағы грамматиканың терминалдары мен ... ... жаңа ... ... деп белгілейік, - олардың мағыналары ағымдағы ... ... сол жақ ... ... Егер S ... грамматиканың бастапқы символы болса, онда сол жақ контекст грамматикасы келесі ережені қамтитын болады:
: e - S сол жақ ... бос ... ... ... ... ... мысалы,
A : B C d E
Жаңа грамматикаға ережелер ... : - L(B) L(A) - ны ... : B - L(C) L(A) B - ны ... : B C d - L(E) L(A) B C d - ны ... - ... ... оң жақ ... символдар арасындағы бір рет белгіленген позициясы бар грамматиканың ережесі деп атайық. Мысалы, S:A ; A:aAA ; A:b ... үшін ... LR(0) - ... бар: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (позиция белгілеу символымен көрсетілген).
x тізбегі А:b_c ... ... деп ... егер x=ab ... және а L(A) - ға ... ... ... айтқанда, LR - тұжырым x_... = ab_... :: abc_... :: aA_... :: S_ . ... ... ... ... L(A:b) - A:b_ ... ... тізбектер жиынтығы, L(A) - A:_b жағдайымен келісілген тізбектер, кез ... ... үшін ... - u - мен ... ... ... V қызметі индуктивті екенін көрсетеміз.
Егер V(u) жиынтығына A:b_cd ... ... ... онда A:bc_d жағдайы V(uc)- ға жататын болады. (c - ... ... ... b, d - ... немесе нетерминалдардың кезектілігі (бос болуы мүмкін)). V(uc) - да бос емес b бар A:b_d ... ... ... жоқ. V(uc) - ға сол жақ ... uc ... әрбір С терминалы үшін енді С:_... түріндегі ... ... ғана ... Егер ... ... ... V(uc) жиынтығына жататын болса, онда uc L(C) - ға жатады және V(uc) ... ... С - ... ... үшін C:_... түріндегі жағдайды қамтиды.
V(uc) басқа жағдайды қамтымайтынын көрсету.
V(e) S:_... (S - бастапқы ... ... ... ... қатар A:_... жағдайын қамтиды, егер A нетерминалы жағдайларда V(e) - ға ... ... ... ... ... S:A; A:aAA; A:b грамматикасы үшін V ... ... V(e) = { S:_A; A:_aAA, A:_b }
1 V(A) = { S:A_ }
2 V(a) = { A:a_AA; A:_aAA, A:_b } ... ... V(b) = { A:b_ }
4 V(aA) = { A:aA_A; A:_aAA, A:_b } ... V(aAA) = { A:aAA_ ... біз LR(0) - грамматикаға анықтама бере аламыз. u - бұл LR - талдаудың үрдісіндегі ... ... V(u) - u-мен ... LR(0) жағдайының жиынтығы. Егер V(u) А:x түріндегі (x- терминалдар мен нетерминалдардың кезектілігі) жағдайды қамтыса, онда u L(A:x) - ға ... және х - тың А - ға ... ... ... Егер V(u) A:..._a... (а-терминал) жағдайын қамтыса, онда ... ... Егер бір u ... ... да, қысу да тән ... онда ... - қысу ... жайлы айтады. Егер әр түрлі ережелер бойынша қысулар тән болса, онда жылжу - қысу шиеленістері жайлы ... LR - ... ... айдағыстың барлық жағдайы үшін жылжу - қысу ... қысу - ... ... болмаса, онда грамматика LR(0) деп аталады.
Жоғарыда қарастырылған грамматика LR(0) - ... ... ... Оның V ... 6 әр ... ... ие. 0,2,4 ... тек қана қысу мүмкін болады, ал 3 - жағдайда A:b ережесіндегі қысу, 5 - ... - A:aAA ... ал 1 - S:A, яғни ... ... аяқталуы мүмкін.
LR(k) - грамматикалар
LR(0) талдауда жылжу мен қысудың арасында таңдау жасау үшін тек қана айдағыштың жағдайы пайдаланылады. LR(k) ... ... ... кіру ... (авантізбек деп аталады) қарастырылмаған бөлігінің k - бірінші символдары ескеріледі. Әдісті негіздеу үшін анықтамаға өзгеріс енгізе отырып, ... ... ... ... ... өту ... сол жақ ... авантізбекті де қосамыз. Егер оң жақ тұжырымда wAu : wvu тұжырымы пайдаланылса, онда {wv,FIRSTk(u)} жұбы Lk(A:v) - ға ... ал ... жұбы Lk(A) - қа ... ... Сол жақ ... ... LR(0) жағдайындағы секілді сол жақ тізбек бойынша индукцияның көмегімен есептеуге болады. Жұпты LR(k) - жағдай деп ... ... ... бар грамматиканың ережесі мен ұзындығы k - дан көп емес авантізбек. Авантізбектен ережені вертикалды сызба арқылы ... ... А:b_c|t ... ... деп ... егер LR - ... бар болса: x_yz = ab_yz :: abc_z :: aA_z :: S_, және FIRSTk(z)=t. Vk жағдайының ... ... ... ... ... S:a - тың ... ережелері үшін S:_a|e жағдайларын қамтиды, бұл жерде S - бастапқы символ. Vk(e) - дағы ... А:_Ba|u ... ... ... B:b ереже мен FIRSTk(au) - қа ... х ... үшін Vk(wc) - ға C:_f|x ... қосу ... S:A; A:AaAb|e ... үшін V1 қызметін құрастырайық.
0 V1(e) = { S:_A|e; A:_AaAb|e,a, A:_|e,a }
1 V1(A) = { S:A_|e, ... }
2 V1(Aa) = { ... ... A:_|a,b }
3 V1(AaA) = { ... ... }
4 V1(AaAa) = { ... ... A:_|a,b }
5 V1(AaAb) = { A:AaAb_|e,a }
6 V1(AaAaA) = { A:AaA_b|a,b A:A_aAb|a,b } ... = ... ... { ... }
( ... - екі LR(1) - ... қысқартылған жазбасы:
A:_AaAb|e и A:_AaAb|а )
Жылжу - қысу сұрақтарын бөлу үшін LR(k) - ... ... ... ... u - айдағыштың құрамы, ал х - авантізбек ... A:b ... ... қысу ... ... егер Vk(u) A:b_|x жағдайын қамтитын болса. Қысудың ... болу ... шешу ... ... ... егер ... е - ... болса. A:b_c|t жағдайында (с бос емес) жылжу ... ... егер с ... басталып, х FIRSTk(ct) - қа жататын болса. Формалды емес түрде айтсақ, айдағышқа ереженің оң бөлігіндегі ең сол ... ... ... болады. егер с нетерминалдан басталса (жағдай A:b_Cd|t түрде болады), онда С - ға ... ... ... ... ... ... тек С бос ... тудырмаған жағдайда ғана мүмкін. Мысалы, V(e) = { S:_A|e; A:_AaAb|e,a, A:_|e,a } жағдайында мүмкін болатын жылжулар болмайды, ... А ... ... шығарда бірнеше қадамда A:e ережесін тізбектің сол жақ шетінде орналасқан А ... ... ... етіледі.
Тәжірибеде k>1 шартында LR(k) - грамматикалар пайдаланылмайды. Бұның екі себебі бар: ... ... - LR(k) ... өте ... ... ... себеп - LR(k) - грамматиканы анықтайтын кез келген тіл үшін LR(1) - грамматика болады; бұдан басқа кез келген ... КС - тіл үшін LR(1) - ... ... ... үшін LR(1) - ... саны жоғары. LR(0) қасиеті бар мұндай грамматикалар сирек. Тәжірибеде LR(0) мен LR(1) арасындағы ... ... ... SLR(1) мен LALR(1) деп ... мен LALR(1) ... екі ... ... бір идея жатыр. Грамматиканың каноникалық LR(0) - жағдайының жиынтығын құрастырайық. Егер бұл жиынтық шиеленісті қамтымаса, онда LR(0) - ... ... ... ... бір символдық авантізбекті қарастыра отырып, туындаған шиеленісті шешуге тырысамыз. Басқаша айтқанда, LR(0) - жағдайдың жиынтығымен LR(1) парсерді ... ... ... грамматикаларда (Simple LR(1) - қарапайым LR(1) - грамматикаларда) шиеленістерді шешу үшін FOLLOW(X) жиынтығы - Х - тан ... ... ... ... ... Егер ... A:b_ ... болса, егер тек авантізбек FOLLOW(A) - қа жатса ғана қысу бола алады.
Грамматика бір жағдайдағы A:a_b және B:c_d кез ... екі LR(0) ... үшін ... ... біреуі орындалғанда SLR(1) - грамматика болып табылады:
- b!=e, d!=e (шиеленіс жоқ, жылжу қажет етіледі);
- b=d=e и ... ... - пен ... ( ... ... ... ... жойылуы мүмкін);
- b=e, de и FOLLOW(A) EFF(tFOLLOW(B)) - пен ... ( ... ... ... отырып жойылуы мүмкін).
Арифметикалық формулалар грамматикасы үшін LR(0) - жағдайды құрайық:
S:E; E:E+T|T; T:T*F|F; F:(E)|a.
0 V(e) ={ S:_E; E:_E+T, E:_T, T:_T*F, T:_F, F_a, F:_(E) }
1 V(E) ={ S:E_, E:E_+T }
2 V(T) ={ E:T_, ... V(F) ={ T:F_ }
4 V(a) ={ F:a_ }
5 V(() ={ F:(_E); E:_E+T, E:_T, T:_T*F, T:_F, F_a, F:_(E) }
6 V(E+) ={ E:E+_T; T:_T*F, T:_F, F_a, F:_(E) }
7 V(T*) ={ T:T*_F; F:_a, F:_(E) }
8 V((E) ={ F:(E_), E:E_+T } (T=T; (F=F; (a=a; ... V(E+T)={ E:E+T_, T:T_*F } E+F=F; E+a=a; ... V(T*F)={ T:T*F_ } T*a=a; ... V((E))={ F:(E)_ } ... ... - шиеленістер 1,2,9 жағдайларында туындайды, алайда
1: FOLLOW(S) = {е}, ... = ... ... = {+,),e} ... = {*}
9: FOLLOW(E) = {+,),e} FIRST(*F) = {*},
Соған сәйкес шиеленістер SLR(1) техникасын пайдаланумен шешіледі және грамматика SLR(1) - ... ... ...
3.2 КЖ - ... талдауының анықталған және анықталмаған сызбалары
Анықталған Шекті автоматты жалпы ... ... ... ретінде анықтаймыз және бізге алда қажет болатын кейбір қосымша анықтамалар мен ... ... ... δ (q, a) ... кез ... q, a үшін бірден көп жағдайды қамтыса, автомат детерминделген деп аталынады. Егер δ(q, a) әрқашан бір ... ... онда ... ... анықталынған деп аталынады.
w тізбегі МЖ автоматынан мүмкін болады, егер бізді осы тізбек бойынша автоматтық қорытынды жағдайына әкелетін ... ... ... ... әрбір сөзі танылатын болса, онда тіл соңғы автоматты ... ... ... ... ... - ... диаграммасы.
Анықтама. Егер δ(q, a) жиынтық кез келген q, a үшін ... көп емес ... ... онда ... ... деп ... Егер δ(q, a) әрқашан да бір жағдайды қамтыса, онда автомат толықтай ... деп ... ... ∑ алфавитіндегі w = ai...ak сөзі M = (Q, ∑, δ, q0, F), шекті автоматымен жіберіледі, егер де qi, q2, ..., qn ... qi = qo, qn ∈ F және ∀i∀j :1

Пән: Информатика
Жұмыс түрі: Дипломдық жұмыс
Көлемі: 53 бет
Бұл жұмыстың бағасы: 1 300 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
Xix ғасырдағы салыстырмалы-тарихи тіл біліміне ғалымдардың қосқан үлесі4 бет
Сөз тіркесінің түрлері7 бет
Астық өңдеу машиналары27 бет
Бағыттаушы электрбайланыс жүйелері13 бет
Жеке жол қиылыстарында қатаң бағдарламалық басқару жағдайында инженерлік есептеулерді тәжірибе жүзінде орындау15 бет
Жол қозғалысын ұйымдастыру22 бет
Жылу қазандықтары шығарылымдарын зиянсыздандыру және оларды іске асыру технологияларын негіздеу мен жасау туралы24 бет
Кернеуі 220/35/10 кв-ты қосалқы станциясын жобалау80 бет
Л2х100 типті дайындау элеваторында арпа дәндерін жинағаннан кейінгі өңдеудің технологиялық линиясы32 бет
Мұнаралы жүк көтеру крандары15 бет


Исходниктер
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь