This directory contains programs for parsing
strings relative a given a grammar, and for 
converting grammars of various kinds.  There are
also auxiliary files and an auxiliary directory
described below.
---
0) Grammar Files:  Grammars are stored as text files
   which should end with the .cfg extension.  They are
   specified as follows:

          o  Each line consists of white-space separated strings which
          o  The first string of any line must have length 1 and is a variable
          o  Subsequent strings on a given line are the right hand sides
                 of productions from the variable for that line
          o  The first variable in the file is the start variable
          o  A single double-quote symbol " represents the empty
                 string epsilon 
                 (we think of " as two single quotes with nothing in between)
          o  Any character which isn't a variable, is a terminal
 
       For example a*b* with rule-set {S->AB,A->",A->aA,B->",B->bB} is
       given by the file which looks like:

S AB
A " aA
B " bB

---
1) Program for parsing strings relative a given grammar
   (by Zeph Grunschlag):

If the string is generated by the grammar, a derivation
tree is created and is represented in two ways:

o    as a JTree, displayed in a JFrame
o    as a LaTeX tree, which can be converted into PDF

USAGE:

I) To create the two trees call:

java CFGParse <grammar-filename> <input-string>

(the name of the created file is "<input-string>.tex" )

II) If you want convert the LaTeX tree into PDF and
you're on CUNIX then use the command:

pdflatex <LaTeX-tree-filename>

----
2) Program for reading and converting various types of
grammars (By Yoav Hirsch and Zeph Grunschlag)

USAGE:

	java CFG <grammar_file> [<conversion instruction>]

	Conversion Instructions:  There are three possible flags which may not be
        combined at the moment:  -removeEpsilons, -removeUnits, -makeCNF.
        If no flags are specified, the program tries to create a CFG and gives some
        information. When flags are specified, a new grammar file is created
	containing the grammar with the desired properties.
  
        -removeEpsilons  -- given an arbitrary grammar, modify the grammar to an
                              equivalent grammar with only one allowable epsilon
                              transtion:  start ---> epsilon

        -removeUnits     -- given a grammar with no epsilon transitions, except possibly
                              from the start variable, modify the grammar to an equivalent
                              grammar with no unit transitions

        -makeCNF         -- given a grammar with no epsilon transitions and no unit
                              transitions, convert into an equivalent grammar in Chomsky
                              Normal Form
--- 
3) There is much more functionality that I would like to add:

      o  Write a GUI to make the program more user-friendly
      o  Allow the user to see a derivation, and not just a derivation-tree
      o  Variables to be more than 1 character long

If you are interested in one of the above (or have another idea for
improving the program) there is EXTRA-CREDIT available for working on
this program.  Contact zeph@cs.columbia.edu for more information.
-----------------------------------------------------

Directory Structure:

CFG.java	     The context free grammar class
			   For extra credit on HW6, you
			   can add functionality to this
			   class.
		     
CFGParse.java	     A class created for simplifying the parsing command.

EarleyAgent.java     A class used in the parsing algorithm.

EarleyRule.java	     A class used in the parsing algorithm.


MalformedGrammarException.java
		     An exception class used to let the user
		     know that their grammar has not been
		     defined properly, has a typo, or 
		     is not the right type for the given operation.

Rule.java	     A class which defines the productions of a CFG.

TreeModel2LaTeX.java A class for converting JTree objects into LaTeX
		     trees.

grammars	     A directory containing some examples of grammars
		     NOTE: some of these grammars contain epsilons
		     and that the success of the parsing algorithm
		     on such grammars is not guaranteed.

README.txt	     This file.

JavaCFG.tar.gz       This directory, compressed for UNIX

JavaCFG.zip	     This directory, compressed for Windows