1 /*************************************************************************/
2 /* Copyright (c) 2004 */
3 /* Daniel Sleator, David Temperley, and John Lafferty */
4 /* Copyright (c) 2013 Linas Vepstas */
5 /* All rights reserved */
6 /* */
7 /* Use of the link grammar parsing system is subject to the terms of the */
8 /* license set forth in the LICENSE file included with this software. */
9 /* This license allows free redistribution and use in source and binary */
10 /* forms, with or without modification, subject to certain conditions. */
11 /* */
12 /*************************************************************************/
13
14 #ifndef _LG_DICT_STRUCTURES_H_
15 #define _LG_DICT_STRUCTURES_H_
16
17 #include "link-includes.h"
18
19 LINK_BEGIN_DECLS
20
21 /* Forward decls */
22 typedef struct Dict_node_struct Dict_node;
23 typedef struct Exp_struct Exp;
24 typedef struct Word_file_struct Word_file;
25 typedef struct condesc_struct condesc_t;
26
27 /**
28 * Types of Exp_struct structures
29 */
30 typedef enum
31 {
32 OR_type = 1,
33 AND_type,
34 CONNECTOR_type
35 } Exp_type;
36
37 static const int cost_max_dec_places = 3;
38 static const double cost_epsilon = 1E-5;
39
40 #define EXPTAG_SZ 100 /* Initial size for the Exptag array. */
41 typedef enum { Exptag_none=0, Exptag_dialect, Exptag_macro } Exptag_type;
42
43 /**
44 * The Exp structure defined below comprises the expression trees that are
45 * stored in the dictionary. The expression has a type (OR_type, AND_type
46 * or CONNECTOR_type). If it is not a terminal "operand_first" points to its
47 * list of operands (when each of them points to the next one through
48 * "operand_next"). Else "condesc" is the connector descriptor, when "dir"
49 * indicates the connector direction.
50 */
51 struct Exp_struct
52 {
53 Exp *operand_next; /* Next same-level operand. */
54 Exp_type type:8; /* One of three types: AND, OR, or connector. */
55 Exptag_type tag_type:8;
56 char dir; /* The connector connects to the left ('-') or right ('+'). */
57 bool multi; /* TRUE if a multi-connector (for connector). */
58 unsigned int tag_id; /* Index in tag_type namespace. */
59 float cost; /* The cost of using this expression. */
60 union
61 {
62 Exp *operand_first; /* First operand (for non-terminals). */
63 condesc_t *condesc; /* Only needed if it's a connector. */
64 };
65 };
66
67 bool cost_eq(double cost1, double cost2);
68 const char *cost_stringify(double cost);
69
70 /* API to access the above structure. */
lg_exp_get_type(const Exp * exp)71 static inline Exp_type lg_exp_get_type(const Exp* exp) { return exp->type; }
lg_exp_get_dir(const Exp * exp)72 static inline char lg_exp_get_dir(const Exp* exp) { return exp->dir; }
lg_exp_get_multi(const Exp * exp)73 static inline bool lg_exp_get_multi(const Exp* exp) { return exp->multi; }
74 const char* lg_exp_get_string(const Exp*);
lg_exp_get_cost(const Exp * exp)75 static inline double lg_exp_get_cost(const Exp* exp) { return exp->cost; }
lg_exp_operand_first(Exp * exp)76 static inline Exp* lg_exp_operand_first(Exp* exp) { return exp->operand_first; }
lg_exp_operand_next(Exp * exp)77 static inline Exp* lg_exp_operand_next(Exp* exp) { return exp->operand_next; }
78 const char *lg_exp_stringify(const Exp *);
79
80 /**
81 * The dictionary is stored as a binary tree comprised of the following
82 * nodes. A list of these (via right pointers) is used to return
83 * the result of a dictionary lookup.
84 */
85 struct Dict_node_struct
86 {
87 const char * string; /* The word itself */
88 Word_file * file; /* The file the word came from (NULL if dict file) */
89 Exp * exp;
90 Dict_node *left, *right;
91 };
92
93 LINK_END_DECLS
94
95 #endif /* _LG_DICT_STRUCTURES_H_ */
96