Здравствуйте. Хотел бы поделится своим опытом с сообществом Habrahabr. Речь пойдет о разработке не очень сложного парсера BBCode, который преобразует его в HTML. Парсер, который мы будем писать — это типичный конечный автомат.
Читать полностью »
Метка «конечный автомат»
Парсер BBCode без регулярных выражений
2014-09-11 в 10:24, admin, рубрики: bbcode, php, конечный автомат, Регулярные выражения, метки: bbcode, PHP, конечный автомат, регулярные выраженияПростые стейт-машины на службе у разработчика
2012-11-26 в 10:08, admin, рубрики: framework, FSM, GoF, KISS, reflection, XML, конечный автомат, Программирование, метки: c++, framework, FSM, GoF, kiss, reflection, XML, конечный автоматПредставьте на минутку обычного программиста. Допустим, его зовут Вася и ему нужно сделать анимированную менюшку на сайт/десктоп приложение/мобильный апп. Знаете, которые выезжают сверху вниз, как меню у окна Windows или меню с яблочком у OS X. Вот такое.
Начинает он с одного выпадающего окошка, тестирует анимацию, выставляет ease out 100% и наслаждается полученным результатом. Но вскоре он понимает, что для того, чтобы управлять менюшкой, хорошо бы знать закрыто оно сейчас или нет. Мы-то с вами тут программисты опытные, все понимаем, что нужно добавить флаг. Не вопрос, флаг есть.
var opened = false;
Вроде, работает. Но, если быстро кликать по кнопке, меню начинает моргать, открываясь и закрываясь не успев доанимироваться в конечное состояние. Вася добавляет флаг animating. Теперь код у нас такой:
var opened = false;
var animating = false;
function onClick(event) {
if (animating) return;
if (opened) close();
else open();
}
Через какое-то время Васе говорят, что меню может быть полностью выключено и неактивно. Не вопрос! Мы-то с вами тут программисты опытные, все понимаем, что… нужно добавить ЕЩЕ ОДИН ФЛАГ! И, всего-то через пару дней разработки, код меню уже пестрит двустрочными IF-ами типа вот такого:
if (enabled && opened && !animating && !selected && finishedTransition && !endOfTheWorld && ...) { ... }
Вася начинает задаваться вопросами: как вообще может быть, что animating == true и enabled == false; почему у него время от времени все глючит; как тут вообще поймешь в каком состоянии находится меню. Ага! Состояния... О них дальше и пойдет речь.
Знакомьтесь, это Вася.
Конечные автоматы. Пишем ДКА
2012-04-05 в 19:24, admin, рубрики: perl, конечный автомат, Программирование, теория автоматов, метки: perl, конечный автомат, теория автоматовЕсли вы когда-нибудь пытались написать своего бота, программу-переговорщик (negotiator), интерпретатор протокола связи и тому подобные вещи, то наверняка сталкивались с конечными автоматами. Данная тема в принципе не представляет большой сложности, но если вдруг у вас не было курса «теории автоматов», милости прошу под кат.
Сегодня мы попытаемся создать простой детерминированный конечный автомат. Мне вдруг захотелось написать его на Perl'е, но так как мы не будем использовать никаких специфических трюков, перенести общую концепцию на любой другой императивный язык не составит большого труда.
Читать полностью »