Cocke–Younger–Kasami Algorithm Parser

This project shows the implementation of CYK algorithm in Java. It is a bottom-up parsing algorithm using dynamic programming paradigm with O(n^3.|G|) time complexity where n is the length of the string and G is the size of the Chomsky Normal Form (CNF) grammars. We also provide a GUI for the visualization.

Requirement

Java 7 (or later)
(Optional) Eclipse IDE

Update rules

The rules are in rules.txt. They are written in Context Free Grammar (CFG) standard form.

Non-Terminal production (left and right: starts with upper case)

ModVPlace -> ModV PrepPlace

Terminal production (left: starts with upper case, right: lower case)

PrepPlace -> in

Run the program

rules.txt must be placed in the same directory as parser.jar
Run the following command

java -jar parser.jar

Type your sentence and press Cek button.

Develop

If you are interested using this code, you can fork and clone this repository and use Eclipse IDE to import the project.

Authors

Genta Indra Winata
Sonny Lazuardi

Note

Natural Language Processing Assignment in Institut Teknologi Bandung