Иногда более-менее не тривиальную задачку приятно решить с чувством легкого базиса под ногами. Базис как бы уже есть, и мы как нечто среднее между художником и архитектором, ловим себя (в данный момент времени) на перекладывании пустого в порожнее, готовя нечто яркое и крепкое (почти как красное полусухое ?. Яркое — потому что без йоты красоты легко сойти на полпути, а крепкое — профессия обязывает. Чтобы было еще ярче, призовем в помощь замечательные серии 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(); } и покорить мир, ну пожалуй это будет уже в следующий раз ?

Еще один пересказ «туториала» Джека Креншоу