68831

Формальні мови

Лекция

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

Форма уявлення інформації визначається мовою тому у поданій дисципліні розглядаються питання пов’язані з переходом від однієї мови до іншої при представленні деякої інформації. Формальні мови Природні мови англійська російська українська та ін. Позбавитись цих недоліків природних мов дозволило...

Украинкский

2014-09-26

88.5 KB

4 чел.

Лекція 1

Вступ

Під трансляцією у програмуванні розуміють процес перетворення форми уявлення інформації (сукупності відомостей). Форма уявлення інформації визначається мовою, тому у поданій дисципліні розглядаються питання, пов’язані з переходом від однієї мови до іншої при представленні деякої інформації.

При застосуванні комп’ютерних інформаційних технологій необхідність у такому переході виникає перш за все в процесі введення інформації у комп’ютер, оскільки людина висловлює інформацію, користуючись природними мовами, а комп’ютер оперує числами. Крім того, перетворювати форму представлення інформації потрібно у процесі її обробки та виведення результатів користувачеві.

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

Формальні мови

Природні мови (англійська, російська, українська та  ін.) суперечливі, неоднозначні та неточні. Для підтвердження можна навести парадокс Рішара: "Найменше з натуральних чисел, які не можна назвати українською мовою за допомогою менш, ніж двадцяти слів". У цій фразі міститься шістнадцять слів і одночасно названо об’єкт, який не можна назвати за допомогою такої кількості слів. Це - парадокс (суперечність). Крім того, зміст багатьох речень залежить від інтонації, додаткових відомостей ( ситуації у світі, країні і т. і.). Використання таких мов  для  передавання  інформації  від користувача до ЕОМ  (або  іншого  технічного  пристрою)  дуже проблематичне, якщо взагалі можливе.

Позбавитись цих недоліків природних мов дозволило створення на базі цих мов ( з використанням їх словарного фонду та граматик) підмов, фрази яких однозначні та у змістовному відношенні не залежать від жодних зовнішніх для даної мови умов. Зміст кожної фрази такої підмови визначається тільки її формою. Тому такі мови називають формальними. Типовим прикладом формальної мови є система числення для уявлення чисел.

Формальна мова не обов’язково повинна бути підмовою природної мови. Можна спеціальним чином (за допомогою деяких знаків) визначити формальну мову, що призначена для використання у певній області науки. Такі мови називають штучними формальними мовами. Прикладом штучної формальної мови є мова програмування.

Повернемося до парадоксу Рішара. Встановлено, що причиною цього парадоксу є те, що у фразі, складеній українською мовою, говориться про цю ж саму мову. Якщо заборонити застосування мови для означення (опису) цієї ж мови, можливість парадоксу Рішара зникає. При цьому для опису формальної мови потрібна інша мова. Мову, що описується, називають мовою-об’єктом, а мову, що використовується для опису, - метамовою. Іноді користуються метамовою по відношенню до метамови, тобто метаметамовою.

Метамова повинна мати властивості для опису як форми фраз (речень або записів) мови-об’єкту, так і змісту цих фраз. Часто метамову розділяють на дві: одна - для опису форми фраз (її називають метасинтаксичною), друга (метасемантична) - для опису змісту. Систему правил (фразу метасинтаксичної мови), що визначають форму речень мови-об’єкту, називають синтаксисом останньої;  відповідність  між реченнями мови-об’єкту та їх змістом - семантикою.

При описі форми речень мови-об’єкту задають її алфавіт - набір символів (букв, літер), що використовується, та сукупність правил побудови речень (формальну граматику). Кожне правило визначає деяку операцію, яку можна застосовувати у процесі побудови речень.

Нормальна нотація Бекуса

Однією з найбільш поширених метасинтаксичних мов, або форм запису правил побудови речень формальної мови, є нормальна нотація Бекуса або бекус-наурова форма (БНФ), що названа так на честь її автора Бекуса та вченого Наура, застосувавшого цю форму для опису синтаксису мови програмування Алгол-60. Опис граматики мови-об’єкту у БНФ складається зі скінченої кількості речень, що називаються металінгвістичними формулами. При написанні цих формул використовують два фіксованих метасимволи: „::=” та  „|”. Перший символ означає - „за означенням є”, а другий - „або”.

Інші метасимволи можна вибирати вільно. Ці метасимволи можуть бути або символами мови-об’єкту, або власно метасимволами, тобто символами, що не належать мові-об’єкту. Позначення останніх записують у кутових дужках  „<”  та  „>”. Звичайно у кутових дужках записують природною мовою назву граматичного класу (множини послідовностей символів) мови-об’єкту.

У лівій частині формули Бекуса стоїть власно метасимвол, за ним прямує знак „::=” , і далі - права частина. Права частина формули може бути або  пустою, або містити скінчену послідовність метасимволів. Між двома  послідовними метасимволами може стояти фіксований метасимвол „|”. За означенням, дві формули Бекуса, що мають однакові ліві та різні праві частини, еквівалентні за змістом формулі, що утворюється додаванням до правої частини однієї з формул символу „|”, а за ним - правої частини іншої формули.

Розглянемо як приклад БНФ граматики формальної мови для уявлення парних натуральних чисел.

 (1) <ненульова цифра> ::= 1|2|3|4|5|6|7|8|9

 (2)   <цифра> ::= 0 | <ненульова цифра>

 (3)   <парна цифра> ::= 0|2|4|6|8

 (4) < початок> ::= <ненульова цифра> | <початок> <цифра>

 (5)  <парне число> ::= <парна цифра> | <початок> <парна цифра>

Метасимвол <парне число> позначає речення мови-об’єкту, а цифри 0, 1, ... , 9 – алфавіт цієї мови. Важливо зауважити, що скінчена кількість формул визначає нескінчену кількість речень. Досягається це за рахунок особливої форми формули (4), що містить металінгвістичний символ <початок> як у лівій частині, так і у правій. Таке означення символу називають рекурсивним.

Слід відзначити, що за допомогою БНФ можна описати не кожну формальну мову. Наприклад,  мову,  кожне  речення  якої складається з двох однакових парних чисел, записаних підряд, описати за допомогою БНФ не можливо. Причина цього стане зрозумілою після розглядання більш загальних форм опису мов.

Формальною мовою, що має семантику, називають мову, що розглядається разом з деякою множиною об’єктів і деяким відображенням, яке ставить у однозначну відповідність реченням мови об’єкти вказаної множини. Цю множину називають семантичною. Серед об’єктів семантичної множини може бути і пустий об’єкт.

У формальній теорії мов розглядаються такі основні задачі:

1. Як за поданою граматикою  G  породжувати речення відповідної мови  L(G) ?

2. Як за поданими мовою L та реченням s встановити, чи належить s до L ?

Мовні процесори

Теоретичні та прикладні питання, пов’язані з використанням формальних мов, найбільш глибоко досліджені у галузі мов програмування високого рівня. Тому курс "Лінгвістичне забезпечення САПР" базується на детальному розгляданні усіх етапів перетворення форми вхідної інформації у вигляді  програми, що написана мовою програмування високого рівня, у форму програми, написаної мовою машинних команд, або у машинний код.

Програма, що перетворює будь-яку вхідну програму, написану конкретною мовою, у еквівалентну програму, написану іншою мовою, називають транслятором. Трансляція складається з двох основних стадій: аналізу - визначення передбаченого результу дії програми, та синтезу - побудови еквівалентної  програми,  написаної  вихідною мовою. Транслятор, призначений для обробки програм, написаних мовою високого рівня, називають компілятором, а для обробки програм, написаних мовою нижчого рівня, - асемблером.  

Рис.1.1. Типи мовних процесорів.

Існує також інший підхід до обробки вхідного тексту програми. Він полягає у тому, що замість перетворення кожної програми у машинний код і подальшого її виконання спочатку перетворюється програма у проміжну форму (проміжний код), а потім перетворюється і виконується кожний оператор проміжного коду. В цьому випадку перетворюючу та виконуючу програму називають інтерпретатором. Застосовується також і змішаний код, коли частина програми, уявлення якої у машинних командах вимагає великих витрат пам’яті, інтерпретується, а інша - компілюється. Це призводить до економії пам’яті комп’ютера. Усі програми, що призначені для перетворення тексту вхідної програми, називають мовними процесорами. Різні типи мовних процесорів показані на рис.1.1.

Окремі аспекти компіляції

У даному курсі, в основному, розглядаються компілятори, при розробці яких знаходять втілення усі основні принципи побудови мовних процесорів. Надалі будемо вважати, що компілятор обробляє вхідну програму, а результатом його роботи є об'єктний  код. Відповідно мова високого рівня буде називатися вхідною мовою, а мова програми-результата - об'єктною.  

Означення вхідної мови задає значення кожної її конструкції, тобто зміст допустимих послідовностей символів. Уся програма - це конструкція,  що  містить  усі  інші  конструкції  (наприклад, підпрограми, розділи, оператори). Поняття конструкції близьке до згаданого раніше поняття граматичного класу.

Після того, як аналізатор (частина компілятора, що виконує аналіз) розпізнає усі конструкції вхідної програми, стає можливим встановлення результату дії програми. Далі синтезатор (частина транслятора, що виконує синтез) формує відповідний об'єктний код.

Конструкції програми та зв'язки між ними утворюють структуру програми, яку можна зобразити у вигляді дерева. Між вершинами дерева та конструкціями  програми  встановлюється  взаємно  однозначна відповідність. Кожне  ребро  (a,b)  показує,  що  конструкція, відображена вершиною b, входить у конструкцію, відображену вершиною a. Наприклад, програмі     

      program;

      var x : integer;

      begin

         x := 3;

         write (x)

      end.

відповідає дерево, що зображено на мал.1.2,  де  прямокутники відповідають вершинам, а спрямовані відрізки та ламані - ребрам.

Аналізатор будує таке дерево, а синтезатор проглядає його, проходячи по усіх вершинах у певному порядку, та створює об’єктний код. Цей граф називають деревом розбору (або синтаксичним деревом). У повному дереві розбору листя відповідають первинним символам або літерам. Звичайно процес аналізу розділяють на два етапи. На першому літери об’єднують у групи або первинні конструкції, які можна вважати словами вхідної мови. Однак, традиційно їх  називають лексемами (а також символами). Процес виділення у вхідній програмі усіх лексем називають лексичним аналізом. Другий етап аналізу називається синтаксичним аналізом  або  розбором.

На  рис.1.2 неперервною лінією  показана  частина  дерева,  що  відповідає синтаксичному аналізу, а штриховою - лексичному. Ціль аналізу - не тільки побудувати синтаксичне дерево, а також визначити помилки у вхідній програмі. Під помилкою  розуміють невідповідність тексту вхідної програми правилам вхідної мови. Для визначення помилок компілятор створює і використовує ряд таблиць. Ці таблиці використовуються  також  на  останньому  етапі  роботи компілятора - синтезі (або генерації коду).

 

Рис.1.2. Дерево, що відображає структуру програми.

З метою створення такого компілятора, що дозволяє застосування його на різних комп’ютерах, процес генерації коду розділяють на два етапи. Перший етап відповідає виконанню дій, що не залежать від типу комп’ютера. На цьому етапі генерується проміжний код. Другий етап відповідає генерації власно машинного коду. Структуру компілятора показано на рис.1.3.

При розробці компілятора переслідуються такі цілі:

1) одержання ефективного об’єктного коду;

2) одержання мінімальних об’єктних програм;

3) мінімізація часу компіляції;

4) мінімізація об’єму компілятора;

5) поширення можливостей компілятора відносно  пошуку  та виправлення помилок;

6) надійність компілятора.

Вказані цілі у значній мірі суперечливі і тому при розробці компіляторів завжди вибирають розумний компроміс.

Рис.1.3. Структура компілятора.


 

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

35729. УЧЕТ ЛИЧНОСТНЫХ КАЧЕСТВ УЧЕНИКА ПРИ ОБУЧЕНИИ ИНФОРМАТИКЕ 284.5 KB
  Личностно-ориентированный подход к современному учебному процессу [3] Принципы построения личностно-ориентированной системы обучения Реализация личностно-ориентированного обучения [5] Современные педагогические типологии школьников [6] Классификация критериев дифференциации учащихся [7] Е. Учет личностных качеств ученика при обучении информатике [10] Заключение [11] Литература Введение При традиционной организации обучения ученик находящийся в позиции объекта подвергается постоянной педагогической обработке целенаправленному...
35731. Примерная структура и содержание творческих проектов 173.5 KB
  После сбора необходимой информации учащиеся выдвигают различные творческие идеи по выполнению того или иного изделия. Изделия могут быть объединены техникой исполнения стилем назначением. Каждый из рассматриваемых вариантов должен иметь краткую характеристику которая может включать название изделия его назначение описание техники исполнения. Содержание данного раздела представляет собой подробное описание выбранного для дальнейшего изготовления окончательного варианта изделия.
35735. МОДУЛЬНОЕ ОРИГАМИ. ТВОРЧЕСКИЙ ПРОЕКТ 27 KB
  Создать изделия в технике МОДУЛЬНОЕ ОРИГАМИ. Задачи: познакомиться с техникой модульное оригами научиться делать сам модуль научиться соединять модули в изделие исследовать интерес к технике оригами.
35736. ТВОРЧЕСКИЙ ПРОЕКТ ПО ТЕХНОЛОГИИ Вышивка гладью «Бордовые маки» 7.94 MB
  Немного из истории вышивки гладью. Во времена Моисея искусство вышивки было сильно развито; особенно славился своим искусством Ахалиаб из колена Дана. При византийских царях искусство вышивки достигло высокой степени совершенства как по богатству так и по исполнению. Сначала узоры для вышивки переходили из рук в руки и копировались самими вышивальщицами что нередко представляло им большие затруднения; после изобретения книгопечатания узоры сделались более доступными они собирались и издавались в специальных с этой целью книгах.