2.3.2 Реалізація діаграми переходів

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

Кожен стан дає частина коду. Якщо зі стану виходять дуги, то його код зчитує черговий символ і вибирає дугу проходження (якщо це можливо). Для читання чергового символу із вхідного буфера використається функція nextchar(), що також переміщає покажчик forward і повертає зчитаний символ. Якщо існує дуга, позначена зчитаним символом (або класом, до якого належить зчитаний символ), то керування передається коду стану, на яке вказує дана дуга. Якщо такої дуги немає, а поточний стан указує, що токен не знайдено, викликається функція fail(), що повертає покажчик переходів. Якщо всі діаграми випробувані, fail() викликає програму обробки помилок.

Для припустимих токенів використаємо глобальну змінну lexical_value, якій присвоюється покажчик, що повертається функціями install_іd() й install_num() .Токен повертається основною функцією лексичного аналізатора, nexttoken().

Для пошуку стартового стану чергової діаграми переходів використається інструкція case. У реалізації мовою програмування C, наведеної на рис. 2.15, дві змінні - state і start - відслідковують поточній й стартове стани випробовуваної діаграми переходів. Номера станів у коді відповідають діаграмам переходів на рис. 2.12-2.14.

int state = 0, start = 0;

int lexical_value; /* Другий компонент токену */

int fail ()

{

forward = token_beginning;

switch (start) {

case 0: start = 9; break;

case 9: start = 12; break;

case 12: start = 20; break;

case 20: start - 25; break;

case 25: recover(); break;

de fault: /* Помилка компіляції */

}

return start;

}

Рис. 2.15. Код С для пошуку наступного стартового стану

Дуги в діаграмах переходів проходяться шляхом повторюваного вибору фрагмента коду для стану і його виконанням для визначення наступного стану, як показано на рис. 2.16. У лістингу наведений код для стану 0, що обробляє проміжки, і код для двох діаграм переходів з рис. 2.13 й 2.14. Звернемо увагу на те, що конструкція while(1) stmt виконує stmt "вічно", тобто до оператора return.

token nexttoken ()

{

while(l) {

switch (state) { case 0: c = nextchar();

/* c - поточний символ, що сканується */

if (c == blank || c == tab, c *= newline) {

state = 0;

lexeme_beginning++;

/* переміщаємо покажчик початку лексеми */

}

else if (c == '<') state = 1;

else if (c == '=') state = 5;

else if (c == '>') state = 6;

else state = fail ();

break;

. .. /* cases 1-8 */

case 9: c = nextchar();

if (isletter(c)) state = 10;

else state = fail();

break;

case 10: c = nextchar();

if (isletter(c)) state = 10;

else if (isdigit(c)) state = 10;

else state = 11;

break;

case 11: retract(1); install_id() ;

return ( gettoken() );

... /* cases 12-24 */

case 25: c = nextchar ();

if (isdigit(c)) state = 26;

else state = fail ();

break;

case 26: c = nextchar();

if (isdigit(c)) state = 26;

else state = 27;

break;

case 27: retract(l); install_num();

return ( NUM );

}

}

}

Рис. 2.16. Код лексичного аналізатора мовою C

Оскільки мова C не дозволяє повернути одночасно й токен, і атрибут-значення, функції install_id () й install_num () установлюють належним чином значення деякої глобальної змінної, привласнюючи їй атрибут-значення, що відповідає запису в таблиці для id або num.

Якщо мова реалізації не має інструкції case, можна створити масив для кожного стану, проіндексований символами. Якщо state1— такий масив, statel[с] — покажчик на частину коду, що повинна виконуватися, якщо поточний скануємий символ — с (звичайно цей код завершується переходом до коду для наступного стану). Масив для стану s можна розглядати як таблицю переходів для s.