LiteCoding

Заметки о программировании

Использование aParse 2.0 для генерации парсера по ABNF-грамматике

without comments

Когда возникает задача что-то быстро распарсить, как правило, берется либо уже готовый парсер, либо пишется что-то свое, которое работает только с исходными данными определенного вида и постоянно требует контроля и ручной корректировки. Но есть еще один вариант — сгенерировать парсер по описанию грамматики входного языка и дальше иметь дело только с его лексическими единицами. Очень часто для таких целей используется Yacc или Bison. Однако, в этой статье речь пойдет о маленькой свободно распространяемой (freeware) утилите aParse.

aParse — генератор Java-парсеров языков, описанных дополненной формой Бэкуса-Наура (Augmented Backus–Naur Form, ABNF, RFC 5234). На данный момент доступна версия 2.0 этой утилиты, в которой устранен ряд мелких ошибок и добавлена поддержка подключаемых правил, которые позволяют расширить возможности парсера. Грамматика, принимаемая aParse отличается от ABNF в следующих пунктах:

  1. Имя правила может содержать знак подчеркивания (_) и начинаться с него
  2. После каждого определения правила ставится точка с запятой (;)
  3. Для комментариев используется решетка (#)
  4. Не поддерживается prose-val

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

#####BASIC RULES#####
HTAB = %x09;
CR = %x0d;
LF = %x0a;
SP = %x20;
CRLF = CR LF;
QUOT = %x22;
HASH = %x23;
COMMA = %x2c;
DOT = %x2e;
COLON = %x3a;
SEMICOLON = %x3b;
EQ = %x3d;
UNDERSCORE = %x5f;
ALPHA = %x41-5a / %x61-7a;
DIGIT = %x30-39;
HEXDIG = DIGIT / "A" / "B" / "C" / "D" / "E" / "F" ;
VCHAR = %x21-7e;

После того, как вы определили грамматику, настает черед сгенерировать парсер. Делается это так:

java -cp aparse-2.0.jar com.parse2.aparse.Parser [параметры] <файл_грамматики> 

Подробнее о параметрах можно прочитать здесь. Обратите особое внимание на параметр -package, с помощью которого задается java-пакет (или пространство имен), к которому будет относиться сгенерированный парсер. Желательно сразу выделить парсер в отдельное пространство имен, т.к. в дополнение к основным 7 классам (Displayer и XmlDisplayer не являются обязательными) будет сгенерировано по одному классу на каждое заданное правило.

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

Rule rule = Parser.parse("entity", srcFile);
Entity entity = (Entity)classrule.accept(new ImplementedVisitor());

Каждое правило содержит свое текстовое представление (Rule.spelling) и упорядоченный список дочерних правил (Rule.rules), примененных в процессе разбора. Реализуя методы интерфейса, вы задаете способ трактовки входных данных, причем, сами контролируете глубину обхода дерева, игнорируя разделители и прочие несущественные правила. Делается это вызовом метода accept() у дочерних правил. Каждое правило может выступать в виде фабрики сущности, выраженной им самим.

Рассмотрим ситуацию, когда у нас есть следующие правила:

qualifier = (ALPHA / UNDERSCORE) *(ALPHA / DIGIT / UNDERSCORE);
className = %x4c qualifier *(%x2f qualifier) SEMICOLON;

В таком случае вовсе необязательно спускаться по дереву правил, вызывая метод accept(), вплоть до правила qualifier. Достаточно взять текстовое представление правила className и вернуть его как сущность, выраженную правилом.

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

public abstract class BasicTextBuilder implements Visitor
{

	@Override
	public Object visit(Rule$CR rule)
	{
		return rule.spelling;
	}

	@Override
	public Object visit(Rule$LF rule)
	{
		return rule.spelling;
	}

	@Override
	public Object visit(Rule$SP rule)
	{
		return rule.spelling;
	}

	//... далее еще несколько подобных методов

	@Override
	public Object visit(Terminal$StringValue rule)
	{
		return rule.spelling;
	}

	@Override
	public Object visit(Terminal$NumericValue rule)
	{
		return rule.spelling;
	}
	
}

Пример реализации интерфейса Visitor можно посмотреть по этой ссылке (соответствующая грамматика).

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

Share and Enjoy:
  • Print
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • LinkedIn
  • Tumblr

Written by Дмитрий Воробьев

Вторник, Май 31st, 2011 at 15:41

Leave a Reply

You must be logged in to post a comment.