Skip to content

Latest commit

 

History

History
104 lines (67 loc) · 2.53 KB

README.md

File metadata and controls

104 lines (67 loc) · 2.53 KB
Raw

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%
  1. 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%.
  1. 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

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) -> )