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


 

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

31712. Двіжущіе сили та умови розвитку особистості 99 KB
  Двіжущіе сили та умови розвитку особистості Розвиток особистості слід розуміти як процес формування особистості як соціальної якості індивіда в результаті його соціалізації та виховання. Володіючи природними анатомофізіологічними передумовами до становлення особистості в процесі соціалізації дитина вступає у взаємодію з навколишнім світом опановуючи досягненнями людства. Створювані в ході цього процесу здібності і функції відтворюють в особистості історично сформувалися людські якості. Оволодіння дійсністю у дитини здійснюється в його...
31713. Соціалізація особистості 95.5 KB
  socilis суспільний характеристика це процес входження індивіда в суспільство соціалізації особистості активного засвоєння ним соціального досвіду соціальних ролей норм цінностей необхідних для успішної життєдіяльності в даному суспільстві. У процесі соціалізації в людини формуються соціальні якості знання вміння відповідні навички що дає їй змогу стати дієздатним учасником соціальних відносин. Отже основа соціальнопсихологічного розуміння соціалізації особистості грунтується на характеристиці соціальнопсихологічного типу...
31714. Загальні поняття про особистість 49 KB
  В особистості немовби концентруються особливості суспільства основні його риси. Тому зрозуміти життя особистості можна тільки розглядаючи її у конкретних суспільних умовах в діяльності та стосунках з іншими людьми аналізуючи її соціальний статус та місце в суспільних відносинах. Усі особистості – індивіди але не кожен індивід – особистість. Паригіна модель особистості котра повинна зайняти місце в системі психології припускає поєднання двох підходів: соціологічного й загальнопсихолоігчного.
31715. ХАРАКТЕРИСТИКА МЕТОДІВ СОЦІАЛЬНОЇ ПСИХОЛОГІЇ 105 KB
  Метод спостереження може використатися як один із центральних самостійних методів дослідження. Метод спостереження здійснюється також з метою збору первинного матеріалу дослідження а також для контролю отриманих емпіричних даних. Класифікація спостереження виконується на різних підставах.
31716. Соціалізація старшокласників у школі 89.5 KB
  Ціннісні орієнтації референтної групи істотною мірою визначають соціальнопсихологічне обличчя підлітка. Оскільки група єдина площина соціальнопсихологічного досвіду в якій може проявити себе підліток яку він може засвоїти й через яку пізнати сукупність суспільних відносин то саме група стає формівною силою в соціалізації підлітка. Тут надзвичайно суттєвим є питання про те що визначає референтну значущість тієї чи іншої групи в очах підлітка або навпаки сприяє її зниженню.
31717. Структура педагогічної психології 35.5 KB
  До кожної теми подано список літератури щоб читач міг поперше більш докладно вивчити певний аспект теми яка його зацікавила подруге мав уявлення та добре орієнтувався у працях авторів які займаються проблемами та дослідженнями в галузі психології навчання та виховання. Предмет і задачі педагогічної психології Предметом педагогічної психології є психологія навчання психологія виховання психологія вчителя та педагогічної діяльності. Основний зміст педагогічної психології складають психологічні закономірності процесів навчання та...
31718. Загальна характеристика процесу виховання 43.5 KB
  Соціальня ситуація розвитку особистості Становлення людини як індивіда та особистості за Л. Виготським передбачає діалектичну взаємодію двох відносно автономних однак нерозривно пов'язаних процесів розвитку природного і соціального. Кожному віку притаманна певна специфічна соціольна сипгуаціярозвитку тобто особливе співвідношення внутрішніх процесів розвитку і зовнішніх умов яке є типовим для кожного вікового етапу зумовлює динаміку психічного розвитку протягом відповідного вікового періоду і нові якісно своєрідні психологічні утворення...
31719. Формування моральної свідомості 39 KB
  Для періоду дитинства взагалі характерне засвоєння моральних норм і перетворення останніх на регулятори поведінки та діяльності дитини через наслідування відповідних дій дорослих. 3 погляду педагогіки це орієнтація на максимальне усвідомлення у межах вікових психологічних можливостей дитиною моральних вимог що їх постійно висуває перед нею життя орієнтація на природну творчість дитини. У моральній свідомості учнів розрізняють два взаємопов'язаних рівні: теоретичний система моральних знань того чи іншого рівня узагальненості та рівень...
31720. Соціально-психологічні аспекти виховання 37 KB
  Такі групи називають референтними. Референтні групи можуть бути як реальними так і уявними але особистість завжди орієнтується на їх цінності і стандарти як на еталонні зразки своєї поведінки завжди прагне до визнання з їх боку. Якщо індивід реально входить до складу референтної групи то це створює психологічно сприятливі умови для успішного розвитку особистості в певному напрямку останній зовсім не обов’язково має співпадати зі загальною стратегією виховання особливо коли референтній групі притаманна асоціальна спрямованість.