CFG Checker

cfgc is a simple command-line tool built with Rust, that allows to check context-free grammars.

Installation

1. Install Rust
2. Run cargo install cfgc
3. Check installation with cfgc --help

Documentation

Here are the basics of cfgc.

cfgc check

cfgc check can be used to compare two grammars for equivalence using different strategies.

By default, the command generates and compares the two languages of the grammars, containing all strings up to a maximum number of tokens. As a result, it returns all strings that are accepted by each grammar, but not both.

cfgc justify

cfgc justify can be used to provide examples that justify the existence of each production rule in a grammar.

By default, the command generates all possible mutations of the original grammar, obtained by choosing one production rule and removing it. Then, it compares the original grammar with each mutation. As a result, it returns all the strings that cannot be generated without the removed production rule.

.cfg format

All grammars in cfgc must be specified in the .cfg minimalistic format.

Here is an example for a grammar that defines sequences of operations over a stack:

P := [ B ] | [ ];
B := push _ B _ pop _ B
   | push _ B _ pop
   | push _ pop _ B
   | push _ B
   | push _ pop
   | push;

Tokens

A grammar contains Tokens, which are either Variables (capitalized) or Literals (non-capitalized).

In the example, P and B are Variables; [, ], push, and pop are four different Literals.

Note: Tokens are assumed to be separated by white-spaces . You can represent white-spaces in your grammar by other symbols (e.g. _).

Definitions

A grammar contains a set of Definitions, of the form X := Y;, where X is a Variable and Y is a set of production Rules.

In the example, P := [ B ] | [ ] and B := push B pop B | ... | push; are Definitions.

Note: every Definition must end with the symbol ;.

Production Rules

On the right side of a Definition, you can specify multiple production Rules separated by | and any amount of white spaces or newlines.

In the example, [ B ], [ ], push B pop B, push B pop, ..., push are all Rules.

Note: epsilon-production are not supported yet (at least not explicitly).

More examples

S := a S 
   | a;

S := a S b 
   | a b;

S := ( S )
   | S S 
   | ( );

Expr := Num
      | Expr + Expr
      | Expr * Expr;
      
Num := 0
     | 1
     | 2;