Диссертация (1090660), страница 16
Текст из файла (страница 16)
Если мы имеем некоторое множество с алфавитом = , , . . ., определенное квантификатором «+» (от одного и более), то мы можем сделать эквивалентную замену (2.1).95+ = **()+ = () ;(2.1)Условие конечности множества. Если в регулярном выражении имеется квантификатор «*» (от до ∞), то количество комбинаций, подходящих заданному регулярному выражению, неограниченно большое. Для устранения неопределенности такогорода используем замену, ограничивающую максимальную длину строки (2.2).* = {1,50} (От 1 до 50)(2.2)Также имеют смысл эквивалентные замены (2.3).(* )* = *| = (2.3)()|() = ()|();Алгоритм вычисления мощности множества.
Возьмем простой пример регулярного выражения (2.4).[a-z]{2}|[0–9]?[a-z]{2, 3}|[a-z][a-z]?(2.4)Разобьем данное выражение на три группы, разделяемые символом «|» и вычислиммощность каждой.1. Группа [a-z]{2} Множество [a-z] имеет 26 символов, квантификатор «{2}»говорит о том, что множество повторяется два раза. Иными словами, у нас две «единичные позиции» – два места: на каждом месте может быть один из 26 символов.А значит, количество возможных вариантов сочетаний равно 26 · 26 = 262 , где 26 –мощность алфавита a-z, а степень 2 – количество повторений.2. Группа [0–9]?[a-z]{2,3} Квантификатор «?» сообщает нам о том, что первое множество [0–9] может встретиться с набором множества [a-z]{2, 3}, а такжеможет и не встретиться.
Также множество [0–9] может встретиться как с множеством[a-z]{2}, так и с [a-z]{3}. Итого мы получаем следующий набор вариантов:96[0..9]*[a..z]*[a..z]*[a..z] = 10 · 263 , где степень 3 – квантификатор {3}[0..9]*[a..z]*[a..z] = 10 · 262 , где 10 – мощность множества [0–9];3[a..z]*[a..z]*[a..z] = 26 ;(2.5)[a..z] * [a..z] = 262 .Вычислив мощности множеств каждого слагаемого, найдем сумму всех результатов каждого из вариантов: 10 · 262 + 10 · 263 + 263 + 262 .3. Группа [0–9]?[a-z]{2,3} Мощность такого выражения равна 262 +26.
Делов том, что слово «ab» служит разделителем между двумя множествами, и его можноне учитывать, так как в перестановках слово «ab» не играет никакой роли.Теперь о том, как распоряжаться нашими результатами от каждой группы.– Результаты мощностей групп, разделенных символом «|», необходимо сложить– В случае, когда группы обособлены скобками «()», результаты мощностей такихгрупп необходимо перемножить.– В случае, когда идет чередование символа «|» и отдельных групп «()», результаты складываются и перемножаются соответственно, приоритетнее операцияумножения.Исходя из представленной методики, получим следующее выражение:(262 ) + (10 · 263 + 10 · 262 + 263 + 262 ) + (262 + 26)(2.6)Но на этом решение не заканчивается.
Дело в том, что мы не учли возможныепересечения множеств, т. е. повторения. В данном примере два раза повторяется множество [a-z]{2} – в первой и во второй группах. Мощность этого множества необходимо вычесть из результата. Таким образом, объединив все замечания, получимокончательный ответ: мощность нашего регулярного выражения равна 201474.Остается главный вопрос – как подобрать алгоритм, учитывающий все пересечения множеств (повторения)?972.9.2Алгоритм вычисления мощности в пересекаемых множествахНайдем количество возможных комбинаций в следующем регулярном выражении –A? B? A? B?. Если бы слагаемые A и B не повторялись, то решением такого выражения было бы (2 · 2 · 2 · 2) − 1 = 15, где 2 – количество состояний (символ может бытьили не быть), вычитаем единицу, так как в контексте практической части задачи неможет быть пустого варианта.В нашем же примере переменные повторяются, т.
е. всего 15 вариантов и минусповторения.ABAB или ABABABAB или ABABABAB или ABAB или ABAB и так далее.Окончательный ответ (2 · 2 · 2 · 2) − (2 · 2) − 1 = 11. Для более сложных выражений найти общее математическое решение по нахождению пересечений такихкомбинаций не удается. Проблемой служит неизвестное поведение роста некоторойфункции повторений таких комбинаций с добавлением новых слагаемых или группчередующихся слагаемых.
Например, A? A? B? A? B? A? B? A? A?, где группа ABAможет встретиться больше 6 раз, каждая из которых разбивается на отдельные повторяющиеся группы.Для более сложных выражений найти общее математическое решение по нахождению пересечений таких комбинаций не удается. Проблемой служит неизвестноеповедение роста некоторой функции повторений таких комбинаций с добавлениемновых слагаемых или групп чередующихся слагаемых.
Например, A? A? B? A? B?A? B? A? A?, где группа ABA может встретиться больше 6 раз, каждая из которыхразбивается на отдельные повторяющиеся группы. Данное ограничение стоит учестьпри реализации алгоритма [104].2.9.3Алгоритм поиска фактора неопределённостиДля решения пересечения множеств в регулярном выражении необходимо вестиотдельный список всех комбинаций, чтобы понять, повторялось ли определенное множество, и, если подобный случай имел место, исключить его.Поскольку поиск эффективного алгоритма сопряжен с поиском практического решения, допускается упрощение общего решения.
Предлагается добавление функции,98устанавливающей факт неопределенности регулярного выражения, что будет предупреждать пользователя о неточной или неэффективной установке шаблона, даваявозможность исправить ошибку. Поскольку случаи, когда под один URL подпадаетнесколько шаблонов, встречаются не часто, а их пересечение происходит еще реже,данное решение имеет законченный практический вид. Таким образом, допустимынекоторые ограничения на регулярное выражение, которые вполне подходят под условия поставленной задачи.Также совместно с другими решениями в реализации проекта BlockSet допустимоприменение предварительной детерминизации. Поскольку каждый блок имеет строго заданное регулярное выражение [101], становится возможным на этапе разработкиинструментария самостоятельно установить мощности множеств регулярных выражений для каждого блока.
Исключение составляет блок типа «string» (строка), имеющийатрибут regexp, с помощью которого задается пользовательское регулярное выражение (мощность которого также придется высчитать с помощью одного из представленных методов). Мощность множества регулярного выражения у каждого блока втаком случае зависит от типа данных блока и его атрибутов. Например, для блока«number» (число) такими атрибутами являются «min» и «max», устанавливающие допустимый числовой отрезок. Так, при = 1 и = 10 мощность множествабудет равна 10.
У блока «float» (число с плавающей запятой) добавляется также атрибут «precision» (точность), устанавливающий число знаков после запятой, что можетмногократно увеличивать число комбинаций. Но несмотря на то что вычисляемое значение вариативно, структура регулярного выражения достаточно детерминирована,чтобы предсказать точную мощность множества в каждом конкретном случае (кроме блока типа «string»). Именно это решение легло в основу методики BlockSet валгоритме выбора локации (динамической страницы).2.10Выводы по второй главеВ данной главе разработан метод декларативного программирования Webприложений на серверной стороне, а также его фундаментальные элементы и их взаимодействие. Предложены базовые сущности языка: модель, локация, набор, блок.Обозначены принципы взаимодействия между сущностями.
Показаны принципы полиморфизма отдельных блоков в зависимости от своих типов. Определен порядокзаписи базовых сущностей методики BlockSet в исходном коде языка BML. Представлен обзор свойств и их значений для основных сущностей: модели, локации, блока99и набора. Проведён подробный обзор типов блоков и их функциональных характеристик. Разработан перечень данных, передаваемых из интерпретатора в шаблонизатори наоборот.100Глава 3Разработка метода комплекснойоценки инструментовимперативной и декларативнойразработки динамическихWeb-узловИсследование качества программного обеспечения – комплексная задача, требующая разработки системы оценивания по ряду критериев.
Подзадачами данной главытакже являются выявление данных критериев и построение на их основе оценочноймодели. Среди критериев оценивания присутствуют элементы оценки как программного кода, так и пользовательского тестирования. В данной главе рассматриваетсяметод, основанный на анализе программного кода и выявляющий объективные показатели, выражающиеся в численных характеристиках [113].Проблеме количественной оценки эффективности языков программирования в целом и качества программного кода в частности посвящены многие труды ученыхсовременников, являющихся основоположниками научных методик в данной области.Стоит отдельно отметить наиболее известные методы: метрика Холстеда [38], метрика Джилба [19], цикломатическая сложность МакКейба [42].
Данные характеристики основаны на количественном подсчете лексем рассматриваемого языка, а такжеоценке сложности графа потока управления. Множество новейших научных иссле-101дований провели Матей Чрепиншек, Томаж Косар, Марьян Мерник. Так, в работе[13] учеными предложен автоматизированный подход к анализу и оценке грамматик языков программирования.
Помимо алгоритмического представления оценки исистематизации метода, они разработали программное обеспечение, позволяющее автоматизировать процесс оценки программного кода, используя заранее подготовленные абстрактные синтаксические деревья на основе предварительно заданных грамматик. Для построения деревьев используется программный комплекс синтаксического и лексического анализа ANTLR (автор профессор Томас Парр [50]. В работе[34] предложены метрики, четко разграничивающие языки общего назначения (англ. general purpose language, GPL) и предметно-специфичные языки (англ. domainspecific language, DSL). Безусловно, фундаментальным трудом, где описаны характеристики DSL и объяснено, в каком случае оправдана его разработка, можно назватьработу Мерника [44].Разрабатываемый в рамках данной диссертационной работы язык BML, безусловно, является предметно-ориентированный, однако большая часть языков в рассматриваемой предметной области (Web-разработка) являются языками общего назначения.
Именно по этой причине основной задачей ставится поиск эффективного методаоценки данного языка с устоявшимися технологиями [95].3.1Разработка обобщённой оценочной моделиРазработка оценочной модели начинается с исследования предметной области,представляющей собой здесь конкурирующие технологии. Предметная область – множество объектов, рассматриваемых в пределах одного рассуждения или научной теории. Далее необходимо разработать методику сравнения и определить набор функционала, который может предоставить технология. Но из-за того, что понятие «функционал» достаточно обширное, его стоит рассматривать на уровне более мелких составляющих.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
