ICSI-409-CNF-CYK

This repository contains an implementation of the CYK (Cocke-Younger-Kasami) Algorithm for ICSI 409 Fall 2024.

Group 1 consists of:

• Mendel M. - Part 1: Grammars
• Wyatt B. - Part 2: Implementation
• Thomas D. - Part 2 : Implementation
• Kevin M. - Part 2: Implementation
• Ryan M. - Part 3: Documentation
• Sharie R. - Part 3: Documentation

Task Descriptions

1. Grammars

• 1 member will produce the grammars from the given language and convert it to the CNF format on paper: Members not comfortable with coding can attempt this section of the homework. 40%. – This Question is 40%, Question 2 is 40% Question 3 is 20%

2. Implementation

• 2-3 members will work on the implementation and preliminary testing. 60%. --This question is 60%, Question 1 is 20% Question 3 is 20%.

3. Documentation

• 2-3 members will work on the testing and documentation (your report and readme file) – (This must still be done and if a member is doesn’t participate, you still provide documentation, but they get no grade for the HW). 50%. - This question is 50%, Question 2 is 30% and Question 1 is 20%

Running the Program

Dependencies

• Java version 21+
• [Optional] Maven 3.8.x

Make sure to clone the repository using your preferred method.

Using a Terminal

1. Change to java Directory

   cd cyk/src/main/java

2. Compile

   javac -d out group1/CYKAlgorithm.java group1/Grammar.java

3. Execute

   java -cp out group1.CYKAlgorithm

4. Follow Commandline Prompts

   Follow the prompts in the terminal to enter a grammar. Next, enter a string to see if it is in the language generated by the grammar.

Using Maven in a Terminal

1. Change to cyk Directory

   cd cyk

2. Build and Execute

   mvn exec:java

3. Follow Commandline Prompts

   Follow the prompts in the terminal to enter a grammar. Next, enter a string to see if it is in the language generated by the grammar.

Running Unit Tests with Maven

1. Change to cyk Directory

   cd cyk

2. Build and Execute

   mvn test

Usage Notes

• E represents epsilon, the empty string.
• Nonterminals may be more than one character, such as S0. In order to differentiate between nonterminals, use spaces.
• Example grammar:

S0 -> X( Z | S S | E
S -> X( Z | S S
Z -> S X) | )
X( -> (
X) -> )