cfg-simplifier

cfg-simplifier is a Context-Free Grammar (GFC) simplification and normalization tool.

Introduction

A Context-Free Grammar (CFG) is a mathematical formalism belonging to the study of formal languages, used to describe context-free languages, which are higher up in the Chomsky with regard to so-called Regular Grammars. Formally, we have a GCF as a structure $G = \lang V, \Sigma, S, P \rangle $, where

• $ V $ is a set of symbols called variables;
• $ \Sigma $ is a set of symbols called terminals;
• $ S $ is the initial variable that generates the language;
• $ P $ is a set of production rules of the form $ A \rightarrow \alpha $, with $ A \in V $ and $ \alpha \in (V \cup \Sigma )^{\ast} $.

Context-Free Grammar (CFG) is primarily applied in Computer Science, such as in defining the structure of a programming language or even in compiler design, especially in parsing, as well as in natural language processing and formal language definitions.

Tip

See docs/references to more details.

The "problem"

Context-Free Grammars are widely used to describe the syntactic structure of languages. However, as these grammars become more complex, the process of analysis and manipulation becomes more difficult and prone to errors. Furthermore, many other applications require the grammar to be in a simplified or normalized form. Performing these simplifications manually ends up being a laborious process, prone to inconsistencies, and theoretically delicate, as each transformation must preserve the original language.

The cfg-simplifier was developed to act as a tool capable of automatically simplifying and normalizing CFGs, applying formal algorithms to eliminate $\lambda$ productions, unitary productions, useless and inaccessible symbols.

Features

Grammar simplification

• $ \lambda $-production removal
• Unit production removal
• Useless symbol removal
• Substitution
• Right recursion

Grammar normalization

• Chomsky Normal Form
• Greibach Normal Form

Input files

The cfg-simplifier accepts two types of grammar definition files:

1. Compact (example1.txt):

   # docs/example1.txt
   S -> aA | B | BC
   A -> AB | b
   B -> CA | bAc | &
   C -> a | AB | c | &

   This format is more compact and requires less detail, as much of the grammar is inferred automatically.

2. Extended example2.txt:

   [variaveis]
   S
   A
   B
   C
   
   [terminais]
   a
   b
   c
   
   [inicial]
   S
   
   [regras]
   S -> aA | B | BC
   A -> AB | b
   B -> CA | bAc | &
   C -> a | AB | c | &

   This format is more detailed and explicit, ideal for cases where you want to control every component of the grammar.

Authors and acknowledgments

This project was developed by the following students from the Computer Science course at the Federal University of Rio Grande do Norte:

• Carolina Nunes de Carvalho (gitlab.com/luanZd)
• Diego Luan de Souza Tavares (gitlab.com/jujubinharol)
• José Carlos da Paz Silva (gitlab.com/carlos-paz12)
• Leandro Andrade (gitlab.com/leandroaa01)
• Mariana Emerenciano Miranda ()
• Yuri Maximiliano Brasileiro Santos (gitlab.com/BrasileiroYuri)

---

© Departamento de Informática e Matemática Aplicada (DIMAp) - 2025