-
Notifications
You must be signed in to change notification settings - Fork 0
/
README.txt
133 lines (88 loc) · 4.47 KB
/
README.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
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