cyk
github.com/kkdai/cyk
go get github.com/kkdai/cyk
cyk

github.com/kkdai/cyk

CYK algorithm in Golang

go get github.com/kkdai/cyk
Readme

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.

GitHub Stars

11

LAST COMMIT

4yrs ago

MAINTAINERS

0

CONTRIBUTORS

2

OPEN ISSUES

0

OPEN PRs

0
VersionTagPublished
v0.0.0-20181107105257-d39a1d2186f4
2yrs ago
No alternatives found
No tutorials found
Add a tutorial