/Context-Free-Grammar-Simplification

This C++ program takes a context free grammar (CFG) as input and performs several steps to simplify the grammar by removing unnecessary productions.

Primary LanguageC++

Context Free Grammar Simplification

This C++ program takes a context free grammar (CFG) as input and performs several steps to simplify the grammar by removing unnecessary productions.

Overview

This program takes a context free grammar as input from the user and applies a series of transformations to simplify the grammar.

The simplified grammar generates the same language as the original grammar but removes unnecessary symbols and productions.

Specifically, it removes:

  • Null productions
  • Unit productions
  • Unreachable symbols
  • Non-generative symbols

This allows creation of a minimal grammar without impacting the language generated.

Input

The user is prompted to enter:

  • Number of productions
  • The productions in the format: A -> α

where A is a nonterminal and α is a string of terminals and/or nonterminals.

Processing Steps

The program processes the input grammar in four main steps:

Remove Null Productions

Any productions of the form A -> λ, where λ represents the empty string, are removed.

For other productions containing null symbols, the null symbols are recursively replaced by ε.

For example, if the grammar contains:

A -> BC

B -> λ

It would be transformed to:

A -> C

By removing B -> λ and substituting ε for B in the first production.

Remove Unit Productions

Unit productions are those where a nonterminal produces a single terminal or nonterminal.

For example:

A -> B

B -> a

The unit production A -> B is removed and replaced with A -> a.

This step is done by analyzing the productions and substituting the right hand side of unit productions until no more unit productions exist.

Remove Unreachable Productions

Any non-start nonterminal that does not appear on the right hand side of any production is considered unreachable.

These symbols and their productions are removed from the grammar as they are unnecessary.

Remove Non-generative Productions

If a nonterminal only produces ε, it is non-generative.

The program finds these nonterminals by analyzing the productions.

Any non-generative nonterminals and their productions are removed. All instances of them in other productions are also removed.

This continues recursively until no non-generative nonterminals remain.

Output

After applying the above simplifications, the program prints out the transformed grammar with:

  • No null productions
  • No unit productions
  • No unreachable symbols
  • No non-generative symbols

Code Structure

The code is structured into logical sections with helper functions to improve readability.

Main Function

  • Handles user input and output
  • Calls simplification functions

Remove Null Productions

  • k tracks null symbols
  • Loop through productions
    • If production is null, skip it
    • Else recursively delete null symbols by substitution

Remove Unit Productions

  • Loop through productions
    • If unit production found
      • Substitute unit symbol with its production
      • Delete unit production
  • Repeat until no unit productions left

Remove Unreachable Productions

  • Loop through non-start productions

    • Check if symbol appears in other productions
    • If not, remove production and symbol

Remove Non-generative Productions

  • Loop through productions
    • If symbol only produces ε
      • Track symbol
      • Remove its productions
    • Remove instances of symbol from all productions
  • Repeat until no changes

Helper Functions

  • checkkol() - Validates final grammar
  • guidence() - Provides hints during game

Data Structures

  • prod[][] - Input productions
  • nullprod[][] - Simplified productions
  • a[] - Tracks key symbols

Compilation and Usage

To use the program:

  1. Compile grammar.cpp
  2. Run the compiled executable
  3. Follow the prompts to enter grammar
  4. View simplified result

Requires a C++ compiler. Developed using GCC on Linux.

Example Run

User input in bold.

Enter number of productions: 4

Enter productions:

A -> BC

B -> λ

C -> aD

D -> b

The simplified grammar is:

A -> aD

C -> aD

D -> b

Applications

  • Grammar analysis
  • Compiler construction
  • Programming language implementation
  • Natural language processing

Limitations and Future Work

  • Only handles context free grammars
  • Does not minimize number of productions
  • Could expand to handle context sensitive grammars
  • Add visualization of grammar
  • Develop full featured parsing system

Conclusion

This program demonstrates simplification of context free grammars through a series of transformations. It removes unnecessary symbols and productions while preserving the language generated by the grammar. The simplified result serves as input for further analysis and processing.