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. Структура компілятора.


 

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

75991. Я - ОСОБИСТІСТЬ 155 KB
  Людина –- індивід особистістю стає в процесі розвитку спілкування життя в суспільстві Розвиток індивідуума відповідає як його інтересам так і загальнодержавним інтересам та інтересам людського суспільства взагалі.
75992. Овочі. Т. Коломієць «Лічилка». Загадки 69.5 KB
  Активізувати словниковий запас дітей. Удосконалювати і розвивати орфоепічні вміння; пам’ять, увагу, спостережливість, відповідати на запитання українською мовою. Виховувати любов до усної народної творчості, почуття любові до української мови.
75993. Ніхто не забутий, ніщо не забуто! 53 KB
  Мета. Поглибити знання дітей про Велику Вітчизняну війну, удосконалювати навички виразного, свідомого читання; розвивати мовлення учнів, вміння висловлювати власну думку; виховувати почуття поваги до героїв війни, гордості за наше героїчне минуле.
75994. «Пандора» (за поемою Овідія «Метаморфози») 55.5 KB
  Анотація: Розробка комбінованого уроку українського позакласного читання на заявлену тему у 4 класі мета якого продовжувати ознайомлювати учнів з міфами; вчити дітей аналізувати твір складати план розвивати уявлення учнів про світове значення міфології виховувати повагу до історичної спадщини.
75995. Азбука дороги — дорожные знаки 464.5 KB
  Цель: расширить знания учащихся о дорожных знаках, учить называть группы дорожных знаков, научить различать дорожные знаки, повторить правила уличного движения для пешеходов, развивать умения самостоятельно пользоваться полученными знаниями в повседневной жизни...
75996. Дорога в школу. Школа «Светофорных наук». Современные средства передвижения 49.5 KB
  Школа Светофорных наук. Всех принять участие в уроке приглашаем И важные правила запомнить разрешаем Приветствуем друзей слева и справа Знать правила дорожные это не забава Пожимаем друзьям множество рук И приглашаем в школу Светофорных наук...
75997. Вивчи Правила, знай і завжди їх пам’ятай 2.77 MB
  Ми завітаємо в гості до казки де зустрінемося з Дідусем Правила Руху Казкою живими Дорожніми знаками Бабою Ягою і навіть зі славнозвісним Світлофором Івановичем. Знаки треба розставити вчасно І розмітку накреслити ясно Світлофори усі засвітити А у горах тунелі пробити...
75998. Безпечний перехід вулиці 840.5 KB
  Мета. Ознайомити учнів з місцями, де можна переходити вулицю; як безпечно переходити проїжджу частину дороги; які знаки, прилади, лінії допомагають безпечному переходу; вчити практично визначати безпечні місця переходу вулиці на шляху додому...