Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
AddRawRule.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <alib/set>
9#include <alib/map>
10#include <grammar/ContextFree/CFG.h>
11#include <grammar/ContextFree/EpsilonFreeCFG.h>
12#include <grammar/ContextFree/GNF.h>
13#include <grammar/ContextFree/CNF.h>
14#include <grammar/ContextFree/LG.h>
15#include <grammar/Regular/LeftLG.h>
16#include <grammar/Regular/LeftRG.h>
17#include <grammar/Regular/RightLG.h>
18#include <grammar/Regular/RightRG.h>
19
20#include <grammar/Grammar.h>
21
22namespace grammar {
23
27class AddRawRule {
28public:
39 template < class TerminalSymbolType, class NonterminalSymbolType >
40 static bool addRawRule ( LG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
41
45 template < class TerminalSymbolType, class NonterminalSymbolType >
46 static bool addRawRule ( GNF < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
47
51 template < class TerminalSymbolType, class NonterminalSymbolType >
52 static bool addRawRule ( EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
53
57 template < class TerminalSymbolType, class NonterminalSymbolType >
58 static bool addRawRule ( CNF < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
59
63 template < class TerminalSymbolType, class NonterminalSymbolType >
64 static bool addRawRule ( CFG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
65
69 template < class TerminalSymbolType, class NonterminalSymbolType >
70 static bool addRawRule ( LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
71
75 template < class TerminalSymbolType, class NonterminalSymbolType >
76 static bool addRawRule ( LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
77
81 template < class TerminalSymbolType, class NonterminalSymbolType >
82 static bool addRawRule ( RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
83
87 template < class TerminalSymbolType, class NonterminalSymbolType >
88 static bool addRawRule ( RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
89};
90
91template < class TerminalSymbolType, class NonterminalSymbolType >
92bool AddRawRule::addRawRule ( LG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide ) {
93 typename ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > >::iterator nonterminalPosition = rightHandSide.begin ( );
94
95 for ( ; nonterminalPosition != rightHandSide.end ( ); ++nonterminalPosition )
96 if ( grammar.getNonterminalAlphabet ( ).count ( * nonterminalPosition ) ) break;
97
98 if ( nonterminalPosition == rightHandSide.end ( ) ) {
99 ext::vector < TerminalSymbolType > rhs;
100
101 for ( ext::variant < TerminalSymbolType, NonterminalSymbolType > & symbol : rightHandSide )
102 rhs.push_back ( std::move ( symbol.template get < TerminalSymbolType > ( ) ) );
103
104 return grammar.addRule ( std::move ( leftHandSide ), std::move ( rhs ) );
105 } else {
106 ext::vector < TerminalSymbolType > rhs1;
107 ext::vector < TerminalSymbolType > rhs2;
108
109 std::for_each ( rightHandSide.begin ( ), nonterminalPosition, [ & ] ( ext::variant < TerminalSymbolType, NonterminalSymbolType > & symbol ) {
110 rhs1.push_back ( std::move ( symbol.template get < TerminalSymbolType > ( ) ) );
111 } );
112 std::for_each ( std::next ( nonterminalPosition ), rightHandSide.end ( ), [ & ] ( ext::variant < TerminalSymbolType, NonterminalSymbolType > & symbol ) {
113 rhs2.push_back ( std::move ( symbol.template get < TerminalSymbolType > ( ) ) );
114 } );
115
116 return grammar.addRule ( leftHandSide, ext::make_tuple ( std::move ( rhs1 ), std::move ( nonterminalPosition->template get < NonterminalSymbolType > ( ) ), std::move ( rhs2 ) ) );
117 }
118}
119
120template < class TerminalSymbolType, class NonterminalSymbolType >
121bool AddRawRule::addRawRule ( GNF < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide ) {
122 if ( rightHandSide.empty ( ) ) {
123 if ( leftHandSide != grammar.getInitialSymbol ( ) )
124 throw GrammarException ( "Illegal left hand side of epsilon rule" );
125
126 bool res = grammar.getGeneratesEpsilon ( );
127 grammar.setGeneratesEpsilon ( true );
128 return !res;
129 } else {
130 TerminalSymbolType first = std::move ( rightHandSide[0].template get < TerminalSymbolType > ( ) );
131
132 ext::vector < NonterminalSymbolType > rest;
133 std::for_each ( rightHandSide.begin ( ) + 1, rightHandSide.end ( ), [ & ] ( ext::variant < TerminalSymbolType, NonterminalSymbolType > & element ) {
134 rest.push_back ( std::move ( element.template get < NonterminalSymbolType > ( ) ) );
135 } );
136
137 return grammar.addRule ( std::move ( leftHandSide ), ext::make_pair ( std::move ( first ), std::move ( rest ) ) );
138 }
139}
140
141template < class TerminalSymbolType, class NonterminalSymbolType >
142bool AddRawRule::addRawRule ( EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide ) {
143 if ( rightHandSide.empty ( ) ) {
144 if ( leftHandSide != grammar.getInitialSymbol ( ) )
145 throw GrammarException ( "Illegal left hand side of epsilon rule" );
146
147 bool res = grammar.getGeneratesEpsilon ( );
148 grammar.setGeneratesEpsilon ( true );
149 return ! res;
150 } else {
151 return grammar.addRule ( std::move ( leftHandSide ), std::move ( rightHandSide ) );
152 }
153}
154
155template < class TerminalSymbolType, class NonterminalSymbolType >
156bool AddRawRule::addRawRule ( CNF < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide ) {
157 if ( rightHandSide.empty ( ) ) {
158 if ( leftHandSide != grammar.getInitialSymbol ( ) )
159 throw GrammarException ( "Illegal left hand side of epsilon rule" );
160
161 bool res = grammar.getGeneratesEpsilon ( );
162 grammar.setGeneratesEpsilon ( true );
163 return ! res;
164 } else if ( rightHandSide.size ( ) == 1 ) {
165 return grammar.addRule ( std::move ( leftHandSide ), std::move ( rightHandSide [ 0 ].template get < TerminalSymbolType > ( ) ) );
166 } else if ( rightHandSide.size ( ) == 2 ) {
167 return grammar.addRule ( std::move ( leftHandSide ), ext::make_pair ( std::move ( rightHandSide [ 0 ].template get < NonterminalSymbolType > ( ) ), std::move ( rightHandSide [ 1 ].template get < NonterminalSymbolType > ( ) ) ) );
168 } else {
169 throw GrammarException ( "Invalid right hand side" );
170 }
171}
172
173template < class TerminalSymbolType, class NonterminalSymbolType >
174bool AddRawRule::addRawRule ( CFG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide ) {
175 return grammar.addRule ( std::move ( leftHandSide ), std::move ( rightHandSide ) );
176}
177
178template < class TerminalSymbolType, class NonterminalSymbolType >
179bool AddRawRule::addRawRule ( LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide ) {
180 if ( rightHandSide.empty ( ) )
181 return grammar.addRule ( std::move ( leftHandSide ), ext::vector < TerminalSymbolType > { } );
182 else if ( grammar.getNonterminalAlphabet ( ).count ( rightHandSide [ 0 ] ) ) {
183 ext::vector < TerminalSymbolType > rhs;
184 std::for_each ( rightHandSide.begin ( ) + 1, rightHandSide.end ( ), [ & ] ( ext::variant < TerminalSymbolType, NonterminalSymbolType > & element ) {
185 rhs.push_back ( std::move ( element.template get < TerminalSymbolType > ( ) ) );
186 } );
187
188 return grammar.addRule ( std::move ( leftHandSide ), ext::make_pair ( std::move ( rightHandSide [ 0 ].template get < NonterminalSymbolType > ( ) ), std::move ( rhs ) ) );
189 } else {
190 ext::vector < TerminalSymbolType > rhs;
191 std::for_each ( rightHandSide.begin ( ), rightHandSide.end ( ), [ & ] ( ext::variant < TerminalSymbolType, NonterminalSymbolType > & element ) {
192 rhs.push_back ( std::move ( element.template get < TerminalSymbolType > ( ) ) );
193 } );
194
195 return grammar.addRule ( std::move ( leftHandSide ), std::move ( rhs ) );
196 }
197}
198
199template < class TerminalSymbolType, class NonterminalSymbolType >
200bool AddRawRule::addRawRule ( LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide ) {
201 if ( rightHandSide.empty ( ) ) {
202 if ( leftHandSide != grammar.getInitialSymbol ( ) )
203 throw GrammarException ( "Illegal left hand side of epsilon rule" );
204
205 bool res = grammar.getGeneratesEpsilon ( );
206 grammar.setGeneratesEpsilon ( true );
207 return res;
208 } else if ( rightHandSide.size ( ) == 1 ) {
209 return grammar.addRule ( std::move ( leftHandSide ), std::move ( rightHandSide [ 0 ].template get < TerminalSymbolType > ( ) ) );
210 } else if ( rightHandSide.size ( ) == 2 ) {
211 return grammar.addRule ( std::move ( leftHandSide ), ext::make_pair ( std::move ( rightHandSide [ 0 ].template get < NonterminalSymbolType > ( ) ), std::move ( rightHandSide [ 1 ].template get < TerminalSymbolType > ( ) ) ) );
212 } else {
213 throw GrammarException ( "Invalid right hand side" );
214 }
215}
216
217template < class TerminalSymbolType, class NonterminalSymbolType >
218bool AddRawRule::addRawRule ( RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide ) {
219 if ( rightHandSide.empty ( ) ) {
220 if ( leftHandSide != grammar.getInitialSymbol ( ) )
221 throw GrammarException ( "Illegal left hand side of epsilon rule" );
222
223 bool res = grammar.getGeneratesEpsilon ( );
224 grammar.setGeneratesEpsilon ( true );
225 return res;
226 } else if ( rightHandSide.size ( ) == 1 ) {
227 return grammar.addRule ( std::move ( leftHandSide ), std::move ( rightHandSide[0].template get < TerminalSymbolType > ( ) ) );
228 } else if ( rightHandSide.size ( ) == 2 ) {
229 return grammar.addRule ( std::move ( leftHandSide ), ext::make_pair ( std::move ( rightHandSide[0].template get < TerminalSymbolType > ( ) ), std::move ( rightHandSide[1].template get < NonterminalSymbolType > ( ) ) ) );
230 } else {
231 throw GrammarException ( "Invalid right hand side" );
232 }
233}
234
235template < class TerminalSymbolType, class NonterminalSymbolType >
236bool AddRawRule::addRawRule ( RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar, NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide ) {
237 if ( rightHandSide.empty ( ) )
238 return grammar.addRule ( std::move ( leftHandSide ), ext::vector < TerminalSymbolType > { } );
239 else if ( grammar.getNonterminalAlphabet ( ).count ( rightHandSide [ rightHandSide.size ( ) - 1 ] ) ) {
240 ext::vector < TerminalSymbolType > rhs;
241 std::for_each ( rightHandSide.begin ( ), rightHandSide.end ( ) - 1, [ & ] ( ext::variant < TerminalSymbolType, NonterminalSymbolType > & element ) {
242 rhs.push_back ( std::move ( element.template get < TerminalSymbolType > ( ) ) );
243 } );
244
245 return grammar.addRule ( std::move ( leftHandSide ), ext::make_pair ( std::move ( rhs ), std::move ( rightHandSide [ rightHandSide.size ( ) - 1 ].template get < NonterminalSymbolType > ( ) ) ) );
246 } else {
247 ext::vector < TerminalSymbolType > rhs;
248 std::for_each ( rightHandSide.begin ( ), rightHandSide.end ( ), [ & ] ( ext::variant < TerminalSymbolType, NonterminalSymbolType > & element ) {
249 rhs.push_back ( std::move ( element.template get < TerminalSymbolType > ( ) ) );
250 } );
251
252 return grammar.addRule ( std::move ( leftHandSide ), std::move ( rhs ) );
253 }
254}
255
256} /* namespace grammar */
257
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::begin
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: vector.hpp:125
ext::vector::end
auto end() &
Inherited behavior of end for non-const instance.
Definition: vector.hpp:155
grammar::AddRawRule
Definition: AddRawRule.h:27
grammar::AddRawRule::addRawRule
static bool addRawRule(LG< TerminalSymbolType, NonterminalSymbolType > &grammar, NonterminalSymbolType leftHandSide, ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > rightHandSide)
Definition: AddRawRule.h:92
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::GrammarException
Definition: GrammarException.h:15
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
automaton::simplify::res
return res
Definition: MinimizeByPartitioning.h:145
ext::make_tuple
constexpr auto make_tuple(Elements &&... args)
Helper of extended tuple construction. The tuple is constructed from values pack, types are deduced.
Definition: tuple.hpp:203
ext::make_pair
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
grammar
Definition: ToAutomaton.h:24
Generated on Mon Dec 27 2021 10:21:53 for Algorithms Library Toolkit by doxygen 1.9.2