CYK: Cocke–Younger–Kasami algorithm in Golang

What is this CYK Algoritgm

In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami. It employs bottom-up parsing and dynamic programming.

The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be transformed to a CNF grammar expressing the same language

Installation and Usage

Install

go get github.com/kkdai/cyk

Usage

Following is sample code to implement a epsilon-NFA automata diagram as follow:

package main

import (
    "github.com/kkdai/cyk"
)

func main() {
	cyk := NewCYK("S")
	cyk.InputGrammar("S", "AB")
	cyk.InputGrammar("A", "BC")
	cyk.InputGrammar("B", "AC")
	cyk.InputGrammar("A", "a")
	cyk.InputGrammar("B", "b")
	cyk.InputGrammar("C", "a")
	cyk.InputGrammar("C", "b")

	//Should be false, fianl result is {A}
	result := cyk.Eval("ababa")
	fmt.Println("Result:", result)
	cyk.PrintResult()
}

Inspired By

• Coursera: Automata
• CYK: Wiki
• CYK: pdf
• CYK: Introduction PDF
• CYK演算法

Project52

It is one of my project 52.

License

This package is licensed under MIT license. See LICENSE for details.