loom

1
/*
2
MIT License
3

4
Copyright (c) 2021 МГТУ им. Н.Э. Баумана, кафедра ИУ-6, Михаил Фетисов,
5

6
https://bmstu.codes/lsx/simodo/loom
7
*/
8

9
#include "simodo/interpret/builtins/hosts/fuze/ParsingTableBuilder_abstract.h"
10

11
#include "simodo/inout/convert/functions.h"
12
#include "simodo/inout/format/fmt.h"
13

14
#include <algorithm>
15
#include <cassert>
16

17
namespace simodo::interpret::builtins
18
{
19
    bool ParsingTableBuilder_abstract::build(const std::vector<parser::GrammarRuleTokens> &rules, const inout::Token &main_rule)
20
    {
21
        if (rules.empty())
22
        {
23
            _m.reportError( inout::null_location, 
24
                            inout::fmt("Не заданы правила грамматики '%1'")
25
                            .arg(_grammar_name));
26
            return false;
27
        }
28

29
        inout::Token main_production = (main_rule.token().empty() ? rules[0].production : main_rule);
30

31
        // Добавляем обобщённое правило
32
        std::vector<inout::Token> pattern {
33
            { inout::LexemeType::Compound, main_production.token(), main_production.location() },
34
            { inout::LexemeType::Empty, u"", main_production.location() },
35
        };
36
        _rules.push_back({ inout::Token { inout::LexemeType::Compound, main_production.token()+u"'", main_production.location() },
37
                        pattern,
38
                        ast::Node(),
39
                        parser::RuleReduceDirection::Undefined });
40

41
        // Вытягиваем из заданных правил грамматики только те, что относятся к основному правилу
42
        if(!extractRules(rules, main_production.token()))
43
            return false;
44

45
        if (_rules.size() <= 1)
46
        {
47
            _m.reportError( main_production.makeLocation(_files),
48
                            inout::fmt("Не удалось извлечь правила грамматики '%1'")
49
                            .arg(_grammar_name));
50
            return false;
51
        }
52

53
        // Заполняем индекс продукций для правил грамматики
54
        for(size_t i=0; i < _rules.size(); ++i)
55
            _production_index.emplace(_rules[i].production.token(),i);
56

57
        // Заполняем индекс символов из образца для правил грамматики
58
        for(size_t i=0; i < _rules.size(); ++i)
59
            for(const inout::Lexeme & s : _rules[i].pattern)
60
                if (s.type() == inout::LexemeType::Compound)
61
                {
62
                    // Повторы пар (s, индекс на правило) нам не нужны - проверяем на наличие
63
                    auto   range = _pattern_index.equal_range(s.lexeme());
64
                    auto & it    = range.first;
65
                    for(; it != range.second; ++it)
66
                        if (it->second == i)
67
                            break;
68

69
                    if (it == range.second)
70
                        _pattern_index.emplace(s.lexeme(),i);
71
                }
72

73
        // Проверяем какие правила не были собраны (не используются)
74
        if (_rules.size() <= rules.size())
75
            for(const parser::GrammarRuleTokens & r : rules)
76
                if (_production_index.end() == _production_index.find(r.production.token()))
77
                    _m.reportWarning(r.production.makeLocation(_files),
78
                                inout::fmt("Нетерминал '%1' не используется в грамматике '%2'")
79
                                .arg(r.production.token())
80
                                .arg(_grammar_name));
81

82
        // Проверяем, что все нетерминалы имеют продукции
83
        bool ok = true;
84
        for(const auto & [p,i] : _pattern_index)
85
        {
86
            std::u16string last;
87
            if (last != p)
88
            {
89
                if (_production_index.find(p) == _production_index.end())
90
                {
91
                    assert(i < _rules.size());
92
                    size_t j = 0;
93
                    for(; j < _rules[i].pattern.size(); ++j)
94
                        if (p == _rules[i].pattern[j].token())
95
                            break;
96

97
                    inout::Token t = (j < _rules[i].pattern.size()) ? _rules[i].pattern[j] : _rules[i].production;
98

99
                    _m.reportError(t.makeLocation(_files),
100
                                inout::fmt("Нетерминал '%1' не имеет продукции для грамматики '%2'")
101
                                .arg(p)
102
                                .arg(_grammar_name));
103
                    ok = false;
104
                }
105
                last = p;
106
            }
107
        }
108
        if (!ok)
109
            return false;
110

111
        // Копируем _rules в _g.rules для работы наследуемого кода (всё равно нужно копировать)
112
        for(const parser::GrammarRuleTokens & r : _rules)
113
        {
114
            std::vector<inout::Lexeme> p;
115

116
            for(const inout::Token & t : r.pattern)
117
                p.push_back(t);
118

119
            _g.rules.emplace_back(r.production.token(), p, r.reduce_action, r.reduce_direction);
120
        }
121

122
        // Заполняем перечень состояний автомата разбора
123
        fillStateTable();
124

125
        // Вычисляем границу для значений таблицы разбора
126
        assert(std::max(_g.rules.size(),_g.states.size()) < UINT32_MAX/5);
127
        _g.value_bound = static_cast<parser::Fsm_value_t>(std::max(_g.rules.size(),_g.states.size())) + 1;
128

129
        // Заполняем значения колонок
130
        fillColumns();
131

132
        // Определяем "вычисляемые" параметры лексики
133
        fillLexemeParameters(_g);
134

135
        // Вычисляем границу для ключа таблицы разбора
136
        assert(_g.columns.size()*_g.states.size() < UINT32_MAX/2);
137
        _g.key_bound = static_cast<parser::Fsm_key_t>(_g.columns.size()) + 1;
138

139
        // Формируем таблицу разбора
140
        if (!fillParseTable())
141
            return false;
142

143
        // Проверяем полноту наполнения
144
        return checkCompleteness();
145
    }
146

147
    bool ParsingTableBuilder_abstract::extractRules(const std::vector<parser::GrammarRuleTokens> &rules, std::u16string production)
148
    {
149
        size_t rule_no = 0;
150
        size_t patt_no = 0;
151

152
        _rules.reserve(rules.size());
153

154
        while(!production.empty())
155
        {
156
            // Вытягиваем все связанные с заданной продукцией правила
157
            for(const parser::GrammarRuleTokens & r : rules)
158
                if (r.production.token() == production)
159
                {
160
                    // Убеждаемся, что это правило не дубль
161
                    size_t i = 0;
162
                    for(; i < _rules.size(); ++i)
163
                    {
164
                        if (_rules[i].production.token() != production)
165
                            continue;
166

167
                        if (_rules[i].pattern.size() != r.pattern.size())
168
                            continue;
169

170
                        size_t j = 0;
171
                        for(; j < _rules[i].pattern.size(); ++j)
172
                            if (_rules[i].pattern[j] != r.pattern[j])
173
                                break;
174

175
                        if (j == _rules[i].pattern.size())
176
                            break;
177
                    }
178
                    if (i != _rules.size())
179
                        continue;
180

181
                    // Добавляем правило в грамматику
182
                    _rules.push_back(r);
183
                }
184

185
            production = u"";
186

187
            // Специально избавляемся от рекурсии, чтобы упорядочить перечень правил по продукциям
188
            do
189
            {
190
                patt_no ++;
191

192
                if (patt_no == _rules[rule_no].pattern.size())
193
                {
194
                    rule_no ++;
195

196
                    if (rule_no == _rules.size())
197
                        break;
198

199
                    patt_no = 0;
200
                }
201

202
                assert(!_rules[rule_no].pattern.empty());
203

204
                if (_rules[rule_no].pattern[patt_no].type() == inout::LexemeType::Compound)
205
                {
206
                    // Сначала убеждаемся, что этого нетерминала нет в нашем списке (оптимизируем)
207
                    const std::u16string & att_prod = _rules[rule_no].pattern[patt_no].lexeme();
208

209
                    size_t i=1;
210
                    for(; i < _rules.size(); ++i)
211
                        if (_rules[i].production.token() == att_prod)
212
                            break;
213

214
                    // Не нашли, значит обрабатываем
215
                    if (i == _rules.size())
216
                        production = att_prod;
217
                }
218
            }
219
            while(production.empty());
220
        }
221

222
        return true;
223
    }
224

225
    void ParsingTableBuilder_abstract::fillColumns() const
226
    {
227
        // Сначала заполняются терминальные символы грамматики
228
        for(const parser::GrammarRule & r : _g.rules)
229
            for(const inout::Lexeme & s : r.pattern)
230
                if (s.type() != inout::LexemeType::Compound)
231
                    if (find(_g.columns.begin(),_g.columns.end(),s) == _g.columns.end())
232
                        _g.columns.push_back(s);
233

234
        // Затем идут нетерминалы
235
        _g.first_compound_index = _g.columns.size();
236

237
        for(const parser::GrammarRule &r : _g.rules)
238
            for(const inout::Lexeme & s : r.pattern)
239
                if (s.type() == inout::LexemeType::Compound)
240
                    if (find(_g.columns.begin(),_g.columns.end(),s) == _g.columns.end())
241
                        _g.columns.push_back(s);
242
    }
243

244
    bool ParsingTableBuilder_abstract::checkCompleteness()
245
    {
246
        bool ok = true;
247

248
        // Проверяем, что все приведения попали в таблицу
249
        // (правило 0 не должно участвовать)
250
        for(size_t i=1; i < _g.rules.size(); ++i)
251
        {
252
            bool found = false;
253
            for(const auto & [key,value] : _g.parse_table)
254
            {
255
                parser::FsmActionType action   = _g.unpackFsmAction(value);
256
                size_t                location = _g.unpackFsmLocation(value);
257

258
                if (action == parser::FsmActionType::Reduce)
259
                    if (location == i)
260
                    {
261
                        found = true;
262
                        break;
263
                    }
264
            }
265
            if (!found)
266
            {
267
                assert(i < _rules.size());
268
                _m.reportFatal( _rules[i].production.makeLocation(_files),
269
                                inout::fmt("Правило %1 грамматики '%2' не участвует в разборе.")
270
                                .arg(i)
271
                                .arg(_grammar_name));
272
                ok = false;
273
            }
274
        }
275

276
        return ok || !_strict_rule_consistency;
277
    }
278

279
}