1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
#ifndef CTLL__PARSER__HPP
#define CTLL__PARSER__HPP
#include "fixed_string.hpp"
#include "list.hpp"
#include "grammars.hpp"
#include "actions.hpp"
#ifndef CTLL_IN_A_MODULE
#include <limits>
#endif
namespace ctll {
enum class decision {
reject,
accept,
undecided
};
struct placeholder { };
template <size_t> using index_placeholder = placeholder;
#if CTLL_CNTTP_COMPILER_CHECK
template <typename Grammar, ctll::fixed_string input, typename ActionSelector = empty_actions, bool IgnoreUnknownActions = false> struct parser { // in c++20
#else
template <typename Grammar, const auto & input, typename ActionSelector = empty_actions, bool IgnoreUnknownActions = false> struct parser {
#endif
#ifdef __GNUC__ // workaround to GCC bug
#if CTLL_CNTTP_COMPILER_CHECK
static constexpr auto _input = input; // c++20 mode
#else
static constexpr auto & _input = input; // c++17 mode
#endif
#else
static constexpr auto _input = input; // everyone else
#endif
using Actions = ctll::conditional<IgnoreUnknownActions, ignore_unknown<ActionSelector>, identity<ActionSelector>>;
using grammar = augment_grammar<Grammar>;
template <size_t Pos, typename Stack, typename Subject, decision Decision> struct results {
static constexpr bool is_correct = Decision == decision::accept;
constexpr inline CTLL_FORCE_INLINE operator bool() const noexcept {
return is_correct;
}
#ifdef __GNUC__ // workaround to GCC bug
#if CTLL_CNTTP_COMPILER_CHECK
static constexpr auto _input = input; // c++20 mode
#else
static constexpr auto & _input = input; // c++17 mode
#endif
#else
static constexpr auto _input = input; // everyone else
#endif
using output_type = Subject;
static constexpr size_t position = Pos;
constexpr auto operator+(placeholder) const noexcept {
if constexpr (Decision == decision::undecided) {
// parse for current char (RPos) with previous stack and subject :)
return parser<Grammar, _input, ActionSelector, IgnoreUnknownActions>::template decide<Pos, Stack, Subject>({}, {});
} else {
// if there is decision already => just push it to the end of fold expression
return *this;
}
}
};
template <size_t Pos> static constexpr auto get_current_term() noexcept {
if constexpr (Pos < input.size()) {
constexpr auto value = input[Pos];
if constexpr (value <= static_cast<decltype(value)>((std::numeric_limits<char>::max)())) {
return term<static_cast<char>(value)>{};
} else {
return term<value>{};
}
} else {
// return epsilon if we are past the input
return epsilon{};
}
}
template <size_t Pos> static constexpr auto get_previous_term() noexcept {
if constexpr (Pos == 0) {
// there is no previous character on input if we are on start
return epsilon{};
} else if constexpr ((Pos-1) < input.size()) {
constexpr auto value = input[Pos-1];
if constexpr (value <= static_cast<decltype(value)>((std::numeric_limits<char>::max)())) {
return term<static_cast<char>(value)>{};
} else {
return term<value>{};
}
} else {
return epsilon{};
}
}
// if rule is accept => return true and subject
template <size_t Pos, typename Terminal, typename Stack, typename Subject>
static constexpr auto move(ctll::accept, Terminal, Stack, Subject) noexcept {
return typename parser<Grammar, _input, ActionSelector, IgnoreUnknownActions>::template results<Pos, Stack, Subject, decision::accept>();
}
// if rule is reject => return false and subject
template <size_t Pos, typename Terminal, typename Stack, typename Subject>
static constexpr auto move(ctll::reject, Terminal, Stack, Subject) noexcept {
return typename parser<Grammar, _input, ActionSelector, IgnoreUnknownActions>::template results<Pos, Stack, Subject, decision::reject>();
}
// if rule is pop_input => move to next character
template <size_t Pos, typename Terminal, typename Stack, typename Subject>
static constexpr auto move(ctll::pop_input, Terminal, Stack, Subject) noexcept {
return typename parser<Grammar, _input, ActionSelector, IgnoreUnknownActions>::template results<Pos+1, Stack, Subject, decision::undecided>();
}
// if rule is string => push it to the front of stack
template <size_t Pos, typename... Content, typename Terminal, typename Stack, typename Subject>
static constexpr auto move(push<Content...> string, Terminal, Stack stack, Subject subject) noexcept {
return decide<Pos>(push_front(string, stack), subject);
}
// if rule is epsilon (empty string) => continue
template <size_t Pos, typename Terminal, typename Stack, typename Subject>
static constexpr auto move(epsilon, Terminal, Stack stack, Subject subject) noexcept {
return decide<Pos>(stack, subject);
}
// if rule is string with current character at the beginning (term<V>) => move to next character
// and push string without the character (quick LL(1))
template <size_t Pos, auto V, typename... Content, typename Stack, typename Subject>
static constexpr auto move(push<term<V>, Content...>, term<V>, Stack stack, Subject) noexcept {
constexpr auto local_input = input;
return typename parser<Grammar, local_input, ActionSelector, IgnoreUnknownActions>::template results<Pos+1, decltype(push_front(list<Content...>(), stack)), Subject, decision::undecided>();
}
// if rule is string with any character at the beginning (compatible with current term<T>) => move to next character
// and push string without the character (quick LL(1))
template <size_t Pos, auto V, typename... Content, auto T, typename Stack, typename Subject>
static constexpr auto move(push<anything, Content...>, term<T>, Stack stack, Subject) noexcept {
constexpr auto local_input = input;
return typename parser<Grammar, local_input, ActionSelector, IgnoreUnknownActions>::template results<Pos+1, decltype(push_front(list<Content...>(), stack)), Subject, decision::undecided>();
}
// decide if we need to take action or move
template <size_t Pos, typename Stack, typename Subject> static constexpr auto decide(Stack previous_stack, Subject previous_subject) noexcept {
// each call means we pop something from stack
auto top_symbol = decltype(ctll::front(previous_stack, empty_stack_symbol()))();
// gcc pedantic warning
[[maybe_unused]] auto stack = decltype(ctll::pop_front(previous_stack))();
// in case top_symbol is action type (apply it on previous subject and get new one)
if constexpr (std::is_base_of_v<ctll::action, decltype(top_symbol)>) {
auto subject = Actions::apply(top_symbol, get_previous_term<Pos>(), previous_subject);
// in case that semantic action is error => reject input
if constexpr (std::is_same_v<ctll::reject, decltype(subject)>) {
return typename parser<Grammar, _input, ActionSelector, IgnoreUnknownActions>::template results<Pos, Stack, Subject, decision::reject>();
} else {
return decide<Pos>(stack, subject);
}
} else {
// all other cases are ordinary for LL(1) parser
auto current_term = get_current_term<Pos>();
auto rule = decltype(grammar::rule(top_symbol,current_term))();
return move<Pos>(rule, current_term, stack, previous_subject);
}
}
// trampolines with folded expression
template <typename Subject, size_t... Pos> static constexpr auto trampoline_decide(Subject, std::index_sequence<Pos...>) noexcept {
// parse everything for first char and than for next and next ...
// Pos+1 is needed as we want to finish calculation with epsilons on stack
auto v = (decide<0, typename grammar::start_stack, Subject>({}, {}) + ... + index_placeholder<Pos+1>());
return v;
}
template <typename Subject = empty_subject> static constexpr auto trampoline_decide(Subject subject = {}) noexcept {
// there will be no recursion, just sequence long as the input
return trampoline_decide(subject, std::make_index_sequence<input.size()>());
}
template <typename Subject = empty_subject> using output = decltype(trampoline_decide<Subject>());
template <typename Subject = empty_subject> static inline constexpr bool correct_with = trampoline_decide<Subject>();
};
} // end of ctll namespace
#endif
|
