Teuchos - Trilinos Tools Package Version of the Day
Loading...
Searching...
No Matches
Teuchos_FiniteAutomaton.hpp
1#ifndef TEUCHOS_FINITE_AUTOMATON_HPP
2#define TEUCHOS_FINITE_AUTOMATON_HPP
3
4#include <Teuchos_TableDecl.hpp>
5#include <iosfwd>
6#include <set>
7#include <stdexcept>
8
9namespace Teuchos {
10
11#ifdef HAVE_TEUCHOSCORE_CXX11
12extern template struct Table<int>;
13#endif
14
15/* This is basically a weird mix between a DFA and
16 an NFA-epsilon. It is really a DFA that can have two extra
17 epsilon symbols that it accepts transitions with.
18 We can simulate epsilon-transitions to multiple new
19 states by making trees of nodes connected by
20 epsilon-transitions.
21
22 by convention, the start state is state 0
23 */
24struct FiniteAutomaton {
25 Table<int> table;
26 std::vector<int> accepted_tokens;
27 bool is_deterministic;
28 FiniteAutomaton() {}
29 FiniteAutomaton(int nsymbols_init, bool is_deterministic_init, int nstates_reserve);
30 void swap(FiniteAutomaton& other);
31};
32
33/* NOTE: this is only needed by Teuchos::any to support its non-standard operator== */
34inline bool operator==(FiniteAutomaton const&, FiniteAutomaton const&) {
35 return false;
36}
37
38inline void swap(FiniteAutomaton& a, FiniteAutomaton& b) { a.swap(b); }
39
40int get_nstates(FiniteAutomaton const& fa);
41int get_nsymbols(FiniteAutomaton const& fa);
42bool get_determinism(FiniteAutomaton const& fa);
43int get_epsilon0(FiniteAutomaton const& fa);
44int get_epsilon1(FiniteAutomaton const& fa);
45int add_state(FiniteAutomaton& fa);
46void add_transition(FiniteAutomaton& fa, int from_state, int at_symbol, int to_state);
47void add_accept(FiniteAutomaton& fa, int state, int token);
48void remove_accept(FiniteAutomaton& fa, int state);
49int step(FiniteAutomaton const& fa, int state, int symbol);
50int accepts(FiniteAutomaton const& fa, int state);
51int get_nsymbols_eps(FiniteAutomaton const& fa);
52void append_states(FiniteAutomaton& fa, FiniteAutomaton const& other);
53
54void make_single_nfa(FiniteAutomaton& result, int nsymbols, int symbol, int token = 0);
55void make_set_nfa(FiniteAutomaton& result, int nsymbols, std::set<int> const& accepted, int token = 0);
56void make_range_nfa(FiniteAutomaton& result, int nsymbols, int range_start, int range_end, int token = 0);
57void unite(FiniteAutomaton& result, FiniteAutomaton const& a, FiniteAutomaton const& b);
58void concat(FiniteAutomaton& result, FiniteAutomaton const& a, FiniteAutomaton const& b, int token = 0);
59void plus(FiniteAutomaton& result, FiniteAutomaton const& a, int token = 0);
60void maybe(FiniteAutomaton& result, FiniteAutomaton const& a, int token = 0);
61void star(FiniteAutomaton& result, FiniteAutomaton const& a, int token = 0);
62void make_deterministic(FiniteAutomaton& result, FiniteAutomaton& nfa);
63void simplify_once(FiniteAutomaton& result, FiniteAutomaton const& fa);
64void simplify(FiniteAutomaton& result, FiniteAutomaton const& fa);
65
66void add_char_transition(FiniteAutomaton& fa, int from_state, char at_char, int to_state);
67bool is_symbol(char c);
68int get_symbol(char c);
69char get_char(int symbol);
70void make_char_set_nfa(FiniteAutomaton& result, std::set<char> const& accepted, int token = 0);
71void make_char_range_nfa(FiniteAutomaton& result, char range_start, char range_end, int token = 0);
72void make_char_single_nfa(FiniteAutomaton& result, char symbol_char, int token = 0);
73void negate_set(std::set<char>& result, std::set<char> const& s);
74
75std::ostream& operator<<(std::ostream& os, FiniteAutomaton const& fa);
76
77}
78
79#endif
The Teuchos namespace contains all of the classes, structs and enums used by Teuchos,...