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


 

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

82411. Споры о метафизике в современной зарубежной философии 26.34 KB
  Действительно любая позиция является таковой только в силу своей выраженности в языке и следовательно отсутствие что влечет за собой поиски как. Текстом является всё. При этом в духе Гегеля это всё является тождественным ничто. В соответствии с ней значение какоголибо утверждения если это утверждение не является аналитическим или конвенциональным должно сводиться к чувственным восприятиям; если для какогото утверждения указать такие восприятия невозможно то такое утверждение считается бессмысленным.
82412. Философия языка (М. Хайдеггер, Г.-Г. Гадамер, Л. Витгенштейн, М. Фуко и др.) 41.05 KB
  Важное место в философии Хайдеггера занимает проблема понимания и языка. Хайдеггер отмечал что хотя язык изучается многими науками языкознанием логикой психологией и другими науками они не способны проникнуть в сущность языка. Они не могут этого сделать поскольку совершают грубую ошибку не понимая монологического характера языка.
82413. Неокантианство 36.93 KB
  Ничто в рамках мыслительных потенций университетской философии не указывало на возможность какойлибо продуктивной кооперации между Гегелем и скажем Г. Налицо оказывалась двоякая угроза: научно несостоятельной философии с одной стороны и философски беспризорной науки с другой. Если опасность научно не фундированной философии лежала в ее открытости мистическим соблазнам то опасность философски не защищенной науки заключалась в стихийных порывах наивно материалистического толкования. спор о материализме в результате которого...
82414. Неогегельянство 29.04 KB
  Стерлинга впервые познакомившего англичан с философией Гегеля Э. внеэмпирической реальности Брэдли; в тенденция к преодолению крайностей абсолютного идеализма Брэдли стремление отстоять права индивидуальности ее свободу: эта тенденция проявилась в умеренном персонализме Бозанкета и радикальном персонализме МакТаггарта которые пытались сочетать гегелевское учение об Абсолюте с утверждением метафизической...
82415. Неомарксизм 32.06 KB
  Первое что предлагают сделать неомарксисты это отказаться от положения марксизма о всемирноисторической роли пролетариата в качестве субъекта социалистической революции и могильщика капитализма. При господстве одномерного сознания одномерный человек этого общества не способен ни выработать ни даже воспринять то революционное социалистическое сознание которое согласно марксизмаленинизма является непременным условием и предпосылкой пролетарской социалистической революции. Второе субъектом революции могут стать лишь те кто еще...
82416. Философия жизни 46.62 KB
  Сознание дух только средства и орудия на службе у жизни. Метафизика это проектированиетотальности жизни на бытие. Все метафизические истолкования и интерпретации мира покоятся напереживании жизни.
82417. Психоанализ З. Фрейда. Фрейдизм, неофрейдизм 28.64 KB
  Классическая психология до Фрейда изучала явления сознания как они проявлялись у здорового человека. Фрейд как психопатолог исследуя характер и причины неврозов натолкнулся на ту область человеческой психики которая раньше никак не изучалась но которая имела большое значение для жизнедеятельности человека бессознательное. Особое значение Фрейд придает психосексуальному развитию человека влиянию его инстинктивной сексуальнобиологической энергии либидо на жизнь его чувств и поведение. В дальнейшем поведение ребенка а затем юноши и...
82418. Феноменология Э. Гуссерля: идейно-теоретические истоки, основные идеи, понятия, этапы развития 38.34 KB
  Феноменология Гуссерля широкое в потенции бесконечное поле методологических а также гносеологических онтологических этических эстетических социальнофилософских исследований любой темы философии через возврат к феноменам сознания и их анализу. Результатом исполнения феноменологической редукции является перемещение на исследовательскую почву чистого сознания; 4 чистое сознание есть смоделированное феноменологией сложное единство структурных элементов и сущностных взаимосвязей сознания. Оригинальность и теоретическая значимость...
82419. Особенности восприятия феноменологии Э. Гуссерля в современной зарубежной философии 34.99 KB
  Гуссерля в современной зарубежной философии Возникновение феноменологии как философского течения связано с творчеством Эдмунда Гуссерля 1859 1938. Однако постепенно происходит изменение его научных интересов в пользуфилософии. Гуссерль изложил в следующих работах: Логические исследования 1901 Философия как строгая наука 1911 Идеи чистой феноменологии и феноменологической философии 1913 Трансцендентальная логика и формальная логика 1921 Картезианские размышления 1931. Особенность философии Э.