Дурацкий Девелопер

Конечный автомат для парсинга JavaScript

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

Q — конечное множество состояний автомата;
q0 — начальное состояние автомата ();

Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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

Для большей наглядности приведу простой пример КА.

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
29

$string = "Simple string with some JS. alert('Hello world'); оно как-бы говорит нам - \"Привет мир\"";
 
$in_string = false;
 
for ($i=0;$i
$char=$string[$i];
 
if( $char == '"' || $char == '\'' )
{
if(!$in_string)
{
$in_string = true;
$string_alt.=$char;
$string_alt.="*";
$instring_char=$char;
continue;
} else if ($in_string && $char==$instring_char)
{
$in_string = false;
$instring_char='';
}
}
 
if (!$in_string) {
$string_alt.=$char;
}
}
echo $string."";
echo $string_alt;

Это довольно простой пример с одним состоянием. Мы посимвольно читаем строку, если встречается символ одинарной или двойной кавычки то переходим в состоянии in_string. Далее, если состояние не определено то просто читаем далее. Но если встретили опять кавычки то смотрим, совпадают ли они с теми которые были найдены в ранее. Если совпадают, то убираем состояние.

Для разбора более сложного примера нам необходимо много чего запомнить (держать в голове). А именно: представлять все возможные варианты, которые стоит учитывать при разборе. Например в строке может встретится экранированная кавычка, которую не стоит воспринимать. Тогда добавим «&& $string[$i-1]!=’\'» что позволит пробрасывать экранированные кавычки и не обращать на них внимание.

Также нам может понадобится распознавать отдельные слова. Тогда поможет следующая конструкция: if(!$in_string && strcasecmp($char, ‘f’) === 0 && strcasecmp(substr($string, $i, 8), «function») === 0)
Это позволяет определить идет ли после f слово function и соответственно принимать определенные решения. Стоит заметить, что если мы нашли букву f в тот момент, когда мы находимся в кавычках (состояние in_string), то мы не придпринимаем действий.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

if($char == '=' && !$in_string && !$container_str_var_read)
{
// читаем назад
$set_read=false;
for ($_i=$i-1;$_i>=0;$_i--) {
// если пошла переменная то флаг
if (preg_match("/[a-z.A-Z0-9_]/i",$string[$_i],$mt) && !$set_read) {
$set_read=true;
}
// если переменная пошла то читаем до стопа
if ($set_read) {
// пока не встретим стопсимвол
if ($string[$_i]==';' || $string[$_i]=="\r" || $string[$_i]=="\t" || $string[$_i]==" " || $string[$_i]=="\n") {
$i=$_i+1;
$container_str_var_read=true; // начали читать
break;
}
}
}
}

В этом примере (наша исходная строка пример не подходит) мы пытаемся определить переменные стоящие до знака «=» (это не боевой образец а всего-лишь пример).
Собственно описание тут лишнее, все видно из комментариев в коде. Нужно заметить, что данный пример предназначен для парсинга JavaScript. И его эквивалент используется в одной из дорогих связок.

На этом с описанием КА хочу остановиться.

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

Например следующий пример позволяет «обфусцировать» некоторые моменты в JS коде:

1
2
3

$patterns[] = '/([\'; \t\n\r]+)([a-zA-Z0-9.-_]+[ =]+)?(eval)/i';
$replacements[] = '\1'.get_var('eval').'=eval;\2'.get_var('eval');
$new_data = preg_replace($patterns, $replacements, $source_data);

Естественно функцию get_var я не привожу. ;)
Спасибо, что дочиталю до конца =)

Все ошибки и прочее прошу в комментарии, будет интересно обсудить.

2 комментария »

Подписаться на комментарии по RSS. URI трекбека

1. Дурацкий Девелопер » Конечный автомат для парсинга JavaScript…

   Конечный автомат — в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимост…

   Обратная ссылка от Социальная сеть для блоггеров sloger.net — 1 июня 2009 #

2. Код немного погрызся. Если нужны примеры, прошу в контакты.

   Коммент от Eugene Che — 20 мая 2011 #

Оставьте Ваш отзыв

Ищем

Реклама

• продам авто в москву
• мотобур хускварна
• навесное буровое оборудование