1.2. Побудова лексичного аналізатора засобами скінченного автомату

1.2.1. Особливості побудови лексичного аналізатора засобами скінченного автомату

При побудові лексичного аналізатора (сканера) всі символи вхідного тексту програми поділяють на символи, що належать будь-яким лексемам, і символи, що розділяють лексеми: пробiли, знаки операцiй i спецiальні символи (новий рядок, знак табуляції). Це дає можливість побудувати скінченний автомат, який видiляє та розпізнає iдентифiкатори, лiтерали i термiнальнi символи (операцiї, ключові слова, тощо), а також видаляє коментарі, прбіли, інші спеціальні символи. Розроблений скінченний автомат можна реалізувати за допомогою операцій обробки рядків реалізованих в стандартних бібліотеках мови С/С++, наприклад, strtok(), strstr(), srtcmp(). При цьому текст вхiдної програми проглядається послiдовно з початку до кінця. При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компiляції звертатись лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора. Імена ідентифікаторів записуються в таблицю ідентифікаторів з присвоєнням унікальної адреси кожному унікальному ідентифікатору в таблицях лексем і ідентифікаторів. Ця таблиця в подальшому буде використана на етапі генерації коду.

1.2.2. Приклад побудови лексичного аналізатора засобами скінченного автомату

Лексичний аналізатор, що розглядається в прикладі здійснює зчитування вхідного тексту з попередньо видаленими пробілами і символами табуляції. З вхідного тексту програми видаляють коментарі. При цьому, коментарі можуть бути вкладеними, і баланс фігурних дужок може бути порушеним. Для виявлення цих помилок будемо використовувати Стек1 в який будуть поміщатися і вилучатися дужки, і Стек2, який буде містити номер рядка в якому стоять відповідні дужки у Стек1. Вхід аналізатора – текст програми з видаленими пробілами і символами табуляції. Вихід аналізатора - масив, у який треба записати вхідну програму без коментарів і пробілів (Рис. 1.2). Далі здійснюють виявлення не термінальних символів у зчитаному тексті і виведення повідомлення про помилки (рис.1.3).

Рис. 1.2. Граф-схема аналізу вкладених коментарів.

Рис. 1.3. Граф-схема аналізу символів.

Після успішного проходження перших двох етапів генерують таблицю ідентифікаторів (рис.1.4) і таблицю лексем (1.5).

Рис. 1.4. Граф-схема аналізу сегменту даних з генерацією таблиці ідентифікаторів.

Рис. 1.5. Граф-схема аналізу сегменту коду з генерацією таблиці лексем.

Рис.1.6. Перевірка таблиці ідентифікаторів на помилки.

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