1. Общая схема парсера

Парсер – это сленговое слово от английского parse (анализ, разбор, произволить структурный анализ). В общем смысле, так назвают программы, которые производят соответсвующее действие, разбивая исходный объект на отдельные части и анализируя каждую часть своим алгоритмом. Примерами работы таких программ может быть: анализ, а в последствии подсветка кода в регулярно-используемых выражениях языков программирования, проверка текста на наличие синтаксических ошибок и граматических ошибок и тд. Понимать структуру работы парсера прежде всего важно потому, что все компиляторы и интепретаторы основаны на таких парсерах. Отличается только алгоритм анализа и обработки данных.

Задача синтаксического анализатора – создание последовательности символов дерева операций конечного языка. Схема его работы представлена на рисунке 1.

Грубо описать его работу можно на примере обычного цикла который перебирает все значения входной строки и проверяет в ней наличие известных лексических едениц (лексем). Лексемой может являться число, оператор либо как в нашем случае тот или иной вид скобки. Для анализа конкретной лексемы будет использоваться свой собственный класс, который определённым образом определяет ту или иную лексему.

Ниже приведён листинг, который отображает общую реализацию парсера для любой лексемы. Проведём разбор каждого метода в данной реализации.

Листинг класса TokensParser:

public class TokensParser { private List<TokenParser> parsers; private int pos; public TokensParser() { … } public List<TokenParser> getParsers() { … } public void parse(String source) { … } } interface TokenParser { public boolean parseToken(String source, int currentIndex); }

Листинг 1.1. Листинг класса TokensParser.

Так как мы подразумеваем в дальнейшем расширять нашу программу, нам необходимо где-то хранить все созданные нами анализаторы, поэтому инициализируем переменную parser типа <List>. Она будет хранить их по мере того как мы будем добалять их в программу. Тип <List> аналогичен типу Array, за исключением того, что он более защищён и значения в нём можно перебирать без инициализации дополнительной переменной итерации i. Переменная pos отвечает за перемещение по строке символов т.е. когда на вход нашей программы подаётся строка мы начинаем анализ с нулевого символа и двигаемся от символа к символу проверяя в строке наличие определённых нами лексем.

Первый метод, называется конструктором класса т.е. при вызове класса TokensParser зарезервированным словом new автоматически выполниться метод TokensParser(). Формально метод-конструктор – это начальные условия какого либо класса, к которому мы обращаемся. Поэтому в правилах хорошего тона программирования неоходимо, чтобы инициализация всех переменных класса происходила именно в этом методе-конструкторе. Помимо этого, необоходимо добавить все анализаторы, которые будут работать по своим особенным алгоритмам. Не будем использовать какую-либо переменную под анализаторы, а просто добавим (add) их в список обычными конструкторами класса.

Ниже представлен листинг метода-конструктора TokensParser:

public TokensParser() { pos = 0; parsers = new ArrayList<TokenParser>(); parsers.add(new BracketParser()); }

Листинг 1.2. Листинг метода TokensParser.

Далее рассмотрим следующий метод также являющийся методом-геттером (англ. get – получать). Мы создали данный метод для того, чтобы поле списка анализаторов было защищено и в памяти не хранилась информация о данном поле. Этот один из методов объектно-ориентированного программирования, может помочь реализовать механизм инкапсуляции. Структура данного метода позволяет получить все анализаторы в виде объекта типа List.

Листинг метода getParsers:

public List<TokenParser> getParsers() { return parsers; }

Листинг 1.3. Листинг метода getParsers.

Прежде чем описывать главный метод данного класса, который реализует его сущность, следует рассмотреть всю структуру программы. Допустим, мы хотим создать анализатор, который будет анализировать не алгебраическое выражение, а организм человека. В основе каждого анализатора лежит разложение какой-либо структуры на составляющие части. Каждая часть при этом, обладает своим собственным набором характеристик. Поэтому для каждой части нужно создать свой особый анализатор, который также является уникальным. Но если части не имеют общих характеристик, которые определяют их однозначно, то анализаторы имеют данную характеристику. Эта характеристика называется парсингом или анализом. Эту характеристику мы включили в так называемый интерфейс класса. Она определяет все общие методы, которые мы должны задействовать в наше программе.

Полный листинг интерфейса представлен выше (листинг 1.1). Он содержит общий метод для всех анализаторов parseToken. Метод анализа текущего символа на наличие лексемы.

И наконец, главный метод данного класса. Метод – parse. Его листинг представлен ниже. Он реализует анализ поступившей строки, определяемой переменной source. Прежде всего нам необходимо определить переменную, которая будет хранить промежуточные результаты анализа выражений. Далее выполняем проверку на пустоту строки, потому что если она пуста то не имеет смысла проделывать дальнейшие операции. Сущность данного метода заключается в структуре представленной ниже. Первым описан бесконечный цикл с предусловием. Бесконечность в данном случае реализуется за счёт применения ключевого слова true в качестве предусловия. Вторым описан цикл с итерацией записанной в специфической форме. Язык Java позволяет данную запись, когда она применяется в рассмотрении списка. Данный цикл можно описать так: «Перебираем все анализаторы в списке parsers, поочерёдно задавая их переменной parser». Тело цикла начинается с проверки на отсутсвие анализатора. В случае, если анализатор был удалён, то просто переходим к следующему анализатору в списке. Далее в теле цикла описан метод parseToken, который анализирует строку с символа определяющейся по значению поля pos. Данный метод возвращает логическое выражение того, опознан ли символ данным анализатором. Если символ распознан, то позиция автоматически инкрементируется. В случае если не одним анализатором выражение не было распознано, то значение промежуточных результатов анализа даёт команду на выход из бесконечного цикла.

public void parse(String source) { boolean statusParsing = false; if (source == null) { throw newIllegalArgumentException("Поступившее выражение является пустой строкой"); } while (true) { for( TokenParser parser : getParsers() ) { if( parser==null ) continue; statusParsing = parser.parseToken(source, pos); if( statusParsing ) { pos++; break; } } if( !statusParsing ) break; } }

Листинг 1.4. Листинг метода parse.