Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Статья: Парсер на РНР - это возможно

Название: Парсер на РНР - это возможно
Раздел: Рефераты по информатике
Тип: статья Добавлен 09:22:32 09 апреля 2011 Похожие работы
Просмотров: 12 Комментариев: 24 Оценило: 2 человек Средний балл: 5 Оценка: неизвестно     Скачать

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

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

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

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

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

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

?>

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Хватит париться. На сайте FAST-REFERAT.RU вам сделают любой реферат, курсовую или дипломную. Сам пользуюсь, и вам советую!
Никита07:23:37 04 ноября 2021
.
.07:23:30 04 ноября 2021
.
.07:23:28 04 ноября 2021
.
.07:23:26 04 ноября 2021
.
.07:23:23 04 ноября 2021

Смотреть все комментарии (24)
Работы, похожие на Статья: Парсер на РНР - это возможно

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(290194)
Комментарии (4186)
Copyright © 2005-2021 HEKIMA.RU [email protected] реклама на сайте