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

 

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

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

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

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

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

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

?>

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

Для подготовки данной работы были использованы материалы с сайта http://www.realcoding.net/




   Еще работы:


Полиморфные вирусы
Введение в полиморфизм Как известно, первые вирусы появились давно. Они заражали древние компьютеры, и ничто не могло их остановить, кроме бдительного пользователя машины. Затем были придуманы антивирусы, определяющие их по характерным симптомам. Но через какое-то время вирус...

Обработка последовательных файлов в программе
Обработка последовательных файлов в программе Кузнецова В. С., преподаватель информатики, МОУ межшкольный учебный комбинат №2, г. Хабаровск Одним из трудных для учащихся и преподавателей разделов программирования является программирование обработки...

САПР
машинная графика и основы сапр в текстильной и легкой промышленности.Введение: Данная тема посвящена теме "Машинная графика и основы САПР в текстильной и легкой промышленности".Развитие машиностроения неразрывно связано с развитиеммашинопотребляющих секторов народного хозяйства.В...

Классификация программного обеспечения ЭВМ
ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ, БРЯНСКИЙ ФИЛИАЛ. КАФЕДРА АВТОМАТИЗАЦИИ ОБРАБОТКИ ЭКОНОМИЧЕСКОЙ ИНФОРМАЦИИ.             Курсовая работа: На тему:  Классификация программного обеспечения ЭВМ. ...

Стеки протоколов
Стеки протоколов Игорь Иванцов Технология Voice over IP (VoIP), называемая также IP-телефонией, предусматривает взаимодействие сети TDM с коммутацией каналов и сети IP с коммутацией пакетов, а также обеспечивает эволюционное движение телекоммуникационных сетей TDM к сетям...

Язык обработки графов на базе JAVA
УДК 681.3 М.Ю. КРУКОВСКИЙ Язык обработки графов на базе JAVA. Abstract: This paper describes a language for definition of...

Базы данных в Delphi
Курсовая работа на тему “Базы данных в Delphi” СОДЕРЖАНИЕ СОДЕРЖАНИЕ.. 1 ВВЕДЕНИЕ.. 2 1. ОБЩАЯ ЧАСТЬ.. 9 1.1. Цель разработки. 9 1.2. Анализ разработки. 9 2. СПЕЦИАЛЬНАЯ ЧАСТЬ.. 10 2.1. Постановка задачи. 10 2.1.1.  Назначение задачи....

Речевые технологии
Перспективы речевого интерфейса Писать о речевом интерфейсе сложно. С одной стороны, тема абсолютно не нова, с другой- активное развитие и применение этой технологии только начинается (в который раз). С одной стороны, успели сформироваться устойчивые стереотипы и предубеждения, с...

Сеть ЭВМ
Информационная безопасность в сетях ЭВМ Защита данных в компьютерных сетях становится одной из самых открытых проблем в современных информационно-вычислительных системах. Насегодняшний день сформулировано три базовых принципа информационной безопасности, задачей которой...

Мониторы
2 Содержание: Введение 3 1. Электронно-лучевые мониторы 4 2. Жидкокристаллические мониторы 8 3....

Проектирование модуля АФАР
московский государственный ордена ленина И ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ авиационный институт имени СЕРГО ОРДЖОНИКИДЗЕ (технический университет) факультет радиоэлектроники ла Кафедра 406 расчетно-пояснительная записка к курсовому проекту по дисциплине...

Основы социальной информатики
Тема1 Социальная информатика: предмет и задачикурса Человечество неотвратимо вступает в информационную эпоху. Вес информационной экономики постоянно возрастает, и ее доля выраженная в суммарномрабочем времени, для экономически развитых стран уже сегодня составляет...

Компьютерные правонарушения
КОМПЬЮТЕРНЫЕ ПРАВОНАРУШЕНИЯ ВВЕДЕНИЕ Информационные технологии, основанные на новейших достижениях электронно-вычислительной техники, которые получили название новых информационных технологий (НИТ), находят все большее применение в различных сферах...

Создание топографических планов масштаба 1:5000
Московский колледж геодезии и картографии Технический проект “Создание...

Топологии сетей ПД, функционирующих в составе систем управления (СУ)
К наиболее важным требованиям, предъявляемым к СПД, функционирующим в СУ рассредоточенными объектами (СУРО), относятся: · обеспечение работы СУ в реальном масштабе времени; · осуществление информационного обмена с высокой верностью; · надежное функционирование. ...

Разработка программы расчета определенного интеграла по формуле Буля по схеме двойного пересчета с заданной точностью
Министерство образования Республики Беларусь УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ МОГИЛЕВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра "ЭП и АПУ" ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К курсовой работе по дисциплине “Вычислительная техника и программирование” Выполнил...

Использование макросов в MS Access 2000
ЗаданиеИспользование макросов в базе данных Microsoft AccessИсследовать возможности Access по созданию макросов 1. ВведениеИспользование макросов в базе данных Microsoft Access С помощью макросов можно выполнить практически все действия над объектами Access....

Основы Visual Basic 5.0
Основы Visual Basic 5.0 В приложениях VB 5.0 исполняемые строки должны размещаться внутри процедур либо функций. Операторы в VB редко используют номера строк, а любые из них обычно начинаются с новой строки. Строки ограничены длиной в 1023 символа. можно расширять...

Позиционные системы счисления
РАБОТА ПО ИНФОРМАТИКЕ ТЕМА «Позиционные системы счисления» Ученицы 11 класса «А» Калашниковой Анны МОСКВА 2004 год План 1) Арифметические основы построения ЭВМ 2) Непозиционные и позиционные системы счисления 3) Непозиционные...

Обеспечение защиты данных в подсистеме "Учет распределения товара"
ТЕМА: «Обеспечение защиты данных в подсистеме «Учет распределения товара»» Содержание Введение 4 1. Класс защищённости разрабатываемой подсистемы 5 2. Горизонтальная модель сети 6 ...

Задачи графических преобразований в приложениях моделирования с использованием ЭВМ
Содержание1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Афинные преобразования на плоскости . . . . . . . . . . . . . . . . . . . . .4 3. Однородные координаты точки . . . . . . . . . . . . . . . . . . . . . ....