blob: 28241cb583c4a4205a74146021f497158bc4152b (
plain)
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
|
@q file: structures.w@>
@q% Copyright Dave Bone 1998 - 2015@>
@q% /*@>
@q% This Source Code Form is subject to the terms of the Mozilla Public@>
@q% License, v. 2.0. If a copy of the MPL was not distributed with this@>
@q% file, You can obtain one at http://mozilla.org/MPL/2.0/.@>
@q% */@>
@** Structure and Rule Recycling Optimization.\fbreak
To improve performance due to the birth-run-delete cyle of grammar rules
on the parse stack,
the following optimization is used:
Stable of rule's symbol when created for recycling purposes.
2 concerns must be attended to:\fbreak
\ptindent{1) the parse stack needs the Rule\_s\_reuse\_entry ptr of the current rule}
\ptindent{2) due to recursion, the recycle table per rule is sequentially searched}
Please see {\bf |rules_use_cnt|} grammar for a thorough discussion on how the rulle count is
calculated for recycling.
\fbreak
\fbreak
Initially an array per specific grammar rule was generated.
It had speed but would have been kludgey to handle overflow on the
number of rules for reuse.
Here is a note on the array [1] definition. The Sun compiler doesn't
like the [] definition being open-ended.
So I fake it.
Each rule will be specifically defined within its namespace.
But, \Yacco2{} is a general library of routines.
So my search uses the entry count to protect against a table overrun situation.
\fbreak
\fbreak
Take 2:\fbreak
Though this approach is speedy when dealing with left recursion only,
it did not have a saftey valve when the count was wrong: eg right recursion
or flawed algorithm on determining rule recursion count.
So i changed it to a stack/double list combo.
The ``in use'' list acts like a stack but its lhs/rhs reduction pair
leaves the lhs as the top item placed in the ``in use'' queue
before its rhs items are removed from the ``in use'' list.
Why?
The lhs rule comes from the reduction when the rhs's symbols are still
sitting on the parse stack.
That is, lhs rule is created first, placed in the ``in use'' list before
the rhs's symbols are popped from the parse stack. If the
popped symbol is a rule it gets recycled and placed back
into the ``for use'' stack for another round of reuse.
@<Structure defs@>+=
struct Per_rule_s_reuse_table;
struct reuse_rule_list;
struct reuse_rule_list{
reuse_rule_list():younger_(0),older_(0),reuse_rule_entry_(0),per_rule_tbl_ptr_(0){};
reuse_rule_list* younger_;
reuse_rule_list* older_;
Rule_s_reuse_entry* reuse_rule_entry_;
Per_rule_s_reuse_table* per_rule_tbl_ptr_;
};
struct Rule_s_reuse_entry{
reuse_rule_list its_linked_list_;
CAbs_lr1_sym* rule_; // new rule symbol for recycling
Rule_s_reuse_entry():rule_(0){};
~Rule_s_reuse_entry(){
if(rule_ == 0) return;
delete rule_;
};
};
struct Per_rule_s_reuse_table{
reuse_rule_list* in_use_list_;
reuse_rule_list* for_use_list_;
Per_rule_s_reuse_table():in_use_list_(0),for_use_list_(0){};
};
struct Fsm_rules_reuse_table{// grammar's stable of rules
int no_rules_entries_;
Per_rule_s_reuse_table* per_rule_s_table_[1];
};
|
