Легковесный конструктор парсеров с интерактивным режимом

Периодически сталкиваясь с мелкими задачками по разработке простеньких анализаторов текста, решил данную задачу автоматизировать, да и академический интерес не давал покоя. Первоначально смотрел в сторону Racc (одна из интерпретаций Yacc), но он мне показался достаточно не простым решением для моих мелких задач и тогда я решил разработать свой простенький анализатор. Хотя, конечно, если вы разрабатываете компилятор или что-то подобное да и еще в промышленных масштабах, то определенно вам стоит посмотреть в сторону Racc.

Но если вы хотите сами разобраться, что же такое парсер и как быстренько его написать самому, при этом не читая кучу статей про лексические анализаторы типа книги дракона, тогда вперед под кат (хотя книга очень хорошая).

Анализ входного потока

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

• состояние определенности.
• состояние не определенности.
• смена состояния.

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

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

Теперь уже, можно произвести декомпозицию, точнее детализацию процесса анализа входного потока на:
классификацию входного потока (совпадает с одним, со многими и не совпадает ни с одним шаблоном) и обработку результата классификации (переход, буферизация и т.п.).

Реализация

Хотя по своему основному роду деятельности являюсь разработчиков встраиваемых систем и основной язык мой программирования это ANSI C, реализовывать данную модель я решил на Ruby, т.к. на нем меньше думаешь о технических деталях реализации и планировал реализовать эту модель как Ruby Gem. Уж очень люблю я все универсальное (в определенных рамках), краткое и лаконичное. В дальнейшем планирую данную модель реализовать в emdedded для анализатора входного трафика, но в более упрощенном виде и возможно на HDL.

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

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

Пример

Для большей понятности я приведу пример реализации простого парсера файла исходного кода для автоматической генерации документации, отдаленно напоминающего doxygen. Первоначально надо установить мой gem:

$ gem install iparser

Как вы уже поняли gem называется iparser и после его установки создадим файл с именем 'parser_example.rb', в котором и будем писать код нашего парсера на базе iparser. Первым делом подключим библиотеку и создадим объект парсер-машины, которая реализует основную логику анализатора, т.е. экземпляр самого парсера:

require 'iparser'

parser = Iparser::Machine.new

Следующим шагом, уже можно описывать состояния парсера. У нас будет совсем простой парсер и он будет иметь только три состояния:

• начальное (idle).
• однострочные комментарии (comment-line).
• многострочные комментарии (comment-block).

Теперь можем описывать каждое состояние отдельно (ниже приведу код скрипта в целом). Состояние 'idle' подробно описывать не буду, т.к. в нашем случае оно пустое, а состояние 'comment-line' рассмотрим по ближе. Для создания экземпляра состояний используем следующий код:

ps_idle = Iparser::State.new('idle')
ps_cline = Iparser::State.new('comment-line')

В параметрах конструктора состояния указывается строка с именем (идентификатором) состояния, желательно понятным вам, т.к. используется для дальней отладки модели. У каждого объекта состояний парсера есть поле entry, это шаблон совпадении с которым производится переход на данное состояние, т.е. условие входа в состояние. Сравнение с шаблоном производится посимвольно, также как и обработка входного потока. Вход в состояние будет осуществлятся при наличии во входном потоке символов '\\\', идущих подряд. Также имеется и поле leave для того чтобы указать шаблон для выхода из состояния (возврат в предыдущее), в нашем случае это символы конца строки '\n\r', хотя достаточно указать первый из них, но для наглядности укажем оба. Теперь опишем 'comment-line':

ps_cline.entry << /\//
ps_cline.entry << /\//
ps_cline.entry << /\//
ps_cline.leave << /[\n\r]/

Обратите внимание, шаблоны задаются с помощью регулярных выражений, можно и без них, но это потом.

Далее создадим состояние для обработки многострочных комментариев, попадать в него будем при встрече символов '/**', а покидать его при наличии '*/'. Тоже запишем:

ps_cblock = Iparser::State.new('comment-block')
ps_cblock.entry << /\//
ps_cblock.entry << /\*/
ps_cblock.entry << /\*/
ps_cblock.leave << /\*/
ps_cblock.leave << /\//
ps_cblock.ignore << '*'

Так же мы указали символы, которые следует игнорировать, находясь в данном состоянии. У нас это символ звездочка, т.к. я люблю писать многострочные комментарии вида:

/**
 * ...
 * ...
 */

Теперь следует связать наши три состояния в единую цепочку, из 'idle' мы можем попасть в 'comment-line' и 'comment-block', а из них только обратно в 'idle'. Связывание осуществляется посредством указания индексов состояний в поле branches каждого из состояний. Индекс будет определяться порядком добавления объектов состояний в экземпляр парсера, для добавления объектов в парсер испоьзуется метод парсера addstate.

ps_idle.branches << 1
ps_idle.branches << 2

parser.addstate ps_idle
parser.addstate ps_cline
parser.addstate ps_cblock

И наконец надо проверить, правильно ли мы создали цепочку состояний, для этого запустим интерактивный режим (метод prestart — установит все начальные параметры):

parser.prestart
parser.interactive_parser

Для большей понятности я приведу код скрипта в целом, конечно я его немного перекомпоновал, но он содержит только тот код я писал выше:

require 'iparser'

#
# Create parser-machine object.
#
parser = Iparser::Machine.new

#
# Create startup state for this parser-machine.
#
ps_idle = Iparser::State.new('idle')

#
# Add branch indexes to 'comment-line' and 'comment-block' state.
#
ps_idle.branches << 1
ps_idle.branches << 2

#
# Create single line comment state for this parser-machine.
#
ps_cline = Iparser::State.new('comment-line')
ps_cline.entry << /\//
ps_cline.entry << /\//
ps_cline.entry << /\//
ps_cline.leave << /[\n\r]/

#
# Create multiline comment state for this parser-machine.
#
ps_cblock = Iparser::State.new('comment-block')
ps_cblock.entry << /\//
ps_cblock.entry << /\*/
ps_cblock.entry << /\*/
ps_cblock.leave << /\*/
ps_cblock.leave << /\//
ps_cblock.ignore << '*'

#
# Add all states to parser-machine.
#
parser.addstate ps_idle
parser.addstate ps_cline
parser.addstate ps_cblock

#
# Call parser startup method.
#
parser.prestart

#
# Call interactive mode for check state-machine.
#
parser.interactive_parser

Не такой уж и большой код, теперь запустим скрипт:

$ ruby parser_example.rb

Для выхода из интерактивного режима надо ввести пустую строку (просто нажать enter сразу).

Вводим '\\\' и видим что что на последнем символе парсер переходит в состояние 'comment-line' (branch to comment-line), теперь вводим '\n' или '\r' и видим что парсер возвращается назад в состояние 'idle' (back). Символ '\' используется для ввода esc-символов, соответственно чтобы ввести символ '\' надо набрать его дважды '\\', ну как и при указании строк в Си и других языках. В интерактивном режиме можно баловаться сколько душе угодно, пока не убедитесь, что цепочка всех состояний связана корректно.

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

• init: инициализатор состояния (конструктор состояния).
• handler: обработчик состояния.
• fini: финализатор состояния (деструктор состояния).

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

Метод-обработчик (handler) также может управлять работой парсера, хотя может это я и зря реализовал, пока есть, значит надо описать. Если обработчик вернет тип данных Fixnum значение которого находится в пределах (>=0), то это будет расценено как индекс для перехода в какое-то состояние, если индекс выходит за границы массива состояний, парсер выкинет исключение. Если обработчик возвращает nil, парсер будет удерживать это состояние, т.е. ни какой реакции и если любое другое значение, то это расценивается как ошибка и парсер вернет false, что сигнализирует об ошибке парсинга, т.к. во всех остальных случаях он возвращает true. Ниже я приведу измененный код полностью, т.к. вроде и так все подробно постарался описать.

require 'iparser'

#
# Simple check startup arguments.
#
if( ARGV.size != 1 || !File.exist?(ARGV[0]) )
  puts
  puts "ERROR: unable to open file #{ARGV[0]}"
  puts
  exit
end
#
# Create output file.
#
$fout = File.new( 'index.html', 'w' )

#
# Create initializer method for parser-states.
#
def doc_init ( str )
  $fout.print "<p>"
end
#
# Create handler method for parser-states.
#
def doc_handler ( c )
  $fout.print c
end
#
# Create finalizer method for parser-states.
#
def doc_fini ( str )
  $fout.puts "</p>"
end

#
# Create parser-machine object.
#
parser = Iparser::Machine.new

#
# Create startup state for this parser-machine.
#
ps_idle = Iparser::State.new('idle')

#
# Add branch indexes to 'comment-line' and 'comment-block' state.
#
ps_idle.branches << 1
ps_idle.branches << 2

#
# Create single line comment state for this parser-machine.
#
ps_cline = Iparser::State.new('comment-line')
ps_cline.entry << /\//
ps_cline.entry << /\//
ps_cline.entry << /\//
ps_cline.leave << /[\n\r]/

#
# Create multiline comment state for this parser-machine.
#
ps_cblock = Iparser::State.new('comment-block')
ps_cblock.entry << /\//
ps_cblock.entry << /\*/
ps_cblock.entry << /\*/
ps_cblock.leave << /\*/
ps_cblock.leave << /\//
ps_cblock.ignore << '*'

#
# Add handlers for states.
#
ps_cline.init( method(:doc_init) )
ps_cline.handler( method(:doc_handler) )
ps_cline.fini( method(:doc_fini) )

ps_cblock.init( method(:doc_init) )
ps_cblock.handler( method(:doc_handler) )
ps_cblock.fini( method(:doc_fini) )

#
# Add all states to parser-machine.
#
parser.addstate ps_idle
parser.addstate ps_cline
parser.addstate ps_cblock

#
# Call parser startup method.
#
parser.prestart

#
# Call interactive mode for check state-machine.
#
$fout.puts "<html>"
$fout.puts "<body>"

File.open( ARGV[0], 'r' ).each do |line|
  line.each_char do |c|
    parser.parse(c)
  end
end

$fout.puts "</body>"
$fout.puts "</html>"
$fout.close

Да, обратите внимание, что наш обработчик (doc_handler) не возвращает nil, т.к. мы не анализируем результат работы парсера (метода parser.parse). Для последней проверки создадим тестовый файл с именем 'test.c' и наполним его следующим содержимым:

#include <stdlib.h>

///Test function - 1.
void test1 ( void )
{
}

/**
 * Test function - 2.
 */
void test2 ( void )
{
}

Запустим наш скрипт в последний раз и увидим результат работы нашего парсера.

$ ruby parser_example.rb test.c

Это файл 'index.html', на этом все, всем спасибо за внимание!

Надеюсь, что кому-то статься поможет и сократит время на изучение базовых принципов работы анализаторов, а может кто-то и захочет использовать мой gem в личных целях не найдя более простого варианта, если не понравилась, сильно не пинайте, хотя нет конечно, критикуйте, ведь не стать хорошим творцом без хорошей критики ни как. Если кому интересно, вот ссылка на gem iparser.