# Fault Expressions for Specializing Context-Free Grammars

## Contents

**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
managing them.

As before, let us start with importing our required modules.

## System Imports

These 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.- sympy

## Available Packages

These 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

**Note** `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 `sympy`

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 `<A and(f1,f2)>`

It is defined by the following grammar.

Next, we need a data structure to represent the boolean language.
First we represent our literals using `LitB`

class.

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. `or(.,.)`

, `and(.,.)`

and `neg(.)`

We then come to the actual representative class. The class is initialized by providing it with a boolean expression.

Using it.

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
expression.

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.

Using it.

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)>

The `get_operator()`

returns the
outer operator, `op_fst()`

returns the first operator if the
operator was a negation (and throws exception if it is used
otherwise, and `op_fst_snd()`

returns the first and second
parameters for the outer `and`

or `or`

.

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.

Usage.

Next, we will see how to reconstruct grammars given the building blocks.
Our `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,

Reconstructions

We also clarify a few defs

Using

We now define the complete reconstruction

Usage

## Artifacts

The runnable Python source for this notebook is available here.

The installable python wheel `gfaultexpressions`

is available here.