Делаем простой парсер химических формул с помощью JavaCC

Я продолжаю очень медленно и по чуть-чуть пилить "химический поиск" ChWiSe.Net. И хотя он пока что в стостоянии протипа, некоторый ненулевой поток запросов есть. Я заметил, что пользователи не всегда хотят использовать SMILES-нотацию. Думаю, она не особо известна за пределами сообщества професионалов-химиков и хемоинформатиков. Вместо этого пользователи пытаются найти вещества по обычной полуструктурной формуле, например, всем известный этиловый спирт пытаются найти запросом C2H5OH вместо SMILES-формулы CCO. Что ж, надо поддержать и такие запросы.

Нам понадобится создать парсер таких формул. Для формул вида (NH4)2CO3, Al2(SO4)3, (CH3)2O или CH3COOH необходимо правильно разобрать все скобочки, числовые коэфициенты, выделить отдельные химические элементы и группы атомов, такие, как сульфат-анион, и использовать эти выделенные составляющие формулы для поиска похожих веществ.

Я решил реализовать парсер формул в соответствии с очень простой грамматикой: терминалами являются круглые скобки, числа, символы химических элементов и "стандартные" группы атомов ( COOH, OH, SO4, и.т.д. ). Правил вывода всего пять:

ELEMENT -> elementToken
ELEMENTARYGROUP -> elementaryGroupToken
GROUP -> '(' FORMULA ')'
TERM ->  (GROUP|ELEMENTARYGROUP|ELEMENT) NUMBER?
FORMULA -> TERM*

Человеческим языком это можно описать так (снизу вверх):

• Формула (FORMULA) это некоторое количество идущих друг за другом "термов" (TERM). Звёздочка после элемента обозначает некоторое (возможно, нулевое) количество повторений этого элемента.
• Терм (TERM) это или группа (GROUP) или "элементарная группа" (ELEMENTARYGROUP), или элемент (ELEMENT) после чего может следовать число (NUMBER). Числа может и не быть: знак вопроса после NUMBER обозначает что этот элемент необязателен.
• Группа (GROUP) - это формула (FORMULA) в скобках.
• Элементарная группа (ELEMENTARYGROUP) - терминал elementaryGroup
• Элемент (ELEMENT) - терминал символа химического элемента

Эта граммтика столь проста, что всю логику разбора формулы можно написать руками, но я так делать не стал: такой код будет плохо поддерживаемым, менять грамматику будет сложно. Есть специальные инструменты, которые позволяют создавать парсеры на вашем любимом языке программирования: lex/yacc, flex/bison, javacc, antlr, boost.spirit и многие другие. Я бы выделил две группы таких инструментов: в первой группе (lex/yacc, flex/bison, javacc, ANTLR) грамматика описывается в отдельном файле в специальном, удобном для описания грамматик формате, а затем специальные трансляторы преобразуют файл описания грамматики в код, который будет осуществлять разбор строк в соответствии с грамматикой. Другая группа инструментов основана на использовании возможностей соответствующего языка программирования. Так, например, в Boost.Spirit с помощью шаблонной магии и перегрузки операторов грамматика описывается прямо в C++-коде.

Для своих целей я выбрал JavaCC (Java Compiler Compiler). Этот простой генератор парсеров является рабочей лошадкой во многих проектах. Из open source могу упомянуть парсеры поисковых запросов Lucene и Solr.

Описание парсера состоит из двух основных частей: описания сканера и собственно парсера. Сканер осуществляет выделение из поступающей на вход строки отдельных терминалов. У меня он определяется так:

Секция TOKEN определяет известные парсеру типы токенов. У меня их 5 типов: открывающаяся скобка, закрывающаяся скобка, число (NUM), символ химического элемента (ELEMENT), и то, что я называю "элементарная группа" (ELEMENTARYGROUP).

Во второй важнейшей часть необходимо описать правила вывода парсера. В JavaCC эти правила описываются "декларативно" с примесью Java-кода. Пять правил, описанных выше на языке JavaCC записывются так:

Файл описания грамматики целиком можно посмотреть здесь.

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

Вот собственно и всё, мы написали простой парсер.

Генерация парсера
JavaCC - это утилита командной строки которая обрабатывает описание грамматики и генерирует собственно парсер: Java-класс, который при конструировании получает на вход объект класса java.io.Reader. Вызвать геренацию парсера из командной строки можно так (это одна строка):

java -cp <ПУТЬ К ДИРЕКТОРИИ JavaCC>/bin/lib/javacc.jar javacc SemistrucutredFormulaParser.jj

Вызов этой команды сгенерирует несколько *.java файлов:

ParseException.java
SemistructuredFormulaParserConstants.java
SemistructuredFormulaParser.java
SemistructuredFormulaParserTokenManager.java
SimpleCharStream.java
Token.java
TokenMgrError.java

Эти файлы можно включить в свой проект руками, но обычно этот процесс автоматизируют. Например, с помощью системы сборки Maven.

Проект Maven

Шаги, описанные выше могут быть включены в проект maven. Следует положить *.jj файл в поддиректорию $PROJECT_ROOT/src/main/javacc, где $PROJECT_ROOT - корневая директория проекта. В pom.xml следует включить такую секцию: