Commit | Line | Data |
---|---|---|
d44e3c4f | 1 | /****************************************************************************** |
2 | * Copyright (c) 2000-2016 Ericsson Telecom AB | |
3 | * All rights reserved. This program and the accompanying materials | |
4 | * are made available under the terms of the Eclipse Public License v1.0 | |
5 | * which accompanies this distribution, and is available at | |
6 | * http://www.eclipse.org/legal/epl-v10.html | |
7 | * | |
8 | * Contributors: | |
9 | * Balasko, Jeno | |
10 | * Forstner, Matyas | |
11 | * | |
12 | ******************************************************************************/ | |
970ed795 EL |
13 | #include "Grammar.hh" |
14 | #include "Rule.hh" | |
15 | #include "Iterator.hh" | |
16 | #include "Symbol.hh" | |
17 | ||
18 | // ================================= | |
19 | // ===== Grammar | |
20 | // ================================= | |
21 | ||
22 | Grammar::Grammar(const Grammar& p) | |
23 | : Node(p) | |
24 | { | |
25 | FATAL_ERROR("Grammar::Grammar()"); | |
26 | } | |
27 | ||
28 | Grammar::Grammar() | |
29 | : max_dist(-1) | |
30 | { | |
31 | } | |
32 | ||
33 | Grammar::~Grammar() | |
34 | { | |
35 | for(size_t i=0; i<gs.size(); i++) | |
36 | delete gs.get_nth_elem(i); | |
37 | gs.clear(); | |
38 | as.clear(); | |
39 | ss.destruct_ss(); | |
40 | } | |
41 | ||
42 | Grammar* Grammar::clone() const | |
43 | { | |
44 | FATAL_ERROR("Grammar::clone()"); | |
45 | } | |
46 | ||
47 | Symbol* Grammar::get_symbol(const string& id) | |
48 | { | |
49 | if(ss.has_s_withId(id)) return ss.get_s_byId(id); | |
50 | Symbol *s=new Symbol(id); | |
51 | if(id[0]=='\'' || id[0]=='"' || id=="error") s->set_is_terminal(); | |
52 | ss.add_s(s); | |
53 | return s; | |
54 | } | |
55 | ||
56 | void Grammar::add_alias(const string& s1, const string& s2) | |
57 | { | |
58 | if(!as.has_key(s1)) | |
59 | as.add(s1, get_symbol(s2)); | |
60 | get_symbol(s1)->set_is_terminal(); | |
61 | } | |
62 | ||
63 | void Grammar::add_grouping(Grouping *p_grouping) | |
64 | { | |
65 | const string& id=p_grouping->get_id(); | |
66 | if(gs.has_key(id)) { | |
67 | gs[id]->steal_rules(p_grouping); | |
68 | delete p_grouping; | |
69 | } | |
70 | else gs.add(id, p_grouping); | |
71 | } | |
72 | ||
73 | Symbol* Grammar::get_alias(Symbol *p_symbol) | |
74 | { | |
75 | const string& id=p_symbol->get_id(); | |
76 | return as.has_key(id)?as[id]:p_symbol; | |
77 | } | |
78 | ||
79 | void Grammar::replace_aliases() | |
80 | { | |
81 | startsymbol=get_alias(startsymbol); | |
82 | for(size_t i=0; i<gs.size(); i++) | |
83 | gs.get_nth_elem(i)->replace_aliases(this); | |
84 | for(size_t i=0; i<as.size(); i++) | |
85 | ss.destruct_symbol(as.get_nth_key(i)); | |
86 | } | |
87 | ||
88 | Grouping* Grammar::get_grouping_bySymbol(Symbol *p_symbol) | |
89 | { | |
90 | const string& id=p_symbol->get_id(); | |
91 | if(!gs.has_key(id)) FATAL_ERROR("Grammar::get_grouping()"); | |
92 | return gs[id]; | |
93 | } | |
94 | ||
95 | void Grammar::compute_refs() | |
96 | { | |
97 | ItRefBuild it; | |
98 | it.visitGrammar(this); | |
99 | } | |
100 | ||
101 | void Grammar::compute_can_be_empty() | |
102 | { | |
103 | bool changed; | |
104 | do { | |
105 | changed=false; | |
106 | size_t ng=get_nof_groupings(); | |
107 | for(size_t ig=0; ig<ng; ig++) { | |
108 | Grouping *grp=get_grouping_byIndex(ig); | |
109 | Symbol *lhs=grp->get_lhs(); | |
110 | if(lhs->get_can_be_empty()) continue; | |
111 | size_t nr=grp->get_nof_rules(); | |
112 | for(size_t ir=0; ir<nr; ir++) { | |
113 | if(lhs->get_can_be_empty()) continue; | |
114 | Rule *rule=grp->get_rule_byIndex(ir); | |
115 | size_t ns=rule->get_nof_ss(); | |
116 | bool b=true; | |
117 | for(size_t is=0; is<ns; is++) | |
118 | if(!rule->get_s_byIndex(is)->get_can_be_empty()) {b=false; break;} | |
119 | if(b) {lhs->set_can_be_empty(); changed=true;} | |
120 | } // for ir | |
121 | } // for ig | |
122 | } while(changed); | |
123 | } | |
124 | ||
125 | void Grammar::compute_dists() | |
126 | { | |
127 | SymbolSet *prev_set, *next_set; | |
128 | prev_set=new SymbolSet(); | |
129 | next_set=new SymbolSet(); | |
130 | int dist=0; | |
131 | if(startsymbol) { | |
132 | prev_set->add_s(startsymbol); | |
133 | startsymbol->set_dist(dist); | |
134 | } | |
135 | size_t n=prev_set->get_nof_ss(); | |
136 | while(n) { | |
137 | dist++; | |
138 | for(size_t i=0; i<n; i++) | |
139 | next_set->add_ss(prev_set->get_s_byIndex(i)->get_refs()); | |
140 | n=next_set->get_nof_ss(); | |
141 | SymbolSet *tmp_set=new SymbolSet(); | |
142 | for(size_t i=0; i<n; i++) { | |
143 | Symbol *s=next_set->get_s_byIndex(i); | |
144 | if(s->get_dist()==-1) s->set_dist(dist); | |
145 | else tmp_set->add_s(s); | |
146 | } | |
147 | next_set->remove_ss(*tmp_set); | |
148 | delete prev_set; | |
149 | prev_set=next_set; | |
150 | next_set=tmp_set; | |
151 | next_set->remove_all(); | |
152 | n=prev_set->get_nof_ss(); | |
153 | } // while n | |
154 | delete prev_set; | |
155 | delete next_set; | |
156 | max_dist=dist; | |
157 | } | |
158 | ||
159 | void Grammar::compute_all() | |
160 | { | |
161 | compute_refs(); | |
162 | compute_can_be_empty(); | |
163 | compute_dists(); | |
164 | } |