Иногда более-менее не тривиальную задачку приятно решить с чувством легкого базиса под ногами. Базис как бы уже есть, и мы как нечто среднее между художником и архитектором, ловим себя (в данный момент времени) на перекладывании пустого в порожнее, готовя нечто яркое и крепкое (почти как красное полусухое 
. Яркое — потому что без йоты красоты легко сойти на полпути, а крепкое — профессия обязывает. Чтобы было еще ярче, призовем в помощь замечательные серии Jack Crenshaw compilers.iecc.com/crenshaw (non-technical introduction to compiler construction) и начнем, пожалуй, с построения маленького, но вполне достойного линтера en.wikipedia.org/wiki/Lint_(software) (Честно говоря, так как ниже будет имплементен разбор яваскрипт кода, вполне допустимо, но только временно, переименовать линтер в парсер и думать дальше в новых терминах)
Сначала хотелось продекларировать базис как есть, но подумав немного, можно неутешительно прийти к выводу — что четко определенный базис не будет иметь всякого смысла, так как находясь в данной точке пространства, в данный момент времени будущее, как и прошлое, весьма туманны.
часть 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(); } и покорить мир, ну пожалуй это будет уже в следующий раз
habr.com
. Яркое — потому что без йоты красоты легко сойти на полпути, а крепкое — профессия обязывает. Чтобы было еще ярче, призовем в помощь замечательные серии Jack Crenshaw compilers.iecc.com/crenshaw (non-technical introduction to compiler construction) и начнем, пожалуй, с построения маленького, но вполне достойного линтера en.wikipedia.org/wiki/Lint_(software) (Честно говоря, так как ниже будет имплементен разбор яваскрипт кода, вполне допустимо, но только временно, переименовать линтер в парсер и думать дальше в новых терминах)Сначала хотелось продекларировать базис как есть, но подумав немного, можно неутешительно прийти к выводу — что четко определенный базис не будет иметь всякого смысла, так как находясь в данной точке пространства, в данный момент времени будущее, как и прошлое, весьма туманны.
часть 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(); } и покорить мир, ну пожалуй это будет уже в следующий раз
Еще один пересказ «туториала» Джека Креншоу
Иногда более-менее не тривиальную задачку приятно решить с чувством легкого базиса под ногами. Базис как бы уже есть, и мы как нечто среднее между художником и архитектором, ловим себя (в данный...
habr.com