Розробка системного програмного забезпечення

Введення

Розробка системного програмного забезпечення-це пряме завданнясистемного програміста. Більш того розробка не є кінцевий пункт йогодіяльності. Досконале володіння цим інструментом-ось головне завдання.
Системне програмування є однією і найбільш широкою областюпрограмного забезпечення. Головним преймуществом його єбезпосередня гнучкість і спрямованість на досягнення певноїзавдання. Логіка і формальність-ключ до системного програмування.

У даній роботі розглянуто приклад реалізації мови за допомогоюпопулярної мови високого рівня C + +. Тому сам продукт розробкиавтоматично відноситься до типу «компіляторів». На відміну від інтерпретаторівта асемблер даний варіант може бути доступним для розуміння широкомуколу програмістів на що і був розрахований. У роботі розглянуто приклад,вхідним мовою якого є мова Сі. Цікавим моментом тутє розвиток мови за допомогою самого себе. Тобто фактично маючипевний набір команд або функції можна не тільки сконструювати а йрозширити свою власну мову. Інша справа чи буде він корисний іоднозначний?

Розроблений мова у цій програмі за класифікацією
Хомського відноситься до автоматною граматики, тому що останню ланкудекомпозиції задовольнять правилом побудові такого роду граматик.
Зауваження: пункт 6, 7, 8 не є правилами виведення, а лише служать длявідображення семантичної і синтаксичної боку граматики.

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

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

Рис 1. Функціональне дерево дзвінка. Елементи І і АБО визначаютьвибірковість при виконанні функції. Тобто у разі елемента І виконається якперша так і друга функція. Для елемента АБО виклик функції визначаєтьсяоднозначно.

| | | | | | | | |
| | | | TREATM | | | | |
| | | | ENT | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | & | & | & | & | & | & | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| TYPE | BRACKET | TERM | SIGN | TERM | BRACKET | FUNC | TZ |
| | | | | | | | |
| | | | | | | | |
| | | 1 | | 1 | | & | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | DIGIT | IDENT | DIGIT | IDENT | TERM | BRACKET | |
| | | | | | | | |

Розшифровка:
1. TYPE - функція TYPE ( «набір термінальних символів»). У даному випадку є TYPE ( «if»). Сканує відповідні термінальні символи і видає повідомлення про помилку у випадку невідповідності поточного та вхідного мов.
2. BRACKET - функція (англ. «дужка»). У даному випадку має вигляд:
BRACKET (1)-параметр функції характеризує тип дужки.
1-відкривається 2-закривається 3-и та і інша

3. TERM - функція TERM (). Сканує на терм-конструкцію.
4. SIGN - функція SIGN () (англ. «знак»). Сканує знак.
5. DIGIT - функція DIGIT () (англ. «цифра»). Сканує на ціле число.
6. IDENT - функція IDENT () (скор. «ідентифікатор»). Сканує на ідентифікатор.
7. FUNC - функція FUNC (), сканує на функціональну конструкцію.
8. TZ - функція TZ () (скор. «крапка з комою»), сканує крапку з комою.

TYPE BRACK TERM SIGN

FUNC TZ

рис. 2 Функціональна схема роботи програми. Кожному входу елементавідповідає свій вихід.

Дана функціональна схема відображає роботу програми з точки зорувиклику функції. Початок роботи програми йде з подачі на вхід блоку TYPEкеруючого термінального символу IF. Після його обробки йде запитнаступного функціонального блоку, що відповідає за обробку термінальнихсимволів «(» та «)». Потім сигнал подається на вхід пристрою,відповідного термінальних символів TERM і т.д.

Завдання функціональної схеми-більш наочно, на мові інженера,відобразити обробку вхідного мови за принципом рекурсивного узвозу. Дляприклад вирішимо завдання:

Завдання: чи належить граматики мови наступне синтаксичнепропозиція:

IF (A

Для вирішення задачі звернемося до наявного вхідногомові G.

Будь-яка мова, назвемо його G в незалежності від його класифікації тафункціонального призначення містить наступні базисні елементи: G = (
Vt, Vn, Z, P), де:
Vt - словник термінальних символів
Vn - словник нетермінальних символів
Z - початковий нетермінальний символ
P - множина правил виводу

Для мови G маємо наступні множини:

Vt = (0, 1, 2, ... , 9; a, b, c, d, ... , z; A, B, C, ..., Z;, =);

Vn = ( «Оператор», «УслВир», «Терм», «Операнд», «Функція», « Ідентифікатор »,
«Дужки», «Ціле»);
Z = ( «Оператор»);
P = (

1. <Оператор> (IF (<УслВир>) <Функція>;

[ELSE <Функція>;]
2. <УслВир> (T | <УслВир> > T |
<УслВир> = Т
3. <Терм> (O | «Ціле» ( «Ціле») | «Ідентифікатор» (О)
4. <Функція> (O <Дужки> | О (О) <Дужки>
5. <Операнд> ( «Ціле» | «Ідентифікатор»
6. <Ціле> = (0, 1, 2, 3, ... , 9)
7. <Ідентифікатор> ((a, b, c, d, ..., z; A, B, C, ..., Z)
8. <Дужки> (((,))

)

<Оператор>

<УВ>

<
Функція>

OOO (O)

ід ід (ид)

ВД
ВД ВД ВД
IF (A ();

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

G <Інструкція> (PRINT (<УВ>) (<УВ>) <Функція>;
(Подальша конструкція мови ідентична мові G <Оператор>).

Сконструіруем дерево виклику в такий спосіб:

TREATMENT (TYPE ( «print») (BRACKET (1) (TERM () ( SIGN () (TERM () (
BRACKET (2) (BRACKET (1) (TERM () (SIGN () (TERM () (BRACKET (2) (FUNC () (
TZ ()

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

Мова G <Оператор> виконаний зі значними усікання тому непретендує на роль ідеального базису. Наприклад обов'язковий виклик функціїпісля круглої дужки,хоча реально це лише мізерна частина можливих операцій.
Автор даної роботи не ставив перед собою завдання сконструювати більшменш оптимальний мову. Головна мета-це відобразити розуміння принципупобудови граматик і вироблення мови.

Кілька слів про саму програму. Програма виконана,як я вже упомянал, на мові Сі, з елементами Сі + +. Після запускупрограми безпосередньо відразу буде запропоновано аналіз синтаксису.
Словом у верхній частині екрана необхідно ввести рядок і натиснути клавішу
«ENTER». Залежно від набору символів у нижній частині з'являтьсявідповідні повідомлення:a) Про помилки-у разі невідповідності вхідного і поточного мовb) «Успіх!»-в іншому випадку

Є можливість використання ключових слів:
1. «Help»-виводить на екран вікно допомоги
2. «Helpme»-виводить на екран авторське вікно
3. «Exit»-вихід з програми

Наведено роздруківка самої програми, з докладними коментарями до неї.
Уточню, що це не повна викладка. Функції роботи з вікнами занепотрібністю упущені автором.

Постановка завдання

Користуючись базовим мовою високого рівня С + + розробити і реалізуватисинтаксичний аналізатор умовного оператора
IF ELSE мови Сі.

Порядок виконання:

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

2. Підбір граматики G [Z] з мови L
Побудований формальний мова L, піддається декомпозиції, в процесіякої виявляються лексичні складові - ідентифікатори, константи іін термінальні символи.

3. Класифікація G [Z]
Для гарантії однозначності та безповоротній розробленого мовногопроцесора обрана мова віднести згідно класси -сифікацію формальних граматик, запропонованих Хомський.

4. Вибір методу аналізу
Проаналізувати і вибрати найбільш відповідний аналіз вхідного мови.

5. Діагностика та нейтралізація помилок
Розробити алгоритм діагностики і нейтралізації помилок.

6. Тестування на програми на символьних ланцюжках
Протестувати розроблений мовної процесор на конкретних символьнихланцюжках.

7. Лістинг
Наприкінці звіту помістити роздруківку програми з докладними коментарями.

Побудова формальної мови L

<Оператор> (IF (<УслВир>) <Функція>;
[ELSE <Функція>;]

<Оператор> - початковий нетермінальний символ

IF - вхідний термінальний символ

ELSE - вхідний термінальний символ (може і відсутнім)

<УВ> - умовне вираження

<Функція>-відображає функціональну конструкцію мови Сі

Приклад правильного синтаксису:

if (a );

«CallTheFunction» і «TheNextFunction» - функції

code1 & code2 - параметри функції

Підбір граматики G [Z] з мови L

Для мови G маємо наступні множини:

Vt = (0, 1, 2, ... , 9; a, b, c, d, ... , z; A, B, C, ..., Z;, =);

1. <Оператор> (IF (<УслВир>) <Функція>

)

Класифікація G [Z]

1. <Оператор> (IF (<УслВир>) < Функція>

Зробимо заміну нетермінальних символів:

<Оператор> (Z
<УслВир> (A
<Терм> (B
<Функція> (C
<Список параметрів> (D
<Параметр> (E
<Ідентифікатор> (F

Зробимо заміну термінальних символів:

IF (a
((b
) (c
; (d
ELSE (e
ЦБЗ (f
Б (g
((H

Вибір методу аналізу

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

Діагностика та нейтралізація помилок

Розроблений алгоритм ставиться до загальновідомого методусинтаксичного розбору, запропонований Айресом.

Основна ідея методу полягає в тому, що на контекст без поверненнявідкидаються ті символи, які привели в контексте і розбіртриває.

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

Дано:
IF (A

1. Z (abAcC [eC]
2. A (B | B B | B = B
3. B (F | f
4. C (FbDcd
5. D (E | h
6. E (F | f | h
7. F (g (g | f)

a b A c
C

BBF bcd

FF g (g)

gg (g) gggg

IF (A );

Тестування на ланцюжках

протестуємо дану програму наступного мовної ланцюжку:
IF (A

<Оператор>

ab <УслВираженіе> c <Функція>

<Терм> <Терм> <Ідент > bcd

<Ідентифікатор> <Ідентифікатор> g (g)

gg (g) gggg

IF (A ) ;

1. Перевірка на нетермінальний символ IF
2. Перевірка на термінальний символ «(»
3. Перевірка на умовне вираження
4 Перевірка на терм
5 Перевірка на знак
6 Перевірка на терм
7. Перевірка на термінальний символ «)»
8. Перевірка на функцію
9 Перевірка на ім'я функції
10 Перевірка на наявність термінального символу «(»
11 Перевірка на параметр функції (може й бути відсутнім)
12 Перевірка на наявність термінального символу «)»
6. Перевірка на термінальний символ «;»

Висновок: помилок не виявлено