Розробка системних програмних модулів та компонент систем програмування

50

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”

Кафедра ЕОМ

КУРСОВА РОБОТА

з предмету “Системне програмування”

на тему “Розробка системних програмних модулів та компонент систем програмування.”

Виконав:

студент групи КІ – 31

Критович Д.М.

Перевірив:

Мархівка В.С.

Львів – 2011

Анотація

Задача, яка вирішується в даному курсовому проекті є розробка транслятора вхідної мови програмування. Транслятор розроблений за допомогою мови програмування C#, на основі програмного продукту “Visual Studio 2010”, в якому використовується стандартний набір користувацького інтерфейсу на основі компонентів пакету “.Net Framework”, який значно спрощує процес тестування, відлагодження та редагування програми.

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

Завдання на курсову роботу

Розробити транслятор вхідної мови програмування, короткий опис якої подано нижче:

-              типи даних:

Integer <змінна>;

-              оператор вводу:

Input (<змінна>);

-              оператор виводу:

Output (" < повідомлення > ");

Output (< змінна >);

-              блок тіла програми:

Program <ім’я>

Var

<опис змінних>;

Start

<тіло програми>;

Finish

-              оператор:

For – DownTo - Do (Паскаль);

For( <змінна> := <вираз>) DownTo(<вираз>)

Start

<тіло циклу>

Finish

-              регістр ключових слів:

Up-Low перший символ Up;

-              регістр ідентифікаторів:

Up-Low6 перший символ Up;

-              операції арифметичні:

+; -; Mul; Div; Mod;

-              операції порівняння:

==; != ; Le; Ge;

-              операції логічні:

!!; &&; ||;

-              коментар:

/* ... */;

-              оператор присвоєння:

:=;

Вступ

Незважаючи на більш ніж піввікову історію обчислювальної техніки, формально роком народження теорії трансляторів можна вважати 1957, коли з'явився перший транслятор мови Фортран, створений Бекасом. До цього часу створення трансляторів було досить "творчим" процесом. Лише поява теорії формальних мов і строгих математичних моделей дозволило перейти від "творчості" до "науки". Саме завдяки цьому стала можливим поява сотень нових мов програмування. Більше того, формальна теорія трансляторів дала новий стимул розвитку математичної лінгвістики і методам штучного інтелекту, пов'язаних із природними і штучними мовами. Основу теорії трансляторів становить теорія формальних мов - досить складними, насиченими термінами, визначеннями, математичними моделями і іншими формалізмами розділ математики. Отже, транслятори є невід'ємною частиною будь-якої обчислювальної системи - без них нам довелося б усе програмувати на автокоді або навіть у машинних командах. Тому транслятори стали важливою практичною областю наукових досліджень, пов'язаних з обчислювальними машинами.

1. Огляд методів та способів проектування трансляторів

1.1. Основні поняття і визначення

Транслятор - обслуговуюча програма, що перетворює вхідну програму, надану вхідною мовою програмування, у робочу програму, представлену об'єктною мовою.

Наведене визначення відноситься до всіх різновидів транслюючих програм. Однак у кожної з таких програм можуть бути свої особливості по організації процесу трансляції. У цей час транслятори розділяються на три основні групи: асемблери, компілятори і інтерпретатори.

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

Разом з тим, мова асемблера, крім аналогів машинних команд, містить безліч додаткових директив, що полегшують, зокрема, керування ресурсами комп'ютера, написання повторюваних фрагментів, побудова багатомодульних програм. Тому виразність мови є набагато кращою, ніж просто мови символічного кодування, що значно підвищує ефективність програмування.

Компілятор - це обслуговуюча програма, що виконує трансляцію на машинну мову програми, записаною вхідною мовою програмування. Також як і асемблер, компілятор забезпечує перетворення програми з однієї мови на іншу (найчастіше, у мову конкретного комп'ютера). Разом з тим, команди вхідної мови значно відрізняються по організації і потужності від команд машинної мови. Існують мови, у яких одна команда вхідної мови транслюється в 7-10 машинних команд. Однак є і такі мови, у яких кожній команді може відповідати 100 і більше машинних команд (наприклад, Пролог). Крім того, у вхідних мовах досить часто використовується строга типізація даних, здійснювана через їхній попередній опис. Програмування може опиратися не на кодуванні алгоритму, а на ретельне обмірковування структур даних або класів. Процес трансляції з таких мов звичайно називається компіляцією, а вихідні мови звичайно відносяться до мов програмування високого рівня. Абстрагування мови програмування від системи команд комп'ютера привело до незалежного створення найрізноманітніших мов, орієнтованих на рішення конкретних завдань. З'явилися мови для наукових, економічних розрахунків, доступу до баз даних і інші.

Інтерпретатор - програма або пристрій, що здійснює по-операторну трансляцію і виконання вхідної програми. На відміну від компілятора, інтерпретатор не породжує на виході програму машинною мовою. Розпізнавши команду вхідної мови, він відразу виконує її. Як у компіляторах, так і в інтерпретаторах використовуються однакові методи аналізу вхідного тексту програми. Але інтерпретатор дозволяє почати обробку даних після написання навіть однієї команди. Це робить процес розробки і налагодження програм більш гнучким. Крім того, відсутність вихідного машинного коду дозволяє не "засмічувати" зовнішні пристрої додатковими файлами, а сам інтерпретатор можна досить легко адаптувати до будь-яких машинних архітектур, розробивши його тільки один раз на широко розповсюдженій мові програмування. Тому, інтерпретуючі мови, типу Java Script, VB Script, одержали широке поширення. Недоліком інтерпретаторів є низька швидкість виконання програм. Звичайно інтерпретуючі програми виконуються в 50-100 разів повільніше програм, написаних у машинних кодах.

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

З огляду на схожість компілятора і інтерпретатора, розглянемо фази, що існують у компіляторі.

У ньому виділяються:

1.      Фаза лексичного аналізу.

2.      Фаза синтаксичного аналізу, що складає з:

      розпізнавання синтаксичної структури;

      семантичного розбору, у процесі якого здійснюється робота з таблицями, породження проміжного семантичного представлення або об'єктної моделі мови.

3.      Фаза генерації коду, що здійснює:

      семантичний аналіз компонентів проміжного представлення або об'єктної моделі мови;

      переклад проміжного представлення або об'єктної моделі в об'єктний код.

Поряд з основними фазами процесу трансляції можливі також додаткові фази:

1. Фаза дослідження і оптимізації проміжного представлення, що складає з:

            аналізу коректності проміжного представлення;

            оптимізації проміжного представлення.

2. Фаза оптимізації об'єктного коду.

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

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

Узагальнена структура компілятора, що враховує існуючі в ньому фази, представлена на рис. 1.1.

Рис. 1.1. Узагальнена структура компілятора.

Він складається з лексичного аналізатора, синтаксичного аналізатора, генератора коду, аналізатора помилок. В інтерпретаторі замість генератора коду використовується емулятор (рис. 1.2), у який, крім елементів проміжного преставлення, передаються вхідні дані. На вихід емулятора видається результат обчислень.

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

Рис. 1.2. Узагальнена структура інтерпретатора.

Синтаксичний аналізатор здійснює розбір вхідної програми, використовуючи надходженні лексеми, побудову синтаксичної структури програми і семантичний аналіз із формуванням об'єктної моделі мови. Об'єктна модель представляє синтаксичну структуру, доповнену семантичними зв'язками між існуючими поняттями.

Цими зв'язками можуть бути:

      посилання на змінні, типи даних і імена процедур, розташовувані в таблицях імен;

      зв'язки, що визначають послідовність виконання команд;

      зв'язки, що визначають вкладеність елементів об'єктної моделі мови й інші.

Таким чином, синтаксичний аналізатор є досить складним блоком транслятора. Тому його можна розбити на наступні складові:

      розпізнавання;

      блок семантичного аналізу;

      об'єктну модель, або проміжне представлення, що складається з таблиці імен і синтаксичної структури.

Узагальнена структура синтаксичного аналізатора наведена на рис. 1.3.

Рис. 1.3. Узагальнена схема синтаксичного аналізатора.

Розпізнавання одержує ланцюжок лексем і на її основі здійснює розбір відповідно до використовуваних правил. Лексеми, при успішному розборі правил, передаються семантичному аналізатору, що будує таблицю імен і фіксує фрагменти синтаксичної структури. Крім цього, між таблицею імен і синтаксичною структурою фіксуються додаткові семантичні зв'язки. У результаті формується об'єктна модель програми, звільнена від прив'язки до синтаксису мови програмування. Досить часто замість синтаксичної структури, що повністю копіює ієрархію об'єктів мови, створюється її спрощений аналог, що називається проміжним представленням.

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

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

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

Можна виділити два основних варіанти взаємодії блоків транслятора:

      багатопрохідну організацію, при якій кожна з фаз є незалежним процесом, що передає керування наступній фазі тільки після закінчення повної обробки своїх даних;

      однопрохідну організацію, при якій всі фази представляють єдиний процес і передають один одному дані невеликими фрагментами.

На основі двох основних варіантів можна також створювати їхні різноманітні сполучення.

2. Формальний опис вхідної мови програмування

2.1. Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура

<program>     ::= Program<ident>; Var < Data_Blok> Start <Code_Blok> Finish.

< Data_Blok >::= [Integer[<declaration> [{, <declaration>} ] ] ] ; .

<declaration> ::= <ident> [ := <const> ] .

<ident>          ::= _<h_letter>[<l _or_n>][<l _or_n>][<l _or_n>][<l _or_n>] .

<l_or_n>        ::= <l_letter>|<number> .

<h_letter>      ::= A|B|C|D|E|F|G|H|I|J|K|L|N|M|O|P|Q|R|S|T|U|V|W|X|Y|Z .

<l_letter>       ::= a|b|c|d|e|f|g|h|i|j|k|l|n|m|o|p|q|r|s|t|u|v|w|x|y|z .

<number>       ::= 0|1|2|3|4|5|6|7|8|9 .

<const>          ::= [-]<number>[{number}] .

<Code_Blok> ::= <statement> [{<statement>}] .

<statement>    ::= <equation>|<cycle>|< Input >|< Output >|<Condition> .

<equation>     ::= <ident> := <expression2>; .

<expression1> ::= [(]<operand>[)] [{ [)]<operation1>[(]<operand>[)] }] | <expression2> .

<operand>      ::= <ident>|<const>| <expression1> .

<operation1> ::= ==|!=|Le|Ge|!!|&&| || .

<expression2> ::= [(]<operand>[)] [{ [)]<operation2>[(]<operand>[)] }] | <expression3> .

<operation2> ::= +|- .

<expression3> ::= [(]<operand>[)] [{ [)]<operation3>[(]<operand>[)] }] .

<operation3> ::= Mul|Div|Mod .

<cycle>           ::= For(<ident>:=<expression2>)DownTo (<expression2) Do

                            Start <Code_Blok> Finish.

<Condition>   ::=If(<expression1>) Start <Code_Block> Finish

< Input >        ::= Input (<ident>); .

< Output >    ::= Output (<string>|<ident>); .

<string>         ::= “{/<l_or_n >|<h_letter>/}” .

2.2. Опис термінальних символів та ключових слів

Визначимо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова):

50

Program

Var

Start

Finish

Integer

Input

Output

For

DownTo

Do

If

+

-

Mul

Div

Mod

==

!=

Le

Ge

!!

&&

||

:=

/*

*/

;

,

“

(

)

50

До термінальних символів віднесемо усі цифри (0 - 9), латинські літери (a - z, A - Z), символи пробілу, табуляції та кінця рядка.

3. Розробка транслятора вхідної мови програмування

3.1. Вибір технології програмування

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

До переваг такого підходу можна віднести:

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

2.      Можливість зберігання даних, одержуваних у результаті роботи кожної з фаз, на зовнішніх запам'ятовувальних пристроях і їхнього використання в міру потреби.

3.      Можливість зменшення обсягу оперативної пам'яті, необхідної для роботи транслятора, за рахунок послідовного виклику фаз.

До недоліків варто віднести:

1.      Наявність більших обсягів проміжної інформації, з якого в цей момент часу потрібно тільки невелика частина.

2.     Зменшення швидкості трансляції через послідовне виконання фаз.

3.2. Проектування таблиць транслятора та вибір структур даних

Використання таблиць значно полегшує створення трансляторів, тому у даному випадку використовуються декілька таблиць:

1.      Таблиця лексем:

public class Lexema

    {

        public Lexema() //конструктор по замовчуванню

        {

            Type = LexemType.Null;

            Line = 0;

            Text = "";

            Value = 0;

        }

        public LexemType Type; //тип лексеми

        public int Line; //лінія, в якій зустрічається лексема

        public string Text; //текст лексеми

        public int Value; //значення лексеми, якщо це константа чи ідентифікатор,

                                    //інакше 0

    }

     List<Lexema> LexTable; //список лексем

2.      Таблиця ідентифікаторів:

   public class Identificator

    {

        public Identificator()  //конструктор по замовчуванню

        {

            Line = 0;

            Name = "";

            Value = 0;

            IsDeclared = false;

        }

        public int Line; //лінія, в якій зустрічається ідентифікатор

        public string Name; // ім’я ідентифікатора

        public int Value; // значення ідентифікатора

        public bool IsDeclared; // інформація чи ідентифікатор є задекларованим

    }

    public List<Identificator> IdentTable; // список ідентифікаторів

3.      Таблиця стрічкових констант:

   public struct Strings

    {

        public string Name; //ім’я стрічкової константи (присвоюється динамічно)

        public string Value; // значення стрічкової константи

    }

    public List<Strings> StringTable; // список стрічкових констант

3.3. Розробка лексичного аналізатора

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

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

3.3.1.     Розробка граф-схеми алгоритму

Для кращого розуміння дій, що виконуються транслятором наведемо граф -схему алгоритму лексичного аналізу (мал. 3.3.1.1):

Малюнок 3.3.1.1 (Граф -схема алгоритму лексичного аналізу)

Призначення блоків:

Блоки 1-2: Ініціалізують члени класу параметрами переданими в конструктор

Блок 3: Викликає функцію отримання чергової лексеми GetLexem(). Алгоритм її роботи наведено на мал. 3.3.1.2

Блок 4: Додає отриману лексему в список лексем(таблиця лексем представлена списком List<Lexema> LexTable;)

Блок 5: Перевіряє чи остання отримана лексема є кінцем файлу. Якщо так тоді переходить до блоку 7, якщо ні тоді до блоку 3.

Блок 6 - 7:  Повертають список лексем та завершують роботу лексичного аналізатора.
Граф - схема отримання лексеми:

Малюнок 3.3.1.2  ( Граф - схема отримання лексеми)

Кінцем тексту вважається символ : $

Роздільником вважається:   \n \t  <space>

Початком рядкової константи вважається: \”

Початком лексеми вважається: A – Z   0 – 9 ; : + - ! & | = ( ) ,

Зарезервовані слова:

50

Program

Var

Start

Finish

Integer

Input

Output

For

DownTo

Do

If

+

-

Mul

Div

Mod

==

!=

Le

Ge

!!

&&

||

:=

;

,

“

(

)

50

3.3.2  Опис програмної реалізації лексичного аналізатора:

Лексичний аналізатор програмно реалізований за допомогою класу:

Основним методом є функція CreateLexTable(), яка повертає таблицю лексем.

Функція працює за алгоритмом наведеному на малюнку 3.3.1.1

-  Поки отримана лексема не є кінцем вхідного тексту, зчитується наступна лексема

   та додається до таблиці.

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

Функція працює за алгоритмом наведеним на малюнку 3.3.1.2

-  Створюється нова лексема, з значеннями по замовчуванню, якщо в ході виконання вони не зміняться, це означає що була помилка, і лексема буде типу Null

-  Перевіряється символ в даній позиції (блоки 2, 3, 5, 14)

-  Якщо символ є:

      Роздільником – він пропускається (блок 4)

      Початком коментаря – пропускається коментар, в випадку якщо не знайдено закінчення коментаря – додається повідомлення про помилку.

(блоки  6, 7, 8)

Початком рядкової константи – обробляється як рядкова константа, якщо не знаходиться закінчення рядкової константи – додається повідомлення про помилку. (блоки  10, 11, 12, 13)

      Початком лексеми – символи до найближчого роздільника