Парсер на РНР - це можливо!
Антон Калмиков
У даній коротенькій статті я хочу продемонструвати,
що РНР може дуже добре справлятися з функцією синтаксичного розбору
виразів. Для тих, хто ніколи не стосувався даної тематики, я думаю, стаття
буде так само цікава, оскільки в ній ми розглянемо метод програмування в
вигляді кінцевих автоматів.
Почну з твердження, що метод програмування з
застосуванням кінцевих автоматів дуже простий, оскільки більша частина програми
міститься всередині автомата, який ви готуєте заздалегідь у вигляді матриці і
використовуєте в своїй програмі.
Що ж таке автомат?
Уявіть собі дискретну функцію від двох аргументів
Ft (d, Ft-1). Як перший аргумент ми використовуємо кінцеве лічильний
безліч (масив даних), яка поступає ззовні. На кожному кроці у функцію
надходить тільки одне число з даного масиву. Другим аргументом функції
є значення функції на попередньому кроці. Додам ще одна умова. Область
значень даної функції являє собою кінцеве рахункове безліч.
У чому привабливість такої функції? Вся краса полягає в
тому, то ми можемо уявити її у вигляді матриці, де номери рядків будуть задавати
дані, що надходять, а номери стовпців будуть представляти область значень
функції. Тоді, записавши в клітинку (рядок, стовпець) число з безлічі значень
функції, ми отримаємо матрицю, яка описує залежність функції від вхідних
даних і всього спектру значень. Будемо називати число з безлічі значень
СТАНОМ, а функцію Автомата.
Якщо ви не зрозуміли попереднього абзацу, то не лякайтеся, на
практиці все виглядає набагато простіше. Давайте розглянемо простий приклад.
Припустимо, нам треба побудувати розбір звичайного арифметичного виразу. Для
цього нам доведеться створити два автомати. Перший буде виділяти
"слова" з буфера даних (тобто сканувати його). Другий буде
перевіряти граматичний порядок проходження слів у виразі.
Почнемо зі сканера. Словами є знаки операцій +, -,
*,/І послідовності символів, якщо вони не містять роздільників, такі
як новий рядок, пробіл і символ табуляції. Роздільники ми будемо просто
ігнорувати. Автомат для сканера, в цьому випадку, буде наступним.
//
стану 0, 1, 2
"0"
=> Array (0, -1, -1),// розділювач
"1"
=> Array (2, -1, -1),// слово з одного символу
"2"
=> Array (1, 1, -1),// символ
Номери рядків задають тип символу, оскільки нам треба
виділити знаки операцій в окремі слова. Стану (номери стовпчиків) будуть
означати наступне.
-1 слово
готове, пора повертати
0 початок
сканування
1 отримали
символ, треба збирати поки це символ
2 отримали
зумовлене слово з одного символу
в стані 1 ми будемо збирати символи, щоб повернути їх
як слово в змозі -1. Наш сканер буде викликатися з парсера і завершувати
свою роботу, коли він розпізнає хоча б одне "слово", тому немає
сенсу вводити стан -1 до таблиці автомата. Для парсера автомат буде
такий.
//
стану 0, 1,
2, 3, 4, 5
"0"
=> Array (1, -1, 1, 1,
1, 1),// оператор
"1"
=> Array (2, 4, -1, 2, -1, -1),// операнд
"2"
=> Array (3, 3, -1, 3, -1, -1),// ліва дужка
"3"
=> Array (-1, -1, 5, -1, 5, 5),
//Права дужка
а стану відповідно
-1 Помилка
0 Початок розбору
1 Отримали
оператор, чекаємо правий операнд
або ліву
дужку
2 Отримали лівий
операнд (треба перевірити чи число це),
чекаємо оператор
або праву дужку
3 Отримали ліву
дужку,
очікуємо
оператор або ліву дужку
4 Отримали правий
операнд (треба перевірити чи число це),
очікуємо
оператор або праву дужку
5 Отримали праву
дужку, чекаємо оператор
Парсер завершить роботу, коли сканер поверне FALSE або при
виникненні помилки - стан -1. З тієї ж причини, що і в сканері ми
можемо не вносити стан -1 до таблиці автомата
Далі привожу код програми з докладними коментарями,
які замінять подальші пояснення. Я не будую дерева операцій у прикладі
даного парсера. Ви можете зробити це самі, адже у відповідних станах
автомата ви отримаєте оператор і операнди.
class ExpressionParser (
var $ pos,// Позиція в буфері для розбору
$ length,// Довжина буфера
$ line,// Поточний номер рядка
$ column,// Поточний номер колонки в рядку
$ data,// Буфер даних
$ brackets,// Кількість відкритих дужок
$ state,// Поточний стан парсера
$ errorstr,// Рядок діагностики помилки
$ instates,// Код слова що подається на вхід автомата
$ prevstate,//
Попереднє стан парсера
$ automat;// Таблиця автомата парсера
/********************************************** ************************
* Конструктор *
************************************************** ********************/
function
ExpressionParser ($ str) (
$ this-> data = $ str;
$ this-> length = strlen ($ str);
$ this-> pos = 0;
$ this-> line = 1;
$ this-> column = 0;
$ this-> brackets = 0;
// Коди слів, виданих сканером, що подаються
на вхід парсера
// Решта слова
мають код 1
$ this-> instates
= Array ( "+" => 0, "*" => 0, "-" => 0, "/"
=> 0, "(" => 2, ")" => 3);
// Автомат парсера
$ this-> automat = array (
/*
-1 Помилка
0 Початок розбору
1 Отримали оператор,
чекаємо правий операнд або ліву дужку
2 Отримали лівий
операнд (треба перевірити чи число це), чекаємо оператор або праву дужку
3 Отримали ліву
дужку, чекаємо оператор або ліву дужку
4 Отримали правий
операнд (треба перевірити на число), чекаємо оператор або праву дужку
5 Отримали праву
дужку, чекаємо оператор
*/
// стани 0, 1, 2, 3, 4, 5
"0" => array (
1, -1, 1, 1, 1, 1),// оператор
"1" => array (
2, 4, -1, 2, -1, -1),// операнд
"2" => array (
3, 3, -1, 3, -1, -1),// ліва дужка
"3" => array (-1, -1, 5, -1,
5, 5),// права дужка
);
$ this-> state = $ this-> prevstate = 0;
)
/********************************************** ************************
* Сканер *
*********************************************** ***********************/
function Scan () (
// Роздільники,
які ігноруємо
$ delimiters = array ( "
"," t "," r "," n ");
// Слова з одного символу
$ words = array ("+","-","*","/","(",")");
// автомат сканера
$ automat = array (
/*
-1 слово готове,
час повертати
0 початок сканування
1 отримали символ,
треба збирати поки це символ
2 отримали зумовлене
слово з одного символу
*/
// стани 0, 1, 2
"0" => array (
0, -1, -1),// розділювач
"1" => array (
2, -1, -1),// слово з одного символу
"2" => array (
1, 1, -1),// символ
);
$ state = 0;
$ word = "";
// Цикл сканування
while ($ this-> pos <$ this-> length) (
// Встановлюємо код що подається на
вхід автомата символу.
if
(in_array ($ this-> data [$ this-> pos], $ delimiters))
$ instate = 0;
elseif
(in_array ($ this-> data [$ this-> pos], $ words))
$ instate = 1;
else
$ instate = 2;
// Отримуємо стан
автомата
$ state = $ automat [$ instate] [$ state];
// Наші дії
по станів автомата
switch ($ state) (
case 0:// початок сканування
if
($ this-> data [$ this-> pos] == "n") (
$ this-> line + +;
$ this-> column = 0;
)
$ word = "";
break;
case -1:// слово
готове, пора повертати
if (strlen ($ word)) return $ word;
break;
case 1:// отримали
символ, треба збирати поки це символ
$ word .= $ this-> data [$ this-> pos];
break;
case 2:// отримали
зумовлене слово з одного символу
$ word = $ this-> data [$ this-> pos];
break;
)
$ this-> pos + +;
$ this-> column + +;
if
($ this-> pos == $ this-> length & & strlen ($ word)) return $ word;
)
return
false;
)
/********************************************** ************************
* Парсер *
************************************************** ********************/
function
Parse () (
// Змінна $ first дорівнює нулю, якщо
функція розбору була викликана перший раз
$ first = $ this-> pos;
// Цикл станів
while (1) (
// Отримуємо слово від сканера
$ word = $ this-> Scan ();
// Якщо слів більше
ні, то перериваємо цикл
if ($ word === false)
break;
// Встановлюємо
код, що подається на вхід автомата, слова
$ instate = isset ($ this-> instates [$ word])?
$ this-> instates [$ word]
: 1;
// Отримуємо стан
автомата парсера
$ this-> state = $ this-> automat [$ instate] [$ this-> state];
// Якщо помилкове стан, то перериваємо
цикл
if ($ this-> state ==- 1) (
$ this-> errorstr = "Помилка в рядку: $ this-> line, колонка: $ this-> column
";
break;
)
// Наші дії
по станів автомата парсера
switch ($ this-> state)
(
case 1:// Отримали
оператор, чекаємо правий операнд або ліву дужку
// Якщо перше слово
оператор, то це може бути тільки "+" або "-"
if (($ this-> prevstate == 3 | |
$ this-> prevstate == 0) & & $ word !="-" & &
$ word !="+") (
$ this-> errorstr = "Помилка в рядку: $ this-> line, колонка: $ this-> column
";
return false;
)
break;
case 2:// Отримали
лівий операнд (треба перевірити чи число це), чекаємо оператор
// або праву
дужку
// Перевіряємо число
Чи це так?
if
(! preg_match ("/^[ 0-9 ]+(.[ 0-9 ]+)?$/",$ word)) (
$ this-> errorstr = "Помилка в рядку: $ this-> line, колонка: $ this-> column
";
return false;
)
break;
case 3:// Отримали
ліву дужку, чекаємо оператор або ліву дужку
// Збільшуємо кол-во
відкритих дужок на 1;
$ this-> brackets + +;
// Зручно використовувати
рекурсію, тому що дані в дужках
// можна розглядати
як самоcтоятельние вирази.
// Ми повернемося з
функції у разі помилки, кінця даних або
// після отримання закритої дужки
if
(! $ this-> Parse ()) return false;
break;
case 4:// Отримали правий операнд
(треба перевірити чи число це), чекаємо оператор
// або праву
дужку
// Перевіряємо число
Чи це так?
if
(! preg_match ("/^[ 0-9 ]+(.[ 0-9 ]+)?$/",$ word)) (
$ this-> errorstr = "Помилка в рядку: $ this-> line, колонка: $ this-> column
";
return false;
)
break;
case 5:// Отримали
праву дужку, чекаємо оператор
// Зменшуємо кол-во
відкритих дужок на 1
$ this-> brackets -;
return true;
)// end
switch
// Запам'ятовуємо поточний стан для
наступного кроку циклу
$ this-> prevstate = $ this-> state;
)// end
while
// Так як у нас відсутня стан
кінця розбору, то треба
// Перевірити в якому
стані ми завершили розбір
// Це треба робити
тільки один раз на самому першому виклику
// функції розбору.
Це перший виклик, якщо $ first == 0
// Отже, ми повинні
повернути помилку, якщо в нас є зайві дужки,
// або якщо ми не
отримали правого операнда або правої дужки,
// тобто розбір завершився
"на середині".
if (! $ first & & ($ this-> brackets
| | $ This-> state! = 4 & & $ this-> state! = 5)) return false;
return true;
)
)
$ p = new
ExpressionParser ( "-4.25 * ((2 +3) * 4 +1)/5");
print $ p-> data. "
";
if ($ p-> Parse ())
print "Вираз коректно.
";
else
print
$ p-> errorstr;
?>
Список літератури
Для підготовки даної роботи були використані матеріали
з сайту http://www.realcoding.net/
