BUPT 2022 Spring Formal Languages and Automata Course Lab2

The simplification of context-free grammars is not a simple problem, and there are many corner cases to consider, such as various circular derivation relationships. I write about 500 lines of this program, considering the vast majority of cases, and it works correctly under the test cases I constructed myself.

At first I thought about using Floyd–Warshall algorithm to implement transitive closures, but found that it was not feasible. If you think more about it, the whole process is completely recursive, in fact, the only algorithm that needs to be used is to hash the string represented by the grammar as a vertex on the graph, and then use a depth-first search. Yes, the problem of this lab only requires depth-first search, no other advanced algorithms are needed at all.

Compile & Run:

g++ main.cpp -std=c++14 -fexec-charset=GBK -o test

./test

TODO:

  • Review the CFG Simplification
  • Think how to use graph theory to solve it
  • Try to remove useless symbol
  • DFS epsilon function can’t return
  • Remove unit production
  • Complexity Analysis

Reference:

GitHub

View Github