Forum Webscript.Ru
Программирование => PHP => Тема начата: Алексей от 27 Апреля 2005, 11:18:07
-
Эх, помнится в институте учили парсить... на С. Тогда я ничего не понимал, как и большинство моих одногрупников.
А сейчас вот просто возникло желание вернуться к азам программирования, чисто для себя попробовать научиться парсить чего-нибудь, хотя бы BB_теги какие-нибудь.. Очевидно на PHP надо это делать, т.к. кроме него и JS я больше никаких языков так хорошо не знаю.
Видел статью на деталях, "Парсер на пхп - это возможно!", но ничего не понял :)
Может у кого есть примеры/статьи про конечные автоматы?
Спасибо.
-
Если ты не понял статью на деталях, то какой смысл тебе давать любые другие?
-
Ну я не знаю, что -нибудть помеьше, где была бы только теория... алгоритмы то я сам как-нибудь сделаю. Плюс ко всему вопрос возникает, так же удобно работать с разбором выражений на пхп, как в том же С?
-
если тебе удобнее на С - делай на С.
-
хотя если выкинуть из твоего текста умные слова, смысла которых ты не понимаешь, и взять только практическую часть, то тебе нужны банальные регулярки
-
RomikChef
Нет, в том то и дело, мне очень хочется научиться именно программировать на самом "низком" уровне.
Про реулярки: [B*]жирный текст[/B*] - это примерно следущее:
$in = preg_replace("#\\\\[B\\\\](.+?)\\\\[/B\\\\]#ims", "$1", $in);
это не совсем программирование, это - ничто. Это доступно любому гуманитарию. Плюс ко всему регулярки очень сильно ограничивают в возможностях, когда нужно сделать нетривиальные замены.
Другое дело, распарсить эту конструкцию исключительно с помощью циклов, массивов и флагов.
Я почему упомянул С - мне кажется, там работа с текстом немного отличается от PHP, даже не намного, а намного. Помню вступительную часть книги Кернигана и ричи - там показан алгорим нахождения или замены (за давностью не помню) текста в тексте. В С есть указатели, чтоупрощают работу, да и вообще, как мне кажется этот язык более предназаначен для написания полноценных программ, но мне хочется это научится делать на PHP.
Про статью на деталях: я её не понял потому, что там в принципе нет никакой теори, как это более-менее правильно делать, а сразу показывается нетривиальный (по моим меркам) пример.
-
Алексей:
Плюс ко всему регулярки очень сильно ограничивают в возможностях, когда нужно сделать нетривиальные замены.
можно реальный пример, который может встретиться на практике ?
Алексей:
мне очень хочется научиться именно программировать на самом "низком" уровне.
на ПХП ? Может тебе просто лень другой язык учить ?
-
Макс:
можно реальный пример, который может встретиться на практике ?
парсер XML например
Макс:
на ПХП ? Может тебе просто лень другой язык учить ?
да, не лень, просто я ж на пхп програмирую, вот и хочу на нём учиться.
-
Алексей:
парсер XML например
А стандартные пхпшные средства (http://ru2.php.net/xml) для работы с XML использовать вам религия не позволяет?
-
Croaker:
А стандартные пхпшные средства для работы с XML использовать вам религия не позволяет?
ребят, вы не читаете что в начале написано? я же сказал - для себя, научиться, понять.
-
я на 3м курсе такой идеей заразился. начал писать парсер, который методом конечных автоматов распарсивал код шаблона. пытался сделать систему типа .net\'вской
наигрался за недельку примерно. с тех пор к автоматам не возвращался.
начал кстати с той-же статьи + знания с некоторых универовских курсов
-
xRUSha
а что забросил? на чем писал?
-
Просто со временем понимаешь, что пиША на всяких пхп и называть себя программистом как то ложно...
-
в универе мы писали приметивный интерпритатор на плюсах.
сам я хотел усовершенствовать свой пхпшный шаблонизатор. сделать объекты типа асп.нетовкого датагрида. кстати сделал, тока пользоватся этим было не очень-то удобно.
сейчас уже понимаю, что это бред, но тогда интересно было поковырятся
-
коли интересно - отмыль на sarutobi@pisem.net. могу популярно рассказать как строится конечный автомат.
-
Да ты не стесняйся. здесь рассказывай. Мы все с удовольствием послушаем.
-
Я не стесняюсь. Это материал примерно на пару страниц печатного текста (вкратце). Стоит это делать в форуме? ;)
А если интересно не одному человеку - могу накнопать, не жалкою
-
sarutobi
напиши, если не сложно. можно прямо сюда.
-
Хорошо, только не сегодня.
-
мне казалось что это материал не на пару страниц, а на пару книг.
-
yt пропал еще интерес? могу щас опус выложить....
-
выкладывай
-
Конечные автоматы.
Опуская сложные математические выкладки, сопутствующие изучению теории функции конечных автоматов, рассмотрим их с практической точки зрения. Различают два типа конечных автоматов – Детерминированный Конечный Автомат (ДКА) и Недетерминированный Конечный Автомат (НКА). Оба они представляют собой функции двух переменных С и 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