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

_

буква

цифра

роздільник

буква


 

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

49990. ИЗУЧЕНИЕ ЯВЛЕНИЯ ИНТЕРФЕРЕНЦИИ СВЕТА НА ДВУХЛУЧЕВОМ ИНТЕРФЕРОМЕТРЕ И ОПРЕДЕЛЕНИЕ ИЗМЕНЕНИЯ ПОКАЗАТЕЛЯ ПРЕЛОМЛЕНИЯ ВОЗДУХА 836.5 KB
  До точки Р волна проходит в среде с показателем преломления n1 путь s1 вторая волна проходит в среде с показателем преломления n2 путь s2. Интерферометр Жамена предназначен для измерения небольших изменений показателей преломления. Для уяснения принципа действия такого рефрактометра вообразим что на пути одного из интерферирующих лучей помещен плоскопараллельный слой какоголибо вещества толщиной с показателем преломления n2.
49991. ИЗУЧЕНИЕ ФОТОЭЛЕМЕНТА С ВНЕШНИМ ФОТОЭЛЕКТРИЧЕСКИМ ЭФФЕКТОМ 120.5 KB
  Внешний фотоэффект используют в приборах называемых фотоэлементами . Измерение основных характеристик фотоэлемента Фотоэлемент представляет собой стеклянный баллон рис. Анод фотоэлемента 3 изготовлен в виде диска или сферы помещенного в центре баллона.
49992. ИЗУЧЕНИЕ ЯВЛЕНИЯ ТЕПЛОВОГО ИЗЛУЧЕНИЯ 200.5 KB
  Энергия нагретого тела E1 много больше энергии излучения E2 что и составляет сущность проблемной ситуации. Происхождение теплового излучения При нагревании любого тела повышается запас его энергии сосредоточенной на различных степенях свободы: поступательного движения атомов и молекул газа вращательного и колебательного движения атомов или ионов в молекулах и кристаллах и т. Таким образом любые нагретые тела т. тела с температурой больше 0 К испускают электромагнитное излучение микроскопические механизмы которого различны в разных...
49993. ОПРЕДЕЛЕНИЕ ПОСТОЯННОЙ ПЛАНКА СПЕКТРОМЕТРИЧЕСКИМ МЕТОДОМ 942 KB
  Краткое теоретическое введение Согласно квантовой теории излучение света атомами вещества связано с изменением их энергетического состояния. По теории Бора переход атома водорода из одного энергетического состояния в другое связан с переходом электрона атома с одной орбиты на другую. Орбиты электрона в атоме квантованы и поэтому энергия атома водорода не может иметь любое произвольное значение.
49994. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА СООТНОШЕНИЯ НЕОПРЕДЕЛЕННОСТЕЙ ДЛЯ ФОТОНОВ 130.5 KB
  Одним из фундаментальных положений квантовой механики является принцип неопределенностей сформулированный В. О том каково его значение можно судить исходя из того факта что всего одного из соотношений неопределенностей достаточно чтобы объяснить целый ряд закономерностей в атомной и ядерной физике. Обозначив канонически сопряженные величины буквами А и В можно написать B ≥ 3 Соотношение 3 называется соотношением неопределенностей для величин А и В.
49995. Стройові вправи. Загальнорозвивальні вправи 69 KB
  Стройові вправи. Шикування як вид стройових вправ. Загальнорозвивальні вправи. Прикладні вправи.
49997. Нечеткая логика. Создание простейшей системы нечеткой логики 67 KB
  Создание простейшей системы нечеткой логики реализованной на языке высокого уровня. Задание Согласно заданным вариантам разработать программу на любом алгоритмическом языке способную: Различать степени изменения лингвистической переменной в трех степенях...
49998. МИКРОПРОГРАММИРОВАНИЕ КОМАНД СМ ЭВМ 92 KB
  Цель работы: Знакомство с принципами микропрограммной эмуляции ЭВМ с программным управлением, микропрограммирование машинных команд СМ ЭВМ. Вариант индивидуального задания: № 5 Найти наибольший общий делитель двух чисел по алгоритму Евклида.