48893 (Розробка системних програмних модулів та компонент систем програмування), страница 2

клас операторів циклу 8

клас лексем оголошення 9

клас лексем опису і аргументів виводу 10

клас синтаксичних лексем 11

клас констант 12

Відомості про класи з таблиці лексем використовуються при синтаксичному аналізі. Інформація з поля atribute використовується при семантичному аналізі.

Ключові слова мають такі коди:

Program 0

Var 1

Start 2

Finish 3

Input 4

Output 5

For 6

DownTo 7

+ 8

– 9

Mul 10

Div 11

Mod 12

:= 13

== 14

!= 15

Le 16

Ge 17

!! 18

&& 19

|| 20

(21

) 22

; 23

24

<< 25

>> 26

Integer 27

Bool 28

Усі ідентифікатори та цифрові константи отримують код 30. Коди використовуються генератором коду для формування відповідних процедур мовою асемблер.

Для реалізації стеку використано таку структуру:

struct stacktype

{char data[20] [10];

int prior[20];

int kod[20];

int top;

};

Поле data використовується для зберігання символу операції;

Поле prior використовується для зберігання пріоритету операції;

Поле kod використовується для зберігання коду операції;

Поле top вказує на вершину стеку.

Для запам’ятовування виразу в постфікс ній формі використовується така структура:

struct Form

{

char post[25] [10];

int cod[25];

};

Поле post призначене для зберігання ідентифікаторів, констант і символів операцій;

Поле cod призначене для зберігання коду лексеми, що міститься у відповідному полі post.

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

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

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

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

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

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

На фазі лексичного аналізу можуть бути сформовані такі помилки:

• не розпізнана лексема;

• перевизначення ідентифікатора;

• неправильний ідентифікатор (не починається з великої літери);

• ідентифікатор є зарезервованим словом;

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

num – містить рядок, у якому була знайдена лексема;

slovo – містить символи, якими описується лексема;

klas – містить клас лексеми;

atribute – містить атрибут ідентифікатора («і» для цілих змінних, «b» лдя логічних змінних і «0» для не ідентифікаторів);

code – містить код лексеми;

Коментарі в таблицю лексем не заносяться.

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

Блок під номером 2 описує частину коду програми, в якому реалізований вибір наступної букви із файлу з програмою. Оскільки пробіл та символ нового рядка в лексеми не входять, то в блоці 3 здійснюється перевірка чи поточний символ не є пробілом або символом переходу на новий рядок. Якщо умова перевірки справджується, то слід вибрати наступну лексему, а цю просто пропустити. Якщо умова перевірки не виконується, то поточний символ додається до лексеми. Якщо лексему не вдається розпізнати (блок 4), то слід перейти до наступного символу, якщо лексема розпізнана, то вона заноситься до таблиці лексем (блок 5).

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

Граф-схема алгоритму лексичного аналізу (1 аркуш) розроблена згідно усіх правил ЄСКД та поміщена у додатках.

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

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

В програмі використовуються такі прапорці:

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

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

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

number_flag – використовується для виділення символьних констант. Якщо прапорець встановлений в одиницю, то використання символьних констант дозволяється (наприклад після оператора присвоєння), якщо прапорець в нулі, то в цьому місці символьні константи використовувати не можна (наприклад після лексем відкриття і закриття блоку).

bool_flag – використовується для надання атрибутів ідентифікаторам при їх описі. При знаходженні відповідної лексеми прапорець встановлюється в одиницю, а прапорець цілих змінних скидається в нуль. Поки прапорець встановлений, змінним присвоюється атрибут «b». Скидається при знаходженні лексеми оголошення цілих змінних чи початку блоку програми.

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

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

blok_flag – використовується для підрахунку відкритих і закритих блоків.

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

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

Розбір призначений для доказу того, що аналізований вхідний ланцюжок, записаний на вхідній стрічці, належить або не належить безлічі ланцюжків породжуваних граматикою даної мови. Виконання синтаксичного розбору здійснюється розпізнавачами, тому даний процес також називається розпізнаванням вхідного ланцюжка. Мета доказу в тому, щоб відповісти на питання: чи належить аналізований ланцюжок безлічі правильних ланцюжків заданої мови. Відповідь «так» дається, якщо така приналежність встановлена. Інакше дається відповідь «ні». Отримання відповіді «ні» пов'язано з поняттям відмови. Єдина відмова на будь-якому рівні веде до загальної відмови.

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

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

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

3.7 Розробка дерев граматичного розбору

Коренем дерева є не термінальний символ <Program>. Безпосередньо його листками є термінал Program та нетермінали <Blok>, <Declaration>, <Ident>. Листками нетерміналу <Blok> є термінали Start і Finish та нетермінали <Statement>, <Equation>, з листком <Cycle> існує двосторонній зв’язок. Нетермінал <Declaration> має термінальний листок Var та нетермінальний <Type> (листки Integer і Bool) і зв’язок з нетерміналом <Ident>. <Ident> має три листки – <Small_letter>, <Big_letter> і <Number>. <Statement> має два листки – <Input> (листок Input) і <Output> (листок Output) і зв’язок з нетерміналом <Equation>. <Equation> має зв’язок з нетерміналом <Ident>, нетермінальні листки <Compare>, <Const>, <Operation_a>, <Operation_m>, <Operation_l> і термінальний листок»:=». <Cycle> має два термінальні листки – For і DownTo і нетермінальний – <Const>. Від <Const> відходять два зв’язки, один до нетерміналу <Number>, другий до термінального символу» –». <Compare> має чотири термінальні листки – «==», "!=», «Le» і «Ge». <Operation_a> має листки «+»,» –»; <Operation_m> має листки «Mul», «Div» і «Mod». <Operation_l> має листки»!!», «And» і «||». Листками нетерміналу <Small_letter> є усі малі літери латинської абетки, <Big_letter> – великі літери латинської абетки. <Number> має десять термінальних листків – «0», «1», «2», «3», «4», «5», «6», «7», «8», «9».

Дерево граматичного розбору розроблено згідно правил, даних у формі розширеної нотації Бекуса-Наура, та оформлено згідно правил ЄСКД. Граф схема дерева граматичного розбору (1 аркуш) міститься в додатках.

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

Другий блок описує частину програми, де з таблиці лексем вибирається чергова лексема. Далі лексема проходить перевірку на її приналежність до одного з класів. В третьому блоці перевіряється чи належить лексема до класу лексем блоку. Якщо так, то вибираються лексеми, що стоять до і після заданої і ланцюжок перевіряється на коректність. Такий алгоритм роботи усіх ділянок програми, на які описані блоками 4, 6, 8, 10, 12, 14, 16, 18, 20, 22. У таблиці наведено усі перевірки, що ведуть до розгалуження алгоритму.

Таблиця 3.1. Блоки галуження

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