Застосування скінчених автоматів при розробці лексичних аналізаторів

Поділ множини лексем мови програмування на класи можна виконати на основі різних критеріїв, наприклад, множину операцій в мові С можна розбити на три класи:

- Однолітерні коди операцій: +, -, *, / …;

- Двохлітерні коди операцій: >=, ++, --, …;

- Трилітерні коди операцій: >>=, <<=, ….

Формальне визначення класу лексем мови програмування можна виконати одним з нижченаведених способів:

- За допомогою праволінійних граматик;

- За допомогою скінчених автоматів;

- За допомогою регулярних виразів;

- Перерахувати лексеми даного класу як скінчену множину елементів;

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

L₀ = { +, -, /, *, ….}

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

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

Скінчений автомат має:

- множину станів Q={q₀, q₁, q₂, q₃, q₄, q_5, .., q₁₇};

- вхідний алфавіт S={0,1,..9, A, B,..F, a, b,..f, X, x, L, l, U, u};

- початковий стан q₀;

- множину заключних станів F= Q\{ q₀, q₁₂};

- відображення d визначено діаграмою переходів.

Програму, яка розпізнає множину лексем, реалізуємо двома способами:

- перший спосіб: створимо програмний модуль, роботою котрого керує таблиця управління скінченого автомата М(q_i, a_j), яка визначається в програмі явно;

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

Програмний модуль з управлінням на основі таблиці М(q_i, a_j):

Реалізуємо програмний модуль для скінченого автомата, діаграма переходів котрого зображена на Мал. 1.

#include <stdio.h>

#define OK 1

#define ERROR 0

char alphabet[ ]="0123456789ABCDEFabcdefXxLlUu"; // кількість елементів - 28

// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, a, b, c, d, e, f, X, x, L, l U, u

int sigma[ ][ ]= {

{6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, // q0=1

{2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 5, 5 }, // q1=2

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4 }, // q2=3

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, // q3=4

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 6, 0, 0 }, // q4=5

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, // q5=6

{8, 8, 8, 8, 8, 8, 8, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 13, 0, 0, 0, 0 }, // q6=7

{8, 8, 8, 8, 8, 8, 8, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 11, 11 }, //q7=8

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 10 }, //q8=9

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, //q9=10

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 12, 0, 0 },

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, //q11=12

{14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,0,0,0,0,0,0} //q12=13 {14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,0,0,17,17,15,15},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,16, 16, 0, 0}, //q14=15

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, //q15=16

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18, 18 }, //q16=17

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } //q17=18

};

//Якщо (q_i,a_j)-невизначено, то M(q_i,a_j)=0

int finish[ ]={1,2,4,5,7,8,9,10,11,12,13,14,15,16,17,0}; //заключні стани автомата

//функція, яка по вхідній літері вказує її індекс в масиві alphabet

int index_litera (int litera)

{ for(int i=0; *(alphabet+i) ;i++)

if (litera = = *(alphabet+i)) return i;

return -1; // помилка: недопустима літера

}

is_final (int row )

{ for (int i = 0; *( finish+i) ; i++) if (*( finish+i) == row ) return 1;

return 0;

)

char text[80];

int * MASSIVE(sigma, row, column)

{ if (row == 0) return NULL else return (sigma+(row-1)*28+colomn); }

int automat (FILE*fp)

{int row, c, column, id=0; //row-ім'я рядка таблиці, column - ім'я стовпчика

*(text+id++)=0; row=0; // початкові установки

while((c=fgetch(fp))!=EOF) {

if ((column = index_litera(c)) = = ERROR) break;

row=*MASSIV(sigma, row, column);

*(text+id++)=c; *(text+id)=0;

if (row = = ERROR) break;

}

//досягли кінця файла, або недопустима літера, або…………….

if (is_final ( row )) //ми знаходимося в заключному стані

return OK; else retutn ERROR;

}

main(int argc, char* argv[ ])

{FILE*fp; char file_name[80];

REPEAT:

printf("Вкажіть ім'я файла з лексеми:");

if(scant("%s", file_name) == 0) return 0; //відмовляється працювати

if( fp = fopen (file_name,"rt") == NULL)

{ printf ("файл %s не відкрито.\ n"); goto REPEAT;}

while (! eof (fp))

if ( automat(fp) == ERROR) printf (" Лексема вірна - %s", text);

else printf (''Лексема помилкова-%s", text);

}// кінець main

Нехай маємо текстовий файл, в якому знаходяться лексеми, які відділяються одна від іншої такими символами як: проміжок, \n, \v, \r, \t.. щоб зменшити об'єм таблиці sigma, пропуск символів, які розділяють лексеми в текст будемо виконувати додатково, цілком у функції automat.

Очевидною перевагою програмної реалізації скінчених автоматів наведеним вище способом є простота визначення інформаційних масивів даних: alphabet — вхідний алфавіт автомата, sigma — таблиця переходів автомата, finish — масив імен заключних станів. Серед недоліків реалізації наведеної вище програми яскраво виділяється один – досить великі затрати пам'яті для таблиці sigma. Очевидно, що матриця sigma сильно розріджена, тобто більшість її елементів має значення ERROR. В такому випадку при реалізації скінчених автоматів, кількість станів яких вимірюється десятками, та як вхідний алфавіт розглядається вся кодова таблиця ЕОМ (255 символів), то затрати оперативної пам'яті будуть занадто великі.