This directory contains a simple implementation of a recognizer, parser and probabilistic parser for Context Free Grammars (CFGs).

You need Perl (ver 5.6 or later) to run these programs.

cky.pm -- CKY parser module for CFGs
testcky.pl -- sample code for using cky.pm
ex1.cfg -- sample CFG file
ex1.test -- sample input file

Run using the command:

perl testcky.pl ex1.cfg ex1.test


Older implementation. You need Perl (ver 5 or later) to run these programs.


To download the scripts, shift click on the following links to save
them to your directory. Look at the sample runs given below for how to
run the programs.

ckycfg.pl       -- CKY recognizer for CFGs
ckycfg_parse.pl -- CKY parser for CFGs
ckycfg_prob.pl  -- CKY parser for Probabilistic CFGs: reports best parse
grammar.pl      -- A slightly more interesting grammar
grammar2.pl     -- Same grammar with an empty input list (see below)
viewtree        -- Adwait Ratnaparkhi's tree viewer


A default simple grammar and input string is contained within the scripts.



Sample run:

% ckycfg.pl
% ckycfg_parse.pl | viewtree
% ckycfg_prob.pl | viewtree




Alternatively, you can try these programs on more interesting
grammars:


For example:

% ckycfg_parse.pl grammar.pl | viewtree
% ckycfg_prob.pl grammar.pl | viewtree



 
If you set the @input list in grammar.pl to
the empty list, you can enter sentences in the stdin of the program.


For example:

% ckycfg_parse.pl grammar2.pl | viewtree
John plays soccer





Alternative loop structures for the CKY search:


#  for ($j = 2; $j <= $N; $j++) {
#      for ($i = $j-2; $i >= 0; $i--) {
#  	  for ($k = $i+1; $k < $j; $k++) {

#  for ($p = 1; $p <= $N; $p++) {
#      for ($i = 0; $i <= $N-$p; $i++) {
#  	$j = $i+$p;
#  	for ($k = $i; $k < $j; $k++) {

#  for ($j = 1; $j <= $N; $j++) {
#      for ($i = 0; $i <= $N-$j+1; $i++) {
#  	for ($k = $i; $k < $j; $k++) {



Anoop Sarkar anoop at linc.cis.upenn.edu