КЖ – грамматикасы үшін талдау анықталған және анықталмаған сұлбасы негізінде синтез алгоритмін талдау
КІРІСПЕ 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 ФОРМАЛДЫ ТІЛДЕР 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.Ол әлде қайда тиімдірек алгоритм құра алады;
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)
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)
Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 57 бет
Таңдаулыға:
Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 57 бет
Таңдаулыға:
ӘЛ-ФАРАБИ АТЫНДАҒЫ ҚАЗАҚ ҰЛТТЫҚ УНИВЕРСИТЕТІ
МЕХАНИКА-МАТЕМАТИКА ФАКУЛЬТЕТІ
АҚПАРАТТЫҚ ЖҮЙЕЛЕР КАФЕДРАСЫ
" КЖ - грамматикасы үшін талдау анықталған және анықталмаған сұлбасы негізінде синтез алгоритмін талдау" тақырыбына жазылған
ДИПЛОМДЫҚ ЖҰМЫС
Орындаған
___________________
(қолы)
Маханов Ш.Б.
Ғылыми жетекші,
т.ғ.д.,профессор
___________________
(қолы)
Дюсембаев А.Е.
Нормобақылаушы
___________________
(қолы)
Жуманов Ж.М.
Қорғауға жіберілді:
Кафедра меңг.қ.а, 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 add-on.
Keywords: formal grammar, natural languages, formal languages, automatic grammar
Object of study: To analyze the grammar to analyze both known and unknown synthesis algorithms - КС.
Objective: To analyze the grammar of the main goal to analyze both known and unknown synthesis algorithms and КС.
Improvements: A Study of natural and formal languages and view their properties. Determination of the formal grammar and study its properties.
Analysis of the КС language, research and analysis of known and unknown drawings of КС.
Results: Did the job performed by analysis on arbitrary formal grammar for the syntactic basis.
The outlook for the future development of the work on the study: in the future based on the results of the work done and hope for the benefit on the industrial region. In the future we will improve this program and research more many useful solutions.
МАЗМҰНЫ
КІРІСПЕ 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 ФОРМАЛДЫ ТІЛДЕР
1.1 Табиғи тілдер мен олардың сипаттамалары
Табиғи тіл - адамдардың қарым-қатынасы үшін пайдаланылатын (формалды емес тілдерден айырмашылығы) және қолдан жасалынбаған (жасанды тілден айырмашылығы) тіл.
Табиғи тілдің сөздігі мен грамматикалық ережелері пайдалану тәжірибесімен анықталынады және әрқашан формалды ретінде тіркеле бермейді.
Тілдің негізгі қызметі - пікірді құрастыру, әрекетті реакцияның мазмұнын анықтау мүмкіндігі, коммуникаторлар қарым-қатынасы кеңістігін ұйымдастыратын кейбір симметриялық формаларды білдіретін ұғымдарды ұйымдастыру:
коммуникативтік:
констациялайтын (дерек жайлы нейтралды хабарлама үшін);
сұрау (деректі сұрату үшін);
апеллетивтік (іс - әрекетке түрткі болу үшін);
экспрессивтік (айтушының көңіл-күйі мен эмоциясын білдіру үшін);
байланыс орнататын (әңгімелесушілер арасында байланыс орнату және оны қолдау үшін);
метатілдік (тілдік деректерді талқылау үшін);
эстетикалық (эстетикалық ықпал ету үшін);
адамдардың белгілі бір тобына жату көрсеткіші қызметі (нәсіл, халық, кәсіп);
ақпараттық;
танымдық.
Қазіргі кезде жүйелілік тілдің маңызды сипаттамасы болып есептелінеді. Табиғи тілдің семиотикалық мазмұны мән универсумы мен дыбысталу универсумы арасындағы сәйкестікті орнатуда болып табылады.
Адамнің тілі өзінің ауызша формасындағы көзқарастар жоспарының табиғаты негіздемесі бойынша есту белгісінің жүйесіне жатса, жазбаша түрде көру жүйесіне жатады.
Табиғи тіл генезис типі бойынша мәдени жүйесіне жатады, осылайша ол табиғи белгілер жүйесіне де, жасанды белгілер жүйесіне де қарама-қайшы қойылады. Белгілер жүйесі ретінде адамнің тілі үшін табиғи және жасанды белгілер жүйесінің сипаттары тән.
Табиғи тіл жүйесі көпдеңгейлі жүйеге жатады, себебі ол әр түрлі элементтерден - фонем, морфем, сөз, сөйлемдерден тұрады, олардың арасында қарым-қатынас күрделі әрі көпжақты келеді.
Табиғи тілдің құрылымдық күрделігіне келетін болсақ, тілді белгілер жүйесінің ішіндегі ең күрделісі деп атайды.
Құрылымдық негіздемесі бойынша детерминделген және ықтимал семиотикалық жүйелерді ажыратады. Табиғи тіл элементтерді қолдану тәртібі қатаң емес ықтимал жүйеге жатады және ықтимал сипатқа ие.
Семиотикалық жүйелер динамикалық, жылжымалы және тұрақты, жылжымайтын деп бөледі. Динамикалық жүйелер элементтері бір біріне қатысты өздерінің жағдайын өзгертіп отырады, ал тұрақты жүйеде элементтердің жағдайы өзгермей, тұрақты қалады. Табиғи тілді динамикалық жүйеге жатқызады, алайда онда тұрақты белгілер де көрініс табады.
Белгілер жүйесінің құрылымдық сипаттамаларының тағы бірі болып олардың толықтылығы табылады. Толық жүйені берілген жиынтықтың элементтерінен тұратын белгілі бір ұзындықтың теориялық тұрғыдан мүмкін болатын барлық комбинациясын білдіретін белгілері бар жүйе ретінде анықтауға болады. Соған сәйкес толық емес жүйені белгілерді білдіру үшін берілген элементтердің мүмкін болатын комбинацияларының барлығы пайдаланылмайтын артықтықтың белгілі бір деңгейіне ие жүйе ретінде сипаттауға болады. Табиғи тіл артықтықтың жоғары деңгейіне ие толық емес жүйе болып табылады.
Белгілер жүйелерінің өзгеру қабілеттерінің арасындағы айырмашылық оларды ашық және жабық жүйелер деп жіктеуге негіз болып табылады. Ашық жүйелер өздерінің қызмет ету үрдісінде өзіне жаңа белгілерді қоса алады және жабық жүйемен салыстырғанда неғұрлым жоғары бейімделушілігімен сипаттамалады. Өзгеру қабілеті адам тіліне де тән.
Табиғи тіл өте күрделі, оның көмегімен сөйлесу қызметі жүзеге асырылады, яғни мәтіндердің туындауы мен оны түсіну. Кез келген мәтін материалдық емес мағынаны жеткізетін материалды объект болып табылады. Мағына адам санасында туындайды, алайда басқа адамға қол жетімді бола алмайды: басқа адамның ойына кіру тәсілі жоқ, себебі олар материалды емес, яғни біздің ешқандай сезім мүшеміз арқылы қабылдана алмайды. Тіл ойлардың материалдануының құралы болып табылады: материалды қабыққа ие мәтінге айнала отырып ойлар қабылдауға қол жетімді болады және оны басқа адам түсіне алады. Осылайша, тіл - бұл материалдық емес ойларды материалдық субстанцияға айналдыратын, материалдық символдар арқылы немесе белгілер арқылы кодталуының құралы, сонымен қатар осы субстанция бойынша ойларды декодтау тәсілі. Табиғи тілдің мәтіндері үшін негізгі субстанция болып дыбыстық табылады: бұл есту мүшелері арқылы қабылданатын ауаның тербелісі; графикалық субстанция (көру арқылы қабылданатын мәтіндер) екінші ретті болып табылады. Дыбыстық субстанцияның ауысуының әр түрлі жүйелері (графика немесе жазбаша) адам мәдениетінде маңызды рөл атқарады, алайда табиғи тілдердің барлығына дерлік жасалынбаған және қалыптастырылмаған. Кез келген субстанция сызықтық: ол уақыт бойынша туындайды, кейбір элементтер ерте, келесісі - кешірек. Ой жалпы жағдайда сызықтық емес; сондықтан да ойдан мәтінге ауысу күрделі үрдіс болып табылады және ойлау үрдісіне ықпал етуі мүмкін.
Хабарламаларды кодтау және декодтау адамның сөйлеу қызметінің екі негізгі түрлері болып табылады: сөйлеу және түсіну, басқаша айтқанда мәтіннің туындауы мен қабылдануы. Тілді толыққанды меңгеру сөйлеу қызметінің осы екі түрлерін сәтті орындау қабілетін көрсетеді; мәтінді туындату қабілеті тасушының белсенді компетенциясы деп аталса, басқа біреудің құрастырған мәтіндерін түсіну қабілетін тасушының пассивті компетенциясы деп атайды.
Табиғи тілдерің ерекшеліктері
Табиғи тілдердің ерекшеліктері олардың болмысынан көрінеді. Табиғи тілдерді зерттеуге формалды тәсілді қиындататын негізгі ерекшеліктер төменде суреттелінген.
- синтаксистің семантикаға (мағынасы) тәуелділігі. Мысалы, сөздің аяқталуы осы сөздердің қандай да бір объектіге қатысты, жанды немесе жансыз нәрсеге байланысты болуы мүмкін. Мысал үшін екі ұқсас сөйлемді қарастырайық.
Мен кесілген ағыштың түбін көрдім (Нені?).
Мен досымды көрдім (Кімді?).
- Семантикалық және синтаксистік әркелкілік. Семантикалық әркелкілік кейбір сөздердің әр түрлі мағынаға ие болуынан туындайды. Мысалы, Косой шел с косой сөйлемі контекске байланысты әр түрлі мағынаға ие бола алады. Синтаксистік әркелкілік синтаксистік ережелердің жеткілікті деңгейде қатаң болмауынан туындайды. Бытие определяет сознание сөйлемі әр түрлі талқылануы мүмкін. Егер базалық элемент бытие (болмыс) деп есептесек, онда осы сөйлемді Бытие является главным и оно определяет сознание деген сөйлеммен ауыстыруға болады. алайда бұл сөйлем былайша талқылануы да мүмкін: бытие определяется сознанием.
- парадоксальды ұсыныстардың пайда болу мүмкіндігі. Парадоксальды ұсыныстар оларды шынайыға да, жалғанға да жатқызуға болмайды. Парадоксальды ұсынстардың мысалы ретінде мына сөйлемді айтуға болады: Данное предложение являетс ложным.
- мағынаның жағдайға тәуелдігі;
- тілдің уақытқа байланысты өзгерісі;
- көптеген шектеулері бар синтаксистік көптеген сан.
1.2 Формалды тілдер және олардың ерекшеліктері
Көптеген жасанды тілдер формалды сөйлемдерді құрастыруда пайдаланылады, яғни мағынаға, ережеге тәуелді емес сөйлемдер. Мұндай тілдер формалды деп аталады. Формалды тілдер синтаксисті сөйлемді құрастыруға формалды тәсілді қамтамасыз етуі керек. Сондықтан да формалды тілдер келесідей ерекшеліктерге ие:
- синтаксистік ережелердің мағынаға тәуелсіздігі;
- парадокстардың пайда болу мүмкін еместігі;
- синтаксистік ережелердің қатаңдығы мен шектеулердің болмауы;
- синтаксистік ережелердің соңғы саны.
Формалды тілдер табиғи тілдер секілді уақыт бойынша өзгеруі мүмкін. Алайда табиғи тілдерден айырмашылығы бұл өзгерістер біртіндеп емес, тілдің жаңа версияларының пайда болуымен көрінеді. Сонымен қатар бір тілдің әр түрлі версияларын әр түрлі тілдер деп қарастыруға болады.
Формалды тілдің төменгі синтаксистік бірлігі болып символ табылады. Символ (әріп) - бұл қарапайым бөлінбейтін белгі. Тіл символдарының жиынтығы алфавитті құрайды. Алфавиттің мысалдары:
Орыс алфавиті - {А, а, Б, б, В, в, ..., Я, я }.
Латын алфавиті - {A, a, b, b, C, c, ..., Z, z }.
Араб алфаваиті - { 0, 1, 2, . . . , 9 }.
Тілдің символдары қатарға бірігеді. Қатар - бұл символдардың реттелген кезектілігі. Қатардың мысалдары:
Орыс алфавитіндегі қатарлар - реттелген, кезектілік, а.
Латын алфавитіндегі қатарлар - "BEGIN" , "THEN" , "END".
Екілік (двоичный) алфавиттегі қатарлар - "0", "1", "00", "10", "01010101".
Қатардағы символдар саны қатардың ұзындығы деп аталады. а1а2а3 . . . аn символдарының қатары n ұзындығына ие. Егер қатардың ұзындығы нөлге тең болса, онда қатар бос деп аталады. Бос қатар λ символымен белгіленеді. λ символының алфавит символы еместігін атап өту керек.
А алфавитінің барлық қатарлар жиынтығы А алфавитімен тұйықталу деп аталады және А* символымен белгіленеді.
А* = А0 U А1 U А2 U . . . U Аn =n=0infinityAn (1)
Бұл жерде: А0 Euro{λ} - бос қатар;
Аn - n ұзындығының қатары.
А+ бос емес қатарлардың жиынтығы келесідей анықталады:
А+ = А* \ {λ} =n=1infinityAn (2)
Тіл жалпы жағдайда А* жиынтығының еркін жиынтығын көрсетеді. А* жиынтығы анықтамасы бойынша шексіз болғандықтан, онда тіл де жалпы жағдайда шексіз болады. Сондықтан да тілді ашықтан - ашық, яғни барлық мүмкін болатын қатарларды атап шығу арқылы жасау мүмкін емес. Мысалы, орыс тілінің барлық дұрыс сөйлемдерін атап шығу мүмкін емес. Тілді сипаттау үшін тілдің мүмкін сөйлемдерін жасау ережелерін қысқа формада суреттейтін арнайы жүйе керек. Мұндай жүйені формалды грамматика деп атайды. Формалды грамматиканың көмегімен құрылған тіл формалды тіл деп аталады. Формалды тілді қоса алғандағы тілдің қатарлары белгілі бір мағынаға ие. Тілдің қатарларының мағынасы кейбір қымбат емес қосымша ақпараттардың көмегімен анықталынады.
Формалды грамматиканың типтері
Формалды грамматикалар бір-бірінен тұжырым ережелер типімен ерекшеленеді. Формалды грамматикалардың тұжырым ережесі типі бойынша жіктелімін американ лингвисті Ноам Хомский енгізген болатын. Хомский формалды грамматиканы төрт типке бөлді.
0 типтегі формалды грамматика (шектелмеген грамматика немесе еркін типті грамматика) келесі түрді айырбастауда қолданылады:
α-- β, (3)
Бұл жерде α және β - еркін түрдің тізбектері.
1 типті формалды грамматика немесе контексті грамматика (контексті тәуелді грамматика) келесі түрді айырбастауда пайдаланылады:
Мұнда, A - нетерминалды символ;
, , - еркін түрдің тізбектері, бұл жерде тізбегі бос емес немесе (N U T)+;
, - ережелер контексті.
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 bS.
Осы грамматиканың көмегімен a және b символдарының қатарлары туындайды. Қатарлардың туындау кезектілігін келесі сызба бойынша түсіндіруге болады:
Қолданылатын тұжырым ережесі Қатарлар мазмұны
S
S aS aS
S aS aaS
S b aab
Тұжырым нәтижесі болып aab қатары табылады.
Контекстісіз грамматиканың мысалы: G = {N, T, P, S).
N ={S};
T = {a, b}
P: S aSb; S ab.
Бұл грамматиканың көмегімен anbn түрдегі қатар туындайды.
a3b3 қатар тұжырымының ережесі
Қолданылатын тұжырым ережесі Қатар мазмұны
S
S aSb aSb
S aSb aaSbb
S ab. aaabbb
Күрделірек түрдегі контекстісіз грамматиканың мысалы:G = {N, T, P, S).
N ={S};
T = { IF, THEN, ELSE, U, B}
P: S B;
S IF U THEN S;
S IF U THEN S ELSE S.
Бұл грамматика Паскаль типіндегі тілдің әр түрлі шартты операторларын қалыптастыруға мүмкіндік береді. Мысалы, 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 B
Екінші нұсқа да мүмкін:
Қолданылатын тұжырым ережесі Қатар мазмұны
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 B.
Формалды логика мен информатикада формалды тіл - бұл соңғы алфавиттің соңғы сөздерінің (қатар, тізбек) жиынтығы. Тілді түсіну көбінесе автоматтар теориясында, есептеу теориясында және алгоритмдер теориясында қолданылады. Осы объектімен байланысты ғылыми теория формалды тілдер теориясы деп аталады.
Модельдер теориясында тіл информатика тіліне емес, алфавитке сәйкес келеді. Тіл көптеген символдар, қызметтер мен қарым-қатынастардан, сонымен қатар айнымалылар жиынтығынан тұрады. Осы жиынтықтың әрбіреуі шексіз болуы мүмкін. Тілден оның универсалды логикалық символдарымен бірге логикалық пікір қалыптастырылады.
Формалды тіл әр түрлі анықталуы мүмкін, мысалы, осы тілге енетін сөздердің қарапайым аударылуы. Бұл тәсіл негізінен соңғы тіл мен қарапайым құрылым тілдерін анықтауға қолданылады.
кейбір формалды грамматикадан туындайтын сөздермен;
тұрақты пікірден туындаған сөздермен;
кейбір шекті автомат арқылы танылатын сөздермен;
БНФ - конструкциядан туындаған сөздермен.
Егер алфавит {a, b} деп берілсе, ал L тіл өзіне оған қатысты барлық сөздерді қамтыса, онда ababba сөзі L - ға жатады. Бос сөз, яғни нөлдік ұзындық қатары мүмкін болады және көбінесе e, ε немесе Λ деп белгіленеді.
Формалды тілдердің кейбір мысалдары:
{a, b} барлық сөздердің жиынтығы
жиынтық, онда n -- теріс емес сан, ал a - ның n - рет қайталануын білдіреді
осы бағдарламалау тіліндегі синтаксистік дұрыс бағдарламалардың жиынтығы
Операциялары
Кейбір операциялар мәліметтерден жаңа тілдер туындату үшін пайдаланылуы мүмкін. Мысалы, және кейбір жалпы алфавитпен анықталған тілдер болсын.
* конкатенация (байланысуы) формасын қанағаттандыратын барлық сөздерді қамтиды, онда - бұл сөзі, ал - сөзі.
қиылысуы және - дегі барлық сөздерді қамтиды;
бірігуі немесе - дегі сөздерді қамтиды.
тілін толықтыру алфавиттегі барлық сөздерді қамтиды.
арақатынасы - де сөзі болғандығын, - де болған -ның барлық сөздерін қамтиды.
Клини тұйықталуы формасында жазыла алатын барлық сөздерді қамтиды, онда - де болады және . Бұл бос сөзін де қамтитынын естен шығармау керек, себебі шарт бойынша мүмкін болады.
айналымы -ге айналған сөздерді қамтиды.
және -нің араласуы формасында жазылған барлық сөздерді қамтиды, онда және болып байланысы -де бар сөздер, ал болып -де болатын сөздер табылады.
1.3 Бағдарламалау тілдері (Pascal, Delphi, C, C++, C#)
Бағдарламалау тілі - бұл компьютерлік бағдарламаларды жазуға арналған формалды белгілер жүйесі. Бағдарламалау тілі бағдарламаның сыртқы бейнесі мен компьютердің атқара алатын іс - әрекеттерін көрсететін лексикалық, синтаксистік және семантикалық ережелер жиынтығын білдіреді.
Алғашқы бағдарлама жасайтын машиналарды құрғаннан бастап адамзат екі жарым мыңнан аса бағдарламалау тілдерін (абстрактілі және стандарттық емес тілдерді қосқанда) ойлап тапты. Жыл сайын олардың саны арта түсуде. Кейбір тілдерді тек оны жасаушылардың аз ғана бөлігі пайдалана алады, басқалары миллиондаған адамдарға танымал. Кәсіби бағдарламашылар (программист) кей кездері өздерінің жұмыстарында бағдарламалау тілдерінің оннан аса түрін пайдаланады.
Тілдерді жасаушылар бағдарламалау тілдері түсінігін әр түрлі түсіндіреді. Көптеген жасаушылар мойындаған кең таралған пікірлерге келесілер жатады:
Қызметі: бағдарламалау тілі компьютерге сол немесе басқа есептеу үрдісін жасау және жекелеген құрылғыларды басқаруды ұйымдастыру нұсқаулықтарын беру үшін пайдаланылатын компьютер бағдарламаларын жазуға арналады.
Міндеті: бағдарламалау тілі табиғи тілден оның командалар мен мәліметтерді адамнан компьютерге беруімен ажыратылады, ал табиғи тіл адамдар арасында қарым - қатынас орнату үшін пайдаланылады. Бағдарламалау тілі анықтамасын қорытындылауға болады: бағдарламалау тілі - бұл командалар, бұйрықтар, іс - әрекет жасау бойынша нақты басшылықтар беру тәсілі; ал адам тілі сонымен қатар ақпараттар алмасуы үшін қызмет етеді.
Орындалуы: бағдарламалау тілі мәліметтер құрылымын анықтау мен манипуляциялау және есептеу үрдісін басқару үшін арнайы конструкцияларды пайдалана алады.
Visual Basic -- мектеп оқушыларының білетін жалғыз нәрсесі. Сонымен қатар Mobile Basic телефонда бағдарламалау үшін арналған. Бұл компьютерден ағылшын тілін білетіндерге қолайлы.
PHP -- бастамашы дамушының өзін-өзі жетілдіру үшін қажет. Онда drupal, joomla, wordpress және mediawiki қоса алғандағы сіздің көптеген cms жазылған.
Python -- бұл школота бағдарламалауын оқыту үшін таптырмайтын тіл.
Pascal -- басқа қарапайым тілдер жайлы білмейтін жас оқушыларды оқытуға пайдаланылады.
Delphi -- 7 версиясы
C# -- Visual Basic - тің мұрагері немесе Java, С++ және Delphi - ді будандастыру талпыныстары.
1С -- win - 1251 - ге ауыстырылған Кобол.
Java -- оны барлық жерде пайдаланады.
C++. Бұл өте танымал, соның ішінде Линусу Торвальдсқа да. Тышқанмен бағдарламалау үшін IDE бар. Нуфф саид.
Си (бағдарламалау тілі)
Си -- стандартталған процедуралық бағдарламалау тілі. Оны 1970 жылдың басында Bell Labs қызметкерлері Кен Томпсон мен Деннис Ритчи жасады. Си UNIX операциялық жүйесінде пайдалану үшін жасалынған болатын. Содан бері ол басқа да көптеген операциялық жүйеге ауыстырылып, өте көп қолданылатын бағдарламалау тілдерінің біріне айналды. Си - ді оның тиімділігі үшін бағалайды. Ол жүйелік бағдарламалық қамтамасыз етуді құру үшін танымал тіл болып табылады. Оны көбінесе қолданбалы бағдарламаларды қалыптастыру үшін де пайдаланады. Си жаңа үйрене бастаған адамдарға арнап шығарылмаса да бағдарламалауды оқытуда белсенді пайдаланылады. Си тілінің синтаксисі басқа да көптеген тілдер үшін негіз болды.
Си тілі үшін ықшамдылық, орындау ағынын басқарудың конструкциясының стандартты жиынтығы, мәліметтер құрылымы мен операциялардың кең жиынтығы тән.
Ерекшеліктері.
Си бағдарламалау тілі минимализммен ерекшеленеді. Тілдің авторлары ондағы бағдарламалардың біржақты компилятордың көмегімен оңай компиляциялануын қалады. Себебі әрбір бағдарламаның қарапайым құраушысына компиляциядан кейін машиналық команданың аз ғана саны сәйкес келді, ал базалық тілдерді пайдалану орындау уақыты бойынша кітапхананы әрекетке қоспады. Біржақты компилятор артқа қайтпай, бағдарламаны компиляциялайды. Сондықтан да қызметтер мен айнымалыларды пайдалану олардың хабарламаларын бұрын болуы керек. Си - ге кодты абстракцияның төменгі деңгейінде оңай жазуға болады. кей кездері Си - ді универсалды ассемблер немесе жоғары деңгейлі ассемблер деп те атайды. Си оның нақты құрылғылармен жақын етене жұмыс жасауын ескере отырып, көбінесе орта деңгейлі немесе тіпті төменгі деңгейлі тіл деп те аталады. Алайда қатаң жіктелімде ол жоғаы деңгейлі болып табылады.
C++ -- жалпы тағайындаудың тұрақты типті бағдарламалау тілі. Сонымен қатар процедуралық бағдарламалау, объектіге бағытталған бағдарламалау, жинақталған бағдарламалау сияқты бағдарламалау парадигмаларын қолдайды, модульділікті, бөлінген компиляцияны, айырмашылықты өңдеуді, мәліметтер абстракциясын, объектілер типін хабарлауды, виртуалды қызметтерді қамтамасыз етеді. Стандартты кітапхана жалпы пайдаланылатын контейнерлер мен алгоритмдерді қамтиды. C++ жоғары деңгейлі және төменгі деңгейлі тілдердің де қасиеттерін қамтиды. Оны С тілімен салыстырғанда онда объектіге бағдарлануға және жинақталған бағдарламалауға көп назар аударылған.
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)+ мен α = β түрде болса, онда G = (VT, VN, P, S) қысқартылмайтын деп атайды. Егер Р ережесінің әрбіреуі келесідей түрге ие болса: α -- β , бұл жерде α = ξ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--AFBAB
AB -- bBA
Ab --bA
AD -- D
Cb -- bC
CB --C
bCD --λ
Тіл типі 1: L = {бірдей 0 мен 1 сандары бар 0 мен 1 тізбектер}
P: S--ASB AB
AB -- BA
A -- 0
B -- 1
Тіл типі 2: L = {(ac)n (cb)n n 0}
P: S--aQbaccb
Q -- cSc
Тіл типі 3: L = {ω ω ∈ {a,b}+, қасында бірге тұрған a жоқ жерде}
P: S -- A⊥ B⊥
A -- a Ba
B--bBb Ab
Танушылардың тілдің типі бойынша жіктелімі
Танушының күрделілігі кіру тізбегін танушы қабылдай алатын тілдің типімен тікелей байланысты. Жоғарыда аталынған тілдің төрт типінің әрбіреуі үшін компоненттің белгілі бір құрамы бар, соған сәйкес алгоритм жұмысының күрделігі бар өзінің танушыларының типі болатыны дәлелденген.
Фразалық құрылымы бар тілдер (тип 0) үшін шексіз сыртқы есі бар детерминделмеген автомат қажет. Сондықтан да осы типтегі тілдер үшін шектеулі уақытта шектеулі есептеуіш ресурстарда танушы жұмысты аяқтайды және кіру тізбегі берілген тілге жататыны немесе жатпайтыны туралы шешім қабылдайтынына кепілдік беруге болмайды.
Контексті тәуелді тілдер (тип 1) үшін танушылар сызықтық шектеулі сыртқы есі бар екі жақты детерминделмеген автоматтар болып табылады. Мұндай автоматтың жұмысының алгоритмі жалпы жағдайда экспоненциалды күрделілікке ие - автоматқа кіру тізбегін тану үшін қажет қадамдар саны осы тізбектің ұзындығына экспоненциалды тәуелді. Соған сәйкес, берілген алгоритм бойынша кіру тізбегін талдауға қажет уақыт та кіру тізбегінің ұзындығына экспоненциалды тәуелді.
Танушының осындай алгоритмі жүзеге асырылуы мүмкін - кіру тізбегінің ұзындығын біле отырып, әрқашан да осы тілге тізбектің жатуы туралы шешім қанша уақытта қабылданатыны және қандай есептеуіш ресурстары қажет екенін айтуға болады. алайда талдау уақытының тізбектің ұзындығына экспоненциалды тәуелділігі танушыларды контексті тәуелді тілдер үшін пайдалануын шектейді. Мұндай танушылар автоматтандырылған ауысым мен табиғи тілдегі мәтіндерді мәтінді талдау үшін уақыт шектеулері аса маңызды емес жағдайда талдау үшін пайдаланылады (себебі табиғи тілдер контексті тәуелді тілдерге қарағанда күрделірек, сондықтан осындай өңдеуден кейін адамның араласуы керек).
Компиляторларда контексті тәуелді танушылар пайдаланылмайды, себебі компилятордың жұмыс жасау жылдамдығы маңызды болып табылады, ал бағдарламаның мәтінін синтаксистік талдауды контексті еркін тілдер секілді қарапайымдырақ тілдер шегінде орындауға болады.
Контексті еркін тілдерге (тип 2) арналған танушылар айдағыш сыртқы есі бар біржақты анықталмаған автоматтар болып табылады. Осындай автоматтың жұмысының алгоритмін қарапайым жүзеге асыру барысында ол экспоненуиалды жылдамдыққа ие, алайда алгоритмнің кейбір жетілдірулері арқылы кіру тізбегін талдауға қажет уақыттың осы тізбектің ұзындығына полимиалды тәуелділігіне қол жеткізуге болады. соған сәйкес контексті еркін тілдер үшін танушылардың колимиалды күрделігі туралы айтуға болады.
Барлық контексті еркін тілдердің арасында анықталған контексті еркін тілдер сыныбын ажыратып көрсетуге болады. Олардың танушылары айдағыш сыртқы есі бар детерминделген автоматтар болып табылады. Бұл тілдер бір мағыналық қасиетке ие, кез келген анықталған контексті еркін тілдер үшін әрқашан да бір мағыналы грамматиканы тұрғызуға болатыны дәлелденген. Бұдан басқа, осындай тілдер үшін квадраттық күрделігі бар танушылардың жұмысының алгоритмі бар. Осы тілдер бір мағыналы болып табылғандықтан олар компиляторларды тұрғызу үшін жоғары қызығушылық тудырады.
Сонымен қатар анықталған контексті еркін тілдердің ішінде сызықтық танушы тұрғызу мүмкін тілдердің сыныптары бар. Сызықтық танушылар - бұл тізбектің тілге жатуы туралы шешім қабылдау уақыты тізбектің ұзындығына сызықтық тәуелді болатын танушы. Бағдарламалаудың барлық тілдерінің синтаксистік конструкциялары осындай тілдердің сыныбының біреуіне жатқызылуы мүмкін.
Бағдарламалау тілдерінің синтаксистік конструкциялары ғана контексті еркін тілдердің танушыларының көмегімен талдауға рұқсат берілетінін естен шығармау керек. Бағдарламалау тілдерінің өздері контексті еркін тілдер тиіне толықтай жатқызылмайды, себебі ағымдағы бағдарламаның мәтінінде кейбір контексті тәуелділікті көрсетеді. Мысалы, айнымалылардың алдын ала сипатталу қажеттілігі. Сондықтан да синтаксистік талдаудан басқа барлық компиляторлар ағымдағы бағдарламаның мәтінін қосымша семантикалық талдауды көрсетеді. Бұны болдырмауға болар еді, егер компиляторды контексті тәуелді танушының негізінде тұрғызғанда, алайда мұндай компилятордың жұмысының жылдамдығы өте төмен болар еді. Себебі мұндай варианттаға талдаудың уақыты ағымдағы бағдарламаның ұзындығына экспоненциалды тәуелді болады. контексті еркін тілдер танушылары мен қосымша семантикалық анализатордың комбинациясы ағымдағы бағдарламаны талдау жылдамдығы тұрғысынан тиімдірек болып табылады.
Тұрақты тілдер (тип 3) үшін танушылар сыртқы ессіз анықталған автоматтар - шекті автоматтар болып табылады. Бұл өте қарапайым танушының типі, әрқашан кіру тізбегін талдау уақытының тізбектің ұзындығына сызықтық тәуелділігін көрсетеді. Бұдан басқа шекті автоматтар маңызды ерекшелікке ие: кез келген анықталмаған соңғы автомат әрқашан детерминделгенге өзгертілуі мүмкін. Бұл жағдай танушының қызметін қамтамасыз ететін бағдарламалық қамсыздандыруды жасауды жеңілдетеді. Танушылардың жұмысының қарапайымдылығы мен жоғары жылдамдығы тұрақты тілдердің пайдалануының кең облысын анықтайды.
Компиляторларда танушылар тұрақты тілдер негізінде ағымдағы бағдарламаның мәтінін лексикалық талдау үшін пайдаланылады. Тұрақты тілдер танушыларының негізінде ассемблерлер қызмет етеді.
Бұдан басқа тұрақты тілдер есептеуіш жүйені бағдарламалық қамсыздандыруды жасаумен байланысты көптеген облыстарда пайдаланылады. Олардың негізінде көптеген командалық процессорлар жүйелік те, қолданбалы бағдарламалық қамсыздандыруда да қызмет етеді. Тұрақты тілдер үшін танушылардың құрылуын жеңілдетуге мүмкіндік беретін, математикалық негізделген, дамыған механизмдер бар.
2.2 Қысқартылмайтын тілдер (неукорачивающие языки) мен олардың ерекшеліктері
Трансляцияның формалды модельдері бұрын қарастырғандай синтаксистік құрылымдарды оқуға қатысты компиляция теориясының бөлімі стандарты болып келеді және де контексті еркін тілдер теориясына негізделеді.
Программалау тілінің синтаксистік формалды анықталуы әдетте грамматика деп аталады. Грамматика программалау тілдің анықталуы үшін мүмкін символдар тізбегін анықтайтын ережелер жиынтығынан тұрады. Формалды грамматика дегеніміз қатаң белгілеулер жүйесінен тұратын грамматика, компиляциялау технологиясында грамматиканың 2 класы қолданылады.
1) БНФ грамматика немесе контекстілі еркін грамматика
2) Регулярлы грамматика
БНФ грамматика. Ағылшын тіліндегі сөйлем құрылымын қарастыра отырып оның категориялары тілдегі қарапайым хабарлас сөйлем мынадай сөйлемнен тұрады:
Бастауыш етістік толықтауыш The gіrl (runs) home.
Әрбір категория өз кезегінде ішкі категорияларға бөлінуі мүмкін. Мысалы: жоғарыдағы құрылымда бастауыш артикль және зат есімнен тұрады. Олай болса құрылым былай жазылуы мүмкін.артикль зат есім етістік толықтауыш
Бұдан басқа сұраулы сөйлемдердің де құрылымы былай жазылады:
Көмекші етістік бастауыш баяндауыш
Мысалы: dіd the gіrl run home?
Келтірілген сөйлемдерді қандай да бір ереженің жиынтығы арқылы сипатттау мүмкін. Яғни біз сөйлемнің хабарлы не сұраулы болатынын айта аламыз немесе оны былай жазуға болады:
сөйлем::=хабарлысұраулы. Мұндағы :: = белгісі - аталған категорияның белгілерінің оң жағындағы ішкі категорияға бөліну мүмкіндігін білдіреді. Яғни келтірілген құрылымды былайша оқиды. Сөйлемдердің келесі тармақталуы былайша анықталады:
хабарлы::=бастауышетістіктол ықтауыш
бастауыш::=артикльзат есім
сұраулы::= қосымша етістікбастауышбаяндауыш
Осылайша, арнайы жазуды БНФ - Бэкустың нормаль формалары деп атады. Оны 50 - ші жылдардың соңында algol тілінің синтаксистік анықталуы ретінде пайдаланып жария етті. Шамамен осы жылдары Ноам Хомский осыған ұқсас грамматикалық форманы ұсынып, оны контекстілі еркін грамматика деп атады. Ол табиғи тілдердің синтаксисін келтіру үшін арналды. БНФ және контекстілі еркін грамматика формалары мүмкіндіктері жағынан эквивалентті болып келеді. Айырмашылығы - олардың белгілеулер жүйесінде ғана, сондықтан синтаксис мәселен талқылау барысында БНФ грамматика және контексті еркін грамматика терминдері өзара бірін - бірі ауыстыратын сөздер ретінде қолданылады.
БНФ грамматиканың синтаксисі. БНФ грамматика программалау тілдерін анықтайтын грамматика ережелерінің аяқталған жиынтығынан тұрады. Бұл ережелерді қарастырмас ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
МЕХАНИКА-МАТЕМАТИКА ФАКУЛЬТЕТІ
АҚПАРАТТЫҚ ЖҮЙЕЛЕР КАФЕДРАСЫ
" КЖ - грамматикасы үшін талдау анықталған және анықталмаған сұлбасы негізінде синтез алгоритмін талдау" тақырыбына жазылған
ДИПЛОМДЫҚ ЖҰМЫС
Орындаған
___________________
(қолы)
Маханов Ш.Б.
Ғылыми жетекші,
т.ғ.д.,профессор
___________________
(қолы)
Дюсембаев А.Е.
Нормобақылаушы
___________________
(қолы)
Жуманов Ж.М.
Қорғауға жіберілді:
Кафедра меңг.қ.а, 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 add-on.
Keywords: formal grammar, natural languages, formal languages, automatic grammar
Object of study: To analyze the grammar to analyze both known and unknown synthesis algorithms - КС.
Objective: To analyze the grammar of the main goal to analyze both known and unknown synthesis algorithms and КС.
Improvements: A Study of natural and formal languages and view their properties. Determination of the formal grammar and study its properties.
Analysis of the КС language, research and analysis of known and unknown drawings of КС.
Results: Did the job performed by analysis on arbitrary formal grammar for the syntactic basis.
The outlook for the future development of the work on the study: in the future based on the results of the work done and hope for the benefit on the industrial region. In the future we will improve this program and research more many useful solutions.
МАЗМҰНЫ
КІРІСПЕ 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 ФОРМАЛДЫ ТІЛДЕР
1.1 Табиғи тілдер мен олардың сипаттамалары
Табиғи тіл - адамдардың қарым-қатынасы үшін пайдаланылатын (формалды емес тілдерден айырмашылығы) және қолдан жасалынбаған (жасанды тілден айырмашылығы) тіл.
Табиғи тілдің сөздігі мен грамматикалық ережелері пайдалану тәжірибесімен анықталынады және әрқашан формалды ретінде тіркеле бермейді.
Тілдің негізгі қызметі - пікірді құрастыру, әрекетті реакцияның мазмұнын анықтау мүмкіндігі, коммуникаторлар қарым-қатынасы кеңістігін ұйымдастыратын кейбір симметриялық формаларды білдіретін ұғымдарды ұйымдастыру:
коммуникативтік:
констациялайтын (дерек жайлы нейтралды хабарлама үшін);
сұрау (деректі сұрату үшін);
апеллетивтік (іс - әрекетке түрткі болу үшін);
экспрессивтік (айтушының көңіл-күйі мен эмоциясын білдіру үшін);
байланыс орнататын (әңгімелесушілер арасында байланыс орнату және оны қолдау үшін);
метатілдік (тілдік деректерді талқылау үшін);
эстетикалық (эстетикалық ықпал ету үшін);
адамдардың белгілі бір тобына жату көрсеткіші қызметі (нәсіл, халық, кәсіп);
ақпараттық;
танымдық.
Қазіргі кезде жүйелілік тілдің маңызды сипаттамасы болып есептелінеді. Табиғи тілдің семиотикалық мазмұны мән универсумы мен дыбысталу универсумы арасындағы сәйкестікті орнатуда болып табылады.
Адамнің тілі өзінің ауызша формасындағы көзқарастар жоспарының табиғаты негіздемесі бойынша есту белгісінің жүйесіне жатса, жазбаша түрде көру жүйесіне жатады.
Табиғи тіл генезис типі бойынша мәдени жүйесіне жатады, осылайша ол табиғи белгілер жүйесіне де, жасанды белгілер жүйесіне де қарама-қайшы қойылады. Белгілер жүйесі ретінде адамнің тілі үшін табиғи және жасанды белгілер жүйесінің сипаттары тән.
Табиғи тіл жүйесі көпдеңгейлі жүйеге жатады, себебі ол әр түрлі элементтерден - фонем, морфем, сөз, сөйлемдерден тұрады, олардың арасында қарым-қатынас күрделі әрі көпжақты келеді.
Табиғи тілдің құрылымдық күрделігіне келетін болсақ, тілді белгілер жүйесінің ішіндегі ең күрделісі деп атайды.
Құрылымдық негіздемесі бойынша детерминделген және ықтимал семиотикалық жүйелерді ажыратады. Табиғи тіл элементтерді қолдану тәртібі қатаң емес ықтимал жүйеге жатады және ықтимал сипатқа ие.
Семиотикалық жүйелер динамикалық, жылжымалы және тұрақты, жылжымайтын деп бөледі. Динамикалық жүйелер элементтері бір біріне қатысты өздерінің жағдайын өзгертіп отырады, ал тұрақты жүйеде элементтердің жағдайы өзгермей, тұрақты қалады. Табиғи тілді динамикалық жүйеге жатқызады, алайда онда тұрақты белгілер де көрініс табады.
Белгілер жүйесінің құрылымдық сипаттамаларының тағы бірі болып олардың толықтылығы табылады. Толық жүйені берілген жиынтықтың элементтерінен тұратын белгілі бір ұзындықтың теориялық тұрғыдан мүмкін болатын барлық комбинациясын білдіретін белгілері бар жүйе ретінде анықтауға болады. Соған сәйкес толық емес жүйені белгілерді білдіру үшін берілген элементтердің мүмкін болатын комбинацияларының барлығы пайдаланылмайтын артықтықтың белгілі бір деңгейіне ие жүйе ретінде сипаттауға болады. Табиғи тіл артықтықтың жоғары деңгейіне ие толық емес жүйе болып табылады.
Белгілер жүйелерінің өзгеру қабілеттерінің арасындағы айырмашылық оларды ашық және жабық жүйелер деп жіктеуге негіз болып табылады. Ашық жүйелер өздерінің қызмет ету үрдісінде өзіне жаңа белгілерді қоса алады және жабық жүйемен салыстырғанда неғұрлым жоғары бейімделушілігімен сипаттамалады. Өзгеру қабілеті адам тіліне де тән.
Табиғи тіл өте күрделі, оның көмегімен сөйлесу қызметі жүзеге асырылады, яғни мәтіндердің туындауы мен оны түсіну. Кез келген мәтін материалдық емес мағынаны жеткізетін материалды объект болып табылады. Мағына адам санасында туындайды, алайда басқа адамға қол жетімді бола алмайды: басқа адамның ойына кіру тәсілі жоқ, себебі олар материалды емес, яғни біздің ешқандай сезім мүшеміз арқылы қабылдана алмайды. Тіл ойлардың материалдануының құралы болып табылады: материалды қабыққа ие мәтінге айнала отырып ойлар қабылдауға қол жетімді болады және оны басқа адам түсіне алады. Осылайша, тіл - бұл материалдық емес ойларды материалдық субстанцияға айналдыратын, материалдық символдар арқылы немесе белгілер арқылы кодталуының құралы, сонымен қатар осы субстанция бойынша ойларды декодтау тәсілі. Табиғи тілдің мәтіндері үшін негізгі субстанция болып дыбыстық табылады: бұл есту мүшелері арқылы қабылданатын ауаның тербелісі; графикалық субстанция (көру арқылы қабылданатын мәтіндер) екінші ретті болып табылады. Дыбыстық субстанцияның ауысуының әр түрлі жүйелері (графика немесе жазбаша) адам мәдениетінде маңызды рөл атқарады, алайда табиғи тілдердің барлығына дерлік жасалынбаған және қалыптастырылмаған. Кез келген субстанция сызықтық: ол уақыт бойынша туындайды, кейбір элементтер ерте, келесісі - кешірек. Ой жалпы жағдайда сызықтық емес; сондықтан да ойдан мәтінге ауысу күрделі үрдіс болып табылады және ойлау үрдісіне ықпал етуі мүмкін.
Хабарламаларды кодтау және декодтау адамның сөйлеу қызметінің екі негізгі түрлері болып табылады: сөйлеу және түсіну, басқаша айтқанда мәтіннің туындауы мен қабылдануы. Тілді толыққанды меңгеру сөйлеу қызметінің осы екі түрлерін сәтті орындау қабілетін көрсетеді; мәтінді туындату қабілеті тасушының белсенді компетенциясы деп аталса, басқа біреудің құрастырған мәтіндерін түсіну қабілетін тасушының пассивті компетенциясы деп атайды.
Табиғи тілдерің ерекшеліктері
Табиғи тілдердің ерекшеліктері олардың болмысынан көрінеді. Табиғи тілдерді зерттеуге формалды тәсілді қиындататын негізгі ерекшеліктер төменде суреттелінген.
- синтаксистің семантикаға (мағынасы) тәуелділігі. Мысалы, сөздің аяқталуы осы сөздердің қандай да бір объектіге қатысты, жанды немесе жансыз нәрсеге байланысты болуы мүмкін. Мысал үшін екі ұқсас сөйлемді қарастырайық.
Мен кесілген ағыштың түбін көрдім (Нені?).
Мен досымды көрдім (Кімді?).
- Семантикалық және синтаксистік әркелкілік. Семантикалық әркелкілік кейбір сөздердің әр түрлі мағынаға ие болуынан туындайды. Мысалы, Косой шел с косой сөйлемі контекске байланысты әр түрлі мағынаға ие бола алады. Синтаксистік әркелкілік синтаксистік ережелердің жеткілікті деңгейде қатаң болмауынан туындайды. Бытие определяет сознание сөйлемі әр түрлі талқылануы мүмкін. Егер базалық элемент бытие (болмыс) деп есептесек, онда осы сөйлемді Бытие является главным и оно определяет сознание деген сөйлеммен ауыстыруға болады. алайда бұл сөйлем былайша талқылануы да мүмкін: бытие определяется сознанием.
- парадоксальды ұсыныстардың пайда болу мүмкіндігі. Парадоксальды ұсыныстар оларды шынайыға да, жалғанға да жатқызуға болмайды. Парадоксальды ұсынстардың мысалы ретінде мына сөйлемді айтуға болады: Данное предложение являетс ложным.
- мағынаның жағдайға тәуелдігі;
- тілдің уақытқа байланысты өзгерісі;
- көптеген шектеулері бар синтаксистік көптеген сан.
1.2 Формалды тілдер және олардың ерекшеліктері
Көптеген жасанды тілдер формалды сөйлемдерді құрастыруда пайдаланылады, яғни мағынаға, ережеге тәуелді емес сөйлемдер. Мұндай тілдер формалды деп аталады. Формалды тілдер синтаксисті сөйлемді құрастыруға формалды тәсілді қамтамасыз етуі керек. Сондықтан да формалды тілдер келесідей ерекшеліктерге ие:
- синтаксистік ережелердің мағынаға тәуелсіздігі;
- парадокстардың пайда болу мүмкін еместігі;
- синтаксистік ережелердің қатаңдығы мен шектеулердің болмауы;
- синтаксистік ережелердің соңғы саны.
Формалды тілдер табиғи тілдер секілді уақыт бойынша өзгеруі мүмкін. Алайда табиғи тілдерден айырмашылығы бұл өзгерістер біртіндеп емес, тілдің жаңа версияларының пайда болуымен көрінеді. Сонымен қатар бір тілдің әр түрлі версияларын әр түрлі тілдер деп қарастыруға болады.
Формалды тілдің төменгі синтаксистік бірлігі болып символ табылады. Символ (әріп) - бұл қарапайым бөлінбейтін белгі. Тіл символдарының жиынтығы алфавитті құрайды. Алфавиттің мысалдары:
Орыс алфавиті - {А, а, Б, б, В, в, ..., Я, я }.
Латын алфавиті - {A, a, b, b, C, c, ..., Z, z }.
Араб алфаваиті - { 0, 1, 2, . . . , 9 }.
Тілдің символдары қатарға бірігеді. Қатар - бұл символдардың реттелген кезектілігі. Қатардың мысалдары:
Орыс алфавитіндегі қатарлар - реттелген, кезектілік, а.
Латын алфавитіндегі қатарлар - "BEGIN" , "THEN" , "END".
Екілік (двоичный) алфавиттегі қатарлар - "0", "1", "00", "10", "01010101".
Қатардағы символдар саны қатардың ұзындығы деп аталады. а1а2а3 . . . аn символдарының қатары n ұзындығына ие. Егер қатардың ұзындығы нөлге тең болса, онда қатар бос деп аталады. Бос қатар λ символымен белгіленеді. λ символының алфавит символы еместігін атап өту керек.
А алфавитінің барлық қатарлар жиынтығы А алфавитімен тұйықталу деп аталады және А* символымен белгіленеді.
А* = А0 U А1 U А2 U . . . U Аn =n=0infinityAn (1)
Бұл жерде: А0 Euro{λ} - бос қатар;
Аn - n ұзындығының қатары.
А+ бос емес қатарлардың жиынтығы келесідей анықталады:
А+ = А* \ {λ} =n=1infinityAn (2)
Тіл жалпы жағдайда А* жиынтығының еркін жиынтығын көрсетеді. А* жиынтығы анықтамасы бойынша шексіз болғандықтан, онда тіл де жалпы жағдайда шексіз болады. Сондықтан да тілді ашықтан - ашық, яғни барлық мүмкін болатын қатарларды атап шығу арқылы жасау мүмкін емес. Мысалы, орыс тілінің барлық дұрыс сөйлемдерін атап шығу мүмкін емес. Тілді сипаттау үшін тілдің мүмкін сөйлемдерін жасау ережелерін қысқа формада суреттейтін арнайы жүйе керек. Мұндай жүйені формалды грамматика деп атайды. Формалды грамматиканың көмегімен құрылған тіл формалды тіл деп аталады. Формалды тілді қоса алғандағы тілдің қатарлары белгілі бір мағынаға ие. Тілдің қатарларының мағынасы кейбір қымбат емес қосымша ақпараттардың көмегімен анықталынады.
Формалды грамматиканың типтері
Формалды грамматикалар бір-бірінен тұжырым ережелер типімен ерекшеленеді. Формалды грамматикалардың тұжырым ережесі типі бойынша жіктелімін американ лингвисті Ноам Хомский енгізген болатын. Хомский формалды грамматиканы төрт типке бөлді.
0 типтегі формалды грамматика (шектелмеген грамматика немесе еркін типті грамматика) келесі түрді айырбастауда қолданылады:
α-- β, (3)
Бұл жерде α және β - еркін түрдің тізбектері.
1 типті формалды грамматика немесе контексті грамматика (контексті тәуелді грамматика) келесі түрді айырбастауда пайдаланылады:
Мұнда, A - нетерминалды символ;
, , - еркін түрдің тізбектері, бұл жерде тізбегі бос емес немесе (N U T)+;
, - ережелер контексті.
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 bS.
Осы грамматиканың көмегімен a және b символдарының қатарлары туындайды. Қатарлардың туындау кезектілігін келесі сызба бойынша түсіндіруге болады:
Қолданылатын тұжырым ережесі Қатарлар мазмұны
S
S aS aS
S aS aaS
S b aab
Тұжырым нәтижесі болып aab қатары табылады.
Контекстісіз грамматиканың мысалы: G = {N, T, P, S).
N ={S};
T = {a, b}
P: S aSb; S ab.
Бұл грамматиканың көмегімен anbn түрдегі қатар туындайды.
a3b3 қатар тұжырымының ережесі
Қолданылатын тұжырым ережесі Қатар мазмұны
S
S aSb aSb
S aSb aaSbb
S ab. aaabbb
Күрделірек түрдегі контекстісіз грамматиканың мысалы:G = {N, T, P, S).
N ={S};
T = { IF, THEN, ELSE, U, B}
P: S B;
S IF U THEN S;
S IF U THEN S ELSE S.
Бұл грамматика Паскаль типіндегі тілдің әр түрлі шартты операторларын қалыптастыруға мүмкіндік береді. Мысалы, 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 B
Екінші нұсқа да мүмкін:
Қолданылатын тұжырым ережесі Қатар мазмұны
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 B.
Формалды логика мен информатикада формалды тіл - бұл соңғы алфавиттің соңғы сөздерінің (қатар, тізбек) жиынтығы. Тілді түсіну көбінесе автоматтар теориясында, есептеу теориясында және алгоритмдер теориясында қолданылады. Осы объектімен байланысты ғылыми теория формалды тілдер теориясы деп аталады.
Модельдер теориясында тіл информатика тіліне емес, алфавитке сәйкес келеді. Тіл көптеген символдар, қызметтер мен қарым-қатынастардан, сонымен қатар айнымалылар жиынтығынан тұрады. Осы жиынтықтың әрбіреуі шексіз болуы мүмкін. Тілден оның универсалды логикалық символдарымен бірге логикалық пікір қалыптастырылады.
Формалды тіл әр түрлі анықталуы мүмкін, мысалы, осы тілге енетін сөздердің қарапайым аударылуы. Бұл тәсіл негізінен соңғы тіл мен қарапайым құрылым тілдерін анықтауға қолданылады.
кейбір формалды грамматикадан туындайтын сөздермен;
тұрақты пікірден туындаған сөздермен;
кейбір шекті автомат арқылы танылатын сөздермен;
БНФ - конструкциядан туындаған сөздермен.
Егер алфавит {a, b} деп берілсе, ал L тіл өзіне оған қатысты барлық сөздерді қамтыса, онда ababba сөзі L - ға жатады. Бос сөз, яғни нөлдік ұзындық қатары мүмкін болады және көбінесе e, ε немесе Λ деп белгіленеді.
Формалды тілдердің кейбір мысалдары:
{a, b} барлық сөздердің жиынтығы
жиынтық, онда n -- теріс емес сан, ал a - ның n - рет қайталануын білдіреді
осы бағдарламалау тіліндегі синтаксистік дұрыс бағдарламалардың жиынтығы
Операциялары
Кейбір операциялар мәліметтерден жаңа тілдер туындату үшін пайдаланылуы мүмкін. Мысалы, және кейбір жалпы алфавитпен анықталған тілдер болсын.
* конкатенация (байланысуы) формасын қанағаттандыратын барлық сөздерді қамтиды, онда - бұл сөзі, ал - сөзі.
қиылысуы және - дегі барлық сөздерді қамтиды;
бірігуі немесе - дегі сөздерді қамтиды.
тілін толықтыру алфавиттегі барлық сөздерді қамтиды.
арақатынасы - де сөзі болғандығын, - де болған -ның барлық сөздерін қамтиды.
Клини тұйықталуы формасында жазыла алатын барлық сөздерді қамтиды, онда - де болады және . Бұл бос сөзін де қамтитынын естен шығармау керек, себебі шарт бойынша мүмкін болады.
айналымы -ге айналған сөздерді қамтиды.
және -нің араласуы формасында жазылған барлық сөздерді қамтиды, онда және болып байланысы -де бар сөздер, ал болып -де болатын сөздер табылады.
1.3 Бағдарламалау тілдері (Pascal, Delphi, C, C++, C#)
Бағдарламалау тілі - бұл компьютерлік бағдарламаларды жазуға арналған формалды белгілер жүйесі. Бағдарламалау тілі бағдарламаның сыртқы бейнесі мен компьютердің атқара алатын іс - әрекеттерін көрсететін лексикалық, синтаксистік және семантикалық ережелер жиынтығын білдіреді.
Алғашқы бағдарлама жасайтын машиналарды құрғаннан бастап адамзат екі жарым мыңнан аса бағдарламалау тілдерін (абстрактілі және стандарттық емес тілдерді қосқанда) ойлап тапты. Жыл сайын олардың саны арта түсуде. Кейбір тілдерді тек оны жасаушылардың аз ғана бөлігі пайдалана алады, басқалары миллиондаған адамдарға танымал. Кәсіби бағдарламашылар (программист) кей кездері өздерінің жұмыстарында бағдарламалау тілдерінің оннан аса түрін пайдаланады.
Тілдерді жасаушылар бағдарламалау тілдері түсінігін әр түрлі түсіндіреді. Көптеген жасаушылар мойындаған кең таралған пікірлерге келесілер жатады:
Қызметі: бағдарламалау тілі компьютерге сол немесе басқа есептеу үрдісін жасау және жекелеген құрылғыларды басқаруды ұйымдастыру нұсқаулықтарын беру үшін пайдаланылатын компьютер бағдарламаларын жазуға арналады.
Міндеті: бағдарламалау тілі табиғи тілден оның командалар мен мәліметтерді адамнан компьютерге беруімен ажыратылады, ал табиғи тіл адамдар арасында қарым - қатынас орнату үшін пайдаланылады. Бағдарламалау тілі анықтамасын қорытындылауға болады: бағдарламалау тілі - бұл командалар, бұйрықтар, іс - әрекет жасау бойынша нақты басшылықтар беру тәсілі; ал адам тілі сонымен қатар ақпараттар алмасуы үшін қызмет етеді.
Орындалуы: бағдарламалау тілі мәліметтер құрылымын анықтау мен манипуляциялау және есептеу үрдісін басқару үшін арнайы конструкцияларды пайдалана алады.
Visual Basic -- мектеп оқушыларының білетін жалғыз нәрсесі. Сонымен қатар Mobile Basic телефонда бағдарламалау үшін арналған. Бұл компьютерден ағылшын тілін білетіндерге қолайлы.
PHP -- бастамашы дамушының өзін-өзі жетілдіру үшін қажет. Онда drupal, joomla, wordpress және mediawiki қоса алғандағы сіздің көптеген cms жазылған.
Python -- бұл школота бағдарламалауын оқыту үшін таптырмайтын тіл.
Pascal -- басқа қарапайым тілдер жайлы білмейтін жас оқушыларды оқытуға пайдаланылады.
Delphi -- 7 версиясы
C# -- Visual Basic - тің мұрагері немесе Java, С++ және Delphi - ді будандастыру талпыныстары.
1С -- win - 1251 - ге ауыстырылған Кобол.
Java -- оны барлық жерде пайдаланады.
C++. Бұл өте танымал, соның ішінде Линусу Торвальдсқа да. Тышқанмен бағдарламалау үшін IDE бар. Нуфф саид.
Си (бағдарламалау тілі)
Си -- стандартталған процедуралық бағдарламалау тілі. Оны 1970 жылдың басында Bell Labs қызметкерлері Кен Томпсон мен Деннис Ритчи жасады. Си UNIX операциялық жүйесінде пайдалану үшін жасалынған болатын. Содан бері ол басқа да көптеген операциялық жүйеге ауыстырылып, өте көп қолданылатын бағдарламалау тілдерінің біріне айналды. Си - ді оның тиімділігі үшін бағалайды. Ол жүйелік бағдарламалық қамтамасыз етуді құру үшін танымал тіл болып табылады. Оны көбінесе қолданбалы бағдарламаларды қалыптастыру үшін де пайдаланады. Си жаңа үйрене бастаған адамдарға арнап шығарылмаса да бағдарламалауды оқытуда белсенді пайдаланылады. Си тілінің синтаксисі басқа да көптеген тілдер үшін негіз болды.
Си тілі үшін ықшамдылық, орындау ағынын басқарудың конструкциясының стандартты жиынтығы, мәліметтер құрылымы мен операциялардың кең жиынтығы тән.
Ерекшеліктері.
Си бағдарламалау тілі минимализммен ерекшеленеді. Тілдің авторлары ондағы бағдарламалардың біржақты компилятордың көмегімен оңай компиляциялануын қалады. Себебі әрбір бағдарламаның қарапайым құраушысына компиляциядан кейін машиналық команданың аз ғана саны сәйкес келді, ал базалық тілдерді пайдалану орындау уақыты бойынша кітапхананы әрекетке қоспады. Біржақты компилятор артқа қайтпай, бағдарламаны компиляциялайды. Сондықтан да қызметтер мен айнымалыларды пайдалану олардың хабарламаларын бұрын болуы керек. Си - ге кодты абстракцияның төменгі деңгейінде оңай жазуға болады. кей кездері Си - ді универсалды ассемблер немесе жоғары деңгейлі ассемблер деп те атайды. Си оның нақты құрылғылармен жақын етене жұмыс жасауын ескере отырып, көбінесе орта деңгейлі немесе тіпті төменгі деңгейлі тіл деп те аталады. Алайда қатаң жіктелімде ол жоғаы деңгейлі болып табылады.
C++ -- жалпы тағайындаудың тұрақты типті бағдарламалау тілі. Сонымен қатар процедуралық бағдарламалау, объектіге бағытталған бағдарламалау, жинақталған бағдарламалау сияқты бағдарламалау парадигмаларын қолдайды, модульділікті, бөлінген компиляцияны, айырмашылықты өңдеуді, мәліметтер абстракциясын, объектілер типін хабарлауды, виртуалды қызметтерді қамтамасыз етеді. Стандартты кітапхана жалпы пайдаланылатын контейнерлер мен алгоритмдерді қамтиды. C++ жоғары деңгейлі және төменгі деңгейлі тілдердің де қасиеттерін қамтиды. Оны С тілімен салыстырғанда онда объектіге бағдарлануға және жинақталған бағдарламалауға көп назар аударылған.
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)+ мен α = β түрде болса, онда G = (VT, VN, P, S) қысқартылмайтын деп атайды. Егер Р ережесінің әрбіреуі келесідей түрге ие болса: α -- β , бұл жерде α = ξ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--AFBAB
AB -- bBA
Ab --bA
AD -- D
Cb -- bC
CB --C
bCD --λ
Тіл типі 1: L = {бірдей 0 мен 1 сандары бар 0 мен 1 тізбектер}
P: S--ASB AB
AB -- BA
A -- 0
B -- 1
Тіл типі 2: L = {(ac)n (cb)n n 0}
P: S--aQbaccb
Q -- cSc
Тіл типі 3: L = {ω ω ∈ {a,b}+, қасында бірге тұрған a жоқ жерде}
P: S -- A⊥ B⊥
A -- a Ba
B--bBb Ab
Танушылардың тілдің типі бойынша жіктелімі
Танушының күрделілігі кіру тізбегін танушы қабылдай алатын тілдің типімен тікелей байланысты. Жоғарыда аталынған тілдің төрт типінің әрбіреуі үшін компоненттің белгілі бір құрамы бар, соған сәйкес алгоритм жұмысының күрделігі бар өзінің танушыларының типі болатыны дәлелденген.
Фразалық құрылымы бар тілдер (тип 0) үшін шексіз сыртқы есі бар детерминделмеген автомат қажет. Сондықтан да осы типтегі тілдер үшін шектеулі уақытта шектеулі есептеуіш ресурстарда танушы жұмысты аяқтайды және кіру тізбегі берілген тілге жататыны немесе жатпайтыны туралы шешім қабылдайтынына кепілдік беруге болмайды.
Контексті тәуелді тілдер (тип 1) үшін танушылар сызықтық шектеулі сыртқы есі бар екі жақты детерминделмеген автоматтар болып табылады. Мұндай автоматтың жұмысының алгоритмі жалпы жағдайда экспоненциалды күрделілікке ие - автоматқа кіру тізбегін тану үшін қажет қадамдар саны осы тізбектің ұзындығына экспоненциалды тәуелді. Соған сәйкес, берілген алгоритм бойынша кіру тізбегін талдауға қажет уақыт та кіру тізбегінің ұзындығына экспоненциалды тәуелді.
Танушының осындай алгоритмі жүзеге асырылуы мүмкін - кіру тізбегінің ұзындығын біле отырып, әрқашан да осы тілге тізбектің жатуы туралы шешім қанша уақытта қабылданатыны және қандай есептеуіш ресурстары қажет екенін айтуға болады. алайда талдау уақытының тізбектің ұзындығына экспоненциалды тәуелділігі танушыларды контексті тәуелді тілдер үшін пайдалануын шектейді. Мұндай танушылар автоматтандырылған ауысым мен табиғи тілдегі мәтіндерді мәтінді талдау үшін уақыт шектеулері аса маңызды емес жағдайда талдау үшін пайдаланылады (себебі табиғи тілдер контексті тәуелді тілдерге қарағанда күрделірек, сондықтан осындай өңдеуден кейін адамның араласуы керек).
Компиляторларда контексті тәуелді танушылар пайдаланылмайды, себебі компилятордың жұмыс жасау жылдамдығы маңызды болып табылады, ал бағдарламаның мәтінін синтаксистік талдауды контексті еркін тілдер секілді қарапайымдырақ тілдер шегінде орындауға болады.
Контексті еркін тілдерге (тип 2) арналған танушылар айдағыш сыртқы есі бар біржақты анықталмаған автоматтар болып табылады. Осындай автоматтың жұмысының алгоритмін қарапайым жүзеге асыру барысында ол экспоненуиалды жылдамдыққа ие, алайда алгоритмнің кейбір жетілдірулері арқылы кіру тізбегін талдауға қажет уақыттың осы тізбектің ұзындығына полимиалды тәуелділігіне қол жеткізуге болады. соған сәйкес контексті еркін тілдер үшін танушылардың колимиалды күрделігі туралы айтуға болады.
Барлық контексті еркін тілдердің арасында анықталған контексті еркін тілдер сыныбын ажыратып көрсетуге болады. Олардың танушылары айдағыш сыртқы есі бар детерминделген автоматтар болып табылады. Бұл тілдер бір мағыналық қасиетке ие, кез келген анықталған контексті еркін тілдер үшін әрқашан да бір мағыналы грамматиканы тұрғызуға болатыны дәлелденген. Бұдан басқа, осындай тілдер үшін квадраттық күрделігі бар танушылардың жұмысының алгоритмі бар. Осы тілдер бір мағыналы болып табылғандықтан олар компиляторларды тұрғызу үшін жоғары қызығушылық тудырады.
Сонымен қатар анықталған контексті еркін тілдердің ішінде сызықтық танушы тұрғызу мүмкін тілдердің сыныптары бар. Сызықтық танушылар - бұл тізбектің тілге жатуы туралы шешім қабылдау уақыты тізбектің ұзындығына сызықтық тәуелді болатын танушы. Бағдарламалаудың барлық тілдерінің синтаксистік конструкциялары осындай тілдердің сыныбының біреуіне жатқызылуы мүмкін.
Бағдарламалау тілдерінің синтаксистік конструкциялары ғана контексті еркін тілдердің танушыларының көмегімен талдауға рұқсат берілетінін естен шығармау керек. Бағдарламалау тілдерінің өздері контексті еркін тілдер тиіне толықтай жатқызылмайды, себебі ағымдағы бағдарламаның мәтінінде кейбір контексті тәуелділікті көрсетеді. Мысалы, айнымалылардың алдын ала сипатталу қажеттілігі. Сондықтан да синтаксистік талдаудан басқа барлық компиляторлар ағымдағы бағдарламаның мәтінін қосымша семантикалық талдауды көрсетеді. Бұны болдырмауға болар еді, егер компиляторды контексті тәуелді танушының негізінде тұрғызғанда, алайда мұндай компилятордың жұмысының жылдамдығы өте төмен болар еді. Себебі мұндай варианттаға талдаудың уақыты ағымдағы бағдарламаның ұзындығына экспоненциалды тәуелді болады. контексті еркін тілдер танушылары мен қосымша семантикалық анализатордың комбинациясы ағымдағы бағдарламаны талдау жылдамдығы тұрғысынан тиімдірек болып табылады.
Тұрақты тілдер (тип 3) үшін танушылар сыртқы ессіз анықталған автоматтар - шекті автоматтар болып табылады. Бұл өте қарапайым танушының типі, әрқашан кіру тізбегін талдау уақытының тізбектің ұзындығына сызықтық тәуелділігін көрсетеді. Бұдан басқа шекті автоматтар маңызды ерекшелікке ие: кез келген анықталмаған соңғы автомат әрқашан детерминделгенге өзгертілуі мүмкін. Бұл жағдай танушының қызметін қамтамасыз ететін бағдарламалық қамсыздандыруды жасауды жеңілдетеді. Танушылардың жұмысының қарапайымдылығы мен жоғары жылдамдығы тұрақты тілдердің пайдалануының кең облысын анықтайды.
Компиляторларда танушылар тұрақты тілдер негізінде ағымдағы бағдарламаның мәтінін лексикалық талдау үшін пайдаланылады. Тұрақты тілдер танушыларының негізінде ассемблерлер қызмет етеді.
Бұдан басқа тұрақты тілдер есептеуіш жүйені бағдарламалық қамсыздандыруды жасаумен байланысты көптеген облыстарда пайдаланылады. Олардың негізінде көптеген командалық процессорлар жүйелік те, қолданбалы бағдарламалық қамсыздандыруда да қызмет етеді. Тұрақты тілдер үшін танушылардың құрылуын жеңілдетуге мүмкіндік беретін, математикалық негізделген, дамыған механизмдер бар.
2.2 Қысқартылмайтын тілдер (неукорачивающие языки) мен олардың ерекшеліктері
Трансляцияның формалды модельдері бұрын қарастырғандай синтаксистік құрылымдарды оқуға қатысты компиляция теориясының бөлімі стандарты болып келеді және де контексті еркін тілдер теориясына негізделеді.
Программалау тілінің синтаксистік формалды анықталуы әдетте грамматика деп аталады. Грамматика программалау тілдің анықталуы үшін мүмкін символдар тізбегін анықтайтын ережелер жиынтығынан тұрады. Формалды грамматика дегеніміз қатаң белгілеулер жүйесінен тұратын грамматика, компиляциялау технологиясында грамматиканың 2 класы қолданылады.
1) БНФ грамматика немесе контекстілі еркін грамматика
2) Регулярлы грамматика
БНФ грамматика. Ағылшын тіліндегі сөйлем құрылымын қарастыра отырып оның категориялары тілдегі қарапайым хабарлас сөйлем мынадай сөйлемнен тұрады:
Бастауыш етістік толықтауыш The gіrl (runs) home.
Әрбір категория өз кезегінде ішкі категорияларға бөлінуі мүмкін. Мысалы: жоғарыдағы құрылымда бастауыш артикль және зат есімнен тұрады. Олай болса құрылым былай жазылуы мүмкін.артикль зат есім етістік толықтауыш
Бұдан басқа сұраулы сөйлемдердің де құрылымы былай жазылады:
Көмекші етістік бастауыш баяндауыш
Мысалы: dіd the gіrl run home?
Келтірілген сөйлемдерді қандай да бір ереженің жиынтығы арқылы сипатттау мүмкін. Яғни біз сөйлемнің хабарлы не сұраулы болатынын айта аламыз немесе оны былай жазуға болады:
сөйлем::=хабарлысұраулы. Мұндағы :: = белгісі - аталған категорияның белгілерінің оң жағындағы ішкі категорияға бөліну мүмкіндігін білдіреді. Яғни келтірілген құрылымды былайша оқиды. Сөйлемдердің келесі тармақталуы былайша анықталады:
хабарлы::=бастауышетістіктол ықтауыш
бастауыш::=артикльзат есім
сұраулы::= қосымша етістікбастауышбаяндауыш
Осылайша, арнайы жазуды БНФ - Бэкустың нормаль формалары деп атады. Оны 50 - ші жылдардың соңында algol тілінің синтаксистік анықталуы ретінде пайдаланып жария етті. Шамамен осы жылдары Ноам Хомский осыған ұқсас грамматикалық форманы ұсынып, оны контекстілі еркін грамматика деп атады. Ол табиғи тілдердің синтаксисін келтіру үшін арналды. БНФ және контекстілі еркін грамматика формалары мүмкіндіктері жағынан эквивалентті болып келеді. Айырмашылығы - олардың белгілеулер жүйесінде ғана, сондықтан синтаксис мәселен талқылау барысында БНФ грамматика және контексті еркін грамматика терминдері өзара бірін - бірі ауыстыратын сөздер ретінде қолданылады.
БНФ грамматиканың синтаксисі. БНФ грамматика программалау тілдерін анықтайтын грамматика ережелерінің аяқталған жиынтығынан тұрады. Бұл ережелерді қарастырмас ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz