ПРОБЛЕМА СИНТАКСИЧЕСКОГО АНАЛИЗА ТЕКСТОВ НА ВНЕШНИХ ПРЕДМЕТНО-ОРИЕНТИРОВАННЫХ ЯЗЫКАХ

Research article
Issue: № 7 (7), 2012
PDF

Филиппов Д.Ю.

Магистрант, кафедра информатики и программного обеспечения вычислительных систем

Национальный исследовательский институт «МИЭТ»

ПРОБЛЕМА СИНТАКСИЧЕСКОГО АНАЛИЗА ТЕКСТОВ НА ВНЕШНИХ ПРЕДМЕТНО-ОРИЕНТИРОВАННЫХ ЯЗЫКАХ

  Аннотация В статье рассмотрено понятие предметно-ориентированного языка, описаны основные преимущества применения таких языков в программных системах. Кроме того, рассмотрен способ построения синтаксических анализаторов средствами парсер-комбинаторов (на примере программного каркаса парсер-комбинаторов из стандартной библиотеки языка Scala):  описаны преимущества и недостатки подобного подхода и область его возможного применения. Ключевые слова: предметно-ориентированный язык, синтаксический анализ, парсер-комбинатор, Scala. Keywords: domain-specific language, parsing, parser combinator, Scala.   При разработке финансовых, корпоративных и других программных систем может возникать необходимость в создании языка, специализированного на решении определенного круга задач. Такой язык называется предметно-ориентированным (англ. domain-specific language, DSL). Предметно-ориентированные языки — противоположность языков программирования общего назначения, таких, как Си, или языков моделирования общего назначения, наподобие UML. Примерами предметно-ориентированных языков могут служить [7]:
  • HTML — язык гипертекстовой разметки,
  • Verilog и VHDL — языки описания аппаратуры,
  • грамматики YACC и ANTLR для создания парсеров.
Предметно-ориентированные языки позволяют решать поставленные задачи в терминах и на уровне абстракции предметной области. Из этого следует, что специалисты в данной предметной области, не имеющие навыков программирования, получают возможность осуществлять проверку корректности бизнес-логики приложений, разработанных с использованием DSL. Кроме того, применение языков, специфичных для определенного круга задач, может упростить работу разработчиков, использующих языки общего назначения. Например, программист, использующий язык Java для разработки финансового программного обеспечения, может воспользоваться языковым расширением, позволяющим в исходном коде программы работать с денежными величинами. Различают встроенные (embedded или internal) и внешние (external)  DSL. Встроенные DSL реализуются в виде библиотек, использующих синтаксис некоторого языка общего назначения, но добавляющих в него элементы (типы данных, процедуры, методы), специфичные для данной предметной области [7]. Внешние же DSL имеют собственную грамматику, а значит, требуют специфичных средств лексического и синтаксического анализа [1]. Из этого, однако, также следует, что  возможно разработать настолько выразительный внешний DSL, что специалисты предметной области смогут не только читать, но и писать код на этом языке. Для встроенного DSL  это может оказаться трудно осуществимой задачей. Для создания синтаксических анализаторов внешних предметно-ориентированных языков часто применяются генераторы парсеров. Примером может служить ANTLR — генератор парсеров, который позволяет автоматически создавать программу-парсер (как и лексический анализатор) на одном из целевых языков программирования (C++, Java, C#, Python, Ruby) по описанию грамматики на языке, близком к расширенной форме Бэкуса-Наура (РБНФ) [6]. В качестве альтернативного подхода при построении  синтаксических анализаторов можно моделировать парсеры как функции и определять функции высшего порядка (комбинаторы),  снабженные грамматическими конструкциями, такими как упорядочение, выбор и повторение [4]. Данный подход применим для функциональных языков. При этом сложные парсеры строятся динамически из более простых посредством парсер-комбинаторов. Для реализации подобного подхода при создании анализатора внешнего предметно-ориентированного языка можно использовать язык программирования Scala, использующий чистую объектно-ориентированную модель и полноценно поддерживающий функциональную парадигму программирования. Исходный код Scala может быть скомпилирован в байт-код, исполняемый виртуальной машиной Java. Таким образом, разрабатываемый на Scala анализатор может свободно взаимодействовать с Java-кодом. Это особенно полезно, если на момент начала разработки уже существует API, реализованное на языке Java и позволяющее решать задачи, специфичные для данной предметной области. Библиотека Scala включает в себя программный каркас парсер-комбинаторов, позволяющий создавать анализаторы текстов на языках, которые могут быть описаны контекстно-свободной грамматикой. При этом главной привлекательной особенностью данного программного каркаса является предоставляемый им внутренний DSL: описание парсера на нем близко к аналогичному описанию с использованием РБНФ. В качестве преимущества можно также отметить то, что программный каркас парсер-комбинаторов Scala проще в изучении и использовании, чем специализированные инструменты по генерации парсеров. При этом разница в производительности полученных парсеров часто оказывается незначительной, если только не требуется осуществлять разбор больших входных данных [3]. Кроме того, парсеры, реализованные средствами Scala, не имеют «тяжеловесных» зависимостей времени выполнения. Таким образом можно заключить, что если этап анализа текстов на разрабатываемом предметно-ориентированном языке не будет критичным  по времени выполнения или подразумевается, что не будет осуществляться разбор больших объемов входных данных, то разработка парсера с использованием программного каркаса парсер-комбинаторов Scala может оказаться приемлемым или даже предпочтительным решением. Несмотря на это, на данный момент для реализации внешних DSL Scala используется редко. Более широкое распространение получили встроенные DSL на базе Scala (Pistache DSL, Apache Camel Scala DSL). Следует отметить, что язык Scala динамично развивается (стабильная версия 2.9.2 выпущена 14 апреля 2012 года [5]). При этом, естественно, совершенствуется и программный каркас парсер-комбинаторов. Так,  в версии библиотеки 2.8 была улучшена поддержка восстановления после ошибок и сообщений о них. Кроме того, была добавлена возможность создания так называемых packrat-парсеров. Packrat-парсер [2] является разновидностью анализатора, работающего схожим с рекурсивным спуском методом, за исключением того, что при анализе он запоминает промежуточные результаты всех вызовов взаимно рекурсивных функций анализа. Благодаря этой особенности packrat-парсер способен анализировать множество контекстно-свободных грамматик и любую РВ-грамматику (грамматику, разбирающую выражение) в линейное время ценой увеличения затрат памяти.

Литература

  1. Dean Wampler, Alex Payne. Programming Scala. O'Relly Media, 2009
  2. Ford, Bryan Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking. Massachusetts Institute of Technology (September 2002)
  3. Martin Odersky, Lex Spoon, Bill Venners. Programming in Scala, Second Edition. Artima, 2001
  4. Грэм Хаттон: Монадические комбинаторы парсеров. Университет Ноттингема, Великобритания — http://ru.wikibooks.org/wiki/Монадические_комбинаторы_парсеров
  5. Официальный сайт Scala. «Scala 2.9.2 final» — http://www.scala-lang.org/node/12603
  6. Статья «ANTLR» энциклопедии «Википедия» —http://ru.wikipedia.org/wiki/ANTLR
  7. Статья «Domain-specific language» энциклопедии «Википедия» — http://en.wikipedia.org/wiki/Domain-specific_language