Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
First.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <alib/vector>
9#include <alib/set>
10#include <alib/variant>
11
12#include <grammar/Grammar.h>
13#include <grammar/RawRules.h>
14
15namespace grammar {
16
17namespace parsing {
18
19class First {
20 template < class TerminalSymbolType, class NonterminalSymbolType >
22
23 template < class TerminalSymbolType, class NonterminalSymbolType >
25
26public:
27 template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
29
30 template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
32};
33
34template < class TerminalSymbolType, class NonterminalSymbolType >
36 // 1. FIRST(\varepsilon) = { \varepsilon }
37 if ( rhs.empty ( ) ) {
39 }
40
41 // 2. FIRST(a) = { a } forall a \in T
42 else if ( terminals.count ( rhs[0] ) ) {
43 return { ext::vector < TerminalSymbolType > { rhs[0].template get < TerminalSymbolType > ( ) } };
44 }
45
46 // 4. FIRST(A \alpha) = first(A) if A \in N and \varepsilon \notin first(A)
47 else if ( nonterminals.count ( rhs[0] ) && !firstOfNonterminal.find ( rhs[0] )->second.count ( ext::vector < TerminalSymbolType > ( ) ) ) {
48 return firstOfNonterminal.find ( rhs[0] )->second;
49 }
50
51 // 5. FIRST(A \alpha) = (first(A) - \varepsilon) \cup FIRST(\alpha) if A \in N and \varepsilon \in first(A)
52 else if ( nonterminals.count ( rhs[0] ) && firstOfNonterminal.find ( rhs[0] )->second.count ( ext::vector < TerminalSymbolType > ( ) ) ) {
53 ext::set < ext::vector < TerminalSymbolType > > res = firstOfNonterminal.find ( rhs[0] )->second;
55
56 ext::set < ext::vector < TerminalSymbolType > > next = first ( terminals, nonterminals, firstOfNonterminal, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > ( rhs.begin ( ) + 1, rhs.end ( ) ) );
57 res.insert ( next.begin ( ), next.end ( ) );
58 return res;
59 } else {
60 throw exception::CommonException ( "Cant be reached" );
61 }
62}
63
64template < class TerminalSymbolType, class NonterminalSymbolType >
66 /*
67 *
68 * 1. foreach A \in N: first(A) = \emptyset
69 * 2. foreach A \rightarrow \alpha:
70 * first(A) = first(A) \cup FIRST(\alpha)
71 * 3. repeat step 2 if at least one set first(A) has changed
72 *
73 */
75
76 for ( const NonterminalSymbolType & nonterminal : nonterminals )
77 firstOfNonterminal1[nonterminal];
78
80
81 do {
82 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & rule : rules )
84 ext::set < ext::vector < TerminalSymbolType > > newFirst = first ( terminals, nonterminals, firstOfNonterminal1, rhs );
85 firstOfNonterminal2[rule.first].insert ( newFirst.begin ( ), newFirst.end ( ) );
86 }
87
88 if ( firstOfNonterminal1 == firstOfNonterminal2 )
89 break;
90
91 firstOfNonterminal1 = std::move ( firstOfNonterminal2 );
92 firstOfNonterminal2.clear ( );
93
94 } while ( true );
95
96 return firstOfNonterminal1;
97}
98
99template < class T, class TerminalSymbolType, class NonterminalSymbolType >
101 auto rawRules = grammar::RawRules::getRawRules ( grammar );
102
103 ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > firstNt = first ( grammar.getTerminalAlphabet ( ), grammar.getNonterminalAlphabet ( ), rawRules );
104
106
107 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & rule : rawRules )
109 res.insert ( std::make_pair ( rhs, first ( grammar.getTerminalAlphabet ( ), grammar.getNonterminalAlphabet ( ), firstNt, rhs ) ) );
110
111 return res;
112}
113
114template < class T, class TerminalSymbolType, class NonterminalSymbolType >
116 auto rawRules = grammar::RawRules::getRawRules ( grammar );
117
118 ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > firstNt = first ( grammar.getTerminalAlphabet ( ), grammar.getNonterminalAlphabet ( ), rawRules );
119
120 return first ( grammar.getTerminalAlphabet ( ), grammar.getNonterminalAlphabet ( ), firstNt, rhs );
121}
122
123} /* namespace parsing */
124
125} /* namespace grammar */
126
Basic exception from which all other exceptions are derived.
Definition: CommonException.h:21
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
std::pair< iterator, bool > insert(const T &key, const R &value)
Insert variant with explicit key and value parameters.
Definition: map.hpp:118
Definition: set.hpp:44
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: set.hpp:99
auto end() &
Inherited behavior of end for non-const instance.
Definition: set.hpp:129
Implementation of the variant class allowing to store any type of those listed in the template parame...
Definition: variant.hpp:98
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
static ext::map< NonterminalSymbolType, ext::set< ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > > getRawRules(const LG< TerminalSymbolType, NonterminalSymbolType > &grammar)
Definition: RawRules.h:92
Definition: First.h:19
return res
Definition: MinimizeByPartitioning.h:145
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
Definition: ToAutomaton.h:24