Лексичний аналіз Програмування,уроки та приклади

Programm.ws - це сайт, на якому ви можете почитати літературу з мов програмування, а також подивитися приклади працюючих програм на С++, асемблері, паскалі і багато іншого.

Програмування - у звичайному розумінні, це процес створення комп'ютерних програм. У вузькому значенні (так зване кодування) під програмуванням розуміється написання інструкцій - програм - конкретною мовою програмування (часто за вже наявним алгоритмом - планом, методом вирішення поставленого завдання). Відповідно, люди, які цим займаються, називаються програмістами (на професійному жаргоні – кодерами), а ті, хто розробляє алгоритми – алгоритмістами, фахівцями предметної галузі, математиками. У більш широкому значенні під програмуванням розуміють весь спектр діяльності, пов'язаний із створенням та підтримкою в робочому стані програм - програмного забезпечення ЕОМ. Точніший сучасний термін — «програмна інженерія» (також інакше «інженерія ПЗ»). Сюди входять аналіз та постановка задачі, проектування програми, побудова алгоритмів, розробка структур даних, написання текстів програм, налагодження та тестування програми (випробування програми), документування, налаштування (конфігурування), доопрацювання та супровід.

Глава 2. Складні структури даних

Лексичний аналіз

Мета лексичного аналізу - виділення та класифікація лексем у тексті вихідної програми. Програма, яка виконує лексичний аналіз, називається сканером або лексичним аналізатором. Сканер здійснює посимвольне читання файлу з вихідним текстом програми. Повний набір лексем мови визначено безліччю термінальних символів у його граматиці. Серед них можна виділити змінні та незмінні лексеми. Незмінні лексеми у будь-якійпрограмі пишуться однаково. Для грам- матики псевдомови це такі лексеми, як: ПРОГРАМА, ЗМІННІ, НАЧ_ПРОГ, КІН_ ПРОГ, НАЧ_БЛОК, КОН_БЛОК, ".", ";", ":", "/", REAL, INTBYTE, INT_WORD, INTD , ",", ":=", "=", "+", "-", "*", DIV, MOD, "(", ")", "[", "]", "", " ==», ЧИТАТИ, ПИСАТИ, ДЛЯ, РОБИТИ, ПОКИ, ДОВНИЗ, ЯКЩО, ЯКЩО, ДО, ТО, ПЕРЕЙТИ_НА, ПОВТОРИТИ. "За бортом" залишилися три термінальні символи - ID, CH_INT, CH_REAL. Ці термінальні символи відповідають ідентифікаторам, цілим і речовим числам. Природно, що навіть у межах однієї програми вони будуть різні. Завданням сканера якраз і є розпізнавання змінних і незмінних термінальних символів. З позиції логіки обробки сканером зручно всі термінальні символи віднести до одного з наступних класів (стосовно нашої граматики псевдомови):

ідентифікатори - ID;
ключові слова - ПРОГРАМА, ЗМІННІ, НАЧПРОГ, КОН_ПРОГ, НАЧБЛОК, КІН_ БЛОК, REAL, INTJYTE, INTWORD, INT_DWORD, DIV, MOD, ЧИТАТИ, ПИСАТИ, ДЛЯ, РОБИТИ, ПОКИ, ДОВНИЗ, ДОВНИ, ПОВТОРИТИ;
цілі числа - CHINT;
речові числа - CH_REAL;
однолітерні роздільники - ".", ",", ";", ": , "+", "-", "*", "/", "(", ")", "=", "[", "]", "";

У дволітерні роздільники - ":=", "=", ">=", "=

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

d – цифра;
1 - літера;
b - літери, які ігноруються, до них може належати, наприклад, пробіл;
s1 - одиночні роздільники: ".", ":", "(", ")", "*";
s2 - особливі одиночні роздільники: ".", "+", "-", ":", "=", "".

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

ПРОГРАМА progl (1M14, #progl) ЗМІННІ (2) INTBYTE 1 (6) (14. #i) ПОЧ_ПРОГ (26) ДЛЯ i := ПРО ТО 9 РОБИТИ (10Н14, #i) (24)(15. 0)(13)(15. 9Н11) ПИСАТИ (i) (9)(12)(14, #i)(25) КОНПРОГ (27)

унікальний номер — номер, який на наступних етапах трансляції ідентифікуватиме дане символьне ім'я;
вказівник на список, що містить символи ідентифікатора;
покажчик на список із номерами рядків, у яких зустрівся цей ідентифікатор.

Згодом, коли імена ідентифікаторів не будуть потрібні, можна на основі цього дерева побудувати хеш-таблицю, доступ до елементів якої здійснюватиметься на основі унікальних номерів. До речі, для підвищення ефективності процесу розпізнавання варто всі термінальні символи - ключові слова мови, роздільники і т. п. (за винятком id, chint і ch_rea1) - також звести в окремелексикографічне дерево або організувати хеш-таблицю. Можна вчинити по-іншому. Цей варіант, який можна використовувати для аналізу введення командного рядка і т. д., працює у випадку, якщо сканер викликається з синтаксичного аналізатора. Суть його в тому, що сканер викликається із синтаксичного аналізатора, коли останньому потрібна чергова лексема. Сканер виділяє її у вхідному потоці і видає синтаксичному аналізатору кортеж із двох елементів: коду лексеми та рядки, що містить саму лексему. А як організувати процес розпізнавання лексем вхідний програми? Для цього спробуємо сформулювати узагальнений алгоритм побудови сканера.

1. Виділити класи лексем. 2. Визначити класи літер. 3. Визначити умови виходу зі сканера кожного класу лексем. 4. Для кожного класу лексем поставити у відповідність граматику класу 3. 5. Для кожної граматики, побудованої на кроці 4, побудувати кінцевий автомат, який розпізнаватиме лексему цього класу. 6. Виконати об'єднання («склеювання») кінцевих автоматів всім класів лексем. 7. Скласти матрицю переходів для «склеєного» кінцевого автомата. 8. "Навісити" семантику на дуги "склеєного" кінцевого автомата. 9. Вибрати коди лексичного згортки для терміналів граматики та формат таблиці ідентифікаторів. 10. Розробити програму сканера.

Цілком реалізовувати цей алгоритм для сканера транслятора спрощеної мови Паскаль ми не будемо. Це не є предметом нашої книги. Нас цікавлять насамперед організація даних та можливості по роботі з ними на асемблері. Тому для того, щоб пояснити підхід до подібних завдань, ми зупинимо свою увагу на кроках 1-8 наведеного алгоритму.