Профессиональная разработка Web-приложений.  
Боишься нашего дизайна?
Новости
PDF журнал
Участники проектa
Сотрудничество
Ссылки
Карта сайта
Комментарии
Комментарии к статье
Добавить комментарий
Обсудить на форуме
Информация об авторе
Оценка статьи

Парсер на РНР - это возможно!

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

Парсер на РНР - это возможно!

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

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

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

Представьте себе дискретную функцию от двух аргументов 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==|| $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!=&& $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;
?>



For comment register here
   2002-12-02 02:58
Не совсем ясен смысл этого материала. Автоматный принцип разбора синтаксических конструкций без проблем реализуется практически на оюбом структурном ЯП, в том числе и на PHP. И нет никакого смысла писать для этого отдельную статью. Различным автоматам и так же посвящено мнодество материалов.

   2002-12-02 13:37
1. Не все знают об этом методе
2. Не все уверены в том, что РНР справится с обработкой большого объема кода.
Исходя из этих двух посылок я и писал статью.

   2002-12-04 14:29
Практически о всем есть уже где-то в нете материалы. Имхо, на этом сайте размещаются статьи об основных, ключевых подходах, применяемым в веб-программировании.

   2002-12-05 22:46
> Имхо, на этом сайте размещаются статьи об основных, ключевых подходах, применяемым в веб-программировании.

В форуме на phpclub не единожды проскакивали вопросы по синтаксическому разбору выражений.

   Unknown 2002-12-20 05:26
парсер Antonio один из самых лутших имхо, а их я перепробывал туеву хучу. Так что есть смысл заявить об этом, что он собственно и сделал.

   2003-07-06 10:46
Когда мне потребовалось разобрать арифметическое выражение с вложенными скобками на PHP, я тоже взялся было за конструирование конечного автомата...
А потом догадался, как можно правильно разобрать такое выражение при помощи только регулярных выражений.
Очень просто:
A) в цикле находим все подстроки вида "(([^()]+))".
B) внутри ищем и заменяем последовательно на числа, результаты операций подстроки вида "([0-9]+)*([0-9]+)", "([0-9]+)/([0-9]+)", "([0-9]+)+([0-9]+)", "([0-9]+)-([0-9]+)".
Заменяем до тех пор, пока не останется одно число. Вставляем его на место бывшего выражения в скобках.
Повторяем пункт А, пока не останется скобочных выражений.
Потом еще раз прогоняем пункт B по остаткам выражения.
Вуаля ! Результат получен !
Мой парсер мог еще разбирать выражения с функциями и переменными, не буду приводить алгоритм, IMHO и так все понятно.

   Unknown 2003-09-24 13:19
И как диагностируем ошибки?

   Unknown 2003-09-24 13:25
Опять же как локализовать ошибку в твоем случае?(строка, столбец)

   2003-11-26 18:17
В общем, пороблема в моем варианте парсера только одна -- ошибка (буде таковая имеется) смещается при каждой замене. Обнаружить сам факт наличия ошибки легко: если у нас не срабатывает больше ни одна замена, а в остатке мы имеем не число, то это и есть ошибка.
Далее мы должны найти позицию этой ошибки. Заметим сразу, если в остатке выражения имеется пара скобок "(...)", то ошибка обязательно находится внутри них и мы можем с легким сердцем игнорировать остальные части выражения. Если скобок нет (или мы уже выбрали скобочное выражение с ошибкой), то вариантов там всего 5, например:
<ошибка><знак><число>
<число><знак><ошибка>
<ошибка><число>
<число><ошибка>
<ошибка>
Перебрать эти варианты можно при помощи регулярных выражений. Далее, найдя первый символ ошибки мы можем вычислить его первоначачальную координату. Для этого следует первоначально создать массив, вида [ 1 2 3 4 5 ... n ], где n -- длина первоначальной строки. При каждой замене будем перекраивать массив, производя над ним операцию вида:

[ 1 2 3 4 5 6 7 ] => [ 1 2 3 0 6 7] при замене символов на позициях
4 и 5 одним символом. Таким образом, мы всегда помним изначальные координаты каждой буквы выражения.

Остается лишь одна проблема, которую следует обрабатывать отдельно.
Пример:

100(20+30) => 100(50) => 10050

При каждой замене следет проверять, не приведет ли она к "склеиванию" цифр. Это легко сделать. Сперва копируем исходную строку и делаем замену не на число, а на некую случайную строку вида "" (например) и проверяем, нет ли в получившемся коде подстроки "<число>".

Я все это написал не по тому, что так следует делать на практике, а лишь чтобы показать, что можно построить полноценный парсер без интерпретатора и вобще без использования конечных автоматов. Это очень красивый результат, вы не находите ?

   2003-11-27 13:56
Граждане, если уж учите программированию на PHP, то могли бы и получше написать обработчик постов. Куда подевались выражения в фигурных скобках ?!!

   2003-11-28 11:11
2Pasha.K: Обещаю разобраться в ближайшее время

   2004-03-12 17:17
pasha_k@chat.ru, имхо, ты мягко говоря не прав. парсер на регулярных выражениях написать ОЧЕНЬ трудно. и если возникает такое количество проблем, то что будет если тебе нужно действительно написать сложную программу разбора. с семнтиком и синтаксисом. пример, который сразу приходит в голову -- обработчик шаблонов :)... с тегом, допустим {assgn var = value} который встречается в теле как минимум 2 раза, (не задумываемся пока обо всем остальном) после выполнения рабзора с помощью регулярных выражением все вхождения переменной var будут заменены на последнее обработанное значение. по другому сдалть просто не получится. а если и получится, то получишь настолько громоздкий и долгий код, что как говорится игра не стоит свеч.

   2004-10-12 15:13
Рекурсивно-нисходящий алгоритм разбора - гораздо более понятный и надёжный.

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

 
 
 
    © 1997-2008 PHPClubTeam
[]