iTEYE

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

1 июня 2009

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

technology, , ,

Comments

vova 24 июля 2013 • 16:51

За отсутствие наличия горизонтальных отступов — расстрел на месте.

Eugene 25 июля 2013 • 11:10

За отсутствие наличия смысла комментария — лучи поноса ;)

Leave a Reply

Скидки до 5% на заказ хостинга!