ання цих параметрів визначає вибір методу. У даній роботі використовується метод впорядкованого списку.
. 2 Метод впорядкованого списку
Цей метод є простим методом побудови таблиць ідентифікаторів. Елементи записуються в таблицю в порядку зростання. Так як упорядкування таблиці ідентифікаторів відбувається на всіх етапах обігу до таблиці, то для її побудови можна користуватися лише алгоритмом прямого упорядкованого включення елементів. При додаванні нового елементу в таблицю ідентифікаторів він спочатку додається в кінець таблиці, а потім йде переупорядочивание елементів таблиці ідентифікаторів. Ефективним методом для пошуку елементів є логарифмічний пошук, на кожному кроці якого, число елементів, які можуть містити шуканий елемент, скорочується в два рази. Максимально число порівнянь при пошуку 1+ log 2 ( N ).
Схема алгоритму додавання ідентифікатора представлена ??на рис. 1
Рисунок 1 - Алгоритм додавання ідентифікатора
Схема алгоритму бінарного пошуку ідентифікатора представлена ??на рис. 2
Малюнок 2 - Алгоритм пошуку ідентифікатора
2.3 Результат виконання програми
У результаті роботи було виявлено, що недоліком такого методу є вимога упорядкування таблиці ідентифікаторів на всіх етапах обігу до цієї таблиці.
До позитивних якостей методу можна віднести простоту його організації.
3. ПРОЕКТУВАННЯ ЛЕКСИЧНОГО АНАЛІЗАТОРА
. 1 Призначення лексичного аналізатора
Лексичний аналізатор (або сканер) - це частина компілятора, яка читає літери програми мовою оригіналу і будує з них слова (лексеми) вихідної мови. На вхід лексичного аналізатора надходить текст вихідної програми, а вихідна інформація передається для подальшої обробки компілятором на етапі синтаксичного аналізу та розбору.
В основному лексичні аналізатори виконують виключення з тексту вихідної програми коментарів і незначущих прогалин, а також виділення лексем наступних типів: ідентифікаторів, строкових, символьних і числових констант, ключових (службових) слів вхідної мови.
. 2 Граф переходів лексичного аналізатора
Розпізнавач лексем мови для даної граматики заданий кінцевим детермінованим автоматом, схема якого представлена ??на малюнках 3, 4 і 5.
Рисунок 3 - Схема распознавателя 1
Малюнок 4 - Схема распознавателя 2
Малюнок 5 - Схема распознавателя 3
Легенда:
V - будь-який визначений алфавітно-цифровий символ (букви латинського алфавіту, знак «_», десяткові цифри);
V (*) - будь-який символ крім перерахованих в дужках; - букви латинського алфавіту і знак «_»; (*) - будь-яка буква крім перерахованих в дужках;
Р - пробіл, табуляція, перенесення рядка;
D - неприпустимі символи (все крім перерахованих); - збереження (ID - у таблиці ідентифікаторів; L -в таблиці лексем);
e - помилка; - ім'я лексеми;
Стани відповідають:
Н - початковий стан;
К - кінцевий стан;
P1, P2, P3, P4 - стану, відповідні ключовим словом prog;
En1, En2 - стану, відповідні ключовим словом end;
I1, I2 - стану, відповідні ключовому слову if;
E1, E2, E3, E4 - стану, відповідні слову else;
T1, T2, T3, T4 - стану, відповідні слову then;
W1, W2, W3, W4, W5 - стану, відповідні ключовим словом while;
D1, D2 - стану, відповідні ключовим словом do;
S1, S2, S3 - стану, відповідні символьне константі:
A1, A2 - стану, відповідні оператору присвоювання: =;
С1, С2 - коментар;
Програма, реалізована на основі даного автомата, виконує лексичний аналіз тексту програми на заданому мовою.
. 3 Результат виконання програми
Результат розбору вхідних виразів на лексеми представлений на малюнку 6.
Малюнок 6 - Результат роботи лексичного аналізатора (таблиця лексем)
Спроектований лексичний аналізатор виконує лексичний аналіз вхідного тексту відповідно до заданої граматикою і породжує таблицю лексем із зазначенням їх типів. Програма виводит...
