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


 

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

83792. Налоговая тайна. Порядок получения информации, содержащей налоговую тайну 42.15 KB
  Порядок получения информации содержащей налоговую тайну. Налоговую тайну составляют любые полученные налоговым органом органами внутренних дел следственными органами органом государственного внебюджетного фонда и таможенным органом сведения о налогоплательщике за исключением сведений: 1 являющихся общедоступными в том числе ставших таковыми с согласия их обладателя налогоплательщика; 2 об идентификационном номере налогоплательщика; 3 о нарушениях законодательства о налогах и сборах и мерах ответственности за эти нарушения; 4...
83793. Взаимозависимые лица: общие положения 40.7 KB
  Взаимозависимыми для целей налогообложения являются: 1 организации в случае если одна организация прямо и или косвенно участвует в другой организации и доля такого участия составляет более 25 процентов; 2 физическое лицо и организация в случае если такое физическое лицо прямо и или косвенно участвует в такой организации и доля такого участия составляет более 25 процентов; На заметку Долей участия физического лица в организации признается совокупная доля участия этого физического лица и его родственников п. 3 организации в случае...
83794. Общие положения о ценах и налогообложении. Особенности признания цен рыночными для целей налогообложения 45.02 KB
  Для целей настоящего Кодекса цены применяемые в сделках сторонами которых являются лица не признаваемые взаимозависимыми а также доходы прибыль выручка получаемые лицами являющимися сторонами таких сделок признаются рыночными. При определении налоговой базы с учетом цены товара работы услуги примененной сторонами сделки для целей налогообложения далее в настоящем разделе цена примененная в сделке указанная цена признается рыночной если федеральным органом исполнительной власти уполномоченным по контролю и надзору в...
83796. Общие положения о методах, используемых при определении для целей налогообложения доходов (прибыли, выручки) в сделках, сторонами которых являются взаимозависимые лица 41.35 KB
  Метод сопоставимых рыночных цен является приоритетным для определения для целей налогообложения соответствия цен. Применение иных методов допускается в случае если применение метода сопоставимых рыночных цен невозможно либо если его применение не позволяет обоснованно сделать вывод о соответствии или несоответствии цен примененных в сделках рыночным ценам для целей налогообложения. При отсутствии общедоступной информации о ценах в сопоставимых сделках с идентичными однородными товарами работами услугами для целей определения полноты...
83797. Контролируемые сделки. Подготовка и представление документации в целях налогового контроля 41.33 KB
  Контролируемыми сделками признаются сделки между взаимозависимыми лицами. К сделкам между взаимозависимыми лицами приравниваются следующие сделки: 1 совокупность сделок по реализации перепродаже товаров выполнению работ оказанию услуг совершаемых с участием при посредничестве лиц не являющихся взаимозависимыми с учетом особенностей предусмотренных настоящим подпунктом. Сделка между взаимозависимыми лицами местом регистрации либо местом жительства либо местом налогового резидентства всех сторон и выгодоприобретателей по которой...
83798. Налоговый контроль в связи с совершением сделок между взаимозависимыми лицами 41.14 KB
  17 НК РФ проверка полноты исчисления и уплаты налогов в связи с совершением сделок между взаимозависимыми лицами проводится федеральным органом исполнительной власти уполномоченным по контролю и надзору в области налогов и сборов по месту его нахождения на основании уведомления о контролируемой сделке полученного от налогоплательщика или извещения полученного от территориального налогового органа выявившего в ходе проверки факт осуществления контролируемой сделки а также в случае выявления контролируемой сделки в результате повторной...
83799. Соглашение о ценообразовании для целей налогообложения: общие положения; стороны соглашения о ценообразовании; порядок заключения соглашения 41.59 KB
  Соглашение о ценообразовании для целей налогообложения представляет собой соглашение между налогоплательщиком отнесенным к категории крупнейших налогоплательщиков и ФНС России о порядке определения цен и или применения методов ценообразования в контролируемых сделках. Заключение соглашения о ценообразовании позволяет налогоплательщикам и налоговым органам. Предметом соглашения о ценообразовании являются: 1 виды и или перечни контролируемых сделок и товаров работ услуг в отношении которых заключается соглашение; 2 порядок...
83800. Общие положения об ответственности за совершение налоговых правонарушений: понятие, лица подлежащие ответственности за их совершение. Условия привлечения к ответственности за совершение налогового правонарушения 39.43 KB
  Условия привлечения к ответственности за совершение налогового правонарушения. Ответственность за совершение налоговых правонарушений несут организации и физические лица. Физическое лицо может быть привлечено к ответственности за совершение налоговых правонарушений с шестнадцатилетнего возраста.