Лабораторные роботи з Теорії обчислювальних процесів і структур

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

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

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

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

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

Сайкин А.И.

Саратов, 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, co, 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 с.