The article describes the process of developing an automated tool to determine the evaluation order in the expression on C programming language and describe the faults made by a student in this task. The main part of this tool is based on the SWRL rule set, which can be divided into several di erent tasks: calculation of the evaluation order of expression based on constructing abstract syntax tree of expression, determine contradictions with the partial student's evaluation order, and describing fault reasons.
Developing basic programming skills is a high-demand area of teaching that is challenging both for teachers and students that makes it a popular research area. Introductory programming courses are a good example of a situation where students have to learn a signi cant number of new concepts but these concepts are formal and well-de ned. This makes basic programming courses a good area to test di erent forms of concept-based education methods, including using ontologies.
Ontologies is commonly used to representing mathematical knowledge as
shown in [
In order to facilitate the comprehension of concepts, ontologies should model the usage of these concepts in the typical domain tasks. This allows calculating the correct answer for a question and, with the student's response converted to ? The reported study was funded by RFBR, project number 20-07-00764.
Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). the ontology, determining the exact fault reason that allows explanatory feedback on mistakes. Such ontologies would have an advantage over procedural task-solving systems which have limited capability for explanatory feedback. However, the suitability of current ontological reasoners for solving problemoriented tasks needs to be researched rst. In this study, we aimed at creating ontology to determine the evaluation order of a C-language expression and detect fault reasons in student-supplied evaluation order using SWRL rules. The studied concepts were operators, their precedence and associativity, sequence points, and order of evaluation.
The order of evaluation in C programming language is a partial order. Because of sequenced-before relation, evaluation order isn't fully de ned by the abstract syntax tree of the expression but can be expressed as a directed acyclic graph where child nodes must be evaluated before the parent nodes. a + b c < f (d ? e jj f : j + k; l) (1)
So, for the questions about evaluation order, the developed ontology should determine the sequenced-before relation as a direct acyclic graph, compare the student's evaluation order marks with the graph to determine fault reasons, and provide information necessary to generate explanatory feedback. 2
The ontology model receives an expression split into tokens. For each token, its position in the expression and the text of the token are set. Each input token is representing by several individuals in ontology, one for each step of constructing abstract syntax tree (AST). First, the ontology builds the AST for the given expression. This takes place inside the ontology that records the state of the expression at each step, marking which operators are evaluated and which evaluation results have already been used by the other operators. Using SWRL rules for building AST di ers from regular imperative algorithms and supplies the later fault-reason determining stage with the necessary information.
A tree node has data properties arity, precedence, associativity, prefix_postfix (for unary operators) lled at initial step of constructing AST using information from text and neighboring tokens. At each step of constructing AST, a set of SWRL rules nds an operator that can be evaluated and generates the tree copy for the next step, connecting the evaluated operator with its operands using property has_operand and changing markers of evaluated and used operators.
To create the evaluation-order graph based on AST, the rules determining sequenced-before relations are applied, accounting for the operators guaranteeing a certain order of evaluation for their operands like binary logical operators, the ternary operator, and the comma operator.
After the end of this stage, AST and the evaluation order graph are copied to a special step that will be used to perform further calculations while the steps for constructing the tree remain to provide information for generating a detailed explanation of found errors. 3
For fault reason determining, students must provide their responses, assigning numbers to the operators in their evaluation order. As the evaluation order is a partial order, many expressions allow several correct answers. The nodes lacking student's order marks are assumed to be evaluated after all marked nodes so they are assigned large numbers corresponding to their positions in the graph. A student makes a mistake by assigning a smaller number to a parent node of the evaluation order graph than to its child node both for the edges representing operands and sequenced-before relations.
The developed ontology provides information about all faults in the given student's answer, including fault reasons and supplementary information for generating the explanation message using a natural-language template. All possible faults are split into two categories: calculating the result of an operator before its operand (for example, mistakes in operator precedence or associativity) and wrong evaluation order of two operators caused by sequence points created by another operator (e.g. trying to evaluate the right operand of a logical and operator before nishing evaluating its left operand). Errors is stored as object properties between two error nodes named like student_error_strict_operands_order or student_error_more_priority_left, etc. In the following examples, the $ followed by a number shows the position of the preceding operator in the student's evaluation order. For example, formula 2 demonstrates a simple mistake caused by the student ignoring associativity. The mistake message generated for it will be: "Operator + on pos 4 cannot be evaluated before operator + on pos 2 because operator + has left associativity".
a + $2 b + $1 c (2)
Formula 3 shows a more complex mistake involving three operators. The mistake message for it will be: "Operator + on pos 6 that belongs to the right operand of operator jj on pos 4 cannot be evaluated before its left operand, including operator * on pos 2." a $2 b jj$3 c + $1 d (3)
So the developed ontology can detect fault reason for mistakes in operators precedence, associativity, and sequence points during evaluating an expression, providing the necessary information for explanatory feedback including the fault reason and operator nodes.
The ontology was tested using Java unit testing framework; constructing expression AST (144 tests), evaluation order tree (10 tests), and determining fault reasons (20 tests, including mistake combination) were tested separately. The ontology and testing system is available on Github1. 4
We developed ontology able to solve determine the evaluation order of a Clanguage expression and fault reasons in a student's answer with the potential to generate explanatory feedback including correctly processing multiple errors. It also supports a subset of C++ language. The results prove that ontological reasoners are capable to process expressions and determine fault reasons so they can be used as a basis of the testing system generating questions, solving them, and generating explanatory feedback for students.
The developed ontology di ers from other ontologies used to generate and
grade questions [
The further development of the ontology includes fully supporting C++ expressions containing complex operators and operands like template function calls and initializer lists and supporting other programming languages like Python, adapting the ontology to the chosen language by tagging its rules. The ontology also will be enhanced to support other expression-related exercises, including determining subexpression data types for statically-typed languages. To use the developed ontology in the learning process, we will develop the core of the testing system and question-generation routines.
The developed testing system will be modular and able to work with other domains provided that the relevant ontologies and question-generation routines are implemented. Our research group is open for collaboration with researchers interested in developing support for their domains.