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

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

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), то мы не придпринимаем действий.
Еще одна ситуация может свтретится когда при нахождении определенного символа, нам требуется узнать что было до него. Вот небольшой пример как это сделать:

В этом примере (наша исходная строка пример не подходит) мы пытаемся определить переменные стоящие до знака “=” (это не боевой образец а всего-лишь пример).
Собственно описание тут лишнее, все видно из комментариев в коде. Нужно заметить, что данный пример предназначен для парсинга JavaScript.
На этом с описанием КА хочу остановиться.
Однако не стоит забывать, что регулярные выражения тоже довольно сильны. И при их правильном использовании можно многого добиться.
Например следующий пример позволяет “обфусцировать” некоторые моменты в JS коде:

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

Join the Conversation

2 Comments

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

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.