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_SLR.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
    // По идее - этот вариант должен быть правильной реализацией SLR, т.к.
20
    // просто поправлена неточность старого алгоритма.
21
    #define SLR_IMPROVED_1
22

23

24
    void ParsingTableBuilder_SLR::fillStateTable()
25
    {
26
        parser::FsmState_t state;
27
        state.emplace_back(parser::FsmStatePosition(0,0));
28
        _g.states.emplace_back(state);
29

30
        fillStateInfo(0);
31

32
        _g.build_method = parser::TableBuildMethod::SLR;
33
    }
34

35
    void ParsingTableBuilder_SLR::fillStateInfo(size_t state_no)
36
    {
37
        // Пример грамматики для дальнейшего пояснения:
38
        // E' = E EOF               // правило 0 (создаётся искусственно)
39
        // E = E "+" T | T          // правила 1 и 2
40
        // T = T "*" F | F          // правила 3 и 4
41
        // F = "(" E ")" | WORD     // правила 5 и 6
42

43
        // Функция вызывается, когда уже создано состояние для первой основной позиции
44
        // Нужно добавить остальные основные позиции, согласно следующему критерию:
45
        // Состояние НКА соответствует одинаковым позициям правил.
46
        // Одинаковость позиций определяется тем, что все основные позиции состояния
47
        // находятся после одного и того же нетерминала
48
        // Например, если текущей позицией является начало последнего символа в шаблоне первого
49
        // правила (E = E "+" .T), то находим все замыкания для текущей позиции.
50
        // В замыкания (closure) попадают все правила, в которых есть начало символа
51
        // текущей позиции (pos) с учётом рекурсивного нисходящего разворачивания правил.
52
        // Другими словами, мы должны учесть, какие символы грамматики (терминалы и нетерминалы)
53
        // могут встретиться на данной позиции, что определяется раскрытием текущего символа
54
        // (если он нетерминал)
55
        // Например, если текущей позицией является начало последнего символа в шаблоне первого
56
        // правила (E = E "+" .T), то замыканиями являются следующие позиции:
57
        // E = .T
58
        // T = .T "*" F
59
        // T = .F
60
        // F = ."(" E ")"
61
        // F = .WORD
62

63
        /// \attention Код данного метода (как и всего данного класса) выполняет активную модификацию
64
        /// структур грамматики, заданной в параметре _g. Поэтому, крайне не желательно создавать
65
        /// ссылки на члены класса _g. Массивы могут реаллокироваться. Будьте осторожны.
66

67
        assert(state_no < _g.states.size());
68
        size_t position_initial_count = _g.states[state_no].size(); // размер массива в цикле не является инвариантом (мы его меняем)
69

70
        for(size_t i=0; i < position_initial_count; ++i)
71
        {
72
            // Точно известно, что основные позиции состояния добавляются в начало
73
            if (!_g.states[state_no][i].is_main)
74
                break;
75

76
            size_t rno = _g.states[state_no][i].rule_no;
77
            size_t pos = _g.states[state_no][i].position;
78

79
            assert(rno < _g.rules.size());
80
            const parser::GrammarRule & rule = _g.rules[rno];   // Текущее правило
81

82
            // Находим замыкания и добавляем в заданное состояние как не основные позиции
83
            if (pos < rule.pattern.size())
84
                fillPreClosure(state_no, rule.pattern[pos]);
85
        }
86

87
        // Текущее состояние создано, готовим следующие состояния для основных правил
88
        // Проходим по всем позициям нашего состояния и для каждого перехода
89
        // создаем следующее состояние. Переходы для одинаковых символов грамматики объединяем,
90
        // создавая в новом состоянии соотв-щие основные позиции. Проставляем значение next для позиций
91

92
        for(size_t i_pos_in_state=0; i_pos_in_state < _g.states[state_no].size(); ++i_pos_in_state)
93
        {
94
            size_t current_rno = _g.states[state_no][i_pos_in_state].rule_no;
95
            size_t current_pos = _g.states[state_no][i_pos_in_state].position;
96

97
            assert(current_rno < _g.rules.size());
98
            const parser::GrammarRule & current_rule = _g.rules[current_rno];
99

100
            // Важно убедиться, что есть куда переходить
101
            if (current_pos == current_rule.pattern.size())
102
                continue;
103
            // и эта позиция не использована ранее в этом же цикле (не установлено состояние перехода)
104
            if (_g.states[state_no][i_pos_in_state].next_state_no > 0)
105
                continue;
106

107
            assert(current_pos < current_rule.pattern.size());
108
            const inout::Lexeme & current_symbol = current_rule.pattern[current_pos];
109

110
            // Для символа конца не создаётся новых состояний
111
            if (current_symbol.type() == inout::LexemeType::Empty )
112
                continue;
113

114
            // Номер нового состояния будет отличаться от 0
115
            uint16_t new_state_no = 0;
116

117
            // Важно отметить, что основные состояния (FsmStatePosition::is_main == true) уникальны,
118
            // в то время, как не основные являются сведёнными под совпадающий входной символ
119
            // и не являются уникальными (см. fillPreClosure)
120

121
            // Убеждаемся, что нужного основного состояния ещё нет
122
            uint16_t find_state = findMainPosition(current_rno, current_pos+1);
123
            uint16_t next_state_no;
124
            if (find_state == 0) // (совпадение с нулевым состоянием невозможно, т.к. оно создаётся искусственно)
125
            {
126
                // Точного совпадения не нашли
127
                // Создаем следующее состояние и нашу следующую основную позицию
128
                next_state_no = static_cast<uint16_t>(_g.states.size());
129
                _g.states[state_no][i_pos_in_state].next_state_no = new_state_no = next_state_no;
130

131
                parser::FsmState_t new_state;
132
                new_state.emplace_back(current_rno, current_pos+1, true, 0);
133
                _g.states.emplace_back(new_state);
134
            }
135
            else
136
            {
137
                next_state_no = find_state;
138
                _g.states[state_no][i_pos_in_state].next_state_no = find_state;
139
            }
140

141
            // Находим позицию с тем же переходным символом
142
            for(size_t i_pos_add=i_pos_in_state+1; i_pos_add < _g.states[state_no].size(); ++i_pos_add)
143
            {
144
                size_t add_rno = _g.states[state_no][i_pos_add].rule_no;
145
                size_t add_pos = _g.states[state_no][i_pos_add].position;
146

147
                assert(add_rno < _g.rules.size());
148
                const parser::GrammarRule & add_rule = _g.rules[add_rno];
149
    #ifdef SLR_IMPROVED_1
150
                // По идее - этот вариант должен быть правильной реализацией SLR, т.к.
151
                // просто поправлена неточность старого алгоритма.
152
                if (add_pos < add_rule.pattern.size())
153
                    if (current_symbol == add_rule.pattern[add_pos])
154
                    {
155
                        // Проверяем, что такой основной позиции ещё нет
156
                        bool found = false;
157
                        auto it = _g.states[next_state_no].begin();
158
                        for(; it != _g.states[next_state_no].end() && it->is_main; ++it)
159
                            if (it->rule_no == add_rno)
160
                            {
161
                                found = true;
162
                                break;
163
                            }
164
                        // Добавляем основную позицию
165
                        _g.states[state_no][i_pos_add].next_state_no = next_state_no;
166
                        if (!found)
167
                        {
168
                            // Позиция добавляется либо после последней основной, либо в конец списка, если неосновных нет
169
                            _g.states[next_state_no].emplace(it, add_rno,add_pos+1,true,0);
170
                            new_state_no = next_state_no;
171
                        }
172
                        _g.states[state_no][i_pos_add].next_state_no = next_state_no;
173
                    }
174
    #else
175
                if (add_pos < add_rule.pattern.size())
176
                    if (current_symbol == add_rule.pattern[add_pos])
177
                    {
178
                        _g.states[state_no][i_pos_add].next_state_no = next_state_no;
179

180
                        if (find_state == 0)
181
                        {
182
                            // Добавляем похожую позицию как основную для нового состояния
183
                            _g.states[next_state_no].emplace_back(add_rno,add_pos+1,true,0);
184
                        }
185
                        else if (add_pos == add_rule.pattern.size()-1)
186
                        {
187
                            // Данный блок кода добавлен исключительно для того,
188
                            // чтобы выявлять неоднозначности грамматики типа R-R,
189
                            // которые в противном случае остаются непроявленными.
190
                            // Кроме того, дерево переходов состояния становиться согласованным
191
                            // и полным, а ошибку можно увидеть визуально.
192
                            // Сами ошибки выявляются чуть позже
193
                            // (см. GrammarBuilder_SLR::fillParseTable и GrammarBuilder_SLR::insertValue)
194
                            size_t i = 0;
195
                            for(; i < _g.states[next_state_no].size(); ++i)
196
                                if (_g.states[next_state_no][i].rule_no == add_rno)
197
                                    break;
198

199
                            if (i == _g.states[next_state_no].size())
200
                                _g.states[next_state_no].emplace_back(add_rno,add_pos+1,true,0);
201
                        }
202
                    }
203
    #endif
204
            }
205
            // Вызываем себя рекурсивно, чтобы заполнить созданное состояние по аналогии
206
            if (new_state_no != 0)
207
                fillStateInfo(new_state_no);
208
        }
209
    }
210

211
    uint16_t ParsingTableBuilder_SLR::findMainPosition(size_t rno, size_t pos) const
212
    {
213
        for(size_t it_state=0; it_state < _g.states.size(); ++it_state)
214
        {
215
            parser::FsmState_t & state = _g.states[it_state];
216

217
            for(const parser::FsmStatePosition & p : state)
218
            {
219
                // Проверяем только основные позиции, и они всегда в начале
220
                if (!p.is_main)
221
                    break;
222

223
                if (rno == p.rule_no && pos == p.position)
224
                    return static_cast<uint16_t>(it_state);
225
            }
226
        }
227

228
        return 0;
229
    }
230

231
    void ParsingTableBuilder_SLR::fillPreClosure(size_t state_no, const inout::Lexeme &lex) const
232
    {
233
        if (lex.type() != inout::LexemeType::Compound)
234
            return;
235

236
        assert(state_no < _g.states.size());
237

238
        auto range = _production_index.equal_range(lex.lexeme());
239

240
        // Просматриваем продукции заданного символа
241
        for(auto &it=range.first; it != range.second; ++it)
242
        {
243
            size_t                      rno = it->second;
244
            const parser::GrammarRule & r   = _g.rules[rno];
245

246
            size_t i = 0;
247
            for(; i < _g.states[state_no].size(); ++i)
248
                if (_g.states[state_no][i].rule_no == rno && _g.states[state_no][i].position == 0)
249
                    break;
250

251
            if (i == _g.states[state_no].size())
252
            {
253
                _g.states[state_no].emplace_back(rno, 0, false, 0);
254
                fillPreClosure(state_no, r.pattern[0]);
255
            }
256
        }
257
    }
258

259
    bool ParsingTableBuilder_SLR::fillParseTable()
260
    {
261
        bool success = true;
262

263
        for(size_t i_state=0; i_state < _g.states.size(); ++i_state)
264
        {
265
            const parser::FsmState_t &state = _g.states.at(i_state);
266

267
            // Сдвиги имеют больший приоритет (правоассоциативная грамматика)
268
            for(const parser::FsmStatePosition &p : state)
269
                if (const parser::GrammarRule & r = _g.rules.at(p.rule_no); p.position < r.pattern.size())
270
                {
271
                    const inout::Lexeme & s = r.pattern.at(p.position);
272

273
                    if (p.next_state_no == 0)    // 0 не в последней позиции означает завершение
274
                    {
275
                        assert(s.type() == inout::LexemeType::Empty);
276

277
                        // Принятие (acceptance)
278
                        if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Acceptance,0)))
279
                            success = false;
280
                    }
281
                    else
282
                        // p.next != 0 означает наличие перехода в соотв-щее состояние НКА
283
                        // Сдвиг (shift)
284
                        if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Shift,static_cast<size_t>(p.next_state_no))))
285
                            success = false;
286

287
                    if (_need_to_break)
288
                        return false;
289
                }
290

291
            // Свёртки обрабатываем позже, чтобы при конфликтах принимать сдвиги
292
            // Правила по умолчанию правоассоциативные
293
            // (свёртки не будут записываться в таблицу, если соотв. позиция занята; кроме правил, помеченных как левоассациативные)
294
            for(const parser::FsmStatePosition &p : state)
295
            {
296
                if (!p.is_main)    // В свёртке могут участвовать только основные позиции, которые находятся всегда в начале списка
297
                    break;
298

299
                if (p.rule_no == 0 || p.next_state_no != 0)
300
                    continue;
301

302
                const parser::GrammarRule &r = _g.rules.at(p.rule_no);
303

304
                assert(p.position == r.pattern.size());
305

306
                // Свёртка (reduce)
307
                auto it_reduce_symbols = _reduce_symbol_set.find(r.production);
308

309
                if (it_reduce_symbols == _reduce_symbol_set.end())
310
                {
311
                    std::vector<inout::Lexeme> reduce_symbols;
312
                    reduce_symbols.reserve(_g.columns.size()-_g.first_compound_index+1);
313
                    std::set<size_t> rule_set;
314

315
                    fillReduceSymbolsUp(reduce_symbols, rule_set, p.rule_no);
316

317
                    auto [it, ok] = _reduce_symbol_set.insert({r.production, {}});
318

319
                    assert(ok);
320
                    it->second.swap(reduce_symbols);
321

322
                    it_reduce_symbols = it;
323
                }
324

325
                for(const inout::Lexeme & s : it_reduce_symbols->second)
326
                    if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Reduce,p.rule_no)))
327
                        success = false;
328

329
                if (_need_to_break)
330
                    return false;
331
            }
332
        }
333

334
        return success;
335
    }
336

337
    void ParsingTableBuilder_SLR::fillReduceSymbolsUp(std::vector<inout::Lexeme> & reduce_symbols, std::set<size_t> & rule_set, size_t rule_no)
338
    {
339
        const size_t RULE_NUMBER_PACK_BOUNDARY = 10000;
340

341
        assert(rule_no < _g.rules.size());
342
        const std::u16string & production = _g.rules[rule_no].production;
343

344
        auto range = _pattern_index.equal_range(production);
345

346
        for(auto &it=range.first; it != range.second; ++it) {
347
            assert(it->second < _g.rules.size());
348
            size_t next_rule_no = it->second;
349

350
            if (rule_set.find(rule_no+RULE_NUMBER_PACK_BOUNDARY*next_rule_no) != rule_set.end())
351
                continue;
352

353
            rule_set.emplace(rule_no+RULE_NUMBER_PACK_BOUNDARY*next_rule_no);
354

355
            const parser::GrammarRule & r = _g.rules[next_rule_no];
356

357
            for(size_t i_pos=0; i_pos < r.pattern.size(); ++i_pos) {
358
                const inout::Lexeme & s = r.pattern[i_pos];
359

360
                if (s.lexeme() != production)
361
                    continue;
362

363
                // Искомый символ найден!
364

365
                // Проверяем позицию в правиле
366
                if (i_pos == r.pattern.size()-1) {
367
                    // Последний в шаблоне. Если продукция отличается от искомого, то рекурсивно заполняем по продукции
368
                    if (r.production != s.lexeme())
369
                        fillReduceSymbolsUp(reduce_symbols, rule_set, next_rule_no);
370
                }
371
                else {
372
                    const inout::Lexeme & next_symbol = r.pattern[i_pos+1];
373

374
                    if (next_symbol.type() == inout::LexemeType::Compound) {
375
                        std::set<inout::Lexeme> processed;
376
                        fillReduceSymbolsDown(reduce_symbols, next_symbol.lexeme(), processed);
377
                    }
378
                    else if (find(reduce_symbols.begin(), reduce_symbols.end(), next_symbol) == reduce_symbols.end())
379
                        reduce_symbols.push_back(next_symbol);
380
                }
381
            }
382
        }
383
    }
384

385
    void ParsingTableBuilder_SLR::fillReduceSymbolsDown(std::vector<inout::Lexeme> & reduce_symbols, const std::u16string & production, std::set<inout::Lexeme> & processed)
386
    {
387
        auto range = _production_index.equal_range(production);
388

389
        // Просматриваем продукции заданного символа
390
        for(auto & it=range.first; it != range.second; ++it) {
391
            assert(it->second < _g.rules.size());
392
            const parser::GrammarRule & r = _g.rules[it->second];
393

394
            assert(!r.pattern.empty());
395
            const inout::Lexeme & s = r.pattern.at(0);
396

397
            if (s.type() == inout::LexemeType::Compound) {
398
                if (s.lexeme() != production)
399
                    if (processed.end() == processed.find(s)) {
400
                        processed.insert(s);
401
                        fillReduceSymbolsDown(reduce_symbols, s.lexeme(), processed);
402
                    }
403
            }
404
            else if (find(reduce_symbols.begin(), reduce_symbols.end(), s) == reduce_symbols.end())
405
                reduce_symbols.push_back(s);
406
        }
407
    }
408

409
    bool ParsingTableBuilder_SLR::insertValue(size_t line, size_t column, parser::Fsm_value_t value)
410
    {
411
        if (!_g.findFsmValue(line,column))
412
        {
413
            // Заданный вариант обработки отсутствует в таблице разбора - просто добавляем
414
            _g.parse_table.emplace(_g.packFsmKey(line,column),value);
415
            return true;
416
        }
417

418
        parser::Fsm_value_t exist_value = _g.getFsmValue(line,column);
419

420
        parser::FsmActionType exist_action = _g.unpackFsmAction(exist_value);
421
        parser::FsmActionType new_action   = _g.unpackFsmAction(value);
422

423
        // Если вариант обработки в таблице совпадает с заданным - всё ОК
424
        if (exist_action == new_action && exist_value == value)
425
            return true;
426

427
        // Вариант обработки существует в таблице разбора и он отличается от нашего - нужно принять решение какой из них использовать
428

429
        const inout::Lexeme & s = _g.columns.at(column);
430

431
        size_t exist_location = _g.unpackFsmLocation(exist_value);
432
        size_t new_location   = _g.unpackFsmLocation(value);
433

434
        std::string sout = inout::fmt("%1'. Состояние %2, символ %3 (#%4). Конфликтуют %5%6 и %7%8. ")
435
                            .arg(_grammar_name)
436
                            .arg(line)
437
                            .arg(inout::getLexemeMnemonic(s))
438
                            .arg(column)
439
                            .arg(parser::getFsmActionChar(exist_action))
440
                            .arg(exist_location)
441
                            .arg(parser::getFsmActionChar(new_action))
442
                            .arg(new_location);
443

444
        const inout::Token & t = (new_action == parser::FsmActionType::Shift)
445
                ? _rules[1].pattern[0]
446
                : _rules[new_location].pattern[_rules[new_location].pattern.size()-1];
447

448
        if (exist_action == parser::FsmActionType::Shift && new_action == parser::FsmActionType::Reduce)
449
        {
450
            assert(new_location < _g.rules.size());
451
            assert(new_location < _rules.size());
452
            if (_g.rules[new_location].reduce_direction == parser::RuleReduceDirection::RightAssociative)
453
            {
454
                sout += inout::fmt("Принят %1%2.")
455
                            .arg(parser::getFsmActionChar(exist_action))
456
                            .arg(exist_location);
457
            }
458
            else
459
            {
460
                _g.parse_table.at(_g.packFsmKey(line,column)) = value;
461
                sout += inout::fmt("Принят %1%2.")
462
                            .arg(parser::getFsmActionChar(new_action))
463
                            .arg(new_location);
464
            }
465

466
            if (_g.rules[new_location].reduce_direction == parser::RuleReduceDirection::Undefined)
467
                _m.reportError( t.makeLocation(files()), 
468
                                inout::fmt("Неоднозначность грамматики '%1").arg(sout));
469

470
            return true;
471
        }
472

473
        if (_number_of_collisions == COLLISIONS_LIMIT) {
474
            _m.reportError( t.makeLocation(files()),
475
                            inout::fmt("Количество коллизий превысило предел (%1), работа прервана")
476
                            .arg(COLLISIONS_LIMIT));
477
            _need_to_break = true;
478
            return false;
479
        }
480

481
        _m.reportError( t.makeLocation(files()), 
482
                        inout::fmt("Критическая неоднозначность грамматики '%1").arg(sout));
483

484
        _number_of_collisions++;
485

486
        return !_strict_rule_consistency;
487
    }
488

489
}