Синтаксичний аналіз та валідація даних на основі скінченних автоматів (Ragel)

Досить часто в роботі зустрічаються завдання пов'язані з синтаксичним аналізом (парсингом) структурованих даних. Іноді розміри полів таких структур мають фіксовану довжину, а іноді ширина поля залежить від типу структури (або розмір задається значенням поля).

Для парсингу простих структур з фіксованим розміром, іноді досить написати просту функцію засновану на адресній арифметиці. Якщо поля структур визначені роздільниками (наприклад CSV), то можна скористатися токенайзером (tokenizer). У випадках коли структура даних підпорядковується нетривіальній логіці, то можна скористатися регулярними виразами (regex).

Скористатися можна, але іноді regex недостатньо гнучкий. Іноді недостатньо продуктивний – внаслідок широких можливостей, інструмент робить навіть більше ніж потрібно (з відповідним «пенальті» по швидкості).

Далі пропонується альтернативне рішення засноване на практично необмежній гнучкості, з чудовою функціональністю і продуктивністю: Ragel. Ragel – компілятор скінченних автоматів, що виробляє вихідний код на C / C ++, C #, Objective-C, D, Java, O'Caml, Go і Ruby.

Опис можливостей з Вікіпедії:

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

Реалізація парсеру на Ragel фактично схожа на оголошення формальної системи опису синтаксису (БНФ).

Опис парсеру на Ragel можна умовно розділити на 4 частини (приклад для C++):

1. Оголошення службових змінних

Ragel розраховує на те що в зоні видимості будуть оголошені змінні, які будуть використані для роботи скінченного автомата (надалі СА).

int cs 0;                             //числове уявлення поточного стану 
int top = 0;                          //глибина рекурсії, при явному переході між станами
int stack[1024] = {0};                //стек для зберігання переходів. В даному випадку 1024 - максимальна
                                      // глибина вкладеності
                                       
const char *p =  <some str>;          //вказівник на початок даних, що розглядаються
const char *pe = p + <size of data>;  //вказівник на кінець даних
const char *eof = pe;                 //теж саме, що й pe
const char *ts = NULL;                //покажчик на початок даних відповідних СА 

Також в коді можуть зустрічатися змінні які оголошені самим Ragel, і вони мають певне призначення.

   fpc ;                    // вказівник на поточний 
                            // символ в рядку, що аналізується
                             
   <ім'я СА>_error;          // номер стану СА,
                            // відповідний неконсистентному стану.

2. Оголошення СА

%%{
        machine test_easy;

        action greet
        {
                /*
                 * 2.1 c/c++  код тут у вигляді action
                 */                
        }

        GREETING_TARGET = "World" | "Me" ;
        SP = space* ',' space*;
        main := "Hello"  SP GREETING_TARGET >{ts=fpc;  /*2.2 c/c++ in-place код тут */} %greet  ;
    }%%

Гнучкість Ragel полягає в тому, що можна виконувати будь-який користувацький код при зміні стану СА. Перехід СА в потрібний «початковий» і «кінцевий» (допустимий) стан, власне кажучи, і є критерієм успішності розбору послідовності (pattern-match). При вході та виході з певного стану необхідно зберегти значення вбудованої змінної fpc. Все що посередині – фрагмент даних, який був валідований СА. Призначений для користувача код може бути виконаний в тілі за допомогою заздалегідь оголошеної спеціальним чином функції (2.1) або in-place (2.2).

Приклад виконання користувальницького коду in-place

    TEST_AUTOMATA = "Hello World" >{ std::cout << "Початок"; }  %{ std::cout << "Кінець"; } ;

Приклад виконання користувальницького коду в тілі action

    action my_begin
    {
         std::cout << "Початок";
    }
    
    action my_end
    {
        std::cout << "Кінець"; 
    }

    TEST_AUTOMATA = "Hello World" >my_begin  %my_end;

Приклади обробки переходів

   TEST_AUTOMATA  >{ /* c/c++ код тут */ } - перехід в початковий стан
   TEST_AUTOMATA  <{ /* c/c++ код тут */ } - перехід в будь-який стан, крім початкового
   TEST_AUTOMATA  ${ /* c/c++ код тут */ } - перехід в будь-який стан
   TEST_AUTOMATA  %{ /* c/c++ код тут */ } - перехід в кінцевий стан
   TEST_AUTOMATA  @{ /* c/c++ код тут */ } - перехід в будь-який стан, крім кінцевого
   TEST_AUTOMATA <>{ /* c/c++ код тут */ } - перехід в будь-який стан, крім початкового і кінцевого

3. Оголошення скрипта генерації коду ініціалізації та старту СА

%%{
        machine test_easy;   #3.1
        
        action greet { /*код c/c++*/}  #3.2
        GREETING_TARGET = "World" | "Me" ; #3.3
        SP = space* ',' space*;       #3.4
        
        main := "Hello"  SP GREETING_TARGET >{ts=fpc;} %greet  ; #3.5
    }%%

Оголошення СА обов'язково має містити ім'я самого СА.

Оголошення імені відбувається за допомогою директиви machine (3.1).

Директива action задає функцію, яка буде викликана на ім'я, при зміні стану СА (3.2). Код вставлений в функцію – звичайний C/C++ код, який може звертатися до всіх функцій і змінних в області видимості. Далі можуть бути оголошені один або більше призначених для користувача СА в форматі:

<ім'я> = <опис>;

Призначені для користувача СА можуть бути скомбіновані в будь-якому порядку, через оператори. (і) |(або) !(не).

В наведеному вище прикладі GREETING_TARGET може приймати одне зі значень «World» або «Me» (3.3).

СА *SP* - це 0 або більше whitespace'ів    
      за якими йде символ ','   
         після якого йде послідовність з 0 або більше whitespace'ів.   (3.4)

Будь-який СА з якого Ragel повинен згенерувати код, повинен містити в собі обов'язкове оголошення main (3.5), яке є підсумковим результатом комбінації всіх оголошених раніше користувальницьких СА.

Ragel надає вбудовані СА, які можуть бути використані окремо або в складі користувальницьких СА.

Вбудовані СА багато в чому повторюють аналоги з регулярних виразів.

4. Перевірка кінцевого стану СА (перевірка валідності парсингу)

     if (cs == test_easy_error )
     {
         /*номер кінцевого стану (cs) відповідає неконсистентному. 
          *позицію (зміщення в символах) в рядку, яка викликала помилку парсеру, можна обчислити як 
          *p-<address of <some str>>
          */
     }
     else
     {
         //все добре, парсинг пройшов без помилок.
     }

Приклад 1 (demo_easy)

У цьому прикладі на вхід парсеру подається простий рядок, яка може приймати вид «Hello, Me» або «Hello, World». У разі якщо вхідна послідовність відповідає очікуваній (одній з), виводиться повідомлення про успішний парсинг. Якщо вхідна послідовність не відповідає очікуваної – виводиться повідомлення про помилку, і індекс символу вихідного буфера починаючи з якого СА не змогла перейти в один з можливих станів.

Приклад 2 (demo_advanced)

Цей приклад трохи ускладнений: на вхід дається рядок, який являє собою якийсь формат, що нагадує кортежі. Елементами кортежу можуть бути інші кортежі, з глибиною вкладеності тисяча двадцять чотири (задається користувачем). Програма послідовно, рядок за рядком виводить значення елементів в консоль, причому відступ при друку залежить від глибини укладення. Ragel безпосередньо не підтримує можливість опису рекурсивних СА, для обробки вкладених структур. Для таких випадків є можливість вказати явно, стан в яке треба перейти. Зв'язка fhold; fcall <мітка> говорить що СА повинен перейти в початковий стан відповідного СА з ім'ям <мітка>. fhold вказує що перед переходом в новий стан останній оброблений символ не треба брати до уваги (відкат). Функція fret використовується для того, щоб повернутися в початковий стан, в якому був СА до виклику fcall.

Для того щоб мати можливість явно переходити в стан за допомогою fcall, повинні бути оголошені в поточній області видимості змінні int top і int stack [N], які використовуються Ragel для зберігання стека переходів.

Інтеграція з проектом

Вихідним для Ragel є файл з розширенням *.rl; Для того щоб згенерувати парсер необхідному мовою, потрібно виконати команду:

>ragel -o main_generate.cpp main.rl

Після цього згенерований файл main_generate.cpp може бути вставлений в будь-який проект (вручну, за допомогою Makefile, qmake тощо).

Щоразу руками генерувати .cpp файл незручно, тому можна засобами вашої системи збирання автоматизувати цей процес. Тестовий приклад для цих цілей використовує CMake.

Для успішної компіляції, однак, вихідний файл * .rl також необхідний, тому що частина коду імпортується в згенерований c/cpp файл за допомогою директиви line:

#line 44 "main.rl"

Для допитливих

Скінченний автомат згенерований Ragel можна візуалізувати за допомогою graphviz. Використовую опцію '--V' можна згенерувати .dot файл, який є графом переходом між станами СА.

>ragel -V main.rl > main.dot
>dot -Tpng -o main.png main.dot

Аналізуючи складність графа переходів можна судити про загальну ефективність реалізованого парсеру.

Посилання на демо-проект на GitHub.