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.
System ImportsThese are available from Pyodide, but you may wish to make sure that they are installed if you are attempting to run the program directly on the machine.
Available PackagesThese are packages that refer either to my previous posts or to pure python packages that I have compiled, and is available in the below locations. As before, install them if you need to run the program directly on the machine. To install, simply download the wheel file (`pkg.whl`) and install using `pip install pkg.whl`.
- earleyparser-0.0.1-py2.py3-none-any.whl from "Earley Parser".
- hdd-0.0.1-py2.py3-none-any.whl from "Hierarchical Delta Debugging".
- simplefuzzer-0.0.1-py2.py3-none-any.whl from "The simplest grammar fuzzer in the world".
- ddset-0.0.1-py2.py3-none-any.whl from "Simple DDSet".
- gatleastsinglefault-0.0.1-py2.py3-none-any.whl from "Specializing Context-Free Grammars for Inducing Faults".
- gmultiplefaults-0.0.1-py2.py3-none-any.whl from "Specializing Context-Free Grammars for Inducing Multiple Faults".
The imported 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.
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 also clarify a few defs
We now define the complete reconstruction
The runnable Python source for this notebook is available here.
The installable python wheel
gfaultexpressions is available here.