CYK algorithm in Golang
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
.travis.yml
README.md
cyk.go
cyk_test.go
doc.go

README.md

CYK: Cocke–Younger–Kasami algorithm in Golang

GitHub license GoDoc Build Status

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

Project52

It is one of my project 52.

License

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