4
Copyright (c) 2021 МГТУ им. Н.Э. Баумана, кафедра ИУ-6, Михаил Фетисов,
6
https://bmstu.codes/lsx/simodo
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"
18
namespace simodo::parser
22
static uint16_t MAX_ERROR_COUNT = 5;
23
static size_t MAX_ERROR_RECOVER_ATTEMPTS = 5;
25
AstBuilder_null null_builder;
28
inline inout::Token error_token(const std::u16string & lexeme, const inout::TokenLocation & location)
30
return { {lexeme, inout::LexemeType::Error}, lexeme, location };
34
PushdownAutomaton::PushdownAutomaton(inout::Reporter_abstract &m, Grammar &g,
35
const inout::uri_set_t & files)
39
, _uri_index(files.size()-1)
40
, _builder(null_builder)
42
assert(!files.empty());
45
PushdownAutomaton::PushdownAutomaton(inout::Reporter_abstract &m, Grammar &g,
46
const inout::uri_set_t & files,
47
AstBuilder_interface & builder)
51
, _uri_index(files.size()-1)
54
assert(!files.empty());
57
bool PushdownAutomaton::parse()
59
/// \todo Несовместима с Windows
60
std::ifstream in(_files[_uri_index]);
64
_m.reportFatal(inout::fmt("Ошибка при открытии файла '%1'")
65
.arg(_files[_uri_index]));
69
inout::InputStream stream(in);
74
/// \todo Изменить имя интерфейса SemanticTreeBuilder_interface
75
bool PushdownAutomaton::parse(inout::InputStream_interface & stream)
77
assert(!_g.parse_table.empty());
78
assert(_g.first_compound_index < _g.columns.size());
80
// inout::LexicalParameters param = makeLexicalParameters(_g);
82
inout::Tokenizer tokenizer(_uri_index, stream, _g.lexical);
84
inout::Token token = getToken(tokenizer,_builder);
85
inout::Token delayed_token = error_token(token.lexeme(), token.location());
87
while(token.type() == inout::LexemeType::NewLine)
88
token = getToken(tokenizer,_builder);
91
if (token.type() == inout::LexemeType::Empty)
94
size_t column_no = _g.getTerminalColumnIndex(token);
97
uint16_t error_count = 0;
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()});
105
if (!_builder.onStart(_g.handlers))
109
while(!end && error_count < MAX_ERROR_COUNT)
111
size_t state_no = states.back().getStateNo();
113
if (!_g.findFsmValue(state_no,column_no))
115
reportSyntaxError(states, token);
119
// Пытаемся восстановиться после ошибки методом "паники"
120
/// \todo Нужно будет доработать алгоритм восстановления после ошибок на что-то более интеллектуальное
122
for(; i < MAX_ERROR_RECOVER_ATTEMPTS; ++i) // Ограничиваем кол-во попыток
124
if (delayed_token.type() != inout::LexemeType::Error) {
125
token = delayed_token;
126
delayed_token = error_token(token.lexeme(), token.location());
129
token = getToken(tokenizer,_builder);
130
while(token.type() == inout::LexemeType::NewLine)
131
token = getToken(tokenizer,_builder);
133
column_no = _g.getTerminalColumnIndex(token);
134
if (_g.findFsmValue(state_no,column_no) || token.type() == inout::LexemeType::Empty)
138
if (i == MAX_ERROR_RECOVER_ATTEMPTS || !_g.findFsmValue(state_no,column_no))
142
Fsm_value_t fsm_value = _g.getFsmValue(state_no,column_no);
143
FsmActionType action = _g.unpackFsmAction(fsm_value);
147
case FsmActionType::Acceptance:
151
case FsmActionType::Error:
152
_m.reportError(token.makeLocation(_files), inout::fmt("Синтаксическая ошибка"));
157
case FsmActionType::Reduce:
159
size_t rule_no = _g.unpackFsmLocation(fsm_value);
160
const GrammarRule & r = _g.rules.at(rule_no);
162
assert(states.size() >= r.pattern.size());
165
inout::TokenLocation prod_location(states.back().location());
166
std::vector<inout::Token> pattern;
167
pattern.reserve(r.pattern.size());
169
for(size_t i=0; i < r.pattern.size() ; ++i) {
170
inout::Token t = states.back();
172
prod_location.merge(t.location());
173
pattern.insert(pattern.begin(), t);
174
/// \todo Нужно проверить: корректно ли именно тут сбрасывать состояние с точки зрения корректного восстановления
175
/// после синтаксической ошибки, значительная часть которых происходит во время редукции (см. обработку ниже).
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'")
187
size_t line = states.back().getStateNo();
189
if (!_g.findFsmValue(line,symbol_index)) {
190
reportSyntaxError(states, token);
194
if (token.type() == inout::LexemeType::Empty)
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() };
203
if (isLexemeValid(states,token)) {
204
column_no = symbol_index;
209
if (symbol_index == 0) {
214
Fsm_value_t val = _g.getFsmValue(line,symbol_index);
215
FsmActionType act = _g.unpackFsmAction(val);
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});
222
_m.reportWithPosition(inout::SeverityLevel::Fatal, token.makeLocation(_files),
223
inout::fmt("При обработке приведения возникло недопустимое состояние"));
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 },
235
states.back().getStateNo())) {
241
if (error_count == 0 &&
242
!_builder.onProduction(
243
inout::Token { {r.production, inout::LexemeType::Compound}, r.production, prod_location },
254
case FsmActionType::Shift:
256
Fsm_value_t val = _g.getFsmValue(state_no,column_no);
257
size_t shift = _g.unpackFsmLocation(val);
259
#ifdef AST_BUILDER_DEBUG
260
if (!_builder.onShift(state_no, _g.columns[column_no], column_no, shift)) {
266
PushdownAutomatonState ps(shift,column_no,token);
268
// Фрагмент кода, анализирующего возможность замены символа новой строки на заданный терминал
269
// (обычно это символ ';')
271
// Логика проверки возможности замены следующая:
272
// 1. Если подменяемый символ не допустим грамматикой языка - замена не производится
273
// 2. Если следующий символ после новой строки допустим грамматикой языка - замена не производится
275
// Чтобы проверить допустимость символа-замены и следующего символа недостаточно проверить текущее
276
// состояние разбора, так как оба символа могут участвовать в текущем контексте, но во вложенных
277
// структурах (например, символ '}' может быть допустим грамматикой в выражении для лямбды и нужно
278
// раскрутить стек состояний, чтобы убедиться, что мы находимся действительно в обработке лямбды,
279
// а не в конце выражения и символ '}' не является концом блока операторов).
280
// Для проверки допустимости токена в данном контексте по глубине стека состояний используется
281
// метод isTokenValid.
283
if (delayed_token.type() != inout::LexemeType::Error) {
284
token = delayed_token;
285
delayed_token = error_token(token.lexeme(), token.location());
288
token = getToken(tokenizer,_builder);
290
if (token.type() == inout::LexemeType::NewLine) {
291
inout::Token nl_token = token;
293
while(token.type() == inout::LexemeType::NewLine)
294
token = getToken(tokenizer,_builder);
296
// Для подмены символа замещения нужно, чтобы следующий символ не соответствовал грамматике
298
std::vector<PushdownAutomatonState> full_stack = states;
300
full_stack.push_back(ps);
302
if (!isLexemeValid(full_stack,token)) {
303
// Не соответствует...
305
nl_token = {inout::LexemeType::Punctuation, nl_token.lexeme(), nl_token.location() };
307
// Для подмены символа замещения нужно, чтобы символ замещения соответствовал грамматике
309
if (isLexemeValid(full_stack,nl_token)) {
312
delayed_token = token;
321
column_no = _g.getTerminalColumnIndex(token);
323
if (column_no == _g.columns.size()) {
324
// Полученный символ (токен) не предусмотрен данной грамматикой.
325
// Такое может быть, например, если грамматика не предусматривает числовых констант, а она таки записана.
326
// Или, что чаще бывает, введены ошибочные символы, которых нет в лексике грамматики (LexemeType::Error)
327
reportSyntaxError(states, token);
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() };
342
states.push_back(ps);
348
if (error_count == MAX_ERROR_COUNT)
349
_m.reportInformation(inout::fmt("Превышено допустимое количество ошибок, разбор прерван"));
351
_m.reportInformation(inout::fmt("Не удалось выполнить восстановление состояния разбора после синтаксической ошибки, разбор прерван"));
353
if (!_builder.onFinish(success, _g.handlers))
359
inout::Token PushdownAutomaton::getToken(inout::Tokenizer & tz, AstBuilder_interface & builder) const
361
inout::Token t = tz.getAnyToken();
363
builder.onTerminal(t);
365
while(t.type() == inout::LexemeType::Comment) {
366
t = tz.getAnyToken();
367
builder.onTerminal(t);
373
void PushdownAutomaton::reportSyntaxError(const std::vector<PushdownAutomatonState> &states, const inout::Token &t) const
375
assert(!states.empty());
377
const PushdownAutomatonState & parser_state = states.back();
380
std::vector<std::string> expected;
382
if (t.type() == inout::LexemeType::Empty)
383
briefly += inout::fmt("Преждевременный конец файла");
385
briefly += inout::fmt("Неподходящий входной символ '%1'.").arg(t.lexeme());
387
const FsmState_t & si = _g.states.at(parser_state.getStateNo());
389
// Просматриваем позиции текущего состояния
390
for(const FsmStatePosition &p : si) {
391
const GrammarRule &rule = _g.rules.at(p.rule_no);
393
if (atlarge.empty()) {
395
atlarge = inout::fmt("При разборе правила '%1").arg(rule.production);
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());
402
atlarge = inout::fmt("При разборе правила '%1").arg(rule.production);
404
atlarge += inout::fmt("' (состояние КА = %1) ").arg(inout::toU16(std::to_string(parser_state.getStateNo())));
406
if (t.type() == inout::LexemeType::Empty)
407
atlarge += inout::fmt("достигнут конец файла");
409
atlarge += inout::fmt("получен неподходящий символ '%1'").arg(t.lexeme());
411
atlarge += inout::fmt(", вместо ожидаемых символов: ");
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)));
419
// Отображаем перечень ожидаемых символов
420
for(auto st=expected.begin(); st != expected.end(); ++st) {
421
if (st != expected.begin())
426
atlarge += inout::fmt("\nПозиция разбора: %1").arg(inout::getLocationString(t.makeLocation(_files)));
428
_m.reportError(t.makeLocation(_files), briefly, atlarge);
431
bool PushdownAutomaton::isLexemeValid(std::vector<PushdownAutomatonState> states, const inout::Lexeme &lexeme) const
433
assert(!states.empty());
435
// Для определения допустимости заданного символа в текущем контексте выполняется следующий алгоритм:
437
// Необходимо для каждого состояния стека состояний, начиная с верхнего, убедиться, что:
438
// 1. если предусмотрен сдвиг или завершение, то символ является разрешённым, возвращаем true
439
// 2. иначе: для заданного символа предусмотрена свёртка, спускаемся ниже по стеку состояний.
440
// 3. достижение конца стека не должно произойти (по идее).
442
size_t column_no = _g.getTerminalColumnIndex(lexeme);
444
if (column_no >= _g.columns.size())
447
while(!states.empty()) {
448
const PushdownAutomatonState & ps = states.back();
449
size_t state_no = ps.getStateNo();
451
if (!_g.findFsmValue(state_no, column_no))
454
Fsm_value_t fsm_value = _g.getFsmValue(state_no, column_no);
455
FsmActionType fsm_action = _g.unpackFsmAction(fsm_value);
457
if (fsm_action == FsmActionType::Error)
460
if (fsm_action == FsmActionType::Shift || fsm_action == FsmActionType::Acceptance)
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();
467
for(size_t i=0; i < pattern_size; ++i)
470
size_t symbol_index = _g.getCompoundColumnIndex(rule.production);
471
assert(symbol_index < _g.columns.size());
473
size_t line = states.back().getStateNo();
475
if(!_g.findFsmValue(line,symbol_index))
478
Fsm_value_t val = _g.getFsmValue(line,symbol_index);
479
FsmActionType act = _g.unpackFsmAction(val);
481
assert(act == FsmActionType::Shift);
483
size_t st = _g.unpackFsmLocation(val);
485
states.emplace_back(st, symbol_index, inout::Token {inout::LexemeType::Compound, rule.production, ps.location()});
491
// inout::LexicalParameters PushdownAutomaton::makeLexicalParameters(const Grammar &g)