The CYK algorithm is an efficient algorithm for determining whether a string is in the language generated by a context-free grammar. It uses dynamic programming and is fastest when the input grammar is in Chomsky normal form.
Questions tagged [cyk]
37 questions
5
votes
1 answer
Generating parse tree from CYK algorithm
I use CYK algorithm (already implemented it in Java) to see if a string recognized according to a specific grammar. Now I need to generate a parse tree for the string, is the a way to generate the tree from the matrix which I use when using the CYK…
Lucy
- 471
- 4
- 12
- 28
5
votes
1 answer
Code review of CYK algorithm implementation in Erlang
I am beginning Erlang and as an exercise I tried to implement the CYK algorithm.
Main code(cyk.erl):
%%% An attempt for a CYK parser in Erlang
-module(cyk).
-export([
init_storage/0,
import_grammar_file/1,
…
Eric
- 2,784
- 1
- 20
- 25
5
votes
1 answer
Cannot understand CYK Algorithm pseudo-code
I was reading about the CYK algorithm, and there is one part of pseudo-code I cannot understand. The whole pseudo-code is:
let the input be a string S consisting of n characters: a1 ... an.
let the grammar contain r nonterminal symbols R1 ...…
user2280838
- 83
- 6
5
votes
1 answer
How does the CYK algorithm work?
I have to check if a string can be derived from a given context free that is in Chomsky normal form. I'm using C++.
There is very nice pseudocode on the Wikipedia article covering the CYK algorithm, but I can't understand it very well.
Would…
neojb1989
- 181
- 1
- 3
- 12
4
votes
1 answer
Does CKY really require CNF?
I've read a number of places that the CYK/CKY algorithms require the grammar to be in Chomsky Normal Form (CNF), e.g.
The standard version of CYK operates only on context-free grammars
given in Chomsky normal form (CNF) ~Wikipedia
However, I've…
Wes
- 1,720
- 3
- 15
- 26
3
votes
0 answers
CYK build parsing tree from table
How do I build a parsing tree after I obtain the CYK table? I didn't understand what Wikipedia was trying to say.
Example:
A
- C
A - B
B,D C,F E B,D
How do I return a list of rules applied to get from A to BCED (or any…
3
votes
1 answer
Steps to generate parse tree from CYK Algorithm (Natural Language Processing)
I am currently working on a project involving NLP. I have implemented a CKY identifier as given in Jurafsky and Martin (algorithm on page 450). The table so produced actually stores the nonterminals in the table (instead of the usual boolean…
nerdier.js
- 591
- 1
- 4
- 15
3
votes
0 answers
Something wrong with my CYK code
I wrote some code implementing the CYK Algorithm. I have some problems with my code, but I don't know which I did wrong. I also asked about the pseudo-code of CYK Algorithm.
Could you please help me with this code:
import…
user2280838
- 83
- 6
3
votes
1 answer
How to speed up a CYK Algorithm in C++?
I would like to implement CYK algorithm in C/C++, but available on various websites pseudo-code doesn't answer how to implement it efficiently. I wrote a version that uses some stl structures like map and sets, but it's very slow. I was thinking…
Jackson Rubbo
- 31
- 3
3
votes
2 answers
CYK algorithm pseudocode confusion
so I've been reading about the CYK algorithm in wikipedia and in many powerpoints/pdfs.
In wikipedia there is a part where I'm not 100% what it's trying to say. Can you guys break it down for me?
let the input be a string S consisting of n…
Kelsey Abreu
- 1,094
- 3
- 17
- 42
3
votes
1 answer
CYK (Cocke-Younger-Kasami) Grammar Rules
I am interested in Natural Language Parsing and have written a Brill Part of Speech Tagger, and would like to enhance it by combining it with a a POS tagger based on grammar rules. Is anyone aware of open source ruleset files for English anywhere? I…
mintydog
- 891
- 1
- 7
- 11
2
votes
0 answers
Building expression tree from parse tree
I wrote a CYK parser, and I use it to parse math expressions like (1+2)/3-4^5. I also wrote a code that builds parse-tree from the table (left triangular matrix) that CYK algorithm provides, using the grammar below. My question would be that is it…
losleon
- 21
- 2
2
votes
1 answer
CYK algorithm implementation
I'm trying to implement the CYK pseudo code provided by wikipedia.
The example sentence I input should be outputting True, however it is outputting false. I think I'm getting issues on the indexing considering the provided example starts from 1.…
user
- 854
- 2
- 12
- 28
2
votes
3 answers
Product of 2 Lists in ocaml without Imperative Functions
ers,
I'm attempting to learn functional programming through ocaml and CYK tables, so no List.mem or any imperative functions for that matter. My objective is to form the product of 2 cells.
Here is what I currently have:
let stringlister =…
Enflamed Chicken
- 23
- 2
2
votes
2 answers
Equating a Sublist to Another Sublist for CYK table in Prolog
I'm currently working on a Prolog program that will generate a CYK parse table after being given a set of productions. However, I am having troubles checking two rows to see if they are equivalent. Here's what I have so far:
answer(X,X).
%Checks to…
altoidmaster
- 23
- 2