додати матеріал


Розробка та налагодження формальної мови

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Введення

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

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

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

Щоб створити подібний мову в рамках даної курсової роботи необхідно відповідно до вимог до мови розробити граматику, в якій буде описаний синтаксис мови, а потім налагодити її за допомогою методів простого і паралельного передування.

Для методу паралельного передування необхідно розробити алгоритм машинного представлення методу; потім провести лексичний аналіз, побудувати автоматні граматики виділення лексем і схему сканера, описати принцип його роботи.

Призначення і область застосування

Розробка мови C + + несе виключно навчальну мету і проводиться з метою поглибити і розширити пізнання автора в дисципліні «Теорія трансляцій», а також у придбанні навичок розробці навчального мови і проведення роботи, що готують мову до побудови транслятора.

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

Технічні характеристики

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

Перелік вимог щодо розроблюваного мови програмування:

Процедура Sub.

Оператор оголошення констант.

Опис типу змінних за допомогою суфікса: Sin 99 gle, Integer.

Масиви фіксованого розміру з макс. розмірністю 2

Оператори введення / виведення MsgBox, InputBox.

Арифметичні операції: + \ ^.

Логічні операції: Not, And, Or.

Операції порівняння.

Умовний оператор типу If ... Then

Оператор циклу типу For ... Next.

Оператор присвоювання.

Оператор безумовного переходу.

Функції: конкатенація рядків, Cbool, Format, GetAllSettings.

Елементи управління: TextBox, CommandButton, CheckBox, PictureBox.

Опис застосовуваних математичних методів

Введемо декілька визначень:

Визначення 1. Контекстно-вільною граматикою G називається четвірка впорядкованих множин:

G = {Vт, Vn, P, S}, де

Vт - словник термінальних символів граматики;

Vn - словник нетермінальних символів граматики;

P - множина правил граматики:

P = {(A, ) | A->  & A  Vn &   V *}

S - початковий символ граматики (S  Vт);

V * - множина рядків, складених із символів повного словника

V (V = Vт  Vn);

V * = { |  = п  ( x  V) ( Q  V *)  = Qx}

п - порожня ланцюжок.

Визначення 2. Ланцюжок  o породжує нетривіальним чином ланцюжок  o (записують  o => + W), якщо існує послідовність безпосередніх висновків:

o =>  1 => ...  n, n> = 1.

Визначення 3. Ланцюжок  породжує ланцюжок Q (записують  => * Q), якщо  => + Q, або  = Q.

Визначення 4. Ланцюжок називається сентенціальной формою граматики G, якщо вона виводиться з початкового символу граматики, тобто якщо S-> * .

Визначення 5. Пропозиція мови - це сентенціальная форма, що складається тільки з термінальних символів.

Визначення 6. Мова L (G) - це безліч пропозицій

L (G) = { | S-> +     Vт *}.

Визначення 7. Символи A, B контекстно-вільної граматики пов'язані ставленням FIRST, якщо виконується умова

A -> B ,

де A  Vn, B  V,   V *.

Визначення 8. Символи A і B граматики пов'язані ставленням .=., Якщо у граматиці є правило види:

W   A У .

Визначення 9. Ставлення>. Між символами A і B граматики знаходиться з правила:

(>.) = (LAST +) T (. =.).

Визначення 10. Ставлення <. Між символами A і B граматики знаходиться з правила:

(<.) = (. =.) (FIRST +).

Розробка граматики з неформального опису мови

Відповідно до технічного завдання на розробку мови напишемо граматику, лістинг якої наведений у Додатку 1.

Щоб перевірити її коректність складемо контрольний приклад:

Sub D11 ()

Dim A As Integer,

B% As Integer

Const D As Single

Dim M (2) As Integer A = (B * 2 + 9) ^ 10

If ((IsNumeric (A) <> 0 and A> 0) Then

MsgBox («A is number», vbOkOnly) EndI

Text. Text = A

End Sub

Дерево до цього прикладу наведено на аркуші А1.

Розробка сканера

Лексичний аналіз проводиться сканером (лексичним аналізатором). Сканер виділяє найпростіші мовні конструкції (лексеми) і класифікує їх тип.

Сканер працює з таблицями, які є базою даних сканера.

Таблиці діляться на постійні і тимчасові.

Постійні таблиці створюються розробником сканера і включають в себе:

ТТС1 - таблиця термінальних символів (однолітерних).

ТТС2 - таблиця термінальних символів (двулітерних).

ТКС - таблиця ключових слів.

Тимчасові таблиці створюються в процесі роботи сканера і залежать від вихідного модуля (програми, що перевіряється сканером). Тимчасові таблиці включають в себе:

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

ТК - таблиця констант.

ТФ - таблиця функцій.

ТСС - таблиця стандартних символів.

ТСС є результатом роботи сканера. Це взаємно-однозначне відображення вихідного модуля.

Формальне визначення лексем.

Лексичні одиниці:

арифметичні операції: «+», «/», «^».

операції порівняння: «>», «<», «=», «>=», «<=», «<>»

операція присвоювання: «=»

дужка відкриває «(«

дужка закриваюча «)»

службові слова:

«Dim», «As», «Private», «Public», «Sub», «End», «goto», «Optional», «MsgBox», «InputBox».

умовний оператор: «If», «Then»

оператор циклу: «For», «Next»

тип и даних: «Single», «Byte», »Date», «Integer», «Boolean», «String», «Variant», «Object».

елементи управління: «TextBox», «ComandButton», «CheckBox», «PictureBox»

властивості елементів управління: «Caption», «Text», «With», «Height», «Visible»

спеціальні константи: «VbOkOnly», «VbOkCansel», «VbAbortRetryIgnore»,

«VbCritical»

логічні функції: «Not», «And», «Or»

функції: «Format», «CBool», «GetAllSettings». нижнє підкреслення: «_»

точка: «."

лапки: «@»

десяткові цілі константи

ідентифікатор

Розробляємо структури даних, які будуть використовуватися сканером.

Таблиця 1. Однолітерние термінальні символи TTC 1:

Адреса

Символ

KTL

1


26

27


54

a

...

z

A

...

Z

1

55

...

64

0

...

9

2

65

=

3

66

>

3

67

<

3

68

^

3

69

*

3

70

-

3

71

\

3

2 липня

#

3

7 березня

%

3

7 Квітень

.

3

75

_

3

76

@

3

77

(

3

7 серпня

)

3

Таблиця 2. Двулітерние термінальні символи

Адреса

Символ

KTL

1

<=

3

2

> =

3

3

<>

3

Таблиця 3. Класи поточних літер

Символ

Клас

Буква

1

Цифра

2

Допустимий символ

3

Таблиця 4. Функції

Логічні ф-та (адреса)

Not (1)

And (2)

Or (3)

Функції (адреса)

CBool ​​(5)

Format (6)

GetAllSettings (7)

Concat (8)

Таблиця 5. Тип лексичної одиниці

Лексична одиниця

Тип

операція «=»

1

операція «-»

2

операція «*»

3

операція «^»

4

операція «\»

5

операція «mod«

6

роздільники «.», »,«

7

нижнє підкреслення "_"

8

лапки «@»

9

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

10

службові слова

11

умовний оператор

2 Січень

оператор циклу

3 січня

тип даних

1 квітня

елементи управління

1 травня

оператор циклу

1 червня

події елементів управління

1 липня

властивості елементів управління

18

спеціальні константи

19

логічні функції

20

функції

21

десяткові а цілий а констант а

22

ідентифікатор

23

назва функції

24

псевдонім функції

25

бібліотек

26

відкриває дужка «(«

27

закриваюча дужка «)»

28

Для кожної лексичної одиниці складаємо автоматну граматику.

Ідентифікатор:

S = б K

K = б K | ЦК |% F | # F

Десяткова ціла константа:


S = «ц» D

D = «ц» D | e 2 F

Ступінь:

S = «^» F

Розподіл:

S = «\» F

C мiщення:

S = «+» F

Знаки відносини:

S = «<» A | «>» B | «=» F

A = «=» D | «>« D | e 3 F

B = «=» D | e 4 F

D = e 5 F


Дужки відкр ивающая «(»:


S = «(« F

Дужка закриваюча »)»:


S = «)» F

Операція «=»:

S = «=» F

Точка «.»:

S = «.» F

Нижня підкреслення «_»:


S = «_» F

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

Схема узагальненого кінцевого автомата

Сканер виконує наступні дії:

1. Виділяє лексичні одиниці.

2. Класифікує лексичні одиниці.

3. Визначає лексичні помилки;

4. Створює деякі внутрішні форми подання - таблиці стандартних символів (ТСС).

Побудуємо узагальнений автомат для всього сканера (схема сканера). Для цього об'єднаємо початкові символи опису всіх лексем в стартову вершину. Схема сканера наведена нa Рис. 12.

У даному сканері використані наступні скорочення:

A - вхідна ланцюжок;

NA - кількість символів вхідний ланцюжка;

TL - поточна літера;

NTL - номер поточної літери;

KTL - клас поточної літери;

TLE - тип лексичної одиниці;

LE - лексична одиниця;

MDLE - максимальна довжина лексичної одиниці;

NLE - поточна довжина LE;

ALE - компонента запису ТСС, яка визначає адресу лексичної одиниці у відповідній таблиці.

На рис. 12 зображена схема сканера

Рис. 12. Схема сканера

Семантичні підпрограми сканера

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

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

1) виділення поточної літери;

2) об'єднання рядків;

3) виконання арифметичних операцій.

У даному сканері задіяні такі підпрограми:

Підпрограма PODGOT (підготовка):

NTL = 0;

NLE = 0;

TLE = A [NTL];

KTL = KLASS (TL); {визначаємо клас TL}

STRCOPY (LE, "»);

Підпрограма TIP (визначення типу):

IF KTL = 2 {цифра}

THEN {можна визначити тип лексичної одиниці}

TLE = 2;

MDLE = 7;

ELSE ERROR («помилка»);

Підпрограма BKL (включення):

NLE + +;

IF NLE> MDLE

THEN ERROR («помилка»)

ELSE LE = LE | | TL;

Підпрограма SLL (наступна літера)

NTL + +;

TL = A [NTL];

KTL = klass (TL);

Підпрограма ZAPTAB (LE, TLE, ALE, REZ):

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

Запис елемента в ТСС можна здійснити за допомогою процедури OUT (TLE, ALE).

Таблиці сканера для тестової ланцюжка

Private Sub D11 () Dim A As Integer, B% As Integer Const D As Single Dim M (2) As Integer A = (B / 2 + 9) ^ 10 If ((IsNumeric (A) <> 0 and A> 0 ) Then MsgBox («A is number», vbOkOnly) EndIf Text. Text = A End Sub

Таблиця 6. Константи

Константа

Атрибути


Тип

Кома

Точність подання

Основа системи числення

2

integer

Ні

1

10

9

integer

Ні

1

10

0

integer

Ні

1

10

10

integer

Ні

1

10

Таблиця 7. Ідентифікатори

Ідентифікатор

Атрибути

Адреса ідентифікатора


Тип

Кома

Основа системи числення


A

integer

немає

10

1

B%

integer

немає

10

2

C

integer

немає

10

3

D

Single

немає

10

4

Таблиця 8. Стандартні символи

Лексична одиниця

Тип лексичної одиниці

Адреса лексичної одиниці

Private

10

10

Sub

10

10

D11

21

21

(

22

77

)

23

78

Dim

10

10

A

21

1

As

10

10

Integer

13

13

,

6

74

B%

21

2

As

10

10

Integer

13

13

Const

10

10

D

21

3

As

10

10

Single

13

13

A

2 Січень

1

=

1

65

(

22

77

B%

21

2

,

6

74

B%

21

2

/

5

70

2

20

2

+

2

69

9

20

4

)

23

78

^

3

68

10

20

3

If

11

11

(

2 лютого

78

(

2 лютого

78

IsNumeric

19

2

(

2 лютого

77

A

21

1

)

2 Березня

78

<>

9

67

0

20

3

and

18

1

A

21

1

>

9

66

0

20

3

)

23

78

Then

11

11

A

21

1

=

1

65

B

21

2

EndIf

11

11

Text

14

14

.

6

74

Text

16

16

=

1

65

A

21

1

End

10

10

Sub

10

10

Налагодження формальної граматики

Налагодження граматики - це процес перетворення граматики до виду, що задовольняє використовуваний метод синтаксичного аналізу.

У вихідній граматиці 42 конфлікту. Серед них зустрічаються конфлікти трьох типів:

Конфлікти типу = <



uslovie

(

= <

Рис. 13. Конфлікт типу = <

Для того, щоб показати як налагодити цей конфлікт, розглянемо його на прикладі:

З рисунка 3. 13 в ідно, що між термінальним символом «(» та нетермінальним uslovie конфлікт типу = <. Щоб його налагодити необхідно опустити нетермінал uslovie вниз по дереву.

Таким чином, між символами «(» та uslovie залишилося тільки ставлення <.

Всі інші конфлікти цього типу вирішуються аналогічно.

Конфлікт типу =>

Щоб показати як вирішуються конфлікти цього типу, дозволимо конфлікт між символами Вody і Еnd. Цей конфлікт зображений на малюнку 15.


End

Вody

=>

Рис. 15. Конфлікт типу =>

Синтаксичний аналіз

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

Завдання синтаксичного аналізатора:

1) виділення синтаксичних одиниць;

2) визначення всіх синтаксичних помилок (якщо вони є);

3) перетворення таблиці стандартних символів (ТСС) в деяку внутрішню форму представлення програми (ВФПП).

Схема програми синтаксичного аналізатора

Схема програми синтаксичного аналізу методом простого передування наведена в графічному додатку (Лист1).

Прийняті позначення:

X - масив символів аналізованої ланцюжка;

MP - матриця простого передування;

P - множина правил граматики, які описують мова;

ST - стік для визначення хвоста основи;

ST 1 - стек для визначення голови основи;

TL - поточна літера;

NTL - номер поточної літери;

OSN - масив, в якому буде накопичуватися основа;

NOSN - кількість символів в масиві OSN (поточну кількість символів в основі);

A -> , де  - права частина правила, яка збігається з масивом OSN, A - ліва частина правила, на яку замінюється основа;

REZ - результат.

Щоб виділити основу необхідно спочатку знайти кінець основи, а потім її початок, після чого виділяється основа (блоки J 2 - O 8).

Якщо після виділення рядка OSN знаходиться правило, у якого права частина правила збігається з OSN те, змінної REZ присвоюється 1, якщо такого правила немає - помилка, синтаксичний аналіз може бути припинено або потрібно виправити помилку (блок R 8).

Операції виконуються над рядковими змінними:

st. push (i) - помістити елемент i в стек;

st. pop () - видалити елемент з стека;

st. top () - отримати доступ до вершини стека;

st. nst () - визначити кількість елементів в стеку.

Робота даного алгоритму представлена ​​в таблиці синтаксичного аналізу в графічному додатку (Лист1).

Висновок

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

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
111.8кб. | скачати


Схожі роботи:
Закони формальної логіки
Методологічна функція формальної логіки
Вступ до дисципліни логіка предмет і мова формальної логіки
Методична розробка заняття з іноземної мови
Проектування та розробка класів засобами мови програмування СBuilder60
Розробка двох уроків англійської мови для середньої школи
Паскаль Налагодження програм
Налагодження системи та монтаж
Налагодження міжособових комунікацій в менеджменті
© Усі права захищені
написати до нас
Рейтинг@Mail.ru