Parser
(utilities/parser.hpp)

• View this file on GitHub
• Last update: 2026-06-21 10:44:51+09:00
• Include: #include "utilities/parser.hpp"

Overview

Parser is a lightweight cursor over a std::string_view for recursive-descent parsing. It is useful when a problem’s input is an expression, nested notation, command language, encoded tree, or another format that is awkward to read with operator>>.

The parser does not own or copy its input. Most successful operations return std::string_view, and ordinary parsing performs no allocation. Failed try_... operations restore the cursor to where the operation started.

#include "utilities/parser.hpp"

All names are in m1une::utilities.

Cursor operations

Operation	Description	Complexity
Parser(input)	Creates a parser over input. The input must outlive the parser and returned views.	$O(1)$
source()	Returns the complete input.	$O(1)$
size() / position()	Returns the input size or current cursor position.	$O(1)$
eof()	Tests whether the cursor is at the end.	$O(1)$
remaining()	Returns the unparsed suffix.	$O(1)$
peek(offset)	Returns the character at the cursor plus offset, or std::nullopt.	$O(1)$
mark() / restore(mark)	Saves and restores a cursor position.	$O(1)$
checkpoint()	Creates an automatic rollback point.	$O(1)$
skip_whitespace()	Skips characters recognized by std::isspace.	Linear in the skipped length.

Checkpoint restores the old position when it leaves scope. Call commit() to keep the new position, or rollback() to restore it immediately. It is useful for alternatives with several parsing steps:

auto attempt = parser.checkpoint();
if (parser.consume("min") && parser.consume('(')) {
    // Parse the rest of this alternative.
    attempt.commit();
}

Exact parsing primitives

These operations start exactly at the current cursor; they do not skip whitespace.

Operation	Description
consume(character)	Consumes one matching character and returns whether it matched.
consume(text)	Consumes a matching string and returns whether it matched.
consume_if(predicate)	Consumes one character accepted by predicate.
expect(character) / expect(text)	Consumes the expected input or throws ParseError.
take(count)	Consumes exactly count characters, or returns std::nullopt without moving.
read_while(predicate)	Consumes and returns the longest prefix accepted by predicate.
read_until(delimiter, consume_delimiter)	Returns text up to the delimiter or end of input.

ParseError::position() reports the byte position where the failed expectation was made. Its what() message also includes that position.

Token-level readers

The following readers first skip whitespace:

Trying operation	Throwing operation	Accepted input
try_token()	token()	One or more non-whitespace characters.
try_identifier()	identifier()	[A-Za-z_][A-Za-z0-9_]*, using the corresponding character classification functions.
try_integer<T>(base)	integer<T>(base)	An optional sign and digits in base 2 through 36, checked for overflow.
try_real()	real()	A decimal number with an optional sign, fractional part, and exponent.
try_balanced(open, close)	balanced(open, close)	A nested delimiter pair; the returned view excludes the outer pair.

Trying operations return std::nullopt and restore the cursor when parsing fails. Throwing operations throw ParseError. Integer overflow is considered a parse failure. try_balanced only tracks its two delimiter characters; it does not give quotes or escape sequences special meaning.

All operations are linear in the number of characters they inspect.

Recursive-descent example

This parser evaluates integers, parentheses, addition, and subtraction:

#include "utilities/parser.hpp"

using m1une::utilities::Parser;

long long expression(Parser& parser);

long long atom(Parser& parser) {
    parser.skip_whitespace();
    if (parser.consume('(')) {
        long long value = expression(parser);
        parser.skip_whitespace();
        parser.expect(')');
        return value;
    }
    return parser.integer<long long>();
}

long long expression(Parser& parser) {
    long long value = atom(parser);
    while (true) {
        parser.skip_whitespace();
        if (parser.consume('+')) {
            value += atom(parser);
        } else if (parser.consume('-')) {
            value -= atom(parser);
        } else {
            return value;
        }
    }
}

int main() {
    Parser parser("10 - (3 + -2)");
    long long answer = expression(parser);
    parser.skip_whitespace();
    if (!parser.eof()) {
        throw m1une::utilities::ParseError(
            parser.position(),
            "unexpected trailing input"
        );
    }
}

Building a parsing tree

A parsing tree stores the structure of the input instead of immediately evaluating it. This is useful when later steps need to inspect, transform, or evaluate the expression more than once.

In practice, competitive-programming solutions usually build an abstract syntax tree (AST). A concrete parse tree would also contain punctuation and grammar-only nodes, while an AST keeps only meaningful operations and values. For example, the parentheses in 2 * (3 + 4) affect the shape of the AST but do not need their own nodes.

Start by writing a grammar whose functions correspond to precedence levels:

expression := product (('+' | '-') product)*
product    := unary (('*' | '/') unary)*
unary      := ('+' | '-') unary | atom
atom       := integer | '(' expression ')'

Calling lower lines from higher lines gives multiplication and division higher precedence than addition and subtraction. The loops make binary operators left-associative, so 8 - 3 - 2 is parsed as (8 - 3) - 2.

The following node type owns its children with std::unique_ptr. This avoids pointer invalidation and automatically destroys the complete tree:

#include "utilities/parser.hpp"

#include <memory>

enum class NodeKind {
    number,
    negate,
    add,
    subtract,
    multiply,
    divide
};

struct Node {
    NodeKind kind = NodeKind::number;
    long long value = 0;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};

std::unique_ptr<Node> make_number(long long value) {
    auto node = std::make_unique<Node>();
    node->value = value;
    return node;
}

std::unique_ptr<Node> make_unary(
    NodeKind kind,
    std::unique_ptr<Node> child
) {
    auto node = std::make_unique<Node>();
    node->kind = kind;
    node->left = std::move(child);
    return node;
}

std::unique_ptr<Node> make_binary(
    NodeKind kind,
    std::unique_ptr<Node> left,
    std::unique_ptr<Node> right
) {
    auto node = std::make_unique<Node>();
    node->kind = kind;
    node->left = std::move(left);
    node->right = std::move(right);
    return node;
}

Each parsing function consumes exactly one grammar rule and returns the root of the subtree it built:

using m1une::utilities::Parser;

std::unique_ptr<Node> parse_expression(Parser& parser);

std::unique_ptr<Node> parse_atom(Parser& parser) {
    parser.skip_whitespace();
    if (parser.consume('(')) {
        std::unique_ptr<Node> node = parse_expression(parser);
        parser.skip_whitespace();
        parser.expect(')');
        return node;
    }
    return make_number(parser.integer<long long>());
}

std::unique_ptr<Node> parse_unary(Parser& parser) {
    parser.skip_whitespace();
    if (parser.consume('+')) {
        return parse_unary(parser);
    }
    if (parser.consume('-')) {
        return make_unary(NodeKind::negate, parse_unary(parser));
    }
    return parse_atom(parser);
}

std::unique_ptr<Node> parse_product(Parser& parser) {
    std::unique_ptr<Node> node = parse_unary(parser);
    while (true) {
        parser.skip_whitespace();
        if (parser.consume('*')) {
            node = make_binary(
                NodeKind::multiply,
                std::move(node),
                parse_unary(parser)
            );
        } else if (parser.consume('/')) {
            node = make_binary(
                NodeKind::divide,
                std::move(node),
                parse_unary(parser)
            );
        } else {
            return node;
        }
    }
}

std::unique_ptr<Node> parse_expression(Parser& parser) {
    std::unique_ptr<Node> node = parse_product(parser);
    while (true) {
        parser.skip_whitespace();
        if (parser.consume('+')) {
            node = make_binary(
                NodeKind::add,
                std::move(node),
                parse_product(parser)
            );
        } else if (parser.consume('-')) {
            node = make_binary(
                NodeKind::subtract,
                std::move(node),
                parse_product(parser)
            );
        } else {
            return node;
        }
    }
}

Always check for trailing input after constructing the root. Without this check, a valid prefix such as 1 + 2 could hide an invalid suffix.

Parser parser("2 * (3 + 4)");
std::unique_ptr<Node> root = parse_expression(parser);
parser.skip_whitespace();
if (!parser.eof()) {
    throw m1une::utilities::ParseError(
        parser.position(),
        "unexpected trailing input"
    );
}

For very large trees, allocating each node separately can be slower than using a node pool. Store nodes in a pre-reserved std::vector<Node> and use integer indices as child links when performance or memory locality matters. If a node stores an identifier as std::string_view, the parser’s original input must remain alive for as long as the tree.

Verified with

• verify/utilities/parser.test.cpp

Code

#ifndef M1UNE_PARSER_HPP
#define M1UNE_PARSER_HPP 1

#include <cctype>
#include <cmath>
#include <cstddef>
#include <limits>
#include <optional>
#include <stdexcept>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>

namespace m1une {
namespace utilities {

class ParseError : public std::runtime_error {
private:
    std::size_t position_;

public:
    ParseError(std::size_t position, const std::string& message)
        : std::runtime_error(message + " at position " + std::to_string(position)),
          position_(position) {}

    [[nodiscard]] std::size_t position() const noexcept {
        return position_;
    }
};

class Parser {
public:
    using mark_type = std::size_t;

    class Checkpoint {
    private:
        Parser* parser_;
        mark_type position_;

    public:
        explicit Checkpoint(Parser& parser) noexcept
            : parser_(&parser), position_(parser.position()) {}

        Checkpoint(const Checkpoint&) = delete;
        Checkpoint& operator=(const Checkpoint&) = delete;

        Checkpoint(Checkpoint&& other) noexcept
            : parser_(std::exchange(other.parser_, nullptr)),
              position_(other.position_) {}

        Checkpoint& operator=(Checkpoint&&) = delete;

        ~Checkpoint() {
            rollback();
        }

        void commit() noexcept {
            parser_ = nullptr;
        }

        void rollback() noexcept {
            if (parser_ != nullptr) {
                parser_->position_ = position_;
                parser_ = nullptr;
            }
        }
    };

private:
    std::string_view input_;
    std::size_t position_ = 0;

    static int digit_value(char character) noexcept {
        if ('0' <= character && character <= '9') {
            return character - '0';
        }
        if ('a' <= character && character <= 'z') {
            return character - 'a' + 10;
        }
        if ('A' <= character && character <= 'Z') {
            return character - 'A' + 10;
        }
        return -1;
    }

    [[noreturn]] void fail(const std::string& message) const {
        throw ParseError(position_, message);
    }

public:
    Parser() = default;

    explicit Parser(std::string_view input) noexcept : input_(input) {}

    [[nodiscard]] std::string_view source() const noexcept {
        return input_;
    }

    [[nodiscard]] std::size_t size() const noexcept {
        return input_.size();
    }

    [[nodiscard]] std::size_t position() const noexcept {
        return position_;
    }

    [[nodiscard]] bool eof() const noexcept {
        return position_ == input_.size();
    }

    [[nodiscard]] std::string_view remaining() const noexcept {
        return input_.substr(position_);
    }

    [[nodiscard]] std::optional<char> peek(std::size_t offset = 0) const noexcept {
        if (offset >= input_.size() - position_) {
            return std::nullopt;
        }
        return input_[position_ + offset];
    }

    [[nodiscard]] mark_type mark() const noexcept {
        return position_;
    }

    void restore(mark_type saved_position) {
        if (saved_position > input_.size()) {
            throw std::out_of_range("parser position is outside the input");
        }
        position_ = saved_position;
    }

    [[nodiscard]] Checkpoint checkpoint() noexcept {
        return Checkpoint(*this);
    }

    template <typename Predicate>
    std::string_view read_while(Predicate predicate) {
        std::size_t begin = position_;
        while (!eof() && predicate(input_[position_])) {
            ++position_;
        }
        return input_.substr(begin, position_ - begin);
    }

    std::size_t skip_whitespace() noexcept {
        std::size_t begin = position_;
        while (!eof() && std::isspace(static_cast<unsigned char>(input_[position_]))) {
            ++position_;
        }
        return position_ - begin;
    }

    bool consume(char expected) noexcept {
        if (eof() || input_[position_] != expected) {
            return false;
        }
        ++position_;
        return true;
    }

    bool consume(std::string_view expected) noexcept {
        if (remaining().substr(0, expected.size()) != expected) {
            return false;
        }
        position_ += expected.size();
        return true;
    }

    template <typename Predicate>
    bool consume_if(Predicate predicate) {
        if (eof() || !predicate(input_[position_])) {
            return false;
        }
        ++position_;
        return true;
    }

    void expect(char expected) {
        if (!consume(expected)) {
            fail(std::string("expected '") + expected + "'");
        }
    }

    void expect(std::string_view expected) {
        if (!consume(expected)) {
            fail("expected \"" + std::string(expected) + "\"");
        }
    }

    std::optional<std::string_view> take(std::size_t count) noexcept {
        if (count > input_.size() - position_) {
            return std::nullopt;
        }
        std::string_view result = input_.substr(position_, count);
        position_ += count;
        return result;
    }

    std::string_view read_until(char delimiter, bool consume_delimiter = false) noexcept {
        std::size_t begin = position_;
        std::size_t found = input_.find(delimiter, position_);
        if (found == std::string_view::npos) {
            position_ = input_.size();
            return input_.substr(begin);
        }
        position_ = found + (consume_delimiter ? 1 : 0);
        return input_.substr(begin, found - begin);
    }

    std::optional<std::string_view> try_token() noexcept {
        mark_type begin_attempt = mark();
        skip_whitespace();
        std::size_t begin = position_;
        while (!eof() && !std::isspace(static_cast<unsigned char>(input_[position_]))) {
            ++position_;
        }
        if (begin == position_) {
            position_ = begin_attempt;
            return std::nullopt;
        }
        return input_.substr(begin, position_ - begin);
    }

    std::string_view token() {
        std::size_t error_position = position_;
        std::optional<std::string_view> result = try_token();
        if (!result.has_value()) {
            position_ = error_position;
            fail("expected token");
        }
        return *result;
    }

    std::optional<std::string_view> try_identifier() noexcept {
        mark_type begin_attempt = mark();
        skip_whitespace();
        if (eof()) {
            position_ = begin_attempt;
            return std::nullopt;
        }

        unsigned char first = static_cast<unsigned char>(input_[position_]);
        if (!(std::isalpha(first) || input_[position_] == '_')) {
            position_ = begin_attempt;
            return std::nullopt;
        }

        std::size_t begin = position_++;
        while (!eof()) {
            unsigned char current = static_cast<unsigned char>(input_[position_]);
            if (!(std::isalnum(current) || input_[position_] == '_')) {
                break;
            }
            ++position_;
        }
        return input_.substr(begin, position_ - begin);
    }

    std::string_view identifier() {
        std::size_t error_position = position_;
        std::optional<std::string_view> result = try_identifier();
        if (!result.has_value()) {
            position_ = error_position;
            fail("expected identifier");
        }
        return *result;
    }

    template <typename Integer>
    std::optional<Integer> try_integer(int base = 10) {
        static_assert(
            std::is_integral_v<Integer> && !std::is_same_v<Integer, bool>,
            "Integer must be a non-bool integral type"
        );
        if (base < 2 || base > 36) {
            throw std::invalid_argument("integer base must be in [2, 36]");
        }

        mark_type begin_attempt = mark();
        skip_whitespace();

        bool negative = false;
        if (consume('+')) {
            // The sign is already consumed.
        } else if (consume('-')) {
            if constexpr (std::is_unsigned_v<Integer>) {
                position_ = begin_attempt;
                return std::nullopt;
            } else {
                negative = true;
            }
        }

        using Unsigned = std::make_unsigned_t<Integer>;
        Unsigned limit = std::numeric_limits<Integer>::max();
        if constexpr (std::is_signed_v<Integer>) {
            if (negative) {
                limit += Unsigned(1);
            }
        }

        Unsigned value = 0;
        std::size_t digit_count = 0;
        while (!eof()) {
            int digit = digit_value(input_[position_]);
            if (digit < 0 || digit >= base) {
                break;
            }
            Unsigned unsigned_digit = static_cast<Unsigned>(digit);
            if (value > (limit - unsigned_digit) / static_cast<Unsigned>(base)) {
                position_ = begin_attempt;
                return std::nullopt;
            }
            value = value * static_cast<Unsigned>(base) + unsigned_digit;
            ++position_;
            ++digit_count;
        }

        if (digit_count == 0) {
            position_ = begin_attempt;
            return std::nullopt;
        }

        if constexpr (std::is_signed_v<Integer>) {
            if (negative) {
                if (value == static_cast<Unsigned>(std::numeric_limits<Integer>::max()) + 1) {
                    return std::numeric_limits<Integer>::min();
                }
                return static_cast<Integer>(-static_cast<Integer>(value));
            }
        }
        return static_cast<Integer>(value);
    }

    template <typename Integer>
    Integer integer(int base = 10) {
        std::size_t error_position = position_;
        std::optional<Integer> result = try_integer<Integer>(base);
        if (!result.has_value()) {
            position_ = error_position;
            fail("expected integer");
        }
        return *result;
    }

    std::optional<long double> try_real() noexcept {
        mark_type begin_attempt = mark();
        skip_whitespace();

        bool negative = false;
        if (consume('+')) {
            // The sign is already consumed.
        } else if (consume('-')) {
            negative = true;
        }

        long double value = 0;
        std::size_t digit_count = 0;
        while (!eof() && std::isdigit(static_cast<unsigned char>(input_[position_]))) {
            value = value * 10 + (input_[position_] - '0');
            ++position_;
            ++digit_count;
        }

        if (consume('.')) {
            long double place = 0.1L;
            while (!eof() && std::isdigit(static_cast<unsigned char>(input_[position_]))) {
                value += (input_[position_] - '0') * place;
                place *= 0.1L;
                ++position_;
                ++digit_count;
            }
        }

        if (digit_count == 0) {
            position_ = begin_attempt;
            return std::nullopt;
        }

        mark_type exponent_begin = mark();
        int exponent = 0;
        bool exponent_negative = false;
        if (consume('e') || consume('E')) {
            if (consume('+')) {
                // The sign is already consumed.
            } else if (consume('-')) {
                exponent_negative = true;
            }

            std::size_t exponent_digits = 0;
            while (!eof() && std::isdigit(static_cast<unsigned char>(input_[position_]))) {
                if (exponent < 1000000) {
                    exponent = exponent * 10 + (input_[position_] - '0');
                }
                ++position_;
                ++exponent_digits;
            }
            if (exponent_digits == 0) {
                position_ = exponent_begin;
                exponent = 0;
                exponent_negative = false;
            }
        }

        if (exponent != 0) {
            long double scale = std::pow(10.0L, exponent);
            value = exponent_negative ? value / scale : value * scale;
        }
        return negative ? -value : value;
    }

    long double real() {
        std::size_t error_position = position_;
        std::optional<long double> result = try_real();
        if (!result.has_value()) {
            position_ = error_position;
            fail("expected real number");
        }
        return *result;
    }

    std::optional<std::string_view> try_balanced(
        char opening = '(',
        char closing = ')'
    ) {
        if (opening == closing) {
            throw std::invalid_argument("balanced delimiters must be different");
        }

        mark_type begin_attempt = mark();
        skip_whitespace();
        if (!consume(opening)) {
            position_ = begin_attempt;
            return std::nullopt;
        }

        std::size_t content_begin = position_;
        int depth = 1;
        while (!eof()) {
            char current = input_[position_++];
            if (current == opening) {
                ++depth;
            } else if (current == closing) {
                --depth;
                if (depth == 0) {
                    return input_.substr(content_begin, position_ - content_begin - 1);
                }
            }
        }

        position_ = begin_attempt;
        return std::nullopt;
    }

    std::string_view balanced(char opening = '(', char closing = ')') {
        std::size_t error_position = position_;
        std::optional<std::string_view> result = try_balanced(opening, closing);
        if (!result.has_value()) {
            position_ = error_position;
            fail("expected balanced delimiters");
        }
        return *result;
    }
};

}  // namespace utilities
}  // namespace m1une

#endif  // M1UNE_PARSER_HPP

#line 1 "utilities/parser.hpp"



#include <cctype>
#include <cmath>
#include <cstddef>
#include <limits>
#include <optional>
#include <stdexcept>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>

namespace m1une {
namespace utilities {

class ParseError : public std::runtime_error {
private:
    std::size_t position_;

public:
    ParseError(std::size_t position, const std::string& message)
        : std::runtime_error(message + " at position " + std::to_string(position)),
          position_(position) {}

    [[nodiscard]] std::size_t position() const noexcept {
        return position_;
    }
};

class Parser {
public:
    using mark_type = std::size_t;

    class Checkpoint {
    private:
        Parser* parser_;
        mark_type position_;

    public:
        explicit Checkpoint(Parser& parser) noexcept
            : parser_(&parser), position_(parser.position()) {}

        Checkpoint(const Checkpoint&) = delete;
        Checkpoint& operator=(const Checkpoint&) = delete;

        Checkpoint(Checkpoint&& other) noexcept
            : parser_(std::exchange(other.parser_, nullptr)),
              position_(other.position_) {}

        Checkpoint& operator=(Checkpoint&&) = delete;

        ~Checkpoint() {
            rollback();
        }

        void commit() noexcept {
            parser_ = nullptr;
        }

        void rollback() noexcept {
            if (parser_ != nullptr) {
                parser_->position_ = position_;
                parser_ = nullptr;
            }
        }
    };

private:
    std::string_view input_;
    std::size_t position_ = 0;

    static int digit_value(char character) noexcept {
        if ('0' <= character && character <= '9') {
            return character - '0';
        }
        if ('a' <= character && character <= 'z') {
            return character - 'a' + 10;
        }
        if ('A' <= character && character <= 'Z') {
            return character - 'A' + 10;
        }
        return -1;
    }

    [[noreturn]] void fail(const std::string& message) const {
        throw ParseError(position_, message);
    }

public:
    Parser() = default;

    explicit Parser(std::string_view input) noexcept : input_(input) {}

    [[nodiscard]] std::string_view source() const noexcept {
        return input_;
    }

    [[nodiscard]] std::size_t size() const noexcept {
        return input_.size();
    }

    [[nodiscard]] std::size_t position() const noexcept {
        return position_;
    }

    [[nodiscard]] bool eof() const noexcept {
        return position_ == input_.size();
    }

    [[nodiscard]] std::string_view remaining() const noexcept {
        return input_.substr(position_);
    }

    [[nodiscard]] std::optional<char> peek(std::size_t offset = 0) const noexcept {
        if (offset >= input_.size() - position_) {
            return std::nullopt;
        }
        return input_[position_ + offset];
    }

    [[nodiscard]] mark_type mark() const noexcept {
        return position_;
    }

    void restore(mark_type saved_position) {
        if (saved_position > input_.size()) {
            throw std::out_of_range("parser position is outside the input");
        }
        position_ = saved_position;
    }

    [[nodiscard]] Checkpoint checkpoint() noexcept {
        return Checkpoint(*this);
    }

    template <typename Predicate>
    std::string_view read_while(Predicate predicate) {
        std::size_t begin = position_;
        while (!eof() && predicate(input_[position_])) {
            ++position_;
        }
        return input_.substr(begin, position_ - begin);
    }

    std::size_t skip_whitespace() noexcept {
        std::size_t begin = position_;
        while (!eof() && std::isspace(static_cast<unsigned char>(input_[position_]))) {
            ++position_;
        }
        return position_ - begin;
    }

    bool consume(char expected) noexcept {
        if (eof() || input_[position_] != expected) {
            return false;
        }
        ++position_;
        return true;
    }

    bool consume(std::string_view expected) noexcept {
        if (remaining().substr(0, expected.size()) != expected) {
            return false;
        }
        position_ += expected.size();
        return true;
    }

    template <typename Predicate>
    bool consume_if(Predicate predicate) {
        if (eof() || !predicate(input_[position_])) {
            return false;
        }
        ++position_;
        return true;
    }

    void expect(char expected) {
        if (!consume(expected)) {
            fail(std::string("expected '") + expected + "'");
        }
    }

    void expect(std::string_view expected) {
        if (!consume(expected)) {
            fail("expected \"" + std::string(expected) + "\"");
        }
    }

    std::optional<std::string_view> take(std::size_t count) noexcept {
        if (count > input_.size() - position_) {
            return std::nullopt;
        }
        std::string_view result = input_.substr(position_, count);
        position_ += count;
        return result;
    }

    std::string_view read_until(char delimiter, bool consume_delimiter = false) noexcept {
        std::size_t begin = position_;
        std::size_t found = input_.find(delimiter, position_);
        if (found == std::string_view::npos) {
            position_ = input_.size();
            return input_.substr(begin);
        }
        position_ = found + (consume_delimiter ? 1 : 0);
        return input_.substr(begin, found - begin);
    }

    std::optional<std::string_view> try_token() noexcept {
        mark_type begin_attempt = mark();
        skip_whitespace();
        std::size_t begin = position_;
        while (!eof() && !std::isspace(static_cast<unsigned char>(input_[position_]))) {
            ++position_;
        }
        if (begin == position_) {
            position_ = begin_attempt;
            return std::nullopt;
        }
        return input_.substr(begin, position_ - begin);
    }

    std::string_view token() {
        std::size_t error_position = position_;
        std::optional<std::string_view> result = try_token();
        if (!result.has_value()) {
            position_ = error_position;
            fail("expected token");
        }
        return *result;
    }

    std::optional<std::string_view> try_identifier() noexcept {
        mark_type begin_attempt = mark();
        skip_whitespace();
        if (eof()) {
            position_ = begin_attempt;
            return std::nullopt;
        }

        unsigned char first = static_cast<unsigned char>(input_[position_]);
        if (!(std::isalpha(first) || input_[position_] == '_')) {
            position_ = begin_attempt;
            return std::nullopt;
        }

        std::size_t begin = position_++;
        while (!eof()) {
            unsigned char current = static_cast<unsigned char>(input_[position_]);
            if (!(std::isalnum(current) || input_[position_] == '_')) {
                break;
            }
            ++position_;
        }
        return input_.substr(begin, position_ - begin);
    }

    std::string_view identifier() {
        std::size_t error_position = position_;
        std::optional<std::string_view> result = try_identifier();
        if (!result.has_value()) {
            position_ = error_position;
            fail("expected identifier");
        }
        return *result;
    }

    template <typename Integer>
    std::optional<Integer> try_integer(int base = 10) {
        static_assert(
            std::is_integral_v<Integer> && !std::is_same_v<Integer, bool>,
            "Integer must be a non-bool integral type"
        );
        if (base < 2 || base > 36) {
            throw std::invalid_argument("integer base must be in [2, 36]");
        }

        mark_type begin_attempt = mark();
        skip_whitespace();

        bool negative = false;
        if (consume('+')) {
            // The sign is already consumed.
        } else if (consume('-')) {
            if constexpr (std::is_unsigned_v<Integer>) {
                position_ = begin_attempt;
                return std::nullopt;
            } else {
                negative = true;
            }
        }

        using Unsigned = std::make_unsigned_t<Integer>;
        Unsigned limit = std::numeric_limits<Integer>::max();
        if constexpr (std::is_signed_v<Integer>) {
            if (negative) {
                limit += Unsigned(1);
            }
        }

        Unsigned value = 0;
        std::size_t digit_count = 0;
        while (!eof()) {
            int digit = digit_value(input_[position_]);
            if (digit < 0 || digit >= base) {
                break;
            }
            Unsigned unsigned_digit = static_cast<Unsigned>(digit);
            if (value > (limit - unsigned_digit) / static_cast<Unsigned>(base)) {
                position_ = begin_attempt;
                return std::nullopt;
            }
            value = value * static_cast<Unsigned>(base) + unsigned_digit;
            ++position_;
            ++digit_count;
        }

        if (digit_count == 0) {
            position_ = begin_attempt;
            return std::nullopt;
        }

        if constexpr (std::is_signed_v<Integer>) {
            if (negative) {
                if (value == static_cast<Unsigned>(std::numeric_limits<Integer>::max()) + 1) {
                    return std::numeric_limits<Integer>::min();
                }
                return static_cast<Integer>(-static_cast<Integer>(value));
            }
        }
        return static_cast<Integer>(value);
    }

    template <typename Integer>
    Integer integer(int base = 10) {
        std::size_t error_position = position_;
        std::optional<Integer> result = try_integer<Integer>(base);
        if (!result.has_value()) {
            position_ = error_position;
            fail("expected integer");
        }
        return *result;
    }

    std::optional<long double> try_real() noexcept {
        mark_type begin_attempt = mark();
        skip_whitespace();

        bool negative = false;
        if (consume('+')) {
            // The sign is already consumed.
        } else if (consume('-')) {
            negative = true;
        }

        long double value = 0;
        std::size_t digit_count = 0;
        while (!eof() && std::isdigit(static_cast<unsigned char>(input_[position_]))) {
            value = value * 10 + (input_[position_] - '0');
            ++position_;
            ++digit_count;
        }

        if (consume('.')) {
            long double place = 0.1L;
            while (!eof() && std::isdigit(static_cast<unsigned char>(input_[position_]))) {
                value += (input_[position_] - '0') * place;
                place *= 0.1L;
                ++position_;
                ++digit_count;
            }
        }

        if (digit_count == 0) {
            position_ = begin_attempt;
            return std::nullopt;
        }

        mark_type exponent_begin = mark();
        int exponent = 0;
        bool exponent_negative = false;
        if (consume('e') || consume('E')) {
            if (consume('+')) {
                // The sign is already consumed.
            } else if (consume('-')) {
                exponent_negative = true;
            }

            std::size_t exponent_digits = 0;
            while (!eof() && std::isdigit(static_cast<unsigned char>(input_[position_]))) {
                if (exponent < 1000000) {
                    exponent = exponent * 10 + (input_[position_] - '0');
                }
                ++position_;
                ++exponent_digits;
            }
            if (exponent_digits == 0) {
                position_ = exponent_begin;
                exponent = 0;
                exponent_negative = false;
            }
        }

        if (exponent != 0) {
            long double scale = std::pow(10.0L, exponent);
            value = exponent_negative ? value / scale : value * scale;
        }
        return negative ? -value : value;
    }

    long double real() {
        std::size_t error_position = position_;
        std::optional<long double> result = try_real();
        if (!result.has_value()) {
            position_ = error_position;
            fail("expected real number");
        }
        return *result;
    }

    std::optional<std::string_view> try_balanced(
        char opening = '(',
        char closing = ')'
    ) {
        if (opening == closing) {
            throw std::invalid_argument("balanced delimiters must be different");
        }

        mark_type begin_attempt = mark();
        skip_whitespace();
        if (!consume(opening)) {
            position_ = begin_attempt;
            return std::nullopt;
        }

        std::size_t content_begin = position_;
        int depth = 1;
        while (!eof()) {
            char current = input_[position_++];
            if (current == opening) {
                ++depth;
            } else if (current == closing) {
                --depth;
                if (depth == 0) {
                    return input_.substr(content_begin, position_ - content_begin - 1);
                }
            }
        }

        position_ = begin_attempt;
        return std::nullopt;
    }

    std::string_view balanced(char opening = '(', char closing = ')') {
        std::size_t error_position = position_;
        std::optional<std::string_view> result = try_balanced(opening, closing);
        if (!result.has_value()) {
            position_ = error_position;
            fail("expected balanced delimiters");
        }
        return *result;
    }
};

}  // namespace utilities
}  // namespace m1une

Back to top page