How to change the parsing rules based on the parsed content?

[Life4gal]

Imagine a scenario where I have a file with a lot of key-value pairs (in the form of key = value)
I now need to extract these key-value pairs and save them to std::map<std::string, std::string>.

A simple example (omitting some details).

struct variable_key : lexy::transparent_production
{
	[[nodiscard]] CONSTEVAL static auto name() noexcept -> const char* { return "[key]"; }

	struct invalid_key
	{
		constexpr static auto name = "a valid key was required here";
	};

	constexpr static auto rule = []
	{
		// begin with not '\r', '\n', '\r\n', whitespace or '='
		constexpr auto begin_with_not_blank = dsl::unicode::print - dsl::unicode::newline - dsl::unicode::blank - dsl::equal_sign;
		// continue with printable, but excluding '\r', '\n', '\r\n', whitespace and '='
		constexpr auto continue_with_printable = dsl::unicode::print - dsl::unicode::newline - dsl::unicode::blank - dsl::equal_sign;

		return dsl::peek(begin_with_not_blank) >>
				(LEXY_DEBUG("parse variable key begin") +
				dsl::identifier(begin_with_not_blank, continue_with_printable) +
				LEXY_DEBUG("parse variable key end")) |
				dsl::error<invalid_key>;
	}();

	constexpr static auto value = lexy::forward<lexeme_type>;
};

struct variable_value : lexy::transparent_production
{
	[[nodiscard]] CONSTEVAL static auto name() noexcept -> const char* { return "[value]"; }

	constexpr static auto rule = []
	{
		// begin with not '\r', '\n', '\r\n', whitespace or '='
		constexpr auto begin_with_not_blank = dsl::unicode::print - dsl::unicode::newline - dsl::unicode::blank - dsl::equal_sign;

		// continue with printable, but excluding '\r', '\n', '\r\n', whitespace and '='
		constexpr auto continue_with_printable = dsl::unicode::print - dsl::unicode::newline - dsl::unicode::blank - dsl::equal_sign;

		return dsl::peek(begin_with_not_blank) >>
				(LEXY_DEBUG("parse variable value begin") +
				dsl::identifier(begin_with_not_blank, continue_with_printable) +
				LEXY_DEBUG("parse variable value end"));
	}();

	constexpr static auto value = lexy::forward<lexeme_type>;
};

Note that the above example ignores the details of the state we pass when calling lexy::parse

It looks fine, it can successfully parse the following example:

key1 = value1
key2 = value2

However, if the following content appears, the parsing will fail:

a key with whitespace = value
key = a value with whitespace

What's the reason for not allowing whitespace in key/value? We can change the code to look like the following:

struct variable_key : lexy::transparent_production
{
	[[nodiscard]] CONSTEVAL static auto name() noexcept -> const char* { return "[key]"; }

	struct invalid_key
	{
		constexpr static auto name = "a valid key was required here";
	};

	constexpr static auto rule = []
	{
		// begin with not '\r', '\n', '\r\n', whitespace or '='
		constexpr auto begin_with_not_blank = dsl::unicode::print - dsl::unicode::newline - dsl::unicode::blank - dsl::equal_sign;
		// continue with printable, but excluding '\r', '\n', '\r\n' and '='
		constexpr auto continue_with_printable = dsl::unicode::print - dsl::unicode::newline -  dsl::equal_sign;

		return dsl::peek(begin_with_not_blank) >>
				(LEXY_DEBUG("parse variable key begin") +
				dsl::identifier(begin_with_not_blank, continue_with_printable) +
				LEXY_DEBUG("parse variable key end")) |
				dsl::error<invalid_key>;
	}();

	constexpr static auto value = lexy::forward<lexeme_type>;
};

struct variable_value : lexy::transparent_production
{
	[[nodiscard]] CONSTEVAL static auto name() noexcept -> const char* { return "[value]"; }

	constexpr static auto rule = []
	{
		// begin with not '\r', '\n', '\r\n', whitespace or '='
		constexpr auto begin_with_not_blank = dsl::unicode::print - dsl::unicode::newline - dsl::unicode::blank - dsl::equal_sign;

		// continue with printable, but excluding '\r', '\n', '\r\n' and '='
		constexpr auto continue_with_printable = dsl::unicode::print - dsl::unicode::newline - dsl::equal_sign;

		return dsl::peek(begin_with_not_blank) >>
				(LEXY_DEBUG("parse variable value begin") +
				dsl::identifier(begin_with_not_blank, continue_with_printable) +
				LEXY_DEBUG("parse variable value end"));
	}();

	constexpr static auto value = lexy::forward<lexeme_type>;
};

Almost the same code as before, except we remove dsl::unicode::blank in rule.

But that doesn't satisfy us either, we do sometimes want to parse without whitespace, so here's an idea.

Suppose the following is a file to be parsed:

@pragma allow_key_whitespace
@pragma allow_value_whitespace

# OK!
key1 = value1
key2 = value2

# OK!
a key with whitespace = value
key = a value with whitespace

We have added a new entity: pragma
It must be declared in the header of the file, and the parser first parses all pragmas and then sets some parsing flags for state, e.g:

class State
{
// ...

private:
    bool allow_key_whitespace_;
    bool allow_value_whitespace_;
};

These two values of state are then used to determine whether whitespace is allowed when parsing key/value.

But rule must be a compile-time value, how to decide the rule at runtime?

[Life4gal]

Things are much more problematic than I thought.

I also have an entity: comment
Everything starting with # (up to the end of the line) is considered a comment.

key = value # comment here~

Before disallowing whitespace, it is easy to determine that the parsing of values ends at the space after value, after which comments can be parsed (if any).

But once whitespace is allowed, we can't be sure whether the content that follows needs to be parsed. And we can't use "no #" as a parsing rule, because # should not be prohibited in the value.

The expected rule should be as follows.

key = value with whitespace and sharp#sharp # comment here

Parsed as:
key: key
value: value with whitespace and sharp#sharp
comment: comment here

key = value with whitespace and #sharp # comment here

Parsed as:
key: key
value: value with whitespace and
comment: sharp # comment here

Question 1: If an identifier (the key must be followed by =, so parsing is relatively simple) is followed by a lot of spaces, how can I determine if what follows is part of the value? If there are spaces until the end of the line, how can I backtrack to the last non-whitespace position?
Question 2: Comments must start with # and must be preceded by a whitespace character, but whitespace is allowed in the value. How should I write a rule to support backtracking to the last non-whitespace position when parsing to something like #(whitespace+sharp)?

I know that requiring values to be enclosed in quotes would solve this problem very well, but in practice, I can't do it. So I have to find another way to solve this problem.

[foonathan]

This is context-sensitive parsing, which can't easily be done with pure lexy rules.

But your idea with the state is in the right-track. You can use dsl::scan to dispatch between rules based on members of the state. Something like:

struct value : lexy::scan_production<lexeme_type>
{
     template <typename Context, typename Reader>
     static constexpr scan_result scan(lexy::rule_scanner<Context, Reader>& scanner, const State& state)
    {
          if (state.allow_whitespace())
               return scanner.parse(value_with_whitespace_production{});
          else
               return scanner.parse(value_without_whitespace_production{});
    }
};

Likewise, you can use a different scan production to set the members of the state. My partial C parser does it a lot: https://github.com/foonathan/clauf/blob/main/src/compiler.cpp#L1453

[Life4gal]

What if this value is optional? For example:

struct pair
{
    constexpr static auto rule = dsl::p<variable_key> + dsl::equal_sign + dsl::opt(dsl::p<variable_value>) + dsl::opt(comment);
};

This would allow cases such as:

key = # comment here

Parsed as:
key: key
value: `` // <- empty
comment: comment here

[Life4gal]

Parsing
    Invokes P::scan(), passing it an object of type lexy::rule_scanner starting at the current reader position, and optionally the parse state, 
    followed by all values already produced by previous rules. Then parses and consumes everything parsed and consumed by P::scan(). 
    Succeeds, if P::scan() returns a [lexy::scan_result](https://lexy.foonathan.net/reference/action/scan/#scan_result) that contains a value. 
    Fails otherwise.

According to the reference, only returns a scan_result that contains a value is considered a success, otherwise it is considered a failure. How to determine whether the parsing failed or did not contain a value?

[foonathan]

Return a std::optional<T> from scan.

[Life4gal]

This is context-sensitive parsing, which can't easily be done with pure lexy rules.

But your idea with the state is in the right-track. You can use dsl::scan to dispatch between rules based on members of the state. Something like:

struct value : lexy::scan_production<lexeme_type>
{
     template <typename Context, typename Reader>
     static constexpr scan_result scan(lexy::rule_scanner<Context, Reader>& scanner, const State& state)
    {
          if (state.allow_whitespace())
               return scanner.parse(value_with_whitespace_production{});
          else
               return scanner.parse(value_without_whitespace_production{});
    }
};

Likewise, you can use a different scan production to set the members of the state. My partial C parser does it a lot: https://github.com/foonathan/clauf/blob/main/src/compiler.cpp#L1453

Another point is, what if the two structures return different values?

For example, if whitespace is not allowed, we can just return a lexeme_type (or std::string_view).
However, if whitespace is allowed (or furthermore, special characters or code_points are allowed), then the returned type should be able to allocate memory to support the conversion process.

[foonathan]

Return a std::variant from scan.

[Life4gal]

This is context-sensitive parsing, which can't easily be done with pure lexy rules.

But your idea with the state is in the right-track. You can use dsl::scan to dispatch between rules based on members of the state. Something like:

struct value : lexy::scan_production<lexeme_type>
{
     template <typename Context, typename Reader>
     static constexpr scan_result scan(lexy::rule_scanner<Context, Reader>& scanner, const State& state)
    {
          if (state.allow_whitespace())
               return scanner.parse(value_with_whitespace_production{});
          else
               return scanner.parse(value_without_whitespace_production{});
    }
};

Likewise, you can use a different scan production to set the members of the state. My partial C parser does it a lot: https://github.com/foonathan/clauf/blob/main/src/compiler.cpp#L1453

I'm not sure I understand correctly, I found this function in the link you gave me.

I didn't understand at first that this is all that is needed for lexy::scan_production? How do you assume that you can parse and produce a production?

Then I found this line of code, can I understand that scan will be called for parsing only if this rule is satisfied? (when using dsl::p<block_stmt>)

[Life4gal]

By the way, I know I can use:

auto result = scanner.parse<std::string>(production{});

What I want to know is, since there is an interface that only passes rule, how does the implementation of this interface construct the value? Or is it necessary to be able to construct the object directly via lext::construct at this point? But I remember dsl::delimited and dsl::identifier have different return values, and dsl::delimited needs a sink, what should I do with it?

[foonathan]

How will scanner generate the value? (Obviously, you can't construct std::string directly from lexeme_type)

Your production has a value callback, which will be invoked to produce a std::string? Again, I'm not sure what you're asking.

Have you tried writing the code? It should just work.

[Life4gal]

I mean, if scanner had an interface like this:

lexy/include/lexy/dsl/scan.hpp

Lines 194 to 205 in 5e2601b

	template <typename T, typename Rule, typename = std::enable_if_t<lexy::is_rule<Rule>>>
	constexpr void parse(scan_result<T>& result, Rule)
	{
	if (_state == _state_failed)
	return;
	using parser = lexy::parser_for<lexyd::_pas<T, Rule>, scan_final_parser>;
	auto success
	= parser::parse(static_cast<Derived&>(*this).context(), _reader, &result._value);
	if (!success)
	_state = _state_failed;
	}

Does this mean that it is possible to generate a value by just passing the rule (and not the value)? In this case, how would the value be generated (if not simply constructed directly).

[foonathan]

If rule is an atomic rule like dsl::identifier, dsl::lit, or dsl::integer, the value is whatever is produced by the rule like an lexeme, nothing, or an integer.

if rule is dsl::p<Production> the value is the result of the Production::value callback.

[Life4gal]

I think I misunderstood what a RULE was, and I think I get it now. :)