Добро пожаловать,
Гость
. Пожалуйста,
войдите
или
зарегистрируйтесь
.
Не получили
письмо с кодом активации
?
1 час
1 день
1 неделя
1 месяц
Навсегда
Новости:
Начало
Помощь
Поиск
Календарь
Вход
Регистрация
Forum Webscript.Ru
»
Программирование
»
PHP
»
Парсер на пхп - как?
« предыдущая тема
следующая тема »
Печать
Страницы:
1
[
2
]
Вниз
Автор
Тема: Парсер на пхп - как? (Прочитано 11450 раз)
0 Пользователей и 1 Гость просматривают эту тему.
Меняздесьдавнонет
новичЕк
Глобальный модератор
Ветеран
Сообщений: 5698
+0/-0
2
Парсер на пхп - как?
«
Ответ #15 :
02 Мая 2005, 21:14:57 »
Да ты не стесняйся. здесь рассказывай. Мы все с удовольствием послушаем.
Записан
sarutobi
Завсегдатай
Пользователь
Сообщений: 61
+0/-0
0
Парсер на пхп - как?
«
Ответ #16 :
02 Мая 2005, 21:33:40 »
Я не стесняюсь. Это материал примерно на пару страниц печатного текста (вкратце). Стоит это делать в форуме?
А если интересно не одному человеку - могу накнопать, не жалкою
Записан
Алексей
Фанат форума
Постоялец
Сообщений: 176
+0/-0
0
Парсер на пхп - как?
«
Ответ #17 :
02 Мая 2005, 21:44:03 »
sarutobi
напиши, если не сложно. можно прямо сюда.
Записан
sarutobi
Завсегдатай
Пользователь
Сообщений: 61
+0/-0
0
Парсер на пхп - как?
«
Ответ #18 :
02 Мая 2005, 21:49:03 »
Хорошо, только не сегодня.
Записан
xRUSha
...
Постоялец
Сообщений: 200
+0/-0
2
Парсер на пхп - как?
«
Ответ #19 :
03 Мая 2005, 00:53:10 »
мне казалось что это материал не на пару страниц, а на пару книг.
Записан
...
sarutobi
Завсегдатай
Пользователь
Сообщений: 61
+0/-0
0
Парсер на пхп - как?
«
Ответ #20 :
04 Мая 2005, 23:16:04 »
yt пропал еще интерес? могу щас опус выложить....
Записан
xRUSha
...
Постоялец
Сообщений: 200
+0/-0
2
Парсер на пхп - как?
«
Ответ #21 :
04 Мая 2005, 23:40:58 »
выкладывай
Записан
...
sarutobi
Завсегдатай
Пользователь
Сообщений: 61
+0/-0
0
Парсер на пхп - как?
«
Ответ #22 :
04 Мая 2005, 23:42:35 »
Конечные автоматы.
Опуская сложные математические выкладки, сопутствующие изучению теории функции конечных автоматов, рассмотрим их с практической точки зрения. Различают два типа конечных автоматов – Детерминированный Конечный Автомат (ДКА) и Недетерминированный Конечный Автомат (НКА). Оба они представляют собой функции двух переменных С
и S[j], где С
– очередной символ, поступающий на вход автомата, S[j] – текущее состояние автомата. Математически это записывается как f:{C;S}->S (C – множество допустимых входных символов (алфавит), S – множество состояний). Разница между ДКА и НКА только в том, что у ДКА после получения очередного символа может быть только одно состояние, а у НКА – несколько. Дальше мы будем рассматривать только ДКА.
Сфера применения ДКА в программировании – синтаксические и лексические анализы входного текста (в трансляторах и компиляторах), построение регулярных выражений и схожие задачи.
Исходя из вышеприведенного определения (строго говоря, не совсем математически корректного, но отражающего саму суть) ДКА, автомат представляет собой ориентированный граф. Вершинами графа служат состояния автомата, ребрами – возможные переходы из состояния в состояние. Для задания такого графа идеально подходит матрица MxN, где N – число символов входного алфавита, M – число состояний автомата. Каждый элемент этой матрицы представляет собой состояние, в которое автомат перейдет после получения очередного символа. Эта матрица называется матрицей переходов.
Для примера рассмотрим простейший автомат, разбирающий адрес электронной почты.
Сначала определим алфавит автомата (множество C). В нашем случае это множество состоит из 26 букв латинского алфавита a-z, символов ‘.’, ‘-‘, ‘_’ и ‘@’. В этот же алфавит включим символ ‘*’, не соответствующий ни одному из ранее указанных символов. Итак, наш алфавит имеет вид C = {[a-z];.;-;_;@;*}.
Следующим шагом в построении автомата является построение матрицы переходов. В нашем случае она выглядит вот так:
Состояние ![a-z]! - ! _ ! . ! @ ! *
-------------------------------------
1 ! 2 ! e ! e ! e ! e ! e
-------------------------------------
2 ! 2 ! 2 ! 2 ! 3 ! 4 ! e
-------------------------------------
3 ! 2 ! e ! e ! e ! e ! e
-------------------------------------
4 ! 5 ! e ! e ! e ! e ! e
-------------------------------------
5 ! 5 ! 6 ! 7 ! 8 ! e ! e
-------------------------------------
6 ! 5 ! e ! e ! e ! e ! e
-------------------------------------
7 ! 5 ! e ! 7 ! e ! e ! e
-------------------------------------
8 ! 5 ! e ! e ! e ! e ! e
-------------------------------------
e ! e ! e ! e ! e ! e ! e
В общем-то ничего сложного, требуется только внимательность. Пару слов о состоянии e: это состояние сигнализирует о появлении ошибки в правилах разбора, и можно его в автомат не включать а сразу же прекращать разбор.
Теперь надо определить основные параметры автомата – начальное и конечные состояния. Да-да, я не оговорился – конечных состояний у ДКА может быть несколько. Если после окончания потока символов ДКА окажется в одном из конечных состояний – то в потоке данных не было ошибок, можно продолжать работу. Если же ДКА находится в состоянии которое не попало в это множество – то либо в потоке данных была ошибка, либо ошибка содержится в функции переходов ДКА. Для нашего примера входное состояние это 1, выходные – {5}.
Давайте посмотрим, что произойдет, если в качестве входного потока будет подан адрес anonymous@localhost
Входной поток
anonym.ous@local.host
Состояние автомата 1222222322245555585555
То есть, данный адрес прошел проверку и является допустимым (это на самом деле так).
Теперь изменим адрес на anonym.ous@local..host
Входной поток anonym.ous@local..host
Состояние автомата 122222232224555558eeeee
То есть сразу видно, что произошла ошибка.
Теперь о том, как это использовать. Автомат оформляется в виде логической функции, принимающей на входе параметр – поток данных (чаще всего строку, но можно использовать любой). Внутри этой функции определяется начальное состояние автомата, а дальше в цикле по всем символам входного потока работает оператор case. Он проверяет текущее состояние автомата, и выполняет действия над символом потока (например, добавляет его к внутренним переменным функции). По окончании выходного потока на основании допустимых выходных состояний и текущего состояния автомата делается вывод об успехе или неуспехе разбора, который и возвращается в вызывающую процедуру.
Пример построения ДКА на Pascal можно посмотреть здесь:
http://www.rsdn.ru/article/alg/statemachine.xml
Записан
Печать
Страницы:
1
[
2
]
Вверх
« предыдущая тема
следующая тема »
Forum Webscript.Ru
»
Программирование
»
PHP
»
Парсер на пхп - как?
Sitemap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28