Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
ToCNF.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <grammar/Grammar.h>
9#include <grammar/ContextFree/CFG.h>
10#include <grammar/ContextFree/EpsilonFreeCFG.h>
11#include <grammar/ContextFree/CNF.h>
12#include <grammar/ContextFree/GNF.h>
13#include <grammar/ContextFree/LG.h>
14#include <grammar/Regular/LeftLG.h>
15#include <grammar/Regular/LeftRG.h>
16#include <grammar/Regular/RightLG.h>
17#include <grammar/Regular/RightRG.h>
18
19#include <common/createUnique.hpp>
20
21#include "EpsilonRemover.h"
22#include "SimpleRulesRemover.h"
23#include <exception/CommonException.h>
24
25namespace grammar {
26
27namespace simplify {
28
33class ToCNF {
34public:
45 template < class TerminalSymbolType, class NonterminalSymbolType >
46 static grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > convert( const grammar::CFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
47
58 template < class TerminalSymbolType, class NonterminalSymbolType >
59 static grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > convert( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
60
71 template < class TerminalSymbolType, class NonterminalSymbolType >
72 static grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > convert( const grammar::GNF < TerminalSymbolType, NonterminalSymbolType > & grammar );
73
84 template < class TerminalSymbolType, class NonterminalSymbolType >
85 static grammar::CNF < TerminalSymbolType, NonterminalSymbolType > convert( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar );
86
97 template < class TerminalSymbolType, class NonterminalSymbolType >
98 static grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > convert( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar );
99
110 template < class TerminalSymbolType, class NonterminalSymbolType >
111 static grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > convert( const grammar::LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar );
112
123 template < class TerminalSymbolType, class NonterminalSymbolType >
124 static grammar::CNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > convert( const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
125
136 template < class TerminalSymbolType, class NonterminalSymbolType >
137 static grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > convert( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar );
138
149 template < class TerminalSymbolType, class NonterminalSymbolType >
150 static grammar::CNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > convert( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
151};
152
153template < class TerminalSymbolType, class NonterminalSymbolType >
154grammar::CNF < TerminalSymbolType, NonterminalSymbolType > ToCNF::convert(const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar) {
155 return grammar;
156}
157
158template < class TerminalSymbolType, class NonterminalSymbolType >
159grammar::CNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > ToCNF::convert ( const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
160 grammar::CNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > result ( grammar.getInitialSymbol ( ) );
161
162 for ( const NonterminalSymbolType & nonterminal : grammar.getNonterminalAlphabet ( ) )
163 result.addNonterminalSymbol ( nonterminal );
164 result.setTerminalAlphabet ( grammar.getTerminalAlphabet ( ) );
165
166 ext::map < TerminalSymbolType, TerminalSymbolType > terminalToShadowNonterminal;
167 for ( const TerminalSymbolType & symbol : grammar.getTerminalAlphabet ( ) ) {
168 TerminalSymbolType shadowSymbol = common::createUnique ( symbol, result.getTerminalAlphabet ( ), result.getNonterminalAlphabet ( ) );
169 terminalToShadowNonterminal.insert ( std::make_pair ( symbol, shadowSymbol ) );
170 result.addNonterminalSymbol ( shadowSymbol );
171 result.addRule ( std::move ( shadowSymbol ), symbol );
172 }
173
174 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, TerminalSymbolType > > > > & rules : grammar.getRules ( ) ) {
175 for ( const ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, TerminalSymbolType > > & rhs : rules.second ) {
176 if ( rhs.template is < TerminalSymbolType > ( ) ) {
177 result.addRule ( rules.first, rhs.template get < TerminalSymbolType > ( ) );
178 } else {
179 const ext::pair < NonterminalSymbolType, TerminalSymbolType > & rhsPair = rhs.template get < ext::pair < NonterminalSymbolType, TerminalSymbolType > > ( );
180 result.addRule ( rules.first, ext::make_pair ( rhsPair.first, terminalToShadowNonterminal.at ( rhsPair.second ) ) );
181 }
182 }
183 }
184
185 result.setGeneratesEpsilon ( grammar.getGeneratesEpsilon ( ) );
186
187 return result;
188}
189
190template < class TerminalSymbolType, class NonterminalSymbolType >
191grammar::CNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > ToCNF::convert ( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
192 grammar::CNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > result ( grammar.getInitialSymbol ( ) );
193
194 for ( const NonterminalSymbolType & nonterminal : grammar.getNonterminalAlphabet ( ) )
195 result.addNonterminalSymbol ( nonterminal );
196 result.setTerminalAlphabet ( grammar.getTerminalAlphabet ( ) );
197
198 ext::map < TerminalSymbolType, TerminalSymbolType > terminalToShadowNonterminal;
199 for ( const TerminalSymbolType & symbol : grammar.getTerminalAlphabet ( ) ) {
200 TerminalSymbolType shadowSymbol = common::createUnique ( symbol, result.getTerminalAlphabet ( ), result.getNonterminalAlphabet ( ) );
201 terminalToShadowNonterminal.insert ( std::make_pair ( symbol, shadowSymbol ) );
202 result.addNonterminalSymbol ( shadowSymbol );
203 result.addRule ( std::move ( shadowSymbol ), symbol );
204 }
205
206 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > > > & rules : grammar.getRules ( ) ) {
207 for ( const ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > & rhs : rules.second ) {
208 if ( rhs.template is < TerminalSymbolType > ( ) ) {
209 result.addRule ( rules.first, rhs.template get < TerminalSymbolType > ( ) );
210 } else {
211 const ext::pair < TerminalSymbolType, NonterminalSymbolType > & rhsPair = rhs.template get < ext::pair < TerminalSymbolType, NonterminalSymbolType > > ( );
212 result.addRule ( rules.first, ext::make_pair ( terminalToShadowNonterminal.at ( rhsPair.first ), rhsPair.second ) );
213 }
214 }
215 }
216
217 result.setGeneratesEpsilon ( grammar.getGeneratesEpsilon ( ) );
218
219 return result;
220}
221
222template < class TerminalSymbolType, class NonterminalSymbolType >
223void splitRule ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > lhs, const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs, grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > & result ) {
224 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > left;
225 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > right;
226
227 for ( unsigned i = 0; i < rhs.size ( ) / 2; ++ i )
228 left.push_back ( rhs [ i ] );
229
230 if ( result.addNonterminalSymbol ( left ) && left.size ( ) > 1 )
231 splitRule ( left, left, result );
232
233 for ( unsigned i = rhs.size ( ) / 2; i < rhs.size ( ); ++ i )
234 right.push_back ( rhs [ i ] );
235
236 if ( result.addNonterminalSymbol ( right ), right.size ( ) > 1 )
237 splitRule ( right, right, result );
238
239 result.addRule ( std::move ( lhs ), ext::make_pair ( std::move ( left ), std::move ( right ) ) );
240}
241
242template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
243grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > convertInternal( const T & grammar ) {
244 grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > result ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { grammar.getInitialSymbol ( ) } );
245
246 for ( const NonterminalSymbolType & nonterminal : grammar.getNonterminalAlphabet ( ) )
247 result.addNonterminalSymbol ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { nonterminal } );
248
249 result.setTerminalAlphabet ( grammar.getTerminalAlphabet ( ) );
250
251 for ( const TerminalSymbolType & symbol : grammar.getTerminalAlphabet ( ) ) {
252 result.addNonterminalSymbol ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { symbol } );
253 result.addRule ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { symbol }, symbol );
254 }
255
256 for ( const auto & rules : grammar.getRules ( ) ) {
257 for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs : rules.second ) {
258 if ( rhs.size ( ) == 1 ) {
259 result.addRule ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { rules.first }, rhs [ 0 ].template get < TerminalSymbolType > ( ) );
260 } else {
261 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rawRule;
262 for ( const ext::variant < TerminalSymbolType, NonterminalSymbolType > & symbol : rhs ) {
263 if ( grammar.getTerminalAlphabet ( ).count ( symbol ) )
264 rawRule.push_back ( symbol.template get < TerminalSymbolType > ( ) );
265 else
266 rawRule.push_back ( symbol );
267 }
268
269 splitRule ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { rules.first }, std::move ( rawRule ), result );
270 }
271 }
272 }
273
274 result.setGeneratesEpsilon ( grammar.getGeneratesEpsilon ( ) );
275
276 return result;
277}
278
279template < class TerminalSymbolType, class NonterminalSymbolType >
280grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > ToCNF::convert(const grammar::CFG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
281 return convert(grammar::simplify::EpsilonRemover::remove(grammar));
282}
283
284template < class TerminalSymbolType, class NonterminalSymbolType >
285grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > ToCNF::convert(const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
286 return convertInternal(grammar::simplify::SimpleRulesRemover::remove(grammar));
287}
288
289template < class TerminalSymbolType, class NonterminalSymbolType >
290grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > ToCNF::convert ( const grammar::GNF < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
291 grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > result ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { grammar.getInitialSymbol ( ) } );
292
293 for ( const NonterminalSymbolType & nonterminal : grammar.getNonterminalAlphabet ( ) )
294 result.addNonterminalSymbol ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { nonterminal } );
295
296 result.setTerminalAlphabet ( grammar.getTerminalAlphabet ( ) );
297
298 for ( const TerminalSymbolType & symbol : grammar.getTerminalAlphabet ( ) ) {
299 result.addNonterminalSymbol ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { symbol } );
300 result.addRule ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { symbol }, symbol );
301 }
302
303 for ( const auto & rules : grammar.getRules ( ) ) {
304 for ( const ext::pair < TerminalSymbolType, ext::vector < NonterminalSymbolType > > & rhs : rules.second ) {
305 if ( rhs.second.empty ( ) )
306 result.addRule ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { rules.first }, rhs.first );
307 else {
308 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rawRule { rhs.first };
309 rawRule.insert ( rawRule.end ( ), rhs.second.begin ( ), rhs.second.end ( ) );
310 splitRule ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { rules.first }, std::move ( rawRule ), result );
311 }
312 }
313 }
314
315 result.setGeneratesEpsilon ( grammar.getGeneratesEpsilon ( ) );
316
317 return result;
318}
319
320template < class TerminalSymbolType, class NonterminalSymbolType >
321grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > ToCNF::convert(const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
322 return convertInternal(grammar::simplify::SimpleRulesRemover::remove(grammar::simplify::EpsilonRemover::remove(grammar)));
323}
324
325template < class TerminalSymbolType, class NonterminalSymbolType >
326grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > ToCNF::convert(const grammar::LeftLG< TerminalSymbolType, NonterminalSymbolType > & grammar) {
327 return convertInternal(grammar::simplify::SimpleRulesRemover::remove(grammar::simplify::EpsilonRemover::remove(grammar)));
328}
329
330template < class TerminalSymbolType, class NonterminalSymbolType >
331grammar::CNF < TerminalSymbolType, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > ToCNF::convert(const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
332 return convertInternal(grammar::simplify::SimpleRulesRemover::remove(grammar::simplify::EpsilonRemover::remove(grammar)));
333}
334
335} /* namespace simplify */
336
337} /* namespace grammar */
338
ext::map
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
ext::map::at
R & at(const T &key, R &defaultValue)
Definition: map.hpp:163
ext::map::insert
std::pair< iterator, bool > insert(const T &key, const R &value)
Insert variant with explicit key and value parameters.
Definition: map.hpp:118
ext::pair
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
ext::set
Definition: set.hpp:44
ext::variant
Implementation of the variant class allowing to store any type of those listed in the template parame...
Definition: variant.hpp:98
ext::vector
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
ext::vector::insert
reverse_iterator insert(const_reverse_iterator pos, const T &value)
Inserts the value on position given by iterator pos.
Definition: vector.hpp:229
grammar::CFG
Context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy. Generates context free lang...
Definition: CFG.h:67
grammar::CNF
Chomsky normal form of a context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: CNF.h:66
grammar::EpsilonFreeCFG
Context free grammar without epsilon rules in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: EpsilonFreeCFG.h:65
grammar::GNF
Greibach normal form of a context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: GNF.h:65
grammar::LG
Context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy. Generates context free lang...
Definition: LG.h:67
grammar::LeftLG
Left linear grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages.
Definition: LeftLG.h:66
grammar::LeftRG
Left regular grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages...
Definition: LeftRG.h:70
grammar::RightLG
Right linear grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages...
Definition: RightLG.h:65
grammar::RightRG
Right regular grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular language...
Definition: RightRG.h:70
grammar::simplify::EpsilonRemover::remove
static grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > remove(const grammar::CFG< TerminalSymbolType, NonterminalSymbolType > &grammar)
Definition: EpsilonRemover.h:202
grammar::simplify::SimpleRulesRemover::remove
static grammar::CFG< TerminalSymbolType, NonterminalSymbolType > remove(const grammar::CFG< TerminalSymbolType, NonterminalSymbolType > &grammar)
Definition: SimpleRulesRemover.h:181
grammar::simplify::ToCNF
Definition: ToCNF.h:33
grammar::simplify::ToCNF::convert
static grammar::CNF< TerminalSymbolType, ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > convert(const grammar::CFG< TerminalSymbolType, NonterminalSymbolType > &grammar)
Definition: ToCNF.h:280
automaton::convert::grammar
return grammar
Definition: ToGrammarLeftRG.h:99
automaton::properties::i
int i
Definition: AllEpsilonClosure.h:118
automaton::simplify::result
for(const StateType &state :fsm.getStates()) renamingData.insert(std Rename::RenamedAutomaton< T > result(renamingData.at(fsm.getInitialState()))
Definition: Rename.h:253
common::createUnique
T createUnique(T object, const Alphabets &... alphabets)
Definition: createUnique.hpp:46
ext::make_pair
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
grammar::simplify::splitRule
void splitRule(ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > lhs, const ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > &rhs, grammar::CNF< TerminalSymbolType, ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > &result)
Definition: ToCNF.h:223
grammar::simplify::convertInternal
grammar::CNF< TerminalSymbolType, ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > convertInternal(const T &grammar)
Definition: ToCNF.h:243
grammar
Definition: ToAutomaton.h:24
Generated on Mon Dec 27 2021 10:21:51 for Algorithms Library Toolkit by doxygen 1.9.2