Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.
This post is the implementation of my paper Input Algebras
In my previous posts on inducing faults
and multiple faults I introduced
the evocative patterns and how to combine them using
and. As our expressions
keep growing in complexity, we need a better way to mange them. This post
introduces a language for the suffixes so that we will have an easier time
As before, let us start with importing our required modules.
sympy may not load immediately. Either click on the [run] button
first before you click the [run all] or if you get errors, and the
import seems to not have been executed, try clicking on the [run] button again.
Our language is a simple language of boolean algebra. That is, it is the
language of expressions in the specialization for a nonterminal such as
It is defined by the following grammar.
We need the ability to parse any expressions. So, let us load the parser
Next, we need a data structure to represent the boolean language.
First we represent our literals using
There are two boolean literals. The top and the bottom. The top literal
also (T) essentially indicates that there is no specialization of the base
nonterminal. For e.g.
<A> is a top literal.
Hence, we indicate it by an empty string.
The bottom literal indicates that there are no possible members for this particular nonterminal. For e.g. <A |> indicates that this is empty. We indicate it by the empty symbol |.
Next, we define the standard terms of the boolean algebra.
We then come to the actual representative class. The class is initialized by providing it with a boolean expression.
Now, we need to define how to simplify boolean expressions. For example,
we want to simplify
and(and(f1,f2),f1) to just
and(f1,f2). Since this
is already offered by
sympy we use that.
First we define a procedure that given the parse tree, converts it to a sympy
Next, we define the reverse. Given the
sympy expression, we define a
procedure to convert it to the boolean data-structure.
Finally, we stitch them together.
We now need to come to one of the main reasons for the existence of
this class. In later posts, we will see that we will need to
recreate a given nonterminal given the basic building blocks, and
the boolean expression of the nonterminal. So, what we will do is
to first parse the boolean expression using
BExpr, then use
sympy to simplify (as we have shown above), then unwrap the
sympy one layer at a time, noting the operator used. When we
come to the faults (or their negations) themselves, we return
back from negation with their definitions from the original grammars,
and as we return from each layer, we reconstruct the required
expression from the given nonterminal definitions (or newly built ones)>
get_operator() returns the
op_fst() returns the first operator if the
operator was a negation (and throws exception if it is used
op_fst_snd() returns the first and second
parameters for the outer
We also define two convenience functions.
Next, given a grammar, we need to find all undefined nonterminals that we need to reconstruct. This is done as follows.
Next, we will see how to reconstruct grammars given the building blocks.
reconstruct_rules_from_bexpr() is a recursive procedure that will take a
given key, the corresponding refinement in terms of a
BExpr() instance, the
grammar containing the nonterminals, and it will attempt to reconstruct the
key definition from the given nonterminals,
We now define the complete reconstruction