СПОСОБ АНАЛИЗА ФОРМУЛЫ НА ПРАВИЛЬНОЕ ПОСТРОЕНИЕ

THE METHOD OF ANALYSIS OF THE FORMULA ON THE CORRECT CONSTRUCTION OF

Seseg Bazaron

ph.D., Associate Professor, East Siberia state university of technology and management,

Russia, Republic of Buryatia, Ulan-Ude

Maria Frantenko

Student, East Siberia state university of technology and management,

Russia, Republic of Buryatia, Ulan-Ude

АННОТАЦИЯ

Работа посвящена оцениванию результатов решения типовых задач в системе автоматизированного тестирования. Имеется решение задачи в виде последовательности формул. Предлагается способ распознавания таких формул. В статье рассматривается алгоритм определения правильно построенной формулы.

ABSTRACT

The work is dedicated to evaluating the results of the solution of typical problems in the system of automated testing. There is a solution in the form of a sequence of formulas. A method of recognition of such formulas. In the article the algorithm for determining the well-formed formula.

Ключевые слова: Тестовые задания; типовая задача; правильно построенная формула; обратная польская запись; нотация Бэкуса Наура.

Keywords: Test items; typical task; well-formed formula; RPN; Backus-Naur notation.

Введение. В условиях современного информационного общества автоматизированное тестирование является одним из инструментов для контроля качества обучения. В современных системах автоматизированного тестирования используются различные типы вопросов, в частности вопросы позволяющие оценивать умение решать типовые задачи, путем ввода в поле ответа конечного результата поставленной задачи. Однако для одного и того же класса задач существуют различные методы решения задач данного класса. Поэтому возникает необходимость оценивать умение применять конкретные методы решения поставленной задачи, т. е. оценивать ход решения задачи. В работе рассматриваются задания, которые требуют написание последовательности формул решения задачи [1].

Основная суть решения задачи заключается в том, что любая задача, решаемая студентом, относится к какой-либо формальной системе или формальной теории, лежащей в плоскости изучаемого предмета. Это означает, что формулы, создаваемые студентом должны принадлежать этой формальной системе. Формулы будут принадлежать формальной системе в том и только в том случае, если они построены по синтаксическим правилам этой формальной системы в нашем случае математической логики. Из этого следует, что необходимо решить три задачи:

1) найти способ представления синтаксических правил;

2) разработать способ преобразования формулы в обратную польскую запись;

3) разработать способ лексического и синтаксического анализа выражения.

Способ представления синтаксических правил. БНФ-конструкция определяет конечное число символов (нетерминалов). Кроме того, она определяет правила замены символа на какую-то последовательность букв (терминалов) и символов. Для получения БНФ-конструкции необходимо выполнить несколько этапов. На первом этапе имеется один символ (символы обычно заключаются в угловые скобки, а их название не несёт никакой информации), после он заменяется на некоторую последовательность букв и символов, согласно одному из правил. Затем процесс повторяется (на каждом шаге один из символов заменяется на последовательность, согласно правилу). В конечном итоге, получается цепочка, состоящая из букв (и не содержащая символов). Получается, что конечная цепочка может быть выведена из первоначального символа [2].

БНФ-конструкция состоит из нескольких предложений вида:

<определяемый символ>::=<посл.1>|<посл.2>|...|<посл.n>, описывающих правила. Такое правило, означает, что символ <определяемый символ> может заменяться на одну из последовательностей <посл.i>. Знак определения, обычно выглядит как ::=, но возможны и другие варианты.

Представим правила построения логических формул в виде БНФ-конструкции:

<ИЗ>  ::= 0 | 1 | И | Л | T | F ;

<ПБ>  ::= A | B | C |…| Z ;

<СБ>  ::= a | b | c |…| z ;

<УО>::= ;

<О>    ::=

<КВ>  ::= <СБ> | <СБ>;

<Ион>::= <ПБ>(<СБ>) | <ПБ>(<СБ> {, <СБ>})

<ОП>::= <ПБ>|<ИЗ>|<Ион>;

<АФ>::=[<ОП>]<УО> | [<ОП>] [<ОП>]<О> | <Ион><КВ>;

<СФ>::=[<АФ>|<СФ>] <УО>|

[<ОП>|<АФ>|<СФ>] [<ОП>|<АФ>|<СФ>]<О> | [<АФ>|<СФ>]<КВ>.

где:

ИЗ – истинностное значение;

ПБ – прописная буква;

СБ – строчная буква;

УО – унарная операция;

О – бинарная операция;

КВ – кванторы;

Ион – ионы, имеющие вид A(-), B(-,-) и т. д.;

ОП – операнд;

АФ – атомарная формула;

СФ – составная формула.

Конструкции типа <ИЗ>, <ПБ>, <СБ>, <УО>, <О>, <КВ>, <Ион> являются элементарными. Остальные конструкции назовем сложными, которые и образуют синтаксические правила построения логических формул.

Способ преобразования формулы в обратную польскую запись. Обратная польская нотация – это форма записи математических выражений, в которой операторы расположены после своих операндов. Существует два метода построения обратной польской записи.

Рассмотрим первый метод. Пусть задано логическое выражение вида:

(A∨B)∧(C∨D)⊃E                                        (1)

Это выражение нужно представить в виде бинарного дерева, состоящего из узлов (вершин) – записей вида G=(data, left, right), где data=(oper, list) – знаки операций и операнды соответственно, входящие в выражение, left, right – ссылки на узлы, являющиеся потомками данного узла. Узел left называется левым потомком дерева, а узел right – правым потомком. Построение начинается с корня, в качестве которого выбирается операция, выполняющаяся последней в выражении. Порядок выполнения логических операций представлен в таблице 1. Дерево выражения (1) показано на рисунке 1.

Затем необходимо совершить обход дерева G=(data, left, right), под которым будет пониматься формирование цепочки символов S из узлов data.

Таблица 1.

Порядок выполнения логических операций

Опишем алгоритм обхода дерева, который начинается с потомка left, а затем по – right:

0)  в пустую цепочку S записать самый левый узел типа list потомка left и перейти на ШАГ 2;

1)  в S добавить левый узел типа list∉S рассматриваемого потомка;

2)  найти узел типа oper, смежный последнему символу list∈S;

3)  если найденный узел oper не корень, то добавить в S узел list∉S, смежный oper (если он есть) и сам узел oper; иначе перейти на ШАГ 8;

4)  если в рассматриваемом потомке есть узлы типа list∉S, то перейти на ШАГ 1;

5)  найти узел типа oper∉S, смежный последнему символу oper∈S;

6)  если найденный узел не корень дерева G, то добавить его в S и перейти на ШАГ 5;

7)  если найденный на 5-ом шаге узел oper является корнем дерева G, то провести обход дерева по потомку right, начиная с ШАГА 1;

8)  добавить корень дерева G в S.

В результате работы алгоритма получим обратную польскую запись математического выражения.

Рисунок 1. Представление исходного выражения в виде дерева

В результате обхода дерева, приведенного на рисунке 1, по описанному выше алгоритму выражение (1) преобразуется к следующему виду:

AB∨CD∨∧E⊃                                                      (2)

Теперь рассмотрим второй метод записи формулы f=(f_i) в обратную польскую запись S [3]. При построении обратной польской записи вторым методом, необходимо просмотреть каждый символ формулы f и переписать их по правилам записанным ниже:

1)  если выражение f просмотрено полностью, то перейти на ШАГ 7, иначе выбрать очередной символ в f­_i и перейти на ШАГ 2;

2)  если просматриваемый символ f­_i – буква, истинностное значение или ион, то f­_i записать в строку S и перейти на ШАГ 1, иначе – на ШАГ 3;

3)  если f­_i – открывающаяся скобка, то записать f­_i в стек и перейти на ШАГ 1, иначе – на ШАГ 4;

4)  если f­_i – операция, а стек пуст или последний символ стека открывающаяся скобка, то f­_i записать в стек и перейти на ШАГ 1, иначе – на ШАГ 5;

5)  если f­_i – операция и последний символ стека операция, то необходимо определить приоритет этих двух операций, иначе перейти на ШАГ 6;

a)  если последний символ стека имеет меньший приоритет чем f­_i, то f­_i записать в стек и перейти на ШАГ 1, иначе – на ШАГ б;

b)  если последний символ стека более приоритетный, чем f­_i, то последний символ стека записать в S, а f­_i записать в стек вместо последнего символа стека и перейти на ШАГ а;

6)  если f­_i – закрывающаяся скобка, то все символы стека до открывающейся скобки переписать в строку S по правилу LIFO, скобки уничтожить и вернуться на ШАГ 1;

7)  все символы, находящиеся в стеке, переписать в строку S по правилу LIFO.

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

Способ лексического анализа выражения. При помощи разработанной БНФ-конструкции необходимо провести лексический анализ цепочки S по следующему алгоритму:

1.  Выделение в S элементарных конструкций. Все символы цепочки S проверяются на принадлежность их элементарным конструкциям. Если символы, входящие в S не принадлежат элементарным конструкциям, то выражение f построено не правильно.

2.  Преобразование цепочки S в БНФ-конструкцию. Символы цепочки S заменяются соответствующими обозначениями элементарных конструкций.

Пример: Выделим в выражении (2) элементарные конструкции. В результате получим, что символы A, B, C, D принадлежат конструкции <ПБ>, а символы ∧, ∨, ⊃ – конструкции <О>. Затем преобразуем выражение (2) в БНФ-конструкцию. В результате получим цепочку BNF:

<ПБ><ПБ><О><ПБ><ПБ><О><О><ПБ><О>           (3)

Следующим этапом анализа является проверка полученной конструкции по синтаксическим правилам.

Способ синтаксического анализа выражения. Для проведения синтаксического анализа преобразуем сложные БНФ-конструкции в алгоритм Маркова, т.е. в правила подстановки следующего вида:

1)  <ПБ>→ <ОП>

2)  <ИЗ> →ОП>

3)  <Ион> → <ОП>

4)  <ОП><УО> → <АФ>

5)  <ОП><ОП><О> → <АФ>

6)  <Ион><КВ> → <АФ>

7)  <АФ><УО> → <СФ>

8)  <СФ><УО> → <СФ>

9)  <ОП><АФ><О> → <СФ>

10)  <ОП><СФ><О> → <СФ>

11)  <АФ><ОП><О> → <СФ>

12)  <АФ><АФ><О> → <СФ>

13)  <АФ><СФ><О> → <СФ>

14)  <СФ><ОП><О> → <СФ>

15)  <СФ><АФ><О> → <СФ>

16)  <СФ><СФ><О> → <СФ>

17)  <АФ><КВ> → <СФ>

18)  <СФ><КВ> → <СФ>

Алгоритм Маркова работает следующим образом: на каждом шаге применяется правило подстановки с минимально возможным номером. Алгоритм заканчивает работу либо после принятия заключительного правила, либо при отсутствии применимых правил. В описанном алгоритме нет заключительных правил.

Пример:

Рассмотрим работу Алгоритма Маркова на примере выражения (3):

<ПБ><ПБ><О><ПБ><ПБ><О><О><ПБ><О>

1. <ОП><ПБ><О><ПБ><ПБ><О><О><ПБ><О>               1) правило 1;
2. <ОП><ОП><О><ПБ><ПБ><О><О><ПБ><О>              2) правило 1;
3. <ОП><ОП><О><ОП><ПБ><О><О><ПБ><О>             3) правило 1;
4. <ОП><ОП><О><ОП><ОП><О><О><ПБ><О>             4) правило 1;
5. <ОП><ОП><О><ОП><ОП><О><О><ОП><О>            5) правило 1;
6. <АФ><ОП><ОП><О><О><ОП><О>                             6) правило 5;
7. <АФ><АФ><О><ОП><О>                                               7) правило 5;
8. <СФ><ОП><О>                                                               8) правило 12;
9. <СФ>                                                                                  9) правило 14.

Так как после синтаксического анализа выражение (1) преобразовалось в <СФ>, то можно сделать вывод, что формула записана корректно.

Заключение. В итоге работы был разработан алгоритм определения правильно построенной формулы. Указанный алгоритм позволяет выявить правильно построенные формулы в ответе испытуемого. Неправильно построенные формулы в дальнейшем планируется анализировать на синтаксические ошибки.

Список литературы:

1. Базарон С.А., Рукавичников А.В. Способ составления спецификации предметной области дисциплины на основе онтологического подхода // Вопросы кибербезопасности: науч.-прак. журнал. – М: ЗАО «НПО «Эшелон», 2014. – № 5 (8). – С. 52–58.
2. Мартыненко Б.К. Регулярные языки и КС-грамматики // Компьютерные инструменты в образовании. – 2012. – № 1. С. 14–20.
3. Расулов В.Е., Рахимова Ю.М. Алгоритм преобразования арифметических выражений в обратную польскую запись // Новые технологии – нефтегазовому региону материалы Международной научно-практической конференции. 2016. С. 23–25.