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

_

буква

цифра

роздільник

буква


 

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

12152. КОМПОНЕНТЫ, ИСПОЛЬЗУЕМЫЕ ДЛЯ СВЯЗИ С БАЗАМИ ДАННЫХ 66 KB
  КОМПОНЕНТЫ ИСПОЛЬЗУЕМЫЕ ДЛЯ СВЯЗИ С БАЗАМИ ДАННЫХ Обзор компонентов используемых для связи с базами данных Компоненты Delphi используемые для работы с базами данных расположены в библиотеке компонентов на страницах Data Access доступ к данным и Data Control управл
12153. Знакомство с интегрированной средой Delphi 136 KB
  Лабораторная работа № 1 Знакомство с интегрированной средой Delphi Загрузка Delphi возможна одним из следующих способов: кнопка Пуск раздел Программы и далее в соответствии с названием программного продукта; ярлык на рабочем столе; быстрая кнопк
12154. СОЗДАНИЕ ОТЧЕТОВ. Система «Быстрый отчет» (Quick Report) 96.18 KB
  СОЗДАНИЕ ОТЧЕТОВ 6.1 Система Быстрый отчет Quick Report Для создания отчетов в Delphi включена система QuickReport все компоненты которой размещены на странице QReport палитры компонентов. Быстрый отчет использует генератор отчетов состоящий из множества полос. Полоса band –э
12155. ПРОГРАММИРОВАНИЕ РАБОТЫ С БАЗАМИ ДАННЫХ 70.04 KB
  ПРОГРАММИРОВАНИЕ РАБОТЫ С БАЗАМИ ДАННЫХ Состояние набора данных Основным свойством компонента Table является свойство State определяющее состояние набора данных. Это свойство доступно только во время выполнения и только для чтения. Набор данных может находиться...
12156. ПРИЛОЖЕНИЯ С НЕСКОЛЬКИМИ СВЯЗАННЫМИ ТАБЛИЦАМИ 31.5 KB
  ПРИЛОЖЕНИЯ С НЕСКОЛЬКИМИ СВЯЗАННЫМИ ТАБЛИЦАМИ Рассмотрим принципы построения приложения с несколькими связанными друг с другом таблицами. 8.1 Связь головной и вспомогательной таблиц Две таблицы могут быть связаны друг с другом по ключу. Одна из этих связанных табл...
12157. ТИПЫ ПОЛЕЙ. НЕКОТОРЫЕ СВОЙСТВА ТАБЛИЦЫ 61.5 KB
  ТИПЫ ПОЛЕЙ. НЕКОТОРЫЕ СВОЙСТВА ТАБЛИЦЫ Типы полей реляционной базы данных Проектирование приложения работающего с базами данных предполагает наличие самих баз данных. Вместе с BDE в Delphi поставляется программа Database Desktop которая позволяет создавать таблицы ба...
12158. ОБЩЕЕ ПОНЯТИЕ О БАЗЕ ДАННЫХ. МОДЕЛИ ДАННЫХ. СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ 182.07 KB
  ОБЩЕЕ ПОНЯТИЕ О БАЗЕ ДАННЫХ. МОДЕЛИ ДАННЫХ. СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ База данных Всегда когда возникает потребность манипулирования большими массивами данных используются базы данных. В общем случае под данными понимается информация наход...
12159. ПОСТРОЕНИЕ ЗАПРОСОВ В DELPHI 36 KB
  ПОСТРОЕНИЕ ЗАПРОСОВ В DELPHI Запрос – это вопрос к базе данных возвращающий запись или множество записей удовлетворяющих вопросу. Любой запрос по базе данных выполняется на языке SQL Structured Query Language – язык структурированных запросов который был создан Microsoft в конце 70х год...
12160. Режимы design-time и run-time. Объектные процедурные типы. Работа с ini файлами 148.5 KB
  Лабораторная работа №1 Тема: Режимы designtime и runtime. Объектные процедурные типы. Работа с iniфайлами Цель работы: показать простоту создания приложений в режиме designtime и удобство использования компонентов; показать возможность создания приложений с настраиваемым интер...