Fault Expressions for Specializing Context-Free Grammars

Contents

1. Artifacts

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.

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.