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.

   Note: To use a .txt file to load a grammar, place the file in cyk/src/main/java. Then type the full file name when selecting the file: Reading grammar from file: your_file.txt

Using Maven in a Terminal

1. Change to cyk Directory

   cd cyk

2. Build and Execute

   mvn clean compile exec:java

   May be broken into multiple commands if desired.

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.

   Note: To use a .txt file to load a grammar, place the file in cyk/src/main/java. Then type the full file name when selecting the file: Reading grammar from file: your_file.txt

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.

• File may have comments using the prefix #.

• Example grammar balanced_parentheses.txt:

  # Grammar for Balanced Parentheses in CNF
  S0 -> X( Z | S S | E
  S -> X( Z | S S
  Z -> S X) | )
  X( -> (
  X) -> )