Парсер на РНР може бути!

Парсер на РНР — це возможно!

Антон Калмиков

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

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

Что ж таке автомат?

Представьте собі дискретну функцію від двох аргументів 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 в таблицю автомата.

Далее наводжу код програми з докладними коментарями, які замінять подальші пояснення. Не строю дерева операцій на прикладі даного парсера. Можете зробити це самі, либонь у відповідних станах автомата ви отримаєте оператор і операнды.

<?php.

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<br> «;

break;

}.

// Наші дії по станам автомата парсера.

switch ($this->state) {.

case 1: // Отримали оператор, очікуємо правий операнд чи ліву скобку.

// Якщо перша слово оператор, це може лише «+ «чи «- «.

if (($this->prevstate==3 || $this->prevstate==0) && $word≠ «- «&& $word≠ «+ ») {.

$this->errorstr= «Помилка в рядку: $this->line, колонка: $this->column<br> «;

return false;

}.

break;

case 2: // Отримали лівий операнд (треба перевірити число це), чекаємо оператор

//чи праву скобку.

// Перевіряємо число це?

if (!preg_match («/^[0−9]+(. 0−9]+)?$/ «,$word)) {.

$this->errorstr= «Помилка в рядку: $this->line, колонка: $this->column<br> «;

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<br> «;

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. «<br> «;

if ($p->Parse ()).

print «Вислів корректно.<br> «;

else.

print $p->errorstr;

?>

Список литературы

Для підготовки даної праці були використані матеріали із російського сайту internet.