This is a Python3 implementation of the CYK Parsing Algorithm.
The goal of the algorithm is to find out if a string is generated or not by a Context-Free Grammar in Chomsky Normal Form. Some variants of the algorithm exist, like the probabilistic version or the version that takes in input CFG not in CNF. This implementation simulates the standard version.
In this repository there 2 kind of files:
- CYKAlgorithm: it implements the algorithm, using Python3.
- Grammars: .txt files containing three default CFG.
If someone would like to test different string, from other grammars, it is necessary to create new .txt files to define these new grammars. When defining the new grammar, the format required to make the algorithm works properly can be infered by the files provided in this repo.
- New grammars MUST BE in CNF.
- Terminals MUST BE declared in the same row, separating each other with just one space.
- Variables MUST BE declared in the same row, separating each other with just one space.
- Production MUST BE declared one per row, separating each symbol with just one space (except from "->").
The algorithm creates a triangular table and fill it up with some variables, starting from the string we want to test. Once it reaches the top of the table, if exist a production that begins with the start symbol of the grammar, at that level, it means that the string can be generated by the grammar. For the chosen grammar, this implementation tests a string that belongs to the language generated from the grammar, and then tests a string that does not belong to it.
More detailed explanations of the algorithm can be found all around the Web.
This implementation includes a method to print the table used step by step, by the algorithm, and a method to print at least, on parsing tree of the input string.