Задумывались ли Вы, уважаемый читатель, о том, как создаются новые языки программирования? А может быть, Вы даже пробовали создать свой интерпретатор или компилятор?

 

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

 

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


Немного теории: для решения подобной задачи необходимо разработать «парсер» - синтаксический анализатор (англ. Parse - анализ, делать грамматический разбор). Сведущий читатель может заметить, что подобная проблема сегодня решается с использованием XML схем и их разбора. Но хочу заметить, что подобный подход не всегда приемлем, особенно если вы занимаетесь модернизацией уже существующей системы с наработанной библиотекой команд. В таком случае вам придется создать свой собственный «синтаксический анализатор рекурсивного спуска» (создание такового подробно рассмотрено в известной книге Герберта Шилдта «С для профессиональных программистов»). Если описывать процесс вкратце, то необходимо последовательно анализировать каждый символ входящего потока и выделять лексемы, а затем преобразовывать их во внутренний формат.


Теперь давайте посмотрим, как подобную задачу можно решить в Java приложениях. Практически одновременно с появлением Java, Sun Microsystems выпустила пакет JavaCC (Java Compiler Compiler), однако сейчас его поддержкой занимается Metamata, недавно вошедшая в состав WebGain. Пакет можно загрузить по адресу:
http://www.webgain.com/products/java_cc/ Сам по себе он, что называется, - «pure Java», поэтому для работы вам понадобится J2SDK.


Подход к работе с пакетом следующий:вы создаете файл с грамматическим описанием возможностей вашего будущего «языка», затем запускаете JavaCC на выполнение и получаете в результате целый пакет классов, позволяющий работать с входным потоком по заданным правилам. В дальнейшем вы сможете использовать их везде, где это необходимо. Файлы с грамматическими описаниями (*.jj) представляют собой текстовые файлы, содержащие как грамматические теги, так и фрагменты кода на языке Java.


Принципы описания грамматики в JavaCC во многом сходны с EBNF (расширенной формой Бакуса Наура - Extended Backus Naur Form). Подробнее о EBNF и о терминах «продукция», «символы», «терминал» и «нетерминал» вы можете узнать по адресу:
http://www.softcraft.ru/translat/lect/t0202.shtml

 

Азы

 

Подготовку к серьезной работе начнем с грамматического описания простейшей задачи. Для этого рассмотрим проблему, решаемую многими интерпретаторами и компиляторами, а именно - определение парности открывающих и закрывающих скобок (в нашем случае это будут фигурные скобки, однако читатель может провести ряд экспериментов и заменить их любыми другими). Для этого воспользуемся файлом %JavaCC_HOME%\examples \SimpleExample \Simple2.jj , который вы найдете после инсталляции JavaCC, где %JavaCC_HOME% - каталог, в котором вы установили «дракошу». Simple2.jj содержит всего 32 строки, или 384 байта, но после обработки его с помощью JavaCC вы получите семь файлов с исходными текстами вашего «парсера» общим объемом 34Кб. Давайте внимательно рассмотрим содержимое этого файла.


Первый блок заключен между двумя тегами PARSER_BEGIN и PARSER_END (листинг 1). Между ними вы можете вставить описание главного класса будущего «парсера». Единственное ограничение накладывается на имя класса - оно должно соответствовать имени файла и имени, оговоренному в обоих тегах. В данном примере это Simple2 . В дальнейшем это имя будет также использоваться как префикс для имен других классов, за генерацию которых возьмется JavaCC.

 

 

Конструктор генерируемых «парсеров» рассчитан на единственный параметр типа java.io.InputStream. Это именно тот входной поток, который и будет подвергнут синтаксическому анализу. В данном примере это будет System.in, что позволит протестировать «парсер» прямо из консоли. Если вам понадобится другой источник входных данных, позаботьтесь об этом, создав соответствующий вызов конструктора.


Далее идет спецификация SKIP. Сразу оговорюсь, что в JavaCC предусмотрено еще три типа спецификаций: TOKEN, SPECIAL_TOKEN и MORE.

 

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

 

 

И наконец, самое главное: описание двух продукций - нетерминалы Input и MatchedBraces (листинг 3).

 

 

Обратите внимание на строку parser.Input(); в методе main (листинг 1). Это и есть вызов метода Input(), представляющего продукцию. В JavaCC нетерминалы имеют равные права, и вы можете инициировать вызов любого из них. В данном случае нетерминал Input() будет вызывать нетерминал MatchedBraces() до тех пор, пока не встретит конец файла - < EOF >. В свою очередь, нетерминал MatchedBraces() будет рекурсивно вызывать самого себя для обнаружения вложенных пар фигурных скобок.

 

При этом возможны такие формы описания вызовов:

  • […] или (…) -  необязательные элементы;
  • e1 |e2 |e3 |… - один из возможных вариантов (e1, ИЛИ e2, ИЛИ e3);
  • (e )+ -  не менее одного повторения выражения e;
  • (e )* - произвольное количество выражений e, включая полное отсутствие такового.

Таким образом, описанный нетерминал MatchedBraces() гласит: «допустимым является рекурсивное вложение пар фигурных скобок друг в друга».


Теперь вы можете запустить JavaCC в интерактивном режиме, обработать исходный файл и после компиляции классов запустить Simple2.class на выполнение. Попробуйте сначала ввести корректно вложенные пары скобок, а затем что то вроде этого: «{{}}}}». В результате вы увидите сообщение об ошибке с указанием причины и координатами ошибочно введенной скобки.

 

Задача, максимально приближенная к боевой

 

Итак, возвращаемся к задаче, упомянутой ранее. Сформулируем ее поточнее: допустим, у нас есть некая таблица DocTable, содержащая товарные накладные и имеющая поля quantity и price - соответственно, количество и цену без НДС (в данном примере это важно). При этом пользователь хотел бы иметь возможность делать следующие выборки: сумма без НДС и сумма с НДС. Естественно также, что пользователю хотелось бы задавать формулу расчета «в человеческом виде», в данном случае остановимся на строках вида: «колво * (цена + ндс)» и «колво * цена». Обращаю ваше внимание и на тот факт, что заставить пользователя вводить «цена + ндс» в строгой последовательности так же нереально, как и описать все возможности JavaCC в одной статье. Поэтому необходимо предусмотреть возможность ввода как одного, так и второго варианта. После того как пользователь ввел формулу, ее надо проверить на соответствие нашей грамматике и превратить в SQL запрос. Вот этим мы сейчас и займемся, с небольшими ограничениями.


Для начала определяем две группы токенов, которые нам понадобятся для работы (листинг 4).

 

 

В первой группе мы определяем операторы, доступные пользователю (соответственно - PLUS и MULTIPLY). Во второй - определяем поля, которыми может оперировать пользователь.


Теперь мы должны описать нетерминалы, которые, собственно, и будут решать поставленную задачу. Их четыре - one_line(), term(), unary(), sum():

  • one_line() - для реакции на конец строки и конец файла;
  • term() -  для обработки произведения;
  • unary() -  для обработки токенов PRICE и TAX;
  • sum() -  для описания суммы полей.

Полный листинг файла sql.jj доступен по адресу: http://www.i.com.ua/~slavay/articleattachment/archive/rc/sql.jj, в данной же статье рассмотрим только токен unary() – как наиболее интересный (листинг 5).


Начнем с того, что определим заголовок токена и проинициализируем переменную Token x. Token - класс, генерируемый JavaCC для определения токенов, - он нам понадобится в дальнейшем. Результаты работы нетерминала будем помещать в экземпляр java.util.stack argStack, а затем, после обработки всего выражения, выстроим элементы стека в sql-выражение. В качестве элементов нетерминала могут выступать либо PRICE, либо TAX - это описывается строкой (x =< PRICE >|x =< TAX >). При этом то, какой конкретно токен встретился парсеру, можно узнать из свойства x.kind. Ну, и в заключение об этом нетерминале:как известно, НДС у нас составляет 20% - таким образом, для того чтобы получить цену с НДС, достаточно умножить цену на коэффициент 1,2. Поэтому, если парсер встретит токен TAX, в стек заносится коэффициент 1,2, а нетерминал sum() должен из выражения «цена + ндс» сделать «price * 1.2».

 


И последнее -  метод main (листинг 6).

 


Здесь мы создаем объект parser , передаем ему входной поток и ожидаем ввода пользователя. А после его завершения анализируем строку и генерируем из него sql-запрос.


Далее надо обработать файл sql.jj с помощью JavaCC и получить пакет классов - их нужно откомпилировать. Теперь можно запустить наш парсер командной строкой Java sql. Вот пример обработки нескольких команд пользователя нашим парсером (листинг 7), где первая строка - ввод пользователя, а вторая -  sql-запрос.

 


Созданный нами парсер имеет ряд недостатков: 3-е и 4-е выражения являются бессмысленными; кроме того, команду «(ндс + цена) * колво» парсер воспринимает как неправильную - но над этим вам придется поработать самостоятельно.


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

 

Ресурсы


1. Исходный текст парсера sql.jj:
http://www.i.com.ua/~slavay/articleattachment/archive/rc/sql.jj
2. Ензелинг Оливер . Создайте свой собственный язык, используя JavaCC.: http://www.javable.com/javaworld/12_00/02/
3. Пакет JavaCC доступен по адресу: www.webgain.com/products/metamata/java_doc.html
4. Основы разработки трансляторов,
http://www.softcraft.ru/translat/lect/content.shtml

2004.09.03
19.03.2009
В IV квартале 2008 г. украинский рынок серверов по сравнению с аналогичным периодом прошлого года сократился в денежном выражении на 34% – до $30 млн (в ценах для конечных пользователей), а за весь календарный год – более чем на 5%, до 132 млн долл.


12.03.2009
4 марта в Киеве компания Telco провела конференцию "Инновационные телекоммуникации", посвященную новым эффективным телекоммуникационным технологиям для решения задач современного бизнеса.


05.03.2009
25 февраля в Киеве компания IBM, при информационной поддержке "1С" и Canonical, провела конференцию "Как сохранить деньги в условиях кризиса?"


26.02.2009
18-19 февраля в Киеве прошел юбилейный съезд ИТ-директоров Украины. Участниками данного мероприятия стали ИТ-директора, ИТ-менеджеры, поставщики ИТ-решений из Киева, Николаева, Днепропетровска, Чернигова и других городов Украины...


19.02.2009
10 февраля в Киеве состоялась пресс-конференция, посвященная итогам деятельности компании "DiaWest – Комп’ютерний світ" в 2008 году.


12.02.2009
С 5 февраля 2009 г. в Киеве начали работу учебные курсы по использованию услуг "электронного предприятия/ учреждения" на базе сети информационно-маркетинговых центров (ИМЦ).


04.02.2009
29 января 2009 года в редакции еженедельника "Computer World/Украина" состоялось награждение победителей акции "Оформи подписку – получи приз!".


29.01.2009
22 января в Киеве компания "МУК" и представительство компании Cisco в Украине провели семинар для партнеров "Обзор продуктов и решений Cisco Small Business"

 

 
 
Copyright © 1997-2008 ИД "Комиздат".