4
Copyright (c) 2021 МГТУ им. Н.Э. Баумана, кафедра ИУ-6, Михаил Фетисов,
6
https://bmstu.codes/lsx/simodo/loom
9
#include "simodo/interpret/builtins/hosts/fuze/ParsingTableBuilder_SLR.h"
11
#include "simodo/inout/convert/functions.h"
12
#include "simodo/inout/format/fmt.h"
17
namespace simodo::interpret::builtins
19
// По идее - этот вариант должен быть правильной реализацией SLR, т.к.
20
// просто поправлена неточность старого алгоритма.
21
#define SLR_IMPROVED_1
24
void ParsingTableBuilder_SLR::fillStateTable()
26
parser::FsmState_t state;
27
state.emplace_back(parser::FsmStatePosition(0,0));
28
_g.states.emplace_back(state);
32
_g.build_method = parser::TableBuildMethod::SLR;
35
void ParsingTableBuilder_SLR::fillStateInfo(size_t state_no)
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
43
// Функция вызывается, когда уже создано состояние для первой основной позиции
44
// Нужно добавить остальные основные позиции, согласно следующему критерию:
45
// Состояние НКА соответствует одинаковым позициям правил.
46
// Одинаковость позиций определяется тем, что все основные позиции состояния
47
// находятся после одного и того же нетерминала
48
// Например, если текущей позицией является начало последнего символа в шаблоне первого
49
// правила (E = E "+" .T), то находим все замыкания для текущей позиции.
50
// В замыкания (closure) попадают все правила, в которых есть начало символа
51
// текущей позиции (pos) с учётом рекурсивного нисходящего разворачивания правил.
52
// Другими словами, мы должны учесть, какие символы грамматики (терминалы и нетерминалы)
53
// могут встретиться на данной позиции, что определяется раскрытием текущего символа
54
// (если он нетерминал)
55
// Например, если текущей позицией является начало последнего символа в шаблоне первого
56
// правила (E = E "+" .T), то замыканиями являются следующие позиции:
63
/// \attention Код данного метода (как и всего данного класса) выполняет активную модификацию
64
/// структур грамматики, заданной в параметре _g. Поэтому, крайне не желательно создавать
65
/// ссылки на члены класса _g. Массивы могут реаллокироваться. Будьте осторожны.
67
assert(state_no < _g.states.size());
68
size_t position_initial_count = _g.states[state_no].size(); // размер массива в цикле не является инвариантом (мы его меняем)
70
for(size_t i=0; i < position_initial_count; ++i)
72
// Точно известно, что основные позиции состояния добавляются в начало
73
if (!_g.states[state_no][i].is_main)
76
size_t rno = _g.states[state_no][i].rule_no;
77
size_t pos = _g.states[state_no][i].position;
79
assert(rno < _g.rules.size());
80
const parser::GrammarRule & rule = _g.rules[rno]; // Текущее правило
82
// Находим замыкания и добавляем в заданное состояние как не основные позиции
83
if (pos < rule.pattern.size())
84
fillPreClosure(state_no, rule.pattern[pos]);
87
// Текущее состояние создано, готовим следующие состояния для основных правил
88
// Проходим по всем позициям нашего состояния и для каждого перехода
89
// создаем следующее состояние. Переходы для одинаковых символов грамматики объединяем,
90
// создавая в новом состоянии соотв-щие основные позиции. Проставляем значение next для позиций
92
for(size_t i_pos_in_state=0; i_pos_in_state < _g.states[state_no].size(); ++i_pos_in_state)
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;
97
assert(current_rno < _g.rules.size());
98
const parser::GrammarRule & current_rule = _g.rules[current_rno];
100
// Важно убедиться, что есть куда переходить
101
if (current_pos == current_rule.pattern.size())
103
// и эта позиция не использована ранее в этом же цикле (не установлено состояние перехода)
104
if (_g.states[state_no][i_pos_in_state].next_state_no > 0)
107
assert(current_pos < current_rule.pattern.size());
108
const inout::Lexeme & current_symbol = current_rule.pattern[current_pos];
110
// Для символа конца не создаётся новых состояний
111
if (current_symbol.type() == inout::LexemeType::Empty )
114
// Номер нового состояния будет отличаться от 0
115
uint16_t new_state_no = 0;
117
// Важно отметить, что основные состояния (FsmStatePosition::is_main == true) уникальны,
118
// в то время, как не основные являются сведёнными под совпадающий входной символ
119
// и не являются уникальными (см. fillPreClosure)
121
// Убеждаемся, что нужного основного состояния ещё нет
122
uint16_t find_state = findMainPosition(current_rno, current_pos+1);
123
uint16_t next_state_no;
124
if (find_state == 0) // (совпадение с нулевым состоянием невозможно, т.к. оно создаётся искусственно)
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;
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);
137
next_state_no = find_state;
138
_g.states[state_no][i_pos_in_state].next_state_no = find_state;
141
// Находим позицию с тем же переходным символом
142
for(size_t i_pos_add=i_pos_in_state+1; i_pos_add < _g.states[state_no].size(); ++i_pos_add)
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;
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])
155
// Проверяем, что такой основной позиции ещё нет
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)
164
// Добавляем основную позицию
165
_g.states[state_no][i_pos_add].next_state_no = next_state_no;
168
// Позиция добавляется либо после последней основной, либо в конец списка, если неосновных нет
169
_g.states[next_state_no].emplace(it, add_rno,add_pos+1,true,0);
170
new_state_no = next_state_no;
172
_g.states[state_no][i_pos_add].next_state_no = next_state_no;
175
if (add_pos < add_rule.pattern.size())
176
if (current_symbol == add_rule.pattern[add_pos])
178
_g.states[state_no][i_pos_add].next_state_no = next_state_no;
182
// Добавляем похожую позицию как основную для нового состояния
183
_g.states[next_state_no].emplace_back(add_rno,add_pos+1,true,0);
185
else if (add_pos == add_rule.pattern.size()-1)
187
// Данный блок кода добавлен исключительно для того,
188
// чтобы выявлять неоднозначности грамматики типа R-R,
189
// которые в противном случае остаются непроявленными.
190
// Кроме того, дерево переходов состояния становиться согласованным
191
// и полным, а ошибку можно увидеть визуально.
192
// Сами ошибки выявляются чуть позже
193
// (см. GrammarBuilder_SLR::fillParseTable и GrammarBuilder_SLR::insertValue)
195
for(; i < _g.states[next_state_no].size(); ++i)
196
if (_g.states[next_state_no][i].rule_no == add_rno)
199
if (i == _g.states[next_state_no].size())
200
_g.states[next_state_no].emplace_back(add_rno,add_pos+1,true,0);
205
// Вызываем себя рекурсивно, чтобы заполнить созданное состояние по аналогии
206
if (new_state_no != 0)
207
fillStateInfo(new_state_no);
211
uint16_t ParsingTableBuilder_SLR::findMainPosition(size_t rno, size_t pos) const
213
for(size_t it_state=0; it_state < _g.states.size(); ++it_state)
215
parser::FsmState_t & state = _g.states[it_state];
217
for(const parser::FsmStatePosition & p : state)
219
// Проверяем только основные позиции, и они всегда в начале
223
if (rno == p.rule_no && pos == p.position)
224
return static_cast<uint16_t>(it_state);
231
void ParsingTableBuilder_SLR::fillPreClosure(size_t state_no, const inout::Lexeme &lex) const
233
if (lex.type() != inout::LexemeType::Compound)
236
assert(state_no < _g.states.size());
238
auto range = _production_index.equal_range(lex.lexeme());
240
// Просматриваем продукции заданного символа
241
for(auto &it=range.first; it != range.second; ++it)
243
size_t rno = it->second;
244
const parser::GrammarRule & r = _g.rules[rno];
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)
251
if (i == _g.states[state_no].size())
253
_g.states[state_no].emplace_back(rno, 0, false, 0);
254
fillPreClosure(state_no, r.pattern[0]);
259
bool ParsingTableBuilder_SLR::fillParseTable()
263
for(size_t i_state=0; i_state < _g.states.size(); ++i_state)
265
const parser::FsmState_t &state = _g.states.at(i_state);
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())
271
const inout::Lexeme & s = r.pattern.at(p.position);
273
if (p.next_state_no == 0) // 0 не в последней позиции означает завершение
275
assert(s.type() == inout::LexemeType::Empty);
277
// Принятие (acceptance)
278
if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Acceptance,0)))
282
// p.next != 0 означает наличие перехода в соотв-щее состояние НКА
284
if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Shift,static_cast<size_t>(p.next_state_no))))
291
// Свёртки обрабатываем позже, чтобы при конфликтах принимать сдвиги
292
// Правила по умолчанию правоассоциативные
293
// (свёртки не будут записываться в таблицу, если соотв. позиция занята; кроме правил, помеченных как левоассациативные)
294
for(const parser::FsmStatePosition &p : state)
296
if (!p.is_main) // В свёртке могут участвовать только основные позиции, которые находятся всегда в начале списка
299
if (p.rule_no == 0 || p.next_state_no != 0)
302
const parser::GrammarRule &r = _g.rules.at(p.rule_no);
304
assert(p.position == r.pattern.size());
307
auto it_reduce_symbols = _reduce_symbol_set.find(r.production);
309
if (it_reduce_symbols == _reduce_symbol_set.end())
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;
315
fillReduceSymbolsUp(reduce_symbols, rule_set, p.rule_no);
317
auto [it, ok] = _reduce_symbol_set.insert({r.production, {}});
320
it->second.swap(reduce_symbols);
322
it_reduce_symbols = it;
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)))
337
void ParsingTableBuilder_SLR::fillReduceSymbolsUp(std::vector<inout::Lexeme> & reduce_symbols, std::set<size_t> & rule_set, size_t rule_no)
339
const size_t RULE_NUMBER_PACK_BOUNDARY = 10000;
341
assert(rule_no < _g.rules.size());
342
const std::u16string & production = _g.rules[rule_no].production;
344
auto range = _pattern_index.equal_range(production);
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;
350
if (rule_set.find(rule_no+RULE_NUMBER_PACK_BOUNDARY*next_rule_no) != rule_set.end())
353
rule_set.emplace(rule_no+RULE_NUMBER_PACK_BOUNDARY*next_rule_no);
355
const parser::GrammarRule & r = _g.rules[next_rule_no];
357
for(size_t i_pos=0; i_pos < r.pattern.size(); ++i_pos) {
358
const inout::Lexeme & s = r.pattern[i_pos];
360
if (s.lexeme() != production)
363
// Искомый символ найден!
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);
372
const inout::Lexeme & next_symbol = r.pattern[i_pos+1];
374
if (next_symbol.type() == inout::LexemeType::Compound) {
375
std::set<inout::Lexeme> processed;
376
fillReduceSymbolsDown(reduce_symbols, next_symbol.lexeme(), processed);
378
else if (find(reduce_symbols.begin(), reduce_symbols.end(), next_symbol) == reduce_symbols.end())
379
reduce_symbols.push_back(next_symbol);
385
void ParsingTableBuilder_SLR::fillReduceSymbolsDown(std::vector<inout::Lexeme> & reduce_symbols, const std::u16string & production, std::set<inout::Lexeme> & processed)
387
auto range = _production_index.equal_range(production);
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];
394
assert(!r.pattern.empty());
395
const inout::Lexeme & s = r.pattern.at(0);
397
if (s.type() == inout::LexemeType::Compound) {
398
if (s.lexeme() != production)
399
if (processed.end() == processed.find(s)) {
401
fillReduceSymbolsDown(reduce_symbols, s.lexeme(), processed);
404
else if (find(reduce_symbols.begin(), reduce_symbols.end(), s) == reduce_symbols.end())
405
reduce_symbols.push_back(s);
409
bool ParsingTableBuilder_SLR::insertValue(size_t line, size_t column, parser::Fsm_value_t value)
411
if (!_g.findFsmValue(line,column))
413
// Заданный вариант обработки отсутствует в таблице разбора - просто добавляем
414
_g.parse_table.emplace(_g.packFsmKey(line,column),value);
418
parser::Fsm_value_t exist_value = _g.getFsmValue(line,column);
420
parser::FsmActionType exist_action = _g.unpackFsmAction(exist_value);
421
parser::FsmActionType new_action = _g.unpackFsmAction(value);
423
// Если вариант обработки в таблице совпадает с заданным - всё ОК
424
if (exist_action == new_action && exist_value == value)
427
// Вариант обработки существует в таблице разбора и он отличается от нашего - нужно принять решение какой из них использовать
429
const inout::Lexeme & s = _g.columns.at(column);
431
size_t exist_location = _g.unpackFsmLocation(exist_value);
432
size_t new_location = _g.unpackFsmLocation(value);
434
std::string sout = inout::fmt("%1'. Состояние %2, символ %3 (#%4). Конфликтуют %5%6 и %7%8. ")
437
.arg(inout::getLexemeMnemonic(s))
439
.arg(parser::getFsmActionChar(exist_action))
441
.arg(parser::getFsmActionChar(new_action))
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];
448
if (exist_action == parser::FsmActionType::Shift && new_action == parser::FsmActionType::Reduce)
450
assert(new_location < _g.rules.size());
451
assert(new_location < _rules.size());
452
if (_g.rules[new_location].reduce_direction == parser::RuleReduceDirection::RightAssociative)
454
sout += inout::fmt("Принят %1%2.")
455
.arg(parser::getFsmActionChar(exist_action))
456
.arg(exist_location);
460
_g.parse_table.at(_g.packFsmKey(line,column)) = value;
461
sout += inout::fmt("Принят %1%2.")
462
.arg(parser::getFsmActionChar(new_action))
466
if (_g.rules[new_location].reduce_direction == parser::RuleReduceDirection::Undefined)
467
_m.reportError( t.makeLocation(files()),
468
inout::fmt("Неоднозначность грамматики '%1").arg(sout));
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;
481
_m.reportError( t.makeLocation(files()),
482
inout::fmt("Критическая неоднозначность грамматики '%1").arg(sout));
484
_number_of_collisions++;
486
return !_strict_rule_consistency;