Branch rule for parsing chr once but not twice

[lmichaelis]

Hi there,
I'm looking for a better way of expressing "match | but not ||" which also backtracks to before the first || so that an upstream parser match || on its own. What I've got right now works, but there has to be a better way of doing it. Do you guys have any idea as to how to simplify this?

struct bitwise_or {
	static constexpr auto whitespace = ws;
	static constexpr auto rule = []{
		// <-- Here. Match not || and then match |, otherwise return nullopt
		auto rhs = dsl::peek_not(LEXY_LIT("||")) >> (dsl::peek(LEXY_LIT("|")) >> LEXY_LIT("|") + dsl::recurse<bitwise_or> | dsl::else_ >> dsl::nullopt);
		return dsl::p<bitwise_and> + dsl::opt(rhs);
	}();

	static constexpr auto value = binary_expression_eval<ast::expressions::bitwise_or>;
};

Solution

constexpr auto operator_ = dsl::identifier(dsl::ascii::punct);
constexpr auto kw_bitwise_or = LEXY_KEYWORD("|", operator_);

struct bitwise_or {
	static constexpr auto whitespace = ws;
	static constexpr auto rule = dsl::p<bitwise_and> + dsl::opt(kw_bitwise_or >> dsl::recurse<bitwise_or>);
	static constexpr auto value = binary_expression_eval<ast::expressions::bitwise_or>;
};

[benjaminwinger]

LEXY_LIT is already a branch condition, so since the input you want to accept and the input you want to reject both begin with a single |, you could just start with that, then peek_not a second | to reject ||.

LEXY_LIT("|") >> dsl::peek_not(LEXY_LIT("|"))

Then it can just be wrapped in dsl::opt to make it optional.

Once a branch condition matches, the branch is taken without backtracking, so you would want to avoid starting with something like peek_not(LEXY_LIT("||")) in a case like this, since the branch will be taken for all input except ||, meaning it won't backtrack if the input doesn't begin with |.

E.g. https://lexy.foonathan.net/playground/?id=hnxeM9P41&mode=tree

[lmichaelis]

Yeah the parser needs to match them in that order so it properly preserves operator precedence. I mean it is possible with the rule I posted but if there is no other, simpler way of doing it, I'll have to make a decision on which is worse 😆

[foonathan]

FYI, I'm right now working on a test file that contains code like this:

struct sum_product : lexy::expression_production<sum_product>
{
    static constexpr auto atom = integer;

    struct product : dsl::binary_op_left
    {
        static constexpr auto op = dsl::op(dsl::lit_c<'*'>) | dsl::op(dsl::lit_c<'/'>);
        using operand            = dsl::atom;
    };
    struct sum : dsl::binary_op_left
    {
        static constexpr auto op = dsl::op(dsl::lit_c<'+'>) | dsl::op(dsl::lit_c<'-'>);
        using operand            = product;
    };
    using operation = sum;
};

So something nicer is coming in a couple of weeks. ;)

[benjaminwinger]

I'm not sure the rule you posted will work (with auto whitespace at least) due to the recursion, as it will parse multiple consecutive bitwise_or rules as long as they have some sort of separation so that they don't end up as ||.

E.g. https://lexy.foonathan.net/playground/?id=GKdGEd8aP&mode=tree

At the very least I don't think either the dsl::recurse or the peeking on the | are necessary, and then you're left with just dsl::peek_not(LEXY_LIT("||")) >> (LEXY_LIT("|") | dsl::else_ >> dsl::nullopt); (e.g.) which lets the rule apply before logical_or while still being able to be optional (it's consuming nothing rather than actually being a branch rule which can backtrack, but maybe that works for what you're doing).

[lmichaelis]

Hm, to be fair, there probably is a better way of doing this but I'm modelling this grammar which, as you can see, does recurse at every step, so that arbitrary expressions are actually possible

Expression ::= LogicAnd [ "||" Expression ]
LogicAnd   ::= BitOr [ "&&" LogicAnd ]
BitOr      ::= BitAnd [ "|" BitOr ]
BitAnd     ::= Equal [ "&" BitAnd ]
Equal      ::= Comparison [ ( "==" | "!=" ) Equal ]
Comparison ::= BitShift [ ( "<" | ">" | "<=" | ">=" ) Comparison ]
BitShift   ::= Add [ ( "<<" | ">>" ) BitShift ]
Add        ::= Mult [ ( "+" | "-" ) Add ]
Mult       ::= Unary [ ( "*" | "/" | "%" ) Mult ]
Unary      ::= [ "-" | "!" | "~" | "+" ] Value

The rules I posted do actually work, however auto-whitespace indeed seems not to be working. I can get around that by adding whitespace manually to the Value rule as seen above though.

[benjaminwinger]

Oh, whoops, I took the recursion out of context in my simplified example. I guess it's just the | peek which is unnecessary.

[foonathan]

Instead of using dsl::peek_not(), there is also an alternative approach: using identifiers and keywords. They are designed to prevent partial matches. In your example, you want to match an operator consisting of e.g. ASCII punctuation, so that's your "identifier", and the operators in question are keywords: https://lexy.foonathan.net/playground/?id=a7berP9Ks&mode=tree Essentially, the keyword rule does something like this: https://lexy.foonathan.net/playground/?id=r4Ye6bxrM&mode=tree

Also note that if you can use the newly added dsl::literal_set() (or previously operator/) to achieve similar maximal munch: https://lexy.foonathan.net/playground/?id=7WG9vnb3e&mode=tree It matches the longest of the alternatives.

But as I've already said in a comment, built-in support for operator precedence parsing is coming.

[lmichaelis]

Hm I'm quite new to building these kinds of parsers so correct me if I'm wrong, but: wouldn't this make it harder to preserve operator precedence? If I parse both operators at the same time, I'd have to implement some manual logic to make sure my AST is built correctly, right? With my current approach, it's basically all handled by the parser itself.

[foonathan]

wouldn't this make it harder to preserve operator precedence? If I parse both operators at the same time, I'd have to implement some manual logic to make sure my AST is built correctly, right?

Yes. This is in fact what I'm currently implementing into the library.

However, my first approach using identifiers for operators works normally. Just write LEXY_KEYWORD("|", operator_) instead of LEXY_LIT("|") and you've got maximal munch for free.

[lmichaelis]

Cool! Yes this works flawlessly. Thanks guys!

[foonathan]

I've just published two additions that can help you here:

1. dsl::not_followed_by(): it parses a literal, but only if it is not followed by another char class. This means you can use dsl::not_followed_by(dsl::lit_c<'|'>, dsl::lit_c<'|'>) to parse a single |. https://lexy.foonathan.net/reference/dsl/follow/#not_followed_by
2. Built-in support for operator precedence parsing: https://lexy.foonathan.net/reference/dsl/expression/#doc