Міністерство освіти Російської Федерації

Саратовський державний технічний університет

ЛАБОРАТОРНА РОБОТА № 1

Лексичний аналіз вхідного мови транслятора лабораторна робота з курсу «Теорія обчисліть-льних процесів і структур »для студентів спеціальності 220400 (ПВС)

Склав доцент кафедри ПВС

Сайкін А.І.

Саратов, 2001 р.

Введення

Дана лабораторна робота призначається для студентівспеціальності ПВС вивчають «Теорію обчислювальних процесів і структур».
Лабораторна робота розрахована на 4 аудиторних годин і 6 годинсамостійної роботи по складаннюпрограми, вивчення літератури і складання звіту.

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

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

Програма складається на мовах Паскаль і С + + за вибором студента всередовищі WINDOWS.

1. Зміст роботи.

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

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

Дескриптор-це пара виду: (. <Покажчик>),де - це, як правило, числовий код класу лексеми, якийозначає, що лексема належить одному з кінцевим безлічі класівслів, виділених у мові програмування;

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

Кількість класів лексем у мовах програмування може бутирізним. Найбільш поширеними класами є: ідентифікатори; службові (ключові) слова; роздільники; константи.

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

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

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

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

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

2. Завдання по роботі.

2.1. Отримати варіант завдання у викладача.

2.2. Відповідно до виданого варіантом виконати наступне:

2.2.1. Скласти технічне завдання (ТЗ) на розробкупрограми сканера, що виробляє лексичний аналіз довільних текстів умежах встановленого алфавіту.

2.2.2. Узгодити ТЗ з викладачем.

2.2.3. Розробити програму-сканер на мовах
Паскаль, С + + або в інтегрованих середовищах на власний розсуд.

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

2.2.5. Скласти звіт по роботі і прикласти до неї ТЗ.

3. Варіанти завдань.

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

Таблиця 1. Алфавіт вхідної мови.
| № | Алфавіт |
| 1 | Латинську, малі літери |
| 2 | Латинську, великі літери |
| 3 | Кирилиця, малі літери |
| 4 | Кирилиця, великі літери |
| 5 | Латинську, малі + заголовні |
| 6 | Кирилиця, малі + заголовні |

Таблиця 2. Ключові слова.
| № | Додаткові ключові слова |
| 1 | Опис циклів, масивів |
| 2 | Опис операторів переходу, |
| | Структури типу switch |
| 3 | Опис безумовних переходів, |
| | Опис функцій |

Таблиця 3. Бібліотечні функції.
| № | Стандартні функції |
| 1 | sin, cos, tan, exp |
| | Sqrt, log, ln, nearby |
| 2 | |
| 3 | abs, fact, code, sign |

Наприклад, 1-2-3 означає, що з першої таблиці необхідно вибратиперший рядок, з другого таблиці - другий рядок, з третьої таблиці --третій рядок.

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

Роздільники: +, -, *,:, _, /, (,), (,), =,, [,
],;, ", ',', 'І про -бел.

Ідентифікатори повинні починатися з літери, не включати в себероздільники, кількість позицій не повинне перевищувати 14.

Текст програми повинен допускати використання коментарів.

4. Методичні вказівки.

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

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

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

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

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

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

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

У ході лексичного аналізу можуть виконуватися і інші видилексичного контролю, зокрема, перевірятися парність дужок та іншихпарних символів, наявність позначки в оператора, наступного за GOTO і т.д.

Результати роботи сканера передаються у наслідку на вхідсинтаксичного анлізатора. Є дві можливості їх зв'язку:роздільна зв'язок і нероздільно зв'язок.

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

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

Розглянемо конкретний приклад. Нехай нам дана програма надеякому алгоритмічній азике:

PROGRAM PRIMER;

VAR X, Y, Z: REAL;

BEGIN

X: = 5;

Y: = 6;

Z: = X + Y;

END;

Застосуємо наступні коди для типів лексем:

К1-ключове слово;

К2-роздільник;

К3-ідентифікатор;

К4-константа.

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

Таблиця 4. Ключові слова.

| № | Ключове слово |
| 1 | PROGRAM |
| 2 | BEGIN |
| 3 | END |
| 4 | FOR |
| 5 | REAL |
| 6 | VAR |

Таблиця 5. Роздільники.
| № | Роздільники |
| 1 |; |
| 2 |, |
| 3 | + |
| 4 | - |
| 5 |/|
| 6 | * |
| 7 |: |
| 8 | = |
| 9 |. |

Результат роботи сканера таблиця ідентифікаторів і таблиця констант

Таблиця 6. Ідентифікатори.
| № | Ідентифікатори |
| 1 | PRIMER |
| 2 | X |
| 3 | Y |
| 4 | Z |

Таблиця 7. Константи.
| № | Знач. констант |
| 1 | 5 |
| 2 | 6 |

На підставі складених таблиць можна записати вхідний текст черезвведені дескриптори (дескріпторний текст):

(К1, 1) (К3, 1) (K2, 1)

(K1, 6) (K3, 2) (K2, 2 ) (k3, 3) (K2, 2) (K3, 4) (K2, 7) (K1, 5) (K2,
1)

(K1, 2)

(K3, 2) (K2, 7) (K2, 8) (K4, 1) (K2, 1)

(K3, 3) (K2, 7) (K2, 8) (K4, 2) (K2, 1)

(K3, 4) (K2, 7) (K2, 8) (K3, 2) (K2, 3) (K3, 3) (K2, 1)

(K1, 3) (K2, 9).

6. Зміст звіту.

1. Титульний лист.

2. Варіант завдання.

3. Повний список обраних ключових слів і стандартних функцій.

4. Внутрішні таблиці сканера.

5. Технічне завдання на розробку сканера (по еурд).

6. Налагодження приклади роботи сканера з вихідними таблицями ідескріпторним текстом.

7. Контрольні питання.

1. Дайте визначення граматики.

2. Назвіть етапи трансляції програми.

3. Що таке лексема?

4. У чому полягають завдання лексичного аналізу?

5. Дайте визначення метамови.

6. Вихідні дані для сканера.

7. Результати роботи сканера.

8. Література.
1. Бек Л. Введення в системне програмування. М,: Світ, 1988.

-448 с.
2. Компанієць Р.І. та ін Системне программірованіе.Основи побудови трансляторів .- СПб.: КОРОНА принт, 2000.-256 с.