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_LR1.h"
10

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

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

18
namespace simodo::interpret::builtins
19
{
20
    // Все улучшения, строго говоря, не соответствуют классу LR1
21
    // См. тест: 
22
    // bin/simodo-grammatize -p test/source/grammar lr1-04 -z lr -r -i
23

24
    // Улучшение выполнено не корректно.
25
    #define LR1_IMPROVED_2_no
26
    // Это улучшение по идее работает корректно
27
    #define LR1_IMPROVED_1
28

29
    namespace {
30
        uint64_t packPositionKey(size_t rno, size_t pos)
31
        {
32
            return rno + pos*UINT32_MAX;
33
        }
34

35
    }
36

37

38
    void ParsingTableBuilder_LR1::fillStateTable()
39
    {
40
        parser::FsmState_t state;
41
        state.emplace_back(parser::FsmStatePosition(0,0,{inout::Lexeme{u"",inout::LexemeType::Empty}}));
42
        addState(state,0);
43

44
        fillState(0);
45

46
        _g.build_method = parser::TableBuildMethod::LR1;
47
    }
48

49
    void ParsingTableBuilder_LR1::fillState(size_t state_no)
50
    {
51
        // При входе в этот метод в заданном состоянии (state_no) уже определены основные позиции
52
        // Этот метод вызывается рекурсивно, единожды для каждого состояния
53

54
        /// \attention Код данного метода (как и всего данного класса) выполняет активную модификацию
55
        /// структур грамматики, заданной в параметре _g. Поэтому, крайне не желательно создавать
56
        /// ссылки на члены класса _g. Массивы могут реаллокироваться. Будьте осторожны.
57
        /// Работайте с индексами, они не меняются.
58

59
        std::multimap<DepthPair,parser::FsmStatePosition,DepthPairComparator>
60
                                    position_multiset;
61
        std::map<std::u16string,std::set<inout::Lexeme>>  prod_lookahead_set;
62

63
        // Первым делом необходимо дополнить заданное состояние (state_no) "замыканиями",
64
        // т.е. символами, которые всегда идут в первой позиции для каждой основной позиции.
65

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

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

74
            size_t rno = _g.states[state_no][i].rule_no;
75
            size_t pos = _g.states[state_no][i].position;
76

77
            assert(rno < _g.rules.size());
78

79
            auto it_prod_lookahead = prod_lookahead_set.find(_g.rules[rno].production);
80

81
            if (it_prod_lookahead == prod_lookahead_set.end())
82
                prod_lookahead_set.insert({_g.rules[rno].production,_g.states[state_no][i].lookahead});
83
            else
84
                for(const inout::Lexeme & l : _g.states[state_no][i].lookahead)
85
                    it_prod_lookahead->second.insert(l);
86

87
            // Находим замыкания (формируем отсортированный по уровням и продукциям перечень замыканий)
88
            // Такое предварительное формирование необходимо для достижения симметрии в обработке разных
89
            // описаний одной и той же грамматики
90
            if (pos < _g.rules[rno].pattern.size())
91
                fillClosure(state_no, rno, pos, 0, position_multiset);
92
        }
93

94
        // Записываем отсортированные не основные позиции в наше состояние
95
        // (теперь внутреннее представление грамматики является инвариантным)
96
        for(const auto & [key,p] : position_multiset)
97
            _g.states[state_no].push_back(p);
98

99
        // Устанавливаем предпросмотры для всех неосновных позиций
100
        // (для основных позиций они должны быть заданы перед вызовом метода)
101

102
        fillLookahead(state_no, position_initial_count, prod_lookahead_set);
103

104
        // Состояния, созданные в результате анализа замыканий (не основных позиций),
105
        // которые нужно будет заполнить
106
        std::set<size_t> new_states;
107

108
        // Текущее состояние создано, готовим следующие состояния
109
        // Проходим по всем позициям нашего состояния и для каждого перехода
110
        // создаем следующее состояние.
111
        // Проставляем значение next для позиций.
112

113
        for(size_t i_pos_in_state=0; i_pos_in_state < _g.states[state_no].size(); ++i_pos_in_state) {
114
            size_t current_rno = _g.states[state_no][i_pos_in_state].rule_no;
115
            size_t current_pos = _g.states[state_no][i_pos_in_state].position;
116

117
            assert(current_rno < _g.rules.size());
118
            const parser::GrammarRule & current_rule = _g.rules[current_rno];
119

120
            // Важно убедиться, что есть куда переходить
121
            if (current_pos == current_rule.pattern.size())
122
                continue;
123
            // и эта позиция не использована ранее в этом же цикле (не установлено состояние перехода)
124
            if (_g.states[state_no][i_pos_in_state].next_state_no > 0)
125
                continue;
126

127
            assert(current_pos < current_rule.pattern.size());
128
            const inout::Lexeme & current_symbol = current_rule.pattern[current_pos];
129

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

134
            // Убеждаемся, что нужного основного состояния ещё нет
135
            size_t find_state = findMainPosition(current_rno, current_pos+1, prod_lookahead_set[_g.rules[current_rno].production]);
136
            size_t next_state_no;
137
            if (find_state == 0) // (совпадение с нулевым состоянием невозможно, т.к. оно создаётся искусственно)
138
            {
139
                // Точного совпадения не нашли
140
                // Создаем следующее состояние и нашу следующую основную позицию
141
                next_state_no = _g.states.size();
142
                _g.states[state_no][i_pos_in_state].next_state_no = next_state_no;
143

144
                parser::FsmState_t new_state;
145
                new_state.emplace_back(current_rno, current_pos+1, prod_lookahead_set[_g.rules[current_rno].production], true, 0);
146
                addState(new_state,next_state_no);
147
                new_states.insert(next_state_no);
148
            }
149
            else
150
                _g.states[state_no][i_pos_in_state].next_state_no = next_state_no = find_state;
151

152
            // Находим позицию с тем же переходным символом
153
            for(size_t i_pos_add=i_pos_in_state+1; i_pos_add < _g.states[state_no].size(); ++i_pos_add) {
154
                if (_g.states[state_no][i_pos_add].next_state_no != 0)
155
                    continue;
156

157
                size_t add_rno = _g.states[state_no][i_pos_add].rule_no;
158
                size_t add_pos = _g.states[state_no][i_pos_add].position;
159

160
                assert(add_rno < _g.rules.size());
161
                const parser::GrammarRule & add_rule = _g.rules[add_rno];
162

163
                if (add_pos < add_rule.pattern.size())
164
                    if (current_symbol == add_rule.pattern[add_pos]) {
165
                        // Проверяем, что такой основной позиции ещё нет
166
                        bool found = false;
167
                        auto it = _g.states[next_state_no].begin();
168
                        for(; it != _g.states[next_state_no].end() && it->is_main; ++it)
169
                            if (it->rule_no == add_rno) {
170
                                found = true;
171
                                break;
172
                            }
173
                        // Добавляем основную позицию
174
                        _g.states[state_no][i_pos_add].next_state_no = next_state_no;
175
                        if (!found) {
176
                            _g.states[next_state_no].emplace(it, add_rno,add_pos+1,prod_lookahead_set[_g.rules[add_rno].production],true,0);
177
                            _position_index.insert({packPositionKey(add_rno,add_pos+1),next_state_no});
178
                            new_states.insert(next_state_no);
179
                        }
180
                    }
181
            }
182
        }
183

184
        // Вызываем себя рекурсивно, чтобы заполнить созданные основные состояния по аналогии
185
        for(auto i : new_states)
186
            fillState(i);
187
    }
188

189
    size_t ParsingTableBuilder_LR1::findMainPosition(size_t rno, size_t pos, const std::set<inout::Lexeme> & lookahead) const
190
    {
191
        auto range = _position_index.equal_range(packPositionKey(rno,pos));
192

193
        for(auto &it=range.first; it != range.second; ++it)
194
        {
195
            size_t               it_state = it->second;
196
            parser::FsmState_t & state    = _g.states[it_state];
197

198
            for(size_t it_pos=0; it_pos < state.size(); ++it_pos)
199
            {
200
                parser::FsmStatePosition & p = state[it_pos];
201

202
                // Проверяем только основные позиции, и они всегда в начале
203
                if (!p.is_main)
204
                    break;
205

206
                if (rno == p.rule_no && pos == p.position)
207
                {
208
    #ifdef LR1_IMPROVED_2
209
                    // Улучшение выполнено не корректно. См. тест:
210
                    // bin/simodo-grammatize -p test/source/grammar lr1-04 -z lr -r -i
211

212
                    if (pos == _g.rules[rno].pattern.size()) {
213
                        // Данный алгоритм выполняет рекомендацию \todo ниже.
214
                        // Можно безопасно слить состояния закрываемых позиций одного правила из разных предпросмотров
215
                        bool is_only_last_positions = true;
216
                        if (state.size() > 1)
217
                            for(size_t i=0; i < state.size(); ++i)
218
                                if (state[i].position != _g.rules[state[i].rule_no].pattern.size()) {
219
                                    is_only_last_positions = false;
220
                                    break;
221
                                }
222

223
                        if (is_only_last_positions) {
224
                            for(const Lexeme & l : lookahead)
225
                                p.lookahead.insert(l);
226
                            return it_state;
227
                        }
228
                    }
229
    #elif defined (LR1_IMPROVED_1)
230
                    if (pos == _g.rules[rno].pattern.size()
231
                        /// \todo Данный алгоритм осторожничает, не оптимизируя случаи нескольких основных закрываемых позиций.
232
                        /// Можно ещё немного оптимизировать количество состояний без потери качества, если разрешать слияние с
233
                        /// не единственными закрываемыми позициями.
234
                        /// Для этого в состоянии не должно быть незакрываемых позиций (и все позиции должны быть основными?).
235
                        && state.size() == 1)
236
                    {
237
                        for(const inout::Lexeme & l : lookahead)
238
                            p.lookahead.insert(l);
239
                        return it_state;
240
                    }
241
    #endif
242
                    if (lookahead == p.lookahead)
243
                        return it_state;
244
                }
245
            }
246
        }
247

248
        return 0;
249
    }
250

251
    void ParsingTableBuilder_LR1::fillClosure(size_t state_no, size_t rno, size_t pos, int depth,
252
                                        std::multimap<DepthPair, parser::FsmStatePosition, DepthPairComparator> &position_multiset)
253
    {
254
        auto production_range = _production_index.equal_range(_g.rules[rno].pattern[pos].lexeme());
255

256
        // Просматриваем продукции заданного символа
257
        for(auto &it=production_range.first; it != production_range.second; ++it)
258
        {
259
            size_t next_rno = it->second;
260

261
            bool find = false;
262
            for(auto & [key_depth,p] : position_multiset)
263
                if (p.rule_no == next_rno && p.position == 0)
264
                {
265
                    find = true;
266
                    break;
267
                }
268

269
            if (!find)
270
            {
271
                int find_depth = INT32_MAX;
272
                for(auto & [key_depth,p] : position_multiset)
273
                    if (_g.rules[p.rule_no].production == _g.rules[next_rno].production)
274
                    {
275
                        find_depth = key_depth.depth;
276
                        break;
277
                    }
278

279
                if (find_depth > depth)
280
                    find_depth = depth;
281

282
                position_multiset.insert({{find_depth,_g.rules[next_rno].pattern.size()},parser::FsmStatePosition(next_rno, 0, false, 0)});
283
                fillClosure(state_no, next_rno, 0, depth+1, position_multiset);
284
            }
285
        }
286
    }
287

288
    void ParsingTableBuilder_LR1::fillLookahead(size_t state_no, size_t position_initial_count, std::map<std::u16string,std::set<inout::Lexeme>> & prod_lookahead_set)
289
    {
290
        assert(state_no < _g.states.size());
291

292
        for(size_t i=position_initial_count; i < _g.states[state_no].size(); ++i)
293
        {
294
            size_t rno = _g.states[state_no][i].rule_no;
295

296
            assert(rno < _g.rules.size());
297

298
            std::set<inout::Lexeme> lookahead;
299

300
            for(size_t parent=0; parent < i; ++parent)
301
            {
302
                size_t prev_rno = _g.states[state_no][parent].rule_no;
303
                size_t prev_pos = _g.states[state_no][parent].position;
304

305
                if(prev_pos < _g.rules[prev_rno].pattern.size())
306
                    if(_g.rules[prev_rno].pattern[prev_pos].lexeme() == _g.rules[rno].production)
307
                    {
308
                        if (prev_pos == _g.rules[prev_rno].pattern.size()-1)
309
                        {
310
                            // Последний элемент
311
                            for(const inout::Lexeme & l : _g.states[state_no][parent].lookahead)
312
                                lookahead.insert(l);
313
                        }
314
                        else if (_g.rules[prev_rno].pattern[prev_pos+1].type() != inout::LexemeType::Compound)
315
                        {
316
                            // Следующий элемент является терминалом и определяет предпросмотр
317
                            lookahead.insert(_g.rules[prev_rno].pattern[prev_pos+1]);
318
                        }
319
                        else
320
                        {
321
                            // Определяем терминалы, с которых может начинаться следующий нетерминал
322
                            std::set<inout::Lexeme> processed;
323
                            fillStartingTerminalsByProd(_g.rules[prev_rno].pattern[prev_pos+1], lookahead, processed);
324
                        }
325
                    }
326
            }
327

328
            auto it_prod_lookahead = prod_lookahead_set.find(_g.rules[rno].production);
329

330
            if (it_prod_lookahead == prod_lookahead_set.end())
331
                prod_lookahead_set.insert({_g.rules[rno].production,lookahead});
332
            else
333
                for(const inout::Lexeme & l : lookahead)
334
                    it_prod_lookahead->second.insert(l);
335

336
            _g.states[state_no][i].lookahead = prod_lookahead_set[_g.rules[rno].production];
337
        }
338
    }
339

340
    void ParsingTableBuilder_LR1::fillStartingTerminalsByProd(const inout::Lexeme &prod, std::set<inout::Lexeme> &terminals, std::set<inout::Lexeme> &processed)
341
    {
342
        auto range = _production_index.equal_range(prod.lexeme());
343

344
        // Просматриваем продукции заданного символа
345
        for(auto &it=range.first; it != range.second; ++it) {
346
            size_t rno = it->second;
347
            const inout::Lexeme & pattern0 = _g.rules[rno].pattern[0];
348

349
            if (pattern0.type() != inout::LexemeType::Compound) {
350
                if (terminals.end() == terminals.find(pattern0))
351
                    terminals.insert(pattern0);
352
            }
353
            else if (pattern0 != prod)
354
                if (processed.end() == processed.find(pattern0)) {
355
                    processed.insert(pattern0);
356
                    fillStartingTerminalsByProd(pattern0,terminals,processed);
357
                }
358
        }
359
    }
360

361
    bool ParsingTableBuilder_LR1::fillParseTable()
362
    {
363
        bool success = true;
364

365
        for(size_t i_state=0; i_state < _g.states.size(); ++i_state)
366
        {
367
            const parser::FsmState_t &state = _g.states.at(i_state);
368

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

375
                    if (p.next_state_no == 0)    // 0 не в последней позиции означает завершение
376
                    {
377
                        if (s.type() == inout::LexemeType::Empty)
378
                        {
379
                            // Принятие (acceptance)
380
                            if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Acceptance,0)))
381
                                success = false;
382
                        }
383
                        else
384
                            assert(false);
385
                    }
386
                    else
387
                        // p.next != 0 означает наличие перехода в соотв-щее состояние НКА
388
                        // Сдвиг (shift)
389
                        if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Shift,static_cast<size_t>(p.next_state_no))))
390
                            success = false;
391

392
                    if (_need_to_break)
393
                        return false;
394
                }
395

396
            // Свёртки обрабатываем позже, чтобы при конфликтах принимать сдвиги
397
            // Правила по умолчанию правоассоциативные
398
            // (свёртки не будут записываться в таблицу, если соотв. позиция занята; кроме правил, помеченных как левоассациативные)
399
            for(const parser::FsmStatePosition &p : state)
400
            {
401
                if (!p.is_main)    // В свёртке могут участвовать только основные позиции, которые находятся всегда в начале списка
402
                    break;
403

404
                if (p.rule_no == 0 || p.next_state_no != 0)
405
                    continue;
406

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

409
                assert(p.position == r.pattern.size());
410

411
                // Свёртка (reduce)
412

413
                for(const inout::Lexeme & s : p.lookahead)
414
                    if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Reduce,p.rule_no)))
415
                        success = false;
416

417
                if (_need_to_break)
418
                    return false;
419
            }
420
        }
421

422
        return success;
423
    }
424

425
    bool ParsingTableBuilder_LR1::insertValue(size_t line, size_t column, parser::Fsm_value_t value)
426
    {
427
        if (!_g.findFsmValue(line,column))
428
        {
429
            // Заданный вариант обработки отсутствует в таблице разбора - просто добавляем
430
            _g.parse_table.emplace(_g.packFsmKey(line,column),value);
431
            return true;
432
        }
433

434
        parser::Fsm_value_t exist_value = _g.getFsmValue(line,column);
435

436
        parser::FsmActionType exist_action = _g.unpackFsmAction(exist_value);
437
        parser::FsmActionType new_action   = _g.unpackFsmAction(value);
438

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

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

445
        const inout::Lexeme & s = _g.columns.at(column);
446

447
        size_t exist_location = _g.unpackFsmLocation(exist_value);
448
        size_t new_location   = _g.unpackFsmLocation(value);
449

450
        std::string sout = inout::fmt("%1'. Состояние %2, символ %3 (#%4). Конфликтуют %5%6 и %7%8. ")
451
                            .arg(_grammar_name)
452
                            .arg(line)
453
                            .arg(inout::getLexemeMnemonic(s))
454
                            .arg(column)
455
                            .arg(parser::getFsmActionChar(exist_action))
456
                            .arg(exist_location)
457
                            .arg(parser::getFsmActionChar(new_action))
458
                            .arg(new_location);
459

460
        const inout::Token & t = (new_action == parser::FsmActionType::Shift)
461
                ? _rules[1].pattern[0]
462
                : _rules[new_location].pattern[_rules[new_location].pattern.size()-1];
463

464
        if (exist_action == parser::FsmActionType::Shift && new_action == parser::FsmActionType::Reduce)
465
        {
466
            assert(new_location < _g.rules.size());
467
            assert(new_location < _rules.size());
468
            if (_g.rules[new_location].reduce_direction == parser::RuleReduceDirection::RightAssociative)
469
            {
470
                sout += inout::fmt("Принят %1%2.")
471
                            .arg(parser::getFsmActionChar(exist_action))
472
                            .arg(exist_location);
473
            }
474
            else
475
            {
476
                _g.parse_table.at(_g.packFsmKey(line,column)) = value;
477
                sout += inout::fmt("Принят %1%2.")
478
                            .arg(parser::getFsmActionChar(new_action))
479
                            .arg(new_location);
480
            }
481

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

486
            return true;
487
        }
488

489
        if (_number_of_collisions == COLLISIONS_LIMIT) {
490
            _m.reportError( t.makeLocation(files()),
491
                            inout::fmt("Количество коллизий превысило предел (%1), работа прервана")
492
                            .arg(COLLISIONS_LIMIT));
493
            _need_to_break = true;
494
            return false;
495
        }
496

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

500
        _number_of_collisions++;
501

502
        return !_strict_rule_consistency;
503
    }
504

505
    void ParsingTableBuilder_LR1::addState(parser::FsmState_t state, size_t state_no)
506
    {
507
        _g.states.emplace_back(state);
508

509
        for(const parser::FsmStatePosition & p : state)
510
        {
511
            if (!p.is_main)
512
                break;
513

514
            _position_index.insert({packPositionKey(p.rule_no,p.position),state_no});
515
        }
516
    }
517

518
}