АРХИТЕКТУРА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ТЕСТОВОГО ВОПРОСА PREG С ОЦЕНКОЙ ОТВЕТА ПО РЕГУЛЯРНЫМ ВЫРАЖЕНИЯМ, ПОДДЕРЖИВАЮЩЕГО ВОЗМОЖНОСТЬ ПОДСКАЗОК ПРОДОЛЖЕНИЯ СОВПАДЕНИЯ

УДК 004.4
О. А. Сычев, В. О. Стрельцов, Д. В. Колесов
АРХИТЕКТУРА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ТЕСТОВОГО ВОПРОСА PREG С ОЦЕНКОЙ ОТВЕТА ПО РЕГУЛЯРНЫМ ВЫРАЖЕНИЯМ,
ПОДДЕРЖИВАЮЩЕГО ВОЗМОЖНОСТЬ ПОДСКАЗОК ПРОДОЛЖЕНИЯ СОВПАДЕНИЯ
Волгоградский государственный технический университет
oasychev@gmail.com, vostreltsov@gmail.com, xapuyc7@gmail.com
Рассматриваются проблемы организации программного кода тестовых вопросов, использующих для проверки ответа студента шаблоны в виде регулярные выражения или их эквиваленты. Проанализированы недостатки аналогичных программ. Описана архитектура вопроса preg, позволяющая сочетать различные методы поиска совпадения с регулярными выражениями (с различными поддерживаемыми функциями, операциями и операндами), поддержкой различных нотации регулярных выражений и инструментов помощи в их составлении.
Ключевые слова: программная архитектура, регулярные выражения, тестовые вопросы.
O. A. Sychev, V. O. Streltsov, D. V. Kolesov
SOFTWARE ARCHITECTURE OF QUESTION TYPE PREG, CAPABLE OF GRADING RESPONSES USING REGULAR EXPRESSION PATTERNS AND HINT MATCH EXTENSION
Volgograd State Technical University
The paper describes software architecture problems in application to design of the code of quiz questions grading student’s responses using pattern matching with regular expression or similar patterns. Drawbacks of similar programs were discussed. Described architecture of preg question, which is capable to combine different match searching methods (supporting different functions, operators and operands), support different regular expression notations and regular expression authoring instruments.
Keywords: software architecture, regular expressions, quiz questions.
Использование регулярных выражений для рить их диапазон применения и снизить коли-проверки строк-ответов студентов на тестовые чество ложноотрицательных оценок за счет вопросы в открытой форме позволяет расши- возможности описания шаблона для совпаде-
ния [1]. Такие вопросы применяются при изучении языков программирования [2], иностранных языков, медицины и т. д. [3].
Однако, по сравнению с использованием конкретных эталонных строк-ответов, регулярные выражения значительно затрудняют генерацию подсказок следующего символа и следующей лексемы, которые полезны при самостоятельной подготовке студентов к выполнению тестов. Дело в том, что стандартные библиотеки работы с регулярными выражениями в большинстве языков программирования (в том числе языка PHP, на котором написана популярная система дистанционного образования (СДО) Moodle [4]) не поддерживают определение частичного совпадения строки с регулярным выражением [5], а также генерацию продолжения частичного совпадения, необходимые для таких подсказок. Поэтому реализация подсказок в вопросах с регулярными выражениями требует самостоятельной реализации алгоритмов поиска совпадения с регулярным выражением и генерации его продолжения. Подобные алгоритмы достаточно сложны и не могут с первого выпуска поддерживать все операции и операнды сложных диалектов регулярных выражений и быть надежно оттестированы (одна из наиболее популярных библиотек поиска совпадения с регулярными выражениями PCRE использует несколько тысяч автоматических тестов). Поэтому при введении механизма подсказок нередко возникает проблема обратной совместимости для вопросов, использующих сложные регулярные выражения.
Наглядным примером этих проблем являлся тестовый вопрос для СДО Moodle «regex», разрабатываемый Джозефом Резо из Университета Ренна 2 [6]. При реализации в очередной версии подсказки следующего символа, была произведена замена стандартной функции поиска совпадения строки с регулярным выражением на собственную реализацию методом генерации всех возможных строк, совпадающих с регулярным выражением, которая не поддерживала множество операндов и операций, в частности большие символьные классы и потенциально бесконечные квантификаторы + и *. В архитектуре вопроса «regex» не было предусмотрено модуля обработки регулярных выражений. Обработка регулярного выражения в вопросе «regex» происходит в функции: expand_re-gexp, которая получает регулярное выражение и формирует массив из всех строк, совпадаю-
щих с полученным регулярным выражением. Функция compare_string_with_wildcard сравнивает ответ студента со всеми совпадающими строками поочередно. Подобный подход привел к низкой скорости работы вопроса «regex», а так же невозможности поддержки многих функций регулярных выражений и отсутствию возможности пополнять вопрос модулями обработки регулярных выражений с лучшими характеристиками.
Для СДО «Moodle» существует другой тип вопроса использующий шаблоны для проверки ответа, разработанный открытым университетом - «pmatch». Этот вопрос использует для проверки ответа собственный язык шаблонов. Он рассчитан на проверку ответов в виде фраз на естественном языке и мало подходит для вопросов связанных с языками программирования.
«Pmatch» имеет более продуманную архитектуру, сравнение ответа с шаблоном отделено от самого вопроса и вынесено в отдельные классы. Класс pmatch_parsed_string выполняет синтаксический разбор строки, содержащей ответ студента, и хранит разобранный ответ; класс pmatch_expression выполняет разбор шаблона и сравнение ответа с шаблоном. Однако, архитектура вопроса «pmatch» не является расширяемой: в ней не предусмотрена возможность использования других типов шаблонов (например, регулярных выражений) с перегрузкой обработчика этих шаблонов, что затрудняет его использование при преподавании дисциплин, связанных с изучением формальных языков (например языков программирования).
Нарушение обратной совместимости в вопросе «regex» привело к неработоспособности нескольких сотен тестовых вопросов по дисциплинам «Программирование на языках высокого уровня» и «Операционные системы» кафедры ПОАС ВолгГТУ. В связи с невозможностью использования вопроса «pmatch» для преподавания этих дисциплин на кафедре была начата разработка типа вопроса «preg», использовавшего стандартные функции поиска совпадения с регулярным выражением.
При внесении подсказок в тип вопроса «preg» были учтены ошибки его предшественника, поэтому было решено сохранить обратную совместимость с вызовом стандартных функций языка PHP для вопросов, не использующих подсказки. В этом случае вопрос перехода на собственную реализацию поиска совпадения мог решаться индивидуально для каж-
дого вопроса. При этом были выдвинуты следующие требования к архитектуре вопроса:
1) наличие нескольких подсистем поиска совпадения строки с регулярным выражением и генерации продолжения, поддерживающих различные функции поиска совпадений и генерации продолжений, операции и операнды;
2) отсутствие дублирования кода между подсистемами поиска совпадения;
3) модульность подсказок с возможностью пополнения их перечня;
4) возможность ввода регулярных выражений в различных нотациях;
5) возможность дополнения вопроса другими обработчиками регулярных выражений: инструментами помощи автору, преобразователями и т. д.;
6) возможность модульного тестирования всех алгоритмически сложных компонентов вопроса.
Основными методами совпадения с регулярным выражением являются методы неде-
терминированных конечных автоматов, детерминированных конечных автоматов и перебора с возвратом (бэктрекинг) [8]. При их изучении выражением было выяснено, что существуют две задачи, код которых может разделяться всеми методами:
1) лексический и синтаксический разбор регулярных выражений;
2) определение совпадения символов с операндами регулярных выражений (поскольку методы различаются лишь в способах реализации операций).
Разработанная в соответствии с этими требованиями архитектура приведена на рис. 1. Вопрос состоит из подсистем интерфейса с СДО Moodle, разбора регулярных выражений, определения совпадения с операндами регулярных выражений, перевода регулярных выражений между нотациями, подсказок, а также модулей определения совпадения с регулярными выражениями (матчеров), модулей отображения регулярных выражений для помощи разработчику.
Рис. І. UML-диаграмма компонентов вопроса Preg
Ключевыми классами для взаимодействия 8и1181. Первые два класса являются абстрактны-
вопроса и всех подсистем регулярных выражений являются qtype_preg_regex_handler,
І qtype_preg_ - обязательный префикс к имени класса
вопроса preg в соответствии с правилами именования qtype_preg_matcher и qtype_preg_matching_re- СДО Moodle.
ми. Класс обработчика (regex_handler) определяет любой обработчик регулярного выражения (матчер, инструмент помощи автору и т. д.), его ответственностью является проведение разбора регулярного выражения (если это необходимо) с генерацией синтаксических деревьев выражений. Класс матчера (matcher) является наследником обработчика и описывает интерфейс для поиска совпадения, а также содержит общий для многих матчеров код перебора позиций начала возможного совпадения и выбора наилучшего среди них (с учетом возможного якорения спереди). Класс результатов матчинга (matc-hing_results) хранит строку, индексы начала и длины совпадений с выражением и подмасками (если матчер поддерживает такую функцию), а также сгенерированное продолжение (включая подмаски).
Лексический анализ осуществляется стандартными методами с помощью конечного автомата, сгенерированного с помощью свободно распространяемой программы JLex PHP. Отдельное стартовое условие используются для разбора символьных классов. Ответственностью лексического анализатора является также контроль за локальным включением (выключением) модификаторов2 и заполнение соответствующих параметров узлов. Синтаксический анализатор генерируется на основе LALR(1)-грамматики с помощью свободно распространяемой программы Lemon PHP. Особенностью синтаксического анализатора является наличие специальных правил грамматики с пониженным приоритетом, отслеживающих нарушения синтаксиса регулярных выражений - незакрытые скобки и квантификатор без операнда.
Абстрактное синтаксическое дерево строится из объектов классов, являющихся потомками класса qtype_preg_node. Две основные ветви наследования идут через абстрактные классы листа дерева (операнда выражения) и операции. К операндам относятся символьные классы (включая соответствующие escape-последовательности, POSIX-классы и юникод-свойства), пустота (в случае альтернативы или пустых скобок), а также простое утверждение, обратная ссылка, рекурсия и управляющая конструкция. Эти классы составляют подсистему определения совпадения с операндами и используются всеми матчерами. Абстрактный класс листа предоставляет интерфейс для общения
2 На данный момент реализован модификатор нечуст-вительности к регистру.
любой реализации матчера со всеми типами операндов. Основными функциями этого интерфейса являются match (проверяет, совпадает ли строка по заданному индексу с этим операндом), и next_character (генерирует символ, подходящий для этого операнда). Операнды, которым для выполнения этих функций недостаточно строки и позиции совпадения в ней (например, обратная ссылка) могут запросить необходимую информацию у матчера, используя сохраняемую в таком операнде ссылку на него.
Классы операций поддерживают конкатенацию, альтернативу, квантификаторы (конечный и бесконечный), сложное утверждение, подмаску и условную подмаску. Они являются пассивными и хранят лишь параметры оператора и массив операндов.
Любой обработчик регулярного выражения может определить свою иерархию классов, параллельную иерархии с корнем в qtype_preg_no-de. При этом будет сгенерировано специфическое для данного обработчика дерево с помощью фабрики, реализованной в классе qtype_preg_re-gex_handler. Объекты узлов специфических классов агрегируют в себя объект узла абстрактного синтаксического дерева. Обработчик может определить только классы необходимых ему узлов, в этом случае остальные объекты будут взяты напрямую из синтаксического дерева.
Реализация абстрактного интерфейса поиска совпадений требовала решения ряда технических противоречий. Различные матчеры поддерживают различный диапазон функций поиска совпадения и генерации продолжения, операндов и операций; различны также методы поиска совпадений - стандартные функции языка PHP уже включают в себя цикл перебора начальных позиций совпадения, в то время как для матчеров, самостоятельно реализующих поиск совпадения реализацию этого цикла следует вынести в базовый класс для исключения дублирования кода.
Поддерживаемые функции матчера определяются через метод is_supporting, для этого можно создать «пустой» объект матчера без выражения. Вопрос учитывает следующие виды функций:
1) определение частичного совпадения;
2) генерация продолжения частичного совпадения;
3) определение минимального количества символов до завершения совпадения;
4) захват подмасок;
5) продолжение совпадения гарантированно генерируется до полного завершения (если оно возможно).
При редактировании вопроса в зависимости от функциональных возможностей выбранного матчера, активируются различные функции вопроса - различные виды подсказок, вставка захваченных значений подмасок в комментарий преподавателя и т. д.
Даже синтаксически корректное регулярное выражение может оказаться не обработанным конкретным матчером из-за наличия неподдерживаемого операнда или операции. Для обработки этой ситуации матчер осуществляет процедуру «принятия» (акцептинга) регулярного выражения - в случае, если в нем были обнаружены неподдерживаемые элементы, пользователь получит соответствующее сообщение и предложение выбрать другой матчер. Матчеры, самостоятельно реализующие поиск совпадений с регулярным выражением, проводят акцептинг на уровне узлов синтаксического дерева; те же матчеры, которые используют стандартные функции языка, перегружают функцию акцептинга всего выражения.
Поддержка различных нотаций регулярных выражений реализована в виде набора классов нотаций, которые могут осуществлять преобразование регулярного выражения в виде строки (а также его модификаторов и опций) из нотации пользователя в нотацию, используемую матчером. В качестве базовой нотации матче-ров выбрана нотация Рег1-совместимых регулярных выражений (РСКЕ) как наиболее богатая описательными средствами из существующих в настоящее время, так что другие нотации всегда могут быть приведены к ней (обратное неверно). На данный момент реализована поддержка дополнительной нотации МооШе 8Ьог-tanswer, позволяющей использовать систему подсказок при записи вопроса строкой с использованием плейсхолдера «*», обозначающего любое количество любых символов, реализованную в стандартном типе вопроса СДО МооШе.
Качественная и надежная реализация алгоритмов такой сложности, как разбор регулярных выражений, поиск совпадения с ними и генерация продолжения совпадения невозможна без активного использования автоматизированного тестирования. Модульные тесты лексического анализа включают в себя 1153 проверки, синтаксического - 471 проверку.
Однако наибольшее количество тестов содержит подсистема тестирования матчеров. Поскольку все матчеры должны соответствовать сходным требованиям, то они могут оцениваться единым набором тестов. Однако их вызов и проверка, с учетом различных функций поиска совпадений и генерации продолжения в матчерах, являются нетривиальной задачей и требуют большого объема кода. В таких условиях целесообразным явилось использование методологии тестирования, управляемого данными [9]. Входные и ожидаемые выходные данные для тестов поставляются специальными функциями, расположенными в отдельных от кода тестирования файлах, при этом дается максимально полный набор выходных данных. Код запуска и проверки тестов расположен в абстрактном классе, и осуществляет проверки учитывая функции, реализуемые матчером (например, поддерживается ли определение частичных совпадений и возврат подмасок). Если регулярное выражение не проходит акцептинг на данном матчере (т. е. содержит неподдерживаемые операнды и операторы), то тест не проверяется без выдачи ошибки. Тестовые данные включают теги, которые используются для выделения множеств тестов и управления их выполнением. Так, например, перед началом тестирования с помощью специального теста определяется ассоциативность конкатенации [10] тестируемого матчера, в зависимости от которой различаются ожидаемые значения для некоторых тестов. В настоящее время используются тесты собственной разработки (265 тестовых случаев) и два набора открытых профессиональных тестов: тесты проекта testregex фирмы AT&T (377 тестовых случаев) и библиотеки PCRE (1084 тестовых случая).
Данная архитектура позволила реализовать тестовый вопрос preg для СДО Moodle с поддержкой трех способов поиска совпадений с регулярными выражениями (через вызов стандартной функции языка PHP preg_match, а также собственной реализацией методов детерминированных и недетерминированных конечных автоматов); двух нотаций (Perl-Compatible Regular Expression и Moodle Shortanswer) и двух видов подсказок (следующего символа и следующей лексемы). Такой вопрос может использоваться как для преподавания дисциплин, связанных с изучением естественных языков (как вопросы «regex» и «pmatch»), так и языков программирования. В настоящее время разрабо-
танный вопрос внедрен в учебный процесс кафедры ПОАС ВолгГТУ при проведении тестирования по дисциплинам «Основы программирования» и «Операционные системы», а также итоговой государственной аттестации бакалавров (по этим дисциплинам).
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Колесов, Д. В. Генерация подсказки в виде следующего правильного символа в открытом вопросе с проверкой ответа по регулярному выражению / Д. В. Колесов, О. А. Сычев // XVI региональная конференция молодых исследователей Волгоградской области, Волгоград, 8-11 ноября 2011 г. : тез. докл. / ВолгГТУ [и др.]. - Волгоград, 2012. - С. 235-236.
2. Литовкин, Д. В. Программное обеспечение для тренировки навыков по составлению логических выражений на языке Си. Сценарий работы программы-тренажера / Д. В. Литовкин, О. А. Сычев, М. П. Гладкова // Известия ВолгГТУ : межвуз. сб. науч. ст. № 12 / ВолгГТУ. - Волгоград, 2011. - (Серия «Актуальные проблемы управления, вычислительной техники и информатики в технических системах»). - С. 99-102.
3. Сычев, О. А. Использование регулярных выраже-
ний для проверки ответов на тестовые вопросы, предоставляемых в виде фрагмента кода программы / О. А. Сычев, Д. В. Литовкин // Информационные технологии в образовании, технике и медицине : матер. междунар. конф., 2124 сент. 2009 / ВолгГТУ [и др.]. - Волгоград, 2009. - C. 45.
4. Jason Cole. Using Moodle: Teaching with the Popular Open Source Course Management System. - O’Reilly, 2005 -219 p.
5. Котеров Д., Костарев А. PHP 5. - С-Пб.:БХВ-Пе-тербург, 2008. - 1104 с.
6. Joseph Rezeau. Regular Expression Short-Answer question type / [Электронный ресурс] - [2012]. - Режим доступа: http://docs.moodle.org/23/en/Regular_Expression_Short-Answer_question_type
7. Pattern match / [Электронный ресурс] - [2012]. -Режим доступа: http://labspace.open.ac.uk/mod/oucontent/ view.php?id=470268&section=5.3.1
8. Russ Cox. Regular Expression Matching Can Be Simple And Fast / [Электронный ресурс] - [2012]. - Режим доступа: http://swtch.com/~rsc/regexp/regexp1 .html
9. Pekka Laukkanen. Data-Driven and Keyword-Driven Test Automation Frameworks. - Master's thesis. Helsinki University of Technology, 2006
10. Glenn Fowler. An Interpretation of the POSIX regex Standard. [Электронный ресурс] - [2012]. - Режим доступа: http://www2.research.att.com/~gsf/testregex/re-interpreta-tion.html