Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Теорія програмування — це категоріальний (поняттєвий) аналіз процесу програмування. Поняття визначаються у єдності їх двох моментів: змісту (інтенсіоналу) та обсягу (екстенсіоналу).
Звідси випливає, що для теорії програмування найважливішим є не конкретна програма, а відношення між програмними поняттями (тобто не стільки предметна, екстенсіональна складова, скільки логічна, інтенсіональна). Тому вміння писати конкретні програми ще не означає розуміти теорію програмування. Тут є аналогія з політикою, бо задача політики є не стільки безпосередня робота з пересічною людиною, скільки вибудова суспільних відносин.
Формалізація простої мови програмування
Центральним завданням теорії, зокрема і теорії програмування, є визначення та дослідження її основних понять. Зробити це не так просто, бо в теоріях, як правило, використовується багато понять, які пов’язані одне з одним. Тому спочатку доцільно ввести основні поняття теорії програмування на невеликому прикладі. Це буде програма знаходження найбільшого спільного дільника двох чисел. Програма записана на деякій простій мові. Ця мова буде формалізована, тобто буде описано її синтаксис і семантику, та їх зв’язок.
Неформальний опис простої мови програмування
Для посилання на певну мову треба надати їй ім’я. Для імені часто використовують абревіатуру короткої характеристики мови. Зважаючи на традиції використання латинських літер у науковій символіці, утворимо абревіатуру SIPL від характеристики SImple Programming Language (Проста Мова Програмування). Цю абревіатуру можна розшифрувати по-іншому, вказуючи на імперативність або структурованість цієї мови: "SIPL" – Simple Imperative Programming Language, "SIPL" – Structured Imperative Programming Language. Говорячи неформально, мова SIPL має числа та змінні цілого типу, над якими будуються арифметичні вирази та умови. Основними операторами є присвоєння, послідовне виконання, розгалуження, цикл. Мова SIPL може розглядатися як надзвичайно спрощена традиційна мова програмування, наприклад, Паскаль. У мові SIPL відсутні складні типи даних, оператори вводу-виводу, процедури та багато інших конструкцій традиційних мов програмування. Також немає явної типізації. Разом із тим ця мова є досить потужною, щоб програмувати різні арифметичні функції, більше того, в цій мові можуть бути запрограмовані всі обчислювані функції над цілими числами. Мета розгляду саме такої мови програмування полягає в тому, щоб формалізація та дослідження цієї мови були якомога простішими.
Приклад
Програма GCD знаходження найбільшого спільного дільника чисел M та N за алгоритмом Евкліда: GCD ≡ begin while ¬M=N do if M>N then M:=M–N else N:=N–M end Тут ¬M=N означає M≠N. Оскільки програми призначені для обчислення результатів за вхідними даними, розглянемо неформально процес виконання цієї програми на вхідних даних, у яких M має значення 8, а N – 16. Вважаємо, що дані записуються в пам’ять, а оператори виконуються деяким процесором. Тому розмітимо програму, відмічаючи оператори мітками: 0: begin 1: while ¬M=N do 2: if M>N then 3: M:=M–N else 4: N:=N–M end Процес виконання програми можна подати у вигляді таблиці, кожний рядок якої вказує на номер виконуваного оператора та на нові значення змінних. Для нашого прикладу ця таблиця може мати такий вигляд.
| Мітка | Значення умови | Значення M | Значення N |
|---|---|---|---|
| 0 | 8 | 16 | |
| 1 | ¬M=N – true | ||
| 2 | M>N – false | ||
| 4 | 8 | ||
| 1 | ¬M=N – false |
Програма припиняє роботу із значеннями M та N, рівними 8. Це число і є найбільшим спільним дільником. Аналізуючи цю програму та процес її виконання, відзначаємо два аспекти: • синтаксичний (текст програми); • семантичний (смисл програми – те, що вона робить). У нашому прикладі ні синтаксис, ні семантика не задані точно (формально). Ми маємо лише інтуїтивне розуміння програм мови SIPL.
Формальний опис синтаксису мови SIPL
Для опису синтаксису мов зазвичай використовують БНФ (Форми Бекуса-Наура). Програми (або їхні частини) виводяться із метазмінних (нетерміналів), які записуються у кутових дужках. Метазмінні задають синтаксичні класи. У процесі виводу метазмінні замінюються на праві частини правил, що задають ці метазмінні. Праві частини для однієї метазмінної розділяються знаком альтернативи «|». Процес породження припиняється, якщо всі метазмінні замінено на термінальні символи (тобто символи без кутових дужок). Синтаксис мови SIPL можна задати за допомогою такої БНФ.
| Ліва частина правила – метазмінна (дефінієндум) | Права частина правила (дефінієнс) | Ім’я пра- вила |
|---|---|---|
| <програма> ::= | begin <оператор> end | NP1 |
| <оператор> ::= | <оператор> ; <оператор>| if <умова> then <оператор> else <оператор> | while <умова> do <оператор> |begin <оператор> end | | NS1-NS6 |
| <вираз> ::= | <змінна> | <вираз> + <вираз> | <вираз> – <вираз> | <вираз> * <вираз> | (<вираз>) | NA1– NA6 |
| <умова> ::= | <вираз> > <вираз> | <умова> ∨ <умова> | ¬ <умова> | (<умова>) | NB1– NB5 |
| <змінна> ::= | N|... | NV... |
| <число> ::= | 0 | 1 | 2 | 3 | . . . | NN... |
Наведена БНФ задає мову SIPL як набір речень (слів), які виводяться з метазмінної <програма>.
Див. також
Література
- Зубенко В.В. Програмування : навчальний посібник (гриф МОН України) / В.В. Зубенко, Л.Л. Омельчук. - К. : ВПЦ "Київський університет", 2011. - 623 c.
- Нікітченко М.С. Теоретичні основи програмування : навчальний посібник / М.С Нікітченко - Ніжин : Видавництво НДУ імені Миколи Гоголя, 2010. - 121с.
| Ця стаття потребує додаткових для поліпшення її . (березень 2017) |
 | Це незавершена стаття про інформаційні технології. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teoriya programuvannya ce kategorialnij ponyattyevij analiz procesu programuvannya Ponyattya viznachayutsya u yednosti yih dvoh momentiv zmistu intensionalu ta obsyagu ekstensionalu Zvidsi viplivaye sho dlya teoriyi programuvannya najvazhlivishim ye ne konkretna programa a vidnoshennya mizh programnimi ponyattyami tobto ne stilki predmetna ekstensionalna skladova skilki logichna intensionalna Tomu vminnya pisati konkretni programi she ne oznachaye rozumiti teoriyu programuvannya Tut ye analogiya z politikoyu bo zadacha politiki ye ne stilki bezposerednya robota z peresichnoyu lyudinoyu skilki vibudova suspilnih vidnosin Formalizaciya prostoyi movi programuvannyaCentralnim zavdannyam teoriyi zokrema i teoriyi programuvannya ye viznachennya ta doslidzhennya yiyi osnovnih ponyat Zrobiti ce ne tak prosto bo v teoriyah yak pravilo vikoristovuyetsya bagato ponyat yaki pov yazani odne z odnim Tomu spochatku docilno vvesti osnovni ponyattya teoriyi programuvannya na nevelikomu prikladi Ce bude programa znahodzhennya najbilshogo spilnogo dilnika dvoh chisel Programa zapisana na deyakij prostij movi Cya mova bude formalizovana tobto bude opisano yiyi sintaksis i semantiku ta yih zv yazok Neformalnij opis prostoyi movi programuvannya Dlya posilannya na pevnu movu treba nadati yij im ya Dlya imeni chasto vikoristovuyut abreviaturu korotkoyi harakteristiki movi Zvazhayuchi na tradiciyi vikoristannya latinskih liter u naukovij simvolici utvorimo abreviaturu SIPL vid harakteristiki SImple Programming Language Prosta Mova Programuvannya Cyu abreviaturu mozhna rozshifruvati po inshomu vkazuyuchi na imperativnist abo strukturovanist ciyeyi movi SIPL Simple Imperative Programming Language SIPL Structured Imperative Programming Language Govoryachi neformalno mova SIPL maye chisla ta zminni cilogo tipu nad yakimi buduyutsya arifmetichni virazi ta umovi Osnovnimi operatorami ye prisvoyennya poslidovne vikonannya rozgaluzhennya cikl Mova SIPL mozhe rozglyadatisya yak nadzvichajno sproshena tradicijna mova programuvannya napriklad Paskal U movi SIPL vidsutni skladni tipi danih operatori vvodu vivodu proceduri ta bagato inshih konstrukcij tradicijnih mov programuvannya Takozh nemaye yavnoyi tipizaciyi Razom iz tim cya mova ye dosit potuzhnoyu shob programuvati rizni arifmetichni funkciyi bilshe togo v cij movi mozhut buti zaprogramovani vsi obchislyuvani funkciyi nad cilimi chislami Meta rozglyadu same takoyi movi programuvannya polyagaye v tomu shob formalizaciya ta doslidzhennya ciyeyi movi buli yakomoga prostishimi Priklad Programa GCD znahodzhennya najbilshogo spilnogo dilnika chisel M ta N za algoritmom Evklida GCD begin while M N do if M gt N then M M N else N N M end Tut M N oznachaye M N Oskilki programi priznacheni dlya obchislennya rezultativ za vhidnimi danimi rozglyanemo neformalno proces vikonannya ciyeyi programi na vhidnih danih u yakih M maye znachennya 8 a N 16 Vvazhayemo sho dani zapisuyutsya v pam yat a operatori vikonuyutsya deyakim procesorom Tomu rozmitimo programu vidmichayuchi operatori mitkami 0 begin 1 while M N do 2 if M gt N then 3 M M N else 4 N N M end Proces vikonannya programi mozhna podati u viglyadi tablici kozhnij ryadok yakoyi vkazuye na nomer vikonuvanogo operatora ta na novi znachennya zminnih Dlya nashogo prikladu cya tablicya mozhe mati takij viglyad Mitka Znachennya umovi Znachennya M Znachennya N 0 8 16 1 M N true 2 M gt N false 4 8 1 M N false Programa pripinyaye robotu iz znachennyami M ta N rivnimi 8 Ce chislo i ye najbilshim spilnim dilnikom Analizuyuchi cyu programu ta proces yiyi vikonannya vidznachayemo dva aspekti sintaksichnij tekst programi semantichnij smisl programi te sho vona robit U nashomu prikladi ni sintaksis ni semantika ne zadani tochno formalno Mi mayemo lishe intuyitivne rozuminnya program movi SIPL Formalnij opis sintaksisu movi SIPL Dlya opisu sintaksisu mov zazvichaj vikoristovuyut BNF Formi Bekusa Naura Programi abo yihni chastini vivodyatsya iz metazminnih neterminaliv yaki zapisuyutsya u kutovih duzhkah Metazminni zadayut sintaksichni klasi U procesi vivodu metazminni zaminyuyutsya na pravi chastini pravil sho zadayut ci metazminni Pravi chastini dlya odniyeyi metazminnoyi rozdilyayutsya znakom alternativi Proces porodzhennya pripinyayetsya yaksho vsi metazminni zamineno na terminalni simvoli tobto simvoli bez kutovih duzhok Sintaksis movi SIPL mozhna zadati za dopomogoyu takoyi BNF Liva chastina pravila metazminna definiyendum Prava chastina pravila definiyens Im ya pra vila lt programa gt begin lt operator gt end NP1 lt operator gt lt operator gt lt operator gt if lt umova gt then lt operator gt else lt operator gt while lt umova gt do lt operator gt begin lt operator gt end NS1 NS6 lt viraz gt lt zminna gt lt viraz gt lt viraz gt lt viraz gt lt viraz gt lt viraz gt lt viraz gt lt viraz gt NA1 NA6 lt umova gt lt viraz gt gt lt viraz gt lt umova gt lt umova gt lt umova gt lt umova gt NB1 NB5 lt zminna gt N NV lt chislo gt 0 1 2 3 NN Navedena BNF zadaye movu SIPL yak nabir rechen sliv yaki vivodyatsya z metazminnoyi lt programa gt Div takozhMova programuvannyaLiteraturaZubenko V V Programuvannya navchalnij posibnik grif MON Ukrayini V V Zubenko L L Omelchuk K VPC Kiyivskij universitet 2011 623 c Nikitchenko M S Teoretichni osnovi programuvannya navchalnij posibnik M S Nikitchenko Nizhin Vidavnictvo NDU imeni Mikoli Gogolya 2010 121s Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno berezen 2017 Ce nezavershena stattya pro informacijni tehnologiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi