-
Notifications
You must be signed in to change notification settings - Fork 0
/
mrt.h
124 lines (99 loc) · 3.29 KB
/
mrt.h
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
/*
This file is part of Hyacc, a LR(0)/LALR(1)/LR(1)/LR(k) parser generator.
Copyright (C) 2007, 2008 Xin Chen. [email protected]
Hyacc is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
Hyacc is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with Hyacc; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
#ifndef _MRT_H_
#define _MRT_H_
/*
* mrt.h
*
* Functions for multi-rooted tree. Used by unit production elimination
* algorithm.
*
* @Author: Xin Chen
* @Date started: March 9, 2007
* @Last modified: March 9, 2007
*/
/*
* MRTreeNode.parent is a dynamically allocated array.
*/
struct _MRTreeNode {
SymbolNode * symbol;
struct _MRTreeNode ** parent; // dynamic array.
int parent_count;
int parent_max_count; // expand parent array if reached.
};
#define MRTreeNode_INIT_PARENT_COUNT 8
typedef struct _MRTreeNode MRTreeNode; // multi-rooted tree node.
/*
* The Multi-rooted forest grows upon this array.
* The Multi-rooted forest consists of 1 or more trees.
* The leaves of the each tree are in this array,
* the leaves then link to the internal nodes of the tree.
*/
MRTreeNode ** MRLeaves;
int MRLeaves_count;
int MRLeaves_max_count;
#define MRLeaves_INIT_MAX_COUNT 8
/*
* Stores the parent symbols in all multirooted trees.
*
* Used in steps 3 and 5 of unit production removal
* algorithm, to avoid having to traverse through
* the MRTree to find out if a symbol is a parent symbol
* each time.
*/
#define MRParents_INIT_MAX_COUNT 8
typedef struct {
SymbolNode ** parents; // dynamic array.
int count;
int max_count;
} MRParents;
MRParents * all_parents;
/*
* Used in step 5.
* Value obtained when calling getAllMRParents().
* It eventually calls getNode(), which does the work.
*
* Used to retrieve a leaf for a parent.
* There may be more than one leaf for a parent,
* just choose the first one in the order of grammar rules.
*
* The correspondence relationship is:
* all_parents[index] => MRLeaves[leafIndexForParent[index]]
*
* Has the same size as all_parents->max_count.
*/
int * leafIndexForParent;
/*
* leafIndexForParent[] array is build in function
* getNode(), which is called by getParentsForMRLeaf().
* getParentsForMRLeaf() is called by functions
* (1) getAllMRParents() and
* (2) remove_unit_production_step1and2().
* This boolean varaible is set to TRUE after calling (1),
* so calling (2) won't change the values stored in
* leafIndexForParent[].
*
* Used in functions getAllMRParents() and getNode().
*/
BOOL leafIndexForParent_Done;
/* function declarations */
extern MRParents * createMRParents();
extern int getIndexInMRParents(SymbolTblNode * s, MRParents * p);
extern void getParentsForMRLeaf(int leaf_index,
MRParents * parents);
extern void destroyMRParents(MRParents * p);
extern void buildMultirootedTree();
#endif