Edinburgh Speech Tools  2.4-release
 All Classes Functions Variables Typedefs Enumerations Enumerator Friends Pages
EST_SCFG_Chart.h
1 /*************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1997 */
6 /* All Rights Reserved. */
7 /* */
8 /* Permission is hereby granted, free of charge, to use and distribute */
9 /* this software and its documentation without restriction, including */
10 /* without limitation the rights to use, copy, modify, merge, publish, */
11 /* distribute, sublicense, and/or sell copies of this work, and to */
12 /* permit persons to whom this work is furnished to do so, subject to */
13 /* the following conditions: */
14 /* 1. The code must retain the above copyright notice, this list of */
15 /* conditions and the following disclaimer. */
16 /* 2. Any modifications must be clearly marked as such. */
17 /* 3. Original authors' names are not deleted. */
18 /* 4. The authors' names are not used to endorse or promote products */
19 /* derived from this software without specific prior written */
20 /* permission. */
21 /* */
22 /* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
23 /* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
24 /* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
25 /* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
26 /* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
27 /* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
28 /* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
29 /* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
30 /* THIS SOFTWARE. */
31 /* */
32 /*************************************************************************/
33 /* Author : Alan W Black */
34 /* Date : June 1997 */
35 /*-----------------------------------------------------------------------*/
36 /* */
37 /* A SCFG chart parser, general functions */
38 /* */
39 /*=======================================================================*/
40 #ifndef __EST_SCFG_CHART_H__
41 #define __EST_SCFG_CHART_H__
42 
43 #include "EST_String.h"
44 #include "EST_simplestats.h"
45 #include "EST_string_aux.h"
46 #include "EST_SCFG.h"
47 #include "ling_class/EST_Relation.h"
48 
50 
51 /** An internal class for \Ref{EST_SCFG_Chart} for representing edges
52  in the chart during parsing with SCFGs.
53 
54  A standard Earley type chart edge, with representations for two
55  daughters and a position or what has been recognised. A probability
56  is also included.
57 */
59  private:
60  int p_d1;
61  int p_d2;
62  int p_pos;
63  double p_prob;
64  public:
65  /**@name Constructor and initialisation functions */
66  //@{
68  EST_SCFG_Chart_Edge(double prob, int d1, int d2, int pos);
70  //@}
71 
72  /// Postion, 0 1 or 2, where 0 is empty, 1 is incomplete 2 is complete.
73  int pos(void) { return p_pos; }
74  /// Edge probability
75  double prob(void) { return p_prob; }
76  /// (Non)terminal of daughter 1
77  int d1() { return p_d1; }
78  /// (Non)terminal of daughter 2
79  int d2() { return p_d2; }
80 
81 };
82 
83 /** A class for parsing with a probabilistic grammars.
84 
85  The chart (sort of closer to CKY table) consists of indexes of
86  edges indexed by vertex number of mother non-terminal.
87 
88  The initial values (well-formed substring table) are taken from
89  an \Ref{EST_Stream} with a given feature. The grammar may be
90  specified as LISP rules or as an already constructed \Ref{EST_SCFG}.
91 
92  This produces a single best parse. It treats the grammar as
93  strictly context free in that the probability of a nonterminal
94  over vertex n to m, is the sum of all the possible analyses
95  of that sub-tree. Only the best analysis is kept for the
96  resulting parse tree.
97 
98  @author Alan W Black (awb@cstr.ed.ac.uk): October 1997
99 */
101  private:
102  /// pointer to grammar
103  EST_SCFG *grammar;
104  /// TRUE is grammar was created internally, FALSE is can't be freed
105  int grammar_local;
106  /// Number of vertices (number of words + 1)
107  int n_vertices;
108  /// Index of edges by vertex start x vertex end x nonterminal
109  EST_SCFG_Chart_Edge ****edges;
110  /// Index of basic symbols indexed by (start) vertex.
111  EST_SCFG_Chart_Edge **wfst;
112  /// An empty edge, denotes 0 probability edge.
113  EST_SCFG_Chart_Edge *emptyedge;
114 
115  // Find the best analysis of nonterminal {\tt p} from {\tt start}
116  // to {\tt end}. Used after parsing
117  double find_best_tree(int start,int end,int p)
118  { EST_SCFG_Chart_Edge *r;
119  if ((r=edges[start][end][p]) != 0) return r->prob();
120  else return find_best_tree_cal(start,end,p); }
121  // Calculate best tree/probability
122  double find_best_tree_cal(int start,int end,int p);
123  void setup_edge_table();
124  void delete_edge_table();
125  LISP print_edge(int start, int end, int name, EST_SCFG_Chart_Edge *e);
126  // Extract edge from chart and add it to stream
127  void extract_edge(int start, int end, int p,
129  EST_Item *s,
130  EST_Item **word);
131  // Build parse from distinguished symbol alone
132  void extract_forced_parse(int start, int end, EST_Item *s, EST_Item *w);
133  public:
134  /**@name Constructor and initialisation functions */
135  //@{
136  EST_SCFG_Chart();
137  ~EST_SCFG_Chart();
138  //@}
139 
140  /**@name Grammar and parse string initialisation functions */
141  //@{
142  /// Initialize from LISP rules set
143  void set_grammar_rules(LISP r);
144  /// Initialize from existing \Ref{EST_SCFG} grammar
145  void set_grammar_rules(EST_SCFG &grammar);
146  /** Initialize for parsing from relation using {\tt name} feature
147  setting up the "Well Formed Substring Table" */
148  void setup_wfst(EST_Relation *s,const EST_String &name="name");
149  /** Initialize for parsing from s to e using {\tt name} feature
150  setting up the "Well Formed Substring Table" */
151  void setup_wfst(EST_Item *s, EST_Item *e,const EST_String &name="name");
152  //@}
153 
154  /**@name parsing functions */
155  //@{
156  /// Parses the loaded WFST with the loaded grammar.
157  void parse();
158  /// Return the parse in full LISP form.
159  LISP find_parse();
160  /// Extract parse tree and add it to syn linking leafs to word
161  void extract_parse(EST_Relation *syn,EST_Relation *word,int force=0);
162  /// Extract parse tree and add it to syn linking leafs to items s to e
163  void extract_parse(EST_Relation *syn,EST_Item *s,
164  EST_Item *e,int force=0);
165  //@}
166 };
167 
168 /** Build a relation from a LISP list of items.
169 */
170 void EST_SCFG_chart_load_relation(EST_Relation *s,LISP sent);
171 
172 /** Parse a given string using the given grammar.
173 */
174 LISP scfg_parse(LISP string,LISP grammar);
175 /** Parse the given string using the given \Ref{EST_SCFG}.
176 */
177 LISP scfg_parse(LISP string,EST_SCFG &grammar);
178 /** Parse named features in (list) relation Word into (tree)
179  ** relation Syntax
180  */
181 void scfg_parse(class EST_Relation *Word, const EST_String &name,
182  class EST_Relation *Syntax, EST_SCFG &grammar);
183 
184 #endif