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

_

буква

цифра

роздільник

буква


 

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

21002. Широтно-импульсный преобразователь 96.55 KB
  КРЕМЕНЧУК 2011 Широтноимпульсный преобразователь Рисунок 1 ШИП с параллельной коммутацией Проектируемый преобразователь относится к классу широтноимпульсных преобразователей и применяется в частности для регулирования напряжения питания в двигателях постоянного тока. Рисунок 2 Структурная схема ШИП ГПН генератор пилообразного напряжения; ПУ пороговое устройство компаратор; ФУН формирователь управляющих импульсов; ВП выпрямитель; СЧ силовая часть; Н нагрузка. Рисунок 3 схемы взаимосвязи процессов Построение алгоритма роботы схемы...
21003. Вибір альтернативи на основі методу рангу 33.19 KB
  КРЕМЕНЧУК 2012 Мета: Освоїти метод пошуку найкращої альтернативи на основі методу рангу. int ijs[4]= {0000}; Порахуємо матрицю нормованих оцінок float z[4][3]; fori = 0;i 4;i { forj = 0;j 3;j z[i][j]= floatZ[i][j] floats[i]; } Знайдемо ваги цілей w[j]= z[0][j]z[1][j]z[2][j]z[3][j] 4; forj = 0;j 3;j cout j1 Альтернатива: w[j] endl; Сортуємо по убуванню Ту альтернативу яка має найбільшу вагу вибираємо як кращий варіант ifw[i] w[j] i j { temp = w[i]; w[i]= w[j]; w[j]= temp; } Реалізували алгоритм пошуку...
21005. Расчет многовибраторных антенн 444.5 KB
  Рассчитать и построить диаграммы направленности системы из полуволнового вибратора и рефлектора. Ток рефлектора составляет 10%, 50%, 90% от тока вибратора и опережает ток вибратора по фазе на
21006. Антенны Радиорелейных Линий связи 188.5 KB
  Донецк 2011 Цель работы: расчет формы диаграммы направленности антенны по известному распределению амплитуд поля. Рассчитать диаграмму направленности параболической антенны с круглым раскрывом амплитуды поля в котором изменяются по закону Er=11r R02 со спадом поля на краях раскрыва относительно центра до =0. Определить коэффициент направленного действия зеркальной параболической антенны по условиям ЗАДАНИЯ 1 приняв значение коэффициента использования равным 05.
21007. Исследование рупорной антенны 95.5 KB
  Цель работы: исследование особенностей распространения радиоволн сантиметрового диапазона и экспериментальное снятие диаграммы направленности рупорной антенны.
21008. РАСЧЕТ ПАРАМЕТРОВ СИММЕТРИЧНОГО И НЕСИММЕТРИЧНОГО ВИБРАТОРОВ. Распределение тока Ix и заряда Qx 108 KB
  Каково распределение поля симметричного и несимметричного вибратора в зависимости от длины вибратора и длины волны. Основные характеристики симметричного и несимметричного вибратора. При каком отношении диаграмма направленности симметричного вибратора имеет боковые лепестки?
21009. РАСЧЕТ ХАРАКТЕРИСТИК И ПАРАМЕТРОВ ТЕЛЕВИЗИОННЫХ АНТЕНН 91.5 KB
  Затухание вносимое коаксиальным кабелем распределительной сети 5дБ фильтром сложения 95 дБ разветвительным устройством 105 дБ. Распределительное устройство имеет проходное затухание 05 дБ и переходное затухание 17 дБ. Полное затухание распределительной сети затухание вносимое коаксиальным кабелем распределительной сети плюс затухание вносимое фильтром сложения плюс затухание вносимое разветвительным устройством плюс полное затухание вносимое всеми распределительными устройствами плюс переходное затухание...
21010. Исследование особенностей распространения радиоволн сантиметрового диапазона и экспериментальное снятие диаграммы направленности рупорной антенны 307.48 KB
  Краткие сведения по теме Диаграмма направленности антенны представляет собой графическую зависимость напряженности электромагнитного поля созданного антенной от углов наблюдения в пространстве. Чтобы построить диаграмму направленности ДН характеристики поля измеряют на одинаковом достаточно большом расстоянии от антенны. Основные значения параметров антенны в режиме приема и передачи остаются неизменными следовательно диаграмма направленности антенны не зависит от того применяется антенна в качестве передающей или приемной т.