loom

1
/*
2
MIT License
3

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

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

9
#include "simodo/parser/automaton/PushdownAutomaton.h"
10
#include "simodo/inout/convert/functions.h"
11
#include "simodo/inout/token/InputStream.h"
12
#include "simodo/inout/format/fmt.h"
13

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

18
namespace simodo::parser
19
{
20
    namespace 
21
    {
22
        static uint16_t MAX_ERROR_COUNT = 5;
23
        static size_t   MAX_ERROR_RECOVER_ATTEMPTS = 5;
24

25
        AstBuilder_null null_builder;
26
    }
27

28
    inline inout::Token error_token(const std::u16string & lexeme, const inout::TokenLocation & location)
29
    {
30
        return { {lexeme, inout::LexemeType::Error}, lexeme, location };
31
    }
32

33

34
    PushdownAutomaton::PushdownAutomaton(inout::Reporter_abstract &m, Grammar &g, 
35
                                         const inout::uri_set_t & files)
36
        : _m(m)
37
        , _g(g)
38
        , _files(files)
39
        , _uri_index(files.size()-1)
40
        , _builder(null_builder)
41
    {
42
        assert(!files.empty());
43
    }
44

45
    PushdownAutomaton::PushdownAutomaton(inout::Reporter_abstract &m, Grammar &g,
46
                                         const inout::uri_set_t & files,
47
                                         AstBuilder_interface & builder)
48
        : _m(m)
49
        , _g(g)
50
        , _files(files)
51
        , _uri_index(files.size()-1)
52
        , _builder(builder)
53
    {
54
        assert(!files.empty());
55
    }
56

57
    bool PushdownAutomaton::parse() 
58
    {
59
        /// \todo Несовместима с Windows
60
        std::ifstream in(_files[_uri_index]);
61

62
        if (!in)
63
        {
64
            _m.reportFatal(inout::fmt("Ошибка при открытии файла '%1'")
65
                            .arg(_files[_uri_index]));
66
            return false;
67
        }
68

69
        inout::InputStream stream(in);
70

71
        return parse(stream);
72
    }
73

74
    /// \todo Изменить имя интерфейса SemanticTreeBuilder_interface
75
    bool PushdownAutomaton::parse(inout::InputStream_interface & stream)
76
    {
77
        assert(!_g.parse_table.empty());
78
        assert(_g.first_compound_index < _g.columns.size());
79

80
        // inout::LexicalParameters param = makeLexicalParameters(_g);
81

82
        inout::Tokenizer tokenizer(_uri_index, stream, _g.lexical);
83

84
        inout::Token token = getToken(tokenizer,_builder);
85
        inout::Token delayed_token = error_token(token.lexeme(), token.location());
86

87
        while(token.type() == inout::LexemeType::NewLine)
88
            token = getToken(tokenizer,_builder);
89

90
        // input is empty
91
        if (token.type() == inout::LexemeType::Empty)
92
            return true;
93

94
        size_t   column_no   = _g.getTerminalColumnIndex(token);
95
        bool     success     = true;
96
        bool     end         = false;
97
        uint16_t error_count = 0;
98

99
        std::vector<PushdownAutomatonState> states;
100
        states.emplace_back(0, 
101
                            _g.first_compound_index, 
102
                            inout::Token { _g.columns[_g.first_compound_index], token.location()});
103

104
        // Вызов генератора
105
        if (!_builder.onStart(_g.handlers))
106
            success = false;
107

108
        // Цикл разбора
109
        while(!end && error_count < MAX_ERROR_COUNT)
110
        {
111
            size_t state_no = states.back().getStateNo();
112

113
            if (!_g.findFsmValue(state_no,column_no))
114
            {
115
                reportSyntaxError(states, token);
116
                error_count ++;
117
                success = false;
118

119
                // Пытаемся восстановиться после ошибки методом "паники"
120
                /// \todo Нужно будет доработать алгоритм восстановления после ошибок на что-то более интеллектуальное
121
                size_t i = 0;
122
                for(; i < MAX_ERROR_RECOVER_ATTEMPTS; ++i) // Ограничиваем кол-во попыток
123
                {
124
                    if (delayed_token.type() != inout::LexemeType::Error) {
125
                        token = delayed_token;
126
                        delayed_token = error_token(token.lexeme(), token.location());
127
                    }
128
                    else {
129
                        token = getToken(tokenizer,_builder);
130
                        while(token.type() == inout::LexemeType::NewLine)
131
                            token = getToken(tokenizer,_builder);
132
                    }
133
                    column_no = _g.getTerminalColumnIndex(token);
134
                    if (_g.findFsmValue(state_no,column_no) || token.type() == inout::LexemeType::Empty)
135
                        break;
136
                }
137

138
                if (i == MAX_ERROR_RECOVER_ATTEMPTS || !_g.findFsmValue(state_no,column_no))
139
                    break;
140
            }
141

142
            Fsm_value_t   fsm_value = _g.getFsmValue(state_no,column_no);
143
            FsmActionType action    = _g.unpackFsmAction(fsm_value);
144

145
            switch(action)
146
            {
147
            case FsmActionType::Acceptance:
148
                end = true;
149
                break;
150

151
            case FsmActionType::Error:
152
                _m.reportError(token.makeLocation(_files), inout::fmt("Синтаксическая ошибка"));
153
                error_count ++;
154
                success = false;
155
                break;
156

157
            case FsmActionType::Reduce:
158
                {
159
                    size_t              rule_no = _g.unpackFsmLocation(fsm_value);
160
                    const GrammarRule & r       = _g.rules.at(rule_no);
161

162
                    assert(states.size() >= r.pattern.size());
163

164
                    // Вызов генератора
165
                    inout::TokenLocation prod_location(states.back().location());
166
                    std::vector<inout::Token> pattern;
167
                    pattern.reserve(r.pattern.size());
168

169
                    for(size_t i=0; i < r.pattern.size() ; ++i) {
170
                        inout::Token t = states.back();
171
                        if (i > 0) 
172
                            prod_location.merge(t.location());
173
                        pattern.insert(pattern.begin(), t);
174
                        /// \todo Нужно проверить: корректно ли именно тут сбрасывать состояние с точки зрения корректного восстановления
175
                        /// после синтаксической ошибки, значительная часть которых происходит во время редукции (см. обработку ниже).
176
                        states.pop_back();
177
                    }
178

179
                    size_t symbol_index = _g.getCompoundColumnIndex(r.production);
180
                    if (symbol_index == _g.columns.size()) {
181
                        _m.reportWithPosition(inout::SeverityLevel::Fatal, token.makeLocation(_files), 
182
                                              inout::fmt("Сбой при определении номера символа продукции '%1'")
183
                                              .arg(r.production));
184
                        success = false;
185
                        break;
186
                    }
187
                    size_t line = states.back().getStateNo();
188

189
                    if (!_g.findFsmValue(line,symbol_index)) {
190
                        reportSyntaxError(states, token);
191
                        error_count ++;
192
                        success = false;
193

194
                        if (token.type() == inout::LexemeType::Empty)
195
                            symbol_index = 0;
196
                        else
197
                            // Восстановление после ошибки путём подстановки подходящего символа
198
                            // (доходим до 1, т.к. 0 - это конец файла)
199
                            for(symbol_index=_g.first_compound_index-1; symbol_index > 0; --symbol_index)
200
                                if (_g.findFsmValue(line,symbol_index)) {
201
                                    token = { _g.columns[symbol_index], token.location() };
202

203
                                    if (isLexemeValid(states,token)) {
204
                                        column_no = symbol_index;
205
                                        break;
206
                                    }
207
                                }
208

209
                        if (symbol_index == 0) {
210
                            end = true;
211
                            break;
212
                        }
213
                    }
214
                    Fsm_value_t   val = _g.getFsmValue(line,symbol_index);
215
                    FsmActionType act = _g.unpackFsmAction(val);
216

217
                    if (act == FsmActionType::Shift) {
218
                        size_t st = _g.unpackFsmLocation(val);
219
                        states.emplace_back(st, symbol_index, inout::Token { inout::LexemeType::Compound, r.production, prod_location});
220
                    }
221
                    else {
222
                        _m.reportWithPosition(inout::SeverityLevel::Fatal, token.makeLocation(_files), 
223
                                              inout::fmt("При обработке приведения возникло недопустимое состояние"));
224
                        success = false;
225
                        break;
226
                    }
227

228
#ifdef AST_BUILDER_DEBUG
229
                    if (error_count == 0 &&
230
                        !_builder.onProduction(state_no, rule_no,
231
                                            inout::Token { {r.production, inout::LexemeType::Compound}, r.production, prod_location },
232
                                            pattern,
233
                                            r.reduce_action,
234
                                            line,
235
                                            states.back().getStateNo())) {
236
                        success = false;
237
                        end = true;
238
                        break;
239
                    }
240
#else
241
                    if (error_count == 0 &&
242
                        !_builder.onProduction(
243
                                            inout::Token { {r.production, inout::LexemeType::Compound}, r.production, prod_location },
244
                                            pattern,
245
                                            r.reduce_action)) {
246
                        success = false;
247
                        end = true;
248
                        break;
249
                    }
250
#endif
251
                }
252
                break;
253

254
            case FsmActionType::Shift:
255
                {
256
                    Fsm_value_t val   = _g.getFsmValue(state_no,column_no);
257
                    size_t      shift = _g.unpackFsmLocation(val);
258

259
#ifdef AST_BUILDER_DEBUG
260
                    if (!_builder.onShift(state_no, _g.columns[column_no], column_no, shift)) {
261
                        success = false;
262
                        end = true;
263
                        break;
264
                    }
265
#endif
266
                    PushdownAutomatonState  ps(shift,column_no,token);
267

268
                    // Фрагмент кода, анализирующего возможность замены символа новой строки на заданный терминал
269
                    // (обычно это символ ';')
270

271
                    // Логика проверки возможности замены следующая:
272
                    // 1. Если подменяемый символ не допустим грамматикой языка - замена не производится
273
                    // 2. Если следующий символ после новой строки допустим грамматикой языка - замена не производится
274

275
                    // Чтобы проверить допустимость символа-замены и следующего символа недостаточно проверить текущее
276
                    // состояние разбора, так как оба символа могут участвовать в текущем контексте, но во вложенных
277
                    // структурах (например, символ '}' может быть допустим грамматикой в выражении для лямбды и нужно
278
                    // раскрутить стек состояний, чтобы убедиться, что мы находимся действительно в обработке лямбды,
279
                    // а не в конце выражения и символ '}' не является концом блока операторов).
280
                    // Для проверки допустимости токена в данном контексте по глубине стека состояний используется
281
                    // метод isTokenValid.
282

283
                    if (delayed_token.type() != inout::LexemeType::Error) {
284
                        token = delayed_token;
285
                        delayed_token = error_token(token.lexeme(), token.location());
286
                    }
287
                    else {
288
                        token = getToken(tokenizer,_builder);
289

290
                        if (token.type() == inout::LexemeType::NewLine) {
291
                            inout::Token nl_token = token;
292

293
                            while(token.type() == inout::LexemeType::NewLine)
294
                                token = getToken(tokenizer,_builder);
295

296
                            // Для подмены символа замещения нужно, чтобы следующий символ не соответствовал грамматике
297

298
                            std::vector<PushdownAutomatonState> full_stack  = states;
299

300
                            full_stack.push_back(ps);
301

302
                            if (!isLexemeValid(full_stack,token)) {
303
                                // Не соответствует...
304

305
                                nl_token = {inout::LexemeType::Punctuation, nl_token.lexeme(), nl_token.location() };
306

307
                                // Для подмены символа замещения нужно, чтобы символ замещения соответствовал грамматике
308

309
                                if (isLexemeValid(full_stack,nl_token)) {
310
                                    // Соответствует...
311

312
                                    delayed_token = token;
313
                                    token = nl_token;
314
                                }
315
                            }
316
                        }
317
                    }
318

319
                    // Штатная обработка
320

321
                    column_no = _g.getTerminalColumnIndex(token);
322

323
                    if (column_no == _g.columns.size()) {
324
                        // Полученный символ (токен) не предусмотрен данной грамматикой.
325
                        // Такое может быть, например, если грамматика не предусматривает числовых констант, а она таки записана.
326
                        // Или, что чаще бывает, введены ошибочные символы, которых нет в лексике грамматики (LexemeType::Error)
327
                        reportSyntaxError(states, token);
328
                        error_count ++;
329
                        success = false;
330

331
                        // Простейший вариант восстановления - попытаться заменить данный токен на один из ожидаемых
332
                        // (начинаем с конца, т.к. в конце списка, как правило, наиболее обобщённые токены)
333
                        // (доходим до 1, т.к. 0 - это конец файла)
334
                        /// \todo Нужно будет доработать алгоритм восстановления на что-то более интеллектуальное
335
                        for(size_t i=_g.first_compound_index-1; i > 0; --i)
336
                            if (_g.findFsmValue(shift,i)) {
337
                                token = { _g.columns[i], token.location() };
338
                                column_no = i;
339
                                break;
340
                            }
341
                    }
342
                    states.push_back(ps);
343
                }
344
                break;
345
            }
346
        }
347

348
        if (error_count == MAX_ERROR_COUNT)
349
            _m.reportInformation(inout::fmt("Превышено допустимое количество ошибок, разбор прерван"));
350
        else if (!end)
351
            _m.reportInformation(inout::fmt("Не удалось выполнить восстановление состояния разбора после синтаксической ошибки, разбор прерван"));
352

353
        if (!_builder.onFinish(success, _g.handlers))
354
            success = false;
355

356
        return success;
357
    }
358

359
    inout::Token PushdownAutomaton::getToken(inout::Tokenizer & tz, AstBuilder_interface & builder) const
360
    {
361
        inout::Token t = tz.getAnyToken();
362
        
363
        builder.onTerminal(t);
364

365
        while(t.type() == inout::LexemeType::Comment) {
366
            t = tz.getAnyToken();
367
            builder.onTerminal(t);
368
        }
369

370
        return t;
371
    }
372

373
    void PushdownAutomaton::reportSyntaxError(const std::vector<PushdownAutomatonState> &states, const inout::Token &t) const
374
    {
375
        assert(!states.empty());
376

377
        const PushdownAutomatonState & parser_state = states.back();
378
        std::string                 briefly;
379
        std::string                 atlarge;
380
        std::vector<std::string>    expected;
381

382
        if (t.type() == inout::LexemeType::Empty)
383
            briefly += inout::fmt("Преждевременный конец файла");
384
        else
385
            briefly += inout::fmt("Неподходящий входной символ '%1'.").arg(t.lexeme());
386

387
        const FsmState_t & si = _g.states.at(parser_state.getStateNo());
388

389
        // Просматриваем позиции текущего состояния
390
        for(const FsmStatePosition &p : si) {
391
            const GrammarRule &rule = _g.rules.at(p.rule_no);
392

393
            if (atlarge.empty()) {
394
                if (p.position == 0)
395
                    atlarge = inout::fmt("При разборе правила '%1").arg(rule.production);
396
                else {
397
                    if (p.position == rule.pattern.size())
398
                        atlarge = inout::fmt("После разбора правила '%1").arg(rule.production);
399
                    else if (rule.pattern.at(p.position-1).type() == inout::LexemeType::Compound)
400
                        atlarge = inout::fmt("После разбора правила '%1").arg(rule.pattern.at(p.position-1).lexeme());
401
                    else
402
                        atlarge = inout::fmt("При разборе правила '%1").arg(rule.production);
403
                }
404
                atlarge += inout::fmt("' (состояние КА = %1) ").arg(inout::toU16(std::to_string(parser_state.getStateNo())));
405

406
                if (t.type() == inout::LexemeType::Empty)
407
                    atlarge += inout::fmt("достигнут конец файла");
408
                else
409
                    atlarge += inout::fmt("получен неподходящий символ '%1'").arg(t.lexeme());
410

411
                atlarge += inout::fmt(", вместо ожидаемых символов: ");
412
            }
413
        }
414

415
        for(size_t i=0; i < _g.first_compound_index; ++i)
416
            if (isLexemeValid(states,_g.columns[i]))
417
                expected.emplace_back(getLexemeMnemonic(_g.columns.at(i)));
418

419
        // Отображаем перечень ожидаемых символов
420
        for(auto st=expected.begin(); st != expected.end(); ++st) {
421
            if (st != expected.begin())
422
                atlarge += ", ";
423
            atlarge += *st;
424
        }
425

426
        atlarge += inout::fmt("\nПозиция разбора: %1").arg(inout::getLocationString(t.makeLocation(_files)));
427

428
        _m.reportError(t.makeLocation(_files), briefly, atlarge);
429
    }
430

431
    bool PushdownAutomaton::isLexemeValid(std::vector<PushdownAutomatonState> states, const inout::Lexeme &lexeme) const
432
    {
433
        assert(!states.empty());
434

435
        // Для определения допустимости заданного символа в текущем контексте выполняется следующий алгоритм:
436

437
        // Необходимо для каждого состояния стека состояний, начиная с верхнего, убедиться, что:
438
        // 1. если предусмотрен сдвиг или завершение, то символ является разрешённым, возвращаем true
439
        // 2. иначе: для заданного символа предусмотрена свёртка, спускаемся ниже по стеку состояний.
440
        // 3. достижение конца стека не должно произойти (по идее).
441

442
        size_t column_no = _g.getTerminalColumnIndex(lexeme);
443

444
        if (column_no >= _g.columns.size())
445
            return false;
446

447
        while(!states.empty()) {
448
            const PushdownAutomatonState & ps         = states.back();
449
            size_t                         state_no   = ps.getStateNo();
450

451
            if (!_g.findFsmValue(state_no, column_no))
452
                return false;
453

454
            Fsm_value_t         fsm_value  = _g.getFsmValue(state_no, column_no);
455
            FsmActionType       fsm_action = _g.unpackFsmAction(fsm_value);
456

457
            if (fsm_action == FsmActionType::Error)
458
                return false;
459

460
            if (fsm_action == FsmActionType::Shift || fsm_action == FsmActionType::Acceptance)
461
                return true;
462

463
            size_t              rule_no      = _g.unpackFsmLocation(fsm_value);
464
            const GrammarRule & rule         = _g.rules.at(rule_no);
465
            size_t              pattern_size = rule.pattern.size();
466

467
            for(size_t i=0; i < pattern_size; ++i)
468
                states.pop_back();
469

470
            size_t symbol_index = _g.getCompoundColumnIndex(rule.production);
471
            assert(symbol_index < _g.columns.size());
472

473
            size_t line = states.back().getStateNo();
474

475
            if(!_g.findFsmValue(line,symbol_index))
476
                return false;
477

478
            Fsm_value_t   val    = _g.getFsmValue(line,symbol_index);
479
            FsmActionType act    = _g.unpackFsmAction(val);
480

481
            assert(act == FsmActionType::Shift);
482

483
            size_t st = _g.unpackFsmLocation(val);
484

485
            states.emplace_back(st, symbol_index, inout::Token {inout::LexemeType::Compound, rule.production, ps.location()});
486
        }
487

488
        return false;
489
    }
490

491
    // inout::LexicalParameters PushdownAutomaton::makeLexicalParameters(const Grammar &g)
492
    // {
493
    //     return g.lexical;
494
    // }
495

496
}