22951

Мова Сі

Лекция

Информатика, кибернетика и программирование

Дамо індуктивне визначення термів. Розрізнюють три види типізованих термів: префіксні інфіксні та постфіксні. Існує ще один вид термів змішані коли в індуктивному переході одночасно використовується два або і всі три різновиди термів. На практиці з метою спрощення запису термів приймаються ті чи інші угоди.

Русский

2013-08-04

240.5 KB

1 чел.

ТЕМА: Мова Сі.

З точки зору розглянутих нами класифікацій МП мова Сі є універсальною МП високого рівня з широкими сферами застосування. Первісно Сі була створена Деннісом Річі (Dennis M. Ritchie) у 1982 р. як просто робочий інструмент  написання ОС UNIX  для машини PDP-11 і реалізована в рамках цієї ОС. По суті і сама  ОС, і Сі-компілятор і майже всі компоненти системи були написані на Сі.    Однак як з’ясувалось, завдяки вдалим рішенням авторів мови (а їх кредо було  - отримати певний гібрид МП високого рівня з елементами мов асемблерного рівня), вона  в багатьох випадках виявилася зручнішою, гнучкішою  і ефективнішою ніж  більш потужні мови і тому заслужено отримала широке розповсюдження. Сьогодні мова Сі реалізована практично  на всіх існуючих  ЕОМ. Популярності мови сприяє також широке застосування ОС UNIX в сучасних системах обробки даних, у тому числі розподілених.

Метазасоби

Для того щоб вивчати ту чи іншу мову  необхідно мати певну метамову.

Метамовою по відношенню до даної мови (мови-об’єкту) виступає  мова, яка використовується для опису синтаксису, семантику та прагматики останньої.

Для опису семантики конструкцій мови Сі ми будемо використовувати природню мову, структурні блок-схеми, терми, структури автоматів з програмним керуванням (АПК).

Терми. Дамо індуктивне визначення термів. Зафіксуємо певні  алфавіти символів  ,   та . Символи  та слова вигляду  будемо називати відповідно типом та  функціональним типом. Функціональні типи вигляду , які відповідають випадку , будемо називати константними. Співставимо  довільним чином кожному символу  певний функціональний тип , а кожному символу    певний тип . Факт такого співставлення будемо  позначати як  або  та , а самі символи () та  називати відповідно типізованими функціональними символами (типізованими константами у випадку типу  ) та типізованими змінними. Алфавіти  та   типізованих функціональних символів та змінних  будемо називати відповідно функціональною сигнатурою та сигнатурою змінних. Розрізнюють три види типізованих термів: префіксні, інфіксні та постфіксні.

ІDef. Префіксні терми:

(Б)  Типізовані константи та змінні сигнатур  та  , допоміжні символи: (,) та кома « ,» .

(Іп) Нехай   : й функціональний символ сигнатури  ,  – типізовані префіксні терми з типами ,,…,  відповідно. Тоді вираз     є префіксним термом типу.

(Пс)  Всі  конструкції, визначені в п.п. (Б) та  (Iп), за виключенням  допоміжних символів,  є префіксними термами.

Приклади….

ІDef. Постфіксні терми:

(Б)  Типізовані константи та змінні сигнатур  та  , допоміжні символи: (,) та кома « ,» .

(Іп) Нехай   : й функціональний символ сигнатури  ,  – типізовані префіксні терми з типами ,,…,  відповідно. Тоді вираз     є постфіксним термом типу.

(Пс)  Всі  конструкції, визначені в п.п. (Б) та  (Iп), за виключенням  допоміжних символів,  є постфіксними термами.

Приклади…

                     Інфіксні терми:

             

(Б)  Типізовані константи та змінні сигнатур  та  , допоміжні символи: (,) та кома « ,» .

(Іп) Нехай   : й бінарний функціональний символ сигнатури  ,  – типізовані префіксні терми з типами  та відповідно. Тоді вираз     є інфікс ним термом типу.

(Пс)  Всі  конструкції, визначені в п.п. (Б) та  (Iп), за виключенням  допоміжних символів,  є інфіксними термами.

Приклади …..

Існує ще один вид термів – змішані, коли в індуктивному переході одночасно використовується два  або  і всі три різновиди термів. Найчастіше в програмуванні використовуються саме змішані терми.

Зауваження. На практиці з метою спрощення запису термів приймаються ті чи інші угоди.

  1.  Опускають зовнішні дужки. Особливо часто у випадках унарних функцій  та бінарних операцій. Нпр.,  пишуть sin x [=sin(x)], lg n[=lg(n)], x+y[=(x+y)] і т.д.
  2.  Якщо в  межах певного контексту сигнатура фіксована, то тип функціонального символу як правило не вказується, а залишається ніби як «за дужками». Нпр.,  замість терму   пишуть  або замість     вживають    і т.д.
  3.  Для спрощення запису інфіксних термів можуть опускатися не тільки зовнішня пара дужок, а  і деякі  пари внутрішніх дужок. При цьому фіксуються певний пріоритет операцій, який за допомогою тих чи інших  угод дозволяє однозначно відновити відсутні дужки. Нпр., серед чотирьох арифметичних  операцій виділяють адитивні (+,-) та мультиплікативні () і мультиплікативні «призначаються»  старшими, а серед однорівнених операцій  дужки відновлюються «зліва-направо». Нпр.,  1)  означає  , 2)   означає   і т.д.

Семантика термів.Кожному терму відповідає певна процедура обчислення його значення при заданих значеннях змінних. Для обчислення значення термів необхідно проінтерпретувати їх сигнатуру. Для цього необхідну вибрати певну багатосортну алгебру . А саме,  кожному типу  співвіднесемо певний сорт значень - . Будемо  говорити , що багатосортна функція  вигляду :має тип і позначати її .
Кожному функціональному символу сигнатури   співвіднесемо певну багатосортну функцію вигляду   типу  . Залишилось означити  кожну змінну  типу  сигнатури    певним значенням  з сорту, що відповідає типу . Тоді значення Зн() довільного префіксного терму   можна визначити індуктивно за структурою термів.

 

(Б)  Зн() =  .

(Іп) Нехай   має вигляд  . Тоді  

      Зн()=

(П) Інших значень терму немає.

Аналогічно визначається правило для обчислення значень інфіксних та  постфіксних термів.

Приклад. Розглянемо  арифметичний терм . Нехай  Зн,  Зн, Зн. За визначенням маємо:  і ,  . Зн. Тоді  Зн

Існує ще один вид термів – змішані, коли в індуктивному переході використовується більше ніж одна форма термів. Найчастіше в програмуванні використовуються саме змішані форми термів.

Дерева Канторовича.  

………  

Синтаксичні  діаграми. Для подання синтаксису МП розроблено багато спеціальних формалізмів. Одні з них орієнтовані на математичне вивчення (формальні граматики, автомати) інші на користувача. До останніх належать,  так звані,  – синтаксичні діаграми (СД),  запропоновані  Н.Віртом.

СД – це метазасоби для подання синтаксису і є певним удосконаленим варіантом БНФ (Дж.Бекус, Алгол-60). Усяка МП має певний алфавіт основних символів, який на практиці задається певною  кодовою таблицею. Широко розповсюдженою такою таблицею є ASCII (American Standard Cod for Information Interchange ) та її національні варіанти. Усяка МП має фіксований лексикон – сукупність базових синтаксичних одиниць (лексем),  які побудовані з основних символів,  і з  яких в свою чергу будуються всі інші  синтаксичні конструкції мови. Нпр., у мові Сі визначено 6 класів  лексем.

1. Константи. Числа та символи: 7,  3.14,  025(=2*8+5),  0хFF(=15*16+15=255),  ‘0(=48),  ‘A(=63), \n,\t,  \0(=0),  \25(=2*8+5), \x25(=2*16+5), \”, \’, \\ і т.п.

2. Ключові (зарезервовані) слова: while,  do, if, …

3. Ідентифікатори: Flag, flag,…

4. Роздільники:  +, -, *, ?, !, . , , , _, =, …..

5. Коментарі: /*…..*/, /*Факультет кібернетики – це супер!!!*/, …

6. Літерали:  “….”, “FOLI=FOrth+LIsp”, …

Зауваження. В програмах будь-які сусідні константи, ідентифікатори та службові слова повинні розділятися одним, або кількома «порожніми» символами: ‘ ’,\t,\v,\n,\f. Прогалики  між сусідніми лексемами необов’язкові,  якщо однією з них є роздільник, коментар або знак операції.

СД являє собою систему певних графів (під діаграм) на площині з вершинами, які мають вигляд:

 

і з’єднані між собою стрілками (більш строге означення графа розглядається в  курсі ДМ).  Кожна   з піддіаграм має рівно одну вхідну и вихідну стрілки. Вершини-лексеми вказують на конкретні лексеми, що входить в дану конструкцію та на їх місце в ній. Кожна з вершин-метазмінних, що фігурує в СД,  має свою  синтаксичну піддіаграму в системі, яка визначає правильно побудовані синтаксичні конструкції, що відповідають їй. Серед усіх метазмінних виділяють одну як головну (аксіому). Решта вважаються допоміжними. Саме сукупність правильно побудованих синтаксичних конструкцій, що відповідають аксіомі і є тією сукупністю, заради якої і пишеться вся СД. Як діє  сам механізм  породження правильних конструкцій в СД  розглянемо на прикладі СД, що задає поняття  «ідентифікатор»  МП. Ідентифікатор - це довільне  слово, що розпочинається з латинської букви і складається  з  букв, десяткових цифр та деяких спец. символів.  СД включає аксіому – < ідентифікатор>,    і три метазмінних  :  <  буква>,  < цифра>, < роздільник>. Відповідна СД складається  з 4-х   піддіаграм:

          <  буква>                                    < цифра>                                  < роздільник>

 <ідентифікатор>

 

З аксіомою  <ідентифікатор> пов’язується сукупність слів ( так званих,  словоформ), що відповідають  усім повним шляхам в її діаграмі. Оскільки піддіаграма циклічна, то таких шляхів, а значить і словоформ – злічена кількість. Для побудови відповідної словоформи  послідовно конкатенуються   лексеми та метазмінні усіх вершин, що належать даному повному  шляху. У нашому випадку всі такі словоформи розпочинаються з метазмінної <  буква>   і  далі за стрілками можуть слідувати в довільному порядку будь-яка кількість метазмінних з числа <буква>,<цифра>  та  < роздільник>. В свою чергу  кожній з цих словоформ відповідає сукупність конкретних ідентифікаторів, які утворюються заміною в них  усіх мета змінних  на їх значення - лексеми, що відповідають  їх піддіаграмам. Напр., за словоформою <буква><роздільник>< цифра>< цифра>  можна отримати   ідентифікатори K-14, K-15, K-16, K-17.  І т.д.

Впр. Побудувати СД для поняття :

             1) <ціле_число>  у мові Паскаль;

             2) <дійсне_ число>  у мові Паскаль;l

             3) <літерал_мови Сі>

             4) <коментар_мови_Сі> 

             5) <16-і константи _мови_Сі>

             6) <8-і константи _мови_Сі>

             7)  <фрагмент_програми>   

                     Procedure H (x: real);

                     Var  i: integer;

                     begin  While x<0 do begin (x:=x+0.5;) (inc(i);) end

                                 write(i);

                      end;

            8)  <мова_Діка>  зі  значеннями  {0}

            9) <дужковий_вираз >     в алфавіті  (,),[,],{,}

         Лінійна форма СД.. В лінійній формі СД «жирні» символи: ::=  |, (,),[,],{,} є метасимволами і означають наступне. Символ ::= читається  як «є» . Символ | означає альтернативу «або».  Пара круглих дужок об’єднує декілька конструкцій в одну загальну. Конструкція в квадратних дужках може бути відсутньою. Конструкція в фігурних дужках  може бути замінена конкатенацією довільною кількості конструкцій (в тому числі і нульвою, тобто порожнім словом).

        1) Наведемо варіант лінійної форми СД для поняття  <ідентифікатор> в Стандарті ANSI 1989 р.

<ідентифікатор> ::=  (<буква>  | <роздільник> ){<буква> | <цифра>  | <роздільник>}

<буква> ::=  А |В | C| D| E| F| G| H| I| J| K| L| M| N| O| P| Q| R| S| T| U| V| W| X| Y| Z 

<цифра> ::=  0 |1 | 2| 3| 4| 5| 6| 7| 8| 9

<роздільник>  ::=  _

        2) Поняття  <фрагмент_програми>   з останньої  Впр.(п.7) може бути заданий наступною СД в ліній формі:

                     Procedure H (x: real);

                     Var  i: integer;

                     begin  While x<0 do begin {x:=x+0.5;} {inc(i);} end

                                 write(i);

                      end;


 

Лексема

Метазмінна

IDef

А

Z

В

0

9

1

_

буква

цифра

роздільник

буква


 

А также другие работы, которые могут Вас заинтересовать

18214. Організаційно-методичні особливості проведення уроку фізичної культури в школі 183.5 KB
  Змістовий модуль 5 Тема 11. Організаційнометодичні особливості проведення уроку фізичної культури в школі. План. Зміст навчальної дисципліни Фізична культура. 1.1. Аналіз шкільної базової програми Основи здоровя та фізична культура Київ 2001 року. ...
18215. Організація і методика фізичного виховання дітей та підлітків з ослабленим здоров’ям 87 KB
  Змістовий модуль 6 Тема 13. Організація і методика фізичного виховання дітей та підлітків з ослабленим здоровям. Особливості організації фізкультурнооздоровчих занять учнів підготовчої і спеціальної медичної груп. 1.1. Організація занять фізичними вправами ...
18216. Планування, контроль та облік навчальної діяльності учнів 141.5 KB
  Змістовий модуль 4 Тема 9. Планування контроль та облік навчальної діяльності учнів. Технологія планування та його функції. 1.1. Функції планування вимоги до планування перспективне поточне оперативне планування. 1.2. Технологія планування встановлення мет...
18217. Принципи побудови процесу фізичного виховання 84.5 KB
  Змістовий модуль 1 Тема 2. Принципи побудови процесу фізичного виховання. Усі явища та процеси у природі і житті підпорядковані певним закономірностям і розвиваються відповідно до них. Ці закономірності існують у природі незалежно від волі людини. П
18218. Загальні основи навчання рухових дій 126 KB
  Змістовий модуль 2 Тема 5. Загальні основи навчання рухових дій. Особливості навчання у фізичному вихованні. 1.1. Зміст спеціальних фізкультурноспортивних знань. 1.2. Класифікація рівнів засвоєння знань. Рухові уміння та навички. 2.1. Характеристика
18219. Загальна характеристика та основи методики розвитку рухових здібностей 262 KB
  Змістовий модуль 3 Тема 6. Загальна характеристика та основи методики розвитку рухових здібностей. Поняття про рухові здібності та основні форми їх прояву. 1.1. Визначення поняття рухові здібності потенціальні та актуальні рухові здібності конди
18220. Теорія і методика фізичного виховання, як наукова та навчальна дисципліна. Система фізичного виховання 122 KB
  Змістовий модуль 1 Тема 1. Теорія і методика фізичного виховання як наукова та навчальна дисципліна. Система фізичного виховання. Під терміном теорія в науці і зокрема в ТМФВ розуміють систему основних ідей форму наукового знання що дає цілісне уявлення про законо...
18221. Урок – основна форма фізичного виховання молодших школярів 308.5 KB
  Змістовий модуль 4 Тема 8. Урок основна форма фізичного виховання молодших школярів. Зміст навчального предмету Фізична культура. 1.1. Аналіз програми Основи здоровя і фізична культура Київ 2001 року програмовий матеріал години на проходження зміст к...
18222. Фізична культура в системі виховання дітей шкільного віку 106.5 KB
  Змістовий модуль 5 Тема 10. Фізична культура в системі виховання дітей шкільного віку. План. Соціальнопедагогічне значення фізичної культури дітей шкільного віку. 1.1. Мета завдання спрямованість фізичного виховання школярів. 1.2. Вікові особливості розвитк...