Сначала хотелось продекларировать базис как есть, но подумав немного, можно неутешительно прийти к выводу — что четко определенный базис не будет иметь всякого смысла, так как находясь в данной точке пространства, в данный момент времени будущее, как и прошлое, весьма туманны.
часть 1
compilers.iecc.com/crenshaw/tutor1.txt
Introduction…
on the theory and practice of developing language parsers and compilers.
Просто очень хорошее чтиво ?
часть 2
compilers.iecc.com/crenshaw/tutor2.txt
Expression Parsing
В итоге нужно будет уметь запарсить вот такое выражение (1+2)/((3+4)+(5-6))
Что ж, начнем, пожалуй
std::string_view s{"(1+2)/((3+4)+(5-6))"}; const m = matcher{std::begin(s), std::end(s)}; lint(expression_t{}, m);То есть мы как бы предполагаем, что токен expression и есть выражение в скобках. Тут по идее нужно определить какую-то взаимосвязь между тремя токенами (почему именно три, честно говоря хз, предположим, что взяли наугад): expression, term и operator.
expression <-> term <-> operator
… есть 5+5
… есть 5+5+5
… есть 5+5+5+5
То есть первый вариант можно описать как: term, operator, term
Второй — term, operator, term, operator, term
Последующие — term, {operator, term}*
То есть expression = term, {operator, term}*
Далее term — это или число, или скобки. Чем так прекрасна рекурсия, что позволяет думать в терминах здесь и сейчас не думая о предыдущем контексте:
term = number | ‘(‘, expression, ‘)’ — или число, или «экспрешен» в скобках, а что за «экспрешен» — да пофиг. То есть можно было начать определение с term, без разницы в целом.
Еще раз что получилось:
expression = term, {operator, term}*
term = number | '(', expression, ')'
Переводим в код:
template<InputIterator I> result_t lint(const expression_t&, matcher<I>& m) { auto x = and_t { term_t{}, optional_t{ iff_t{ operator_t{}, expression_t{}, } } }; return lint(std::move(x), m); } struct term_t {}; template<InputIterator I> result_t lint(const term_t&, matcher<I>& m) { auto x = or_t { iff_t{ char_t{context::Chars::LeftBracket}, and_t{ expression_t{}, char_t{context::Chars::RightBracket} } }, number_t{}, }; return lint(std::move(x), m); } часть 3
compilers.iecc.com/crenshaw/tutor3.txt
More expression
Тут учимся парсить переменные и присваивание.
Довольно прямолийнейно-таки, но работает:
struct assignment_t {}; template<InputIterator I> result_t lint(const assignment_t&, matcher<I>& m) { auto x = std::vector<linter> { // models 'foreach' relation identifier_t{}, char_t{context::Chars::EqualSign}, expression_t{}, optional_t{ char_t{context::Chars::Semicolon} }, }; return lint(std::move(x), m); } часть 4
compilers.iecc.com/crenshaw/tutor4.txt
Interpreters
Не для целей линтера, но интересный и познавательный текст
часть 6
compilers.iecc.com/crenshaw/tutor6.txt
boolean expression
Интересное чтиво, но в нашей версии линтера забиваем на operator precedence
часть 5, часть 7
compilers.iecc.com/crenshaw/tutor7.txt
кейворды и лексический сканер
Вроде как сканер как раз и нужен из-за кейвордов. Люди когда-то поняли, что описание правил для «чистого текста» немного сложновато или скучновато. Почему бы не разобрать текст на токены и только затем применить правила разбора языка программирования? Так и делают взрослые ребята (включая Jack Crenshaw), а для нашего скромного линтера разбор на токены будет излишним или скучным. Но вопрос остался открытым: как различить кейворд и переменную?
while (true) {...} whilling = trueТо есть различие между двумя строчками мы найдем на пятом символе — с одной стороны, как-то поздновато, с другой — это информация, с которой можно работать. То есть у нас есть _выбор_ на основе информации о разборке блока с кейвордом: keyword -> match | mismatch | mismatch after n symbols where n > 0
Или переводя в код:
template<InputIterator I> result_t lint(const while_statement_t&, matcher<I>& m) { auto x = choice_t { keyword_t{context::Keywords::While}, // if we match keyword must_t {/* parse body of while expression */}, // let's check next keyword if we missing on first position if_statement_t{}, // if mismatch on any other positions just checking // for variable or function call mismatch_keyword_t{}, }; return lint(std::move(x), m); } struct choice_t { linter a; linter b; linter c; linter d; }; template <InputIterator I> constexpr result_t lint(const choice_t& x, matcher<I>& m) { auto r = lint(x.a, m); if (!r) return lint(x.b, m); return lint(*r == 0 ? x.c : x.d, m); } часть 8
compilers.iecc.com/crenshaw/tutor8.txt
Философская
На самом деле после семи шикарных, но очень больших частей наступает насыщение. Глава номер восемь читается живо, но с задумкой сделать паузу после. Восемь глав позади и восемь будет впереди, как бы намекая сделать остановку. Остановку сделаем после еще одного блока. Cейчас мы уже можем запарсить вот такой весьма бессмысленный, но возможно, часто встречаемый в продакшене скрипт:
const co = 4; const velosity = 42*co + 4/5; for (const x of xs) { log(x) } for (let x of xs) { x = x + 1 notify(x+x) } if (!shouldShow) { let i = 100; let j = 1000; startRecord(); while (i != (i-j)) { while((j+1 >= 100) && (i <= 50)) { if (i**j === 5) { log(i) } } i = i - 1; j = j - i; next(); } if (!!goodWeather) { i = 6**32 done(); } else { if (!willBeWorse) { i = -2; justSomeFunc(); } i = (1+2)/((3+4)+(5-6)) + i; notify(i); } }Блок, которого не хватает, есть функция. Функция — очень нужная вещь, без нее даже функционального программирования не построить, не говоря об других. Строим:
(a, b) => {...} // our lambda
(a + 5) * 42
Тут проблема парсинга: общая часть у нашей функции и выражения в скобках. На самом деле даже немного сложнее, так как общий префикс состоит как бы из двух токенов: скобки и переменной, — и только после третьего токена появится ответ на вопрос: «функция или не она».
Тут, на самом деле, есть пара направлений. Первый — как делают взрослые ребята — вернуться назад на два токена, если «не функция», и затем запустить парсер для выражения. У нас InputIterator, и вернуться назад, к сожалению, не можем. Была идея, как бы обмануть систему и добавить префикс к строке парсинга:
"(a - 5) * 42" -> начальная строка
"- 5) * 42" -> строка после фейла
"(а" `concat` "- 5) * 42" -> теперь пробуем заматчить выражение
Тут не смог найти что-то простое для объединения двух итераторов, хотя вроде как должно быть и не сложно, потому что last для InputIterator всегда один и тоже.
Второй варик слегка экзотический но тоже рабочий: у каждого линтера есть схема (auto x =… в примерах выше), что если эту схему запустить всего на один шаг, например:
auto x = and_t{ number_t{}, operator_t{}, number_t{}};
auto x2 = make(x, '5'); // скармливаем '5'
x2 // -> and_t{ noop_t{}, operator_t{}, number_t{}};
Теперь x2 валидная схема для ‘+7’ строчки. Алгоритм получается слегка овер сложный, а мы ищем легких и простых путей, поэтому запомним и отложим в сторонку.
Варик в приоритете — собрать ручками валидные схемы для выражения без первой скобки и переменной. Схемы слегка не привычные на вид, но довольно простые.
Кодик для ламбды:
struct lambda_t{}; template<InputIterator I> result_t lint(const lambda_t&, matcher<I>& m) { // (x, ...) => {...} // vs (x + 55) * 6 auto r = lint(char_t{context::Chars::LeftBracket}, m); auto p = lint(identifier_t{}, m); auto q = lint(char_t{context::Chars::Comma}, m); // based on results of r, p and q we have 2**3 = 8 options // halve of them are not supported by our parser // one follows directly to body of our lambda // others to expression or partial_expressions (e.g. without first bracket) } Теперь мы можем запарсить const bar = (a,b) => { foo(); bar(); } и покорить мир, ну пожалуй это будет уже в следующий раз ?
ссылка на оригинал статьи https://habr.com/ru/articles/685434/
Добавить комментарий