Can backtracking be avoided?

[0x8000-0000]

I am working on a grammar where there is ambiguity between identifiers and keywords, and some keywords consist of several identifiers separated by spaces (to make the DSL more user friendly and readable in English). So, for instance I have a keyword that is "required option", which could be parsed as either two identifiers, or two keywords which are later combined with an if_must<Key1, Space+, Key2, ...> - and I have some trouble with spurious actions triggering and need to backtrack to pop the state and remove the falsely matched identifiers.

I have read https://github.com/taocpp/PEGTL/blob/main/doc/Actions-and-States.md#backtracking and the proposed solutions are not quite satisfying, but the section "Looking Ahead" made me think: why can't we parse the input twice ? Once just to figure out what everything is, and the second time to just trigger the actions, with perfect foreknowledge? Yes, that will require the parser to allocate some memory to keep this state, but it should be fairly compact, probably an int or so for each terminal and nonterminal.

In a way, this would create an AST - and I read the documentation on the PEGTL's AST implementation but I'm not satisfied with the way it forces string comparison for node types. It would be much preferred to have a visit similar to variant - which is what the Action interface is all about. So maybe this is a riff on #248 ?

---

Alternatively, if one wants to allow 'require' and 'option' as identifiers in some contexts, and keywords in others, is there an idiomatic way to express that?

I want to avoid defining identifiers as: [a-z][a-z_0-9]* except 'require', 'option', ... (like the lua53.cpp example does)

[skyrich62]

You should look at the "at<>" rule. This rule does exactly what you want. It attempts to parse, (but not consume), input. If the match is successful, no actions are called. You can leverage this with the if_then, or if_must rules like this:

    struct require : keyword<'r', 'e', 'q', 'u', 'i', 'r', 'e'> { };
    struct  option : keyword<'o', 'p', 't', 'i', 'o', 'n'> { };

    struct require_option : 
        if_must< at< require >,
            seq< require, option >
        > { };

Obviously, you'll have to add appropriate padding for white space, but I wanted a bit of clarity here.

This does parse the input twice, but the second time doesn't have "perfect foreknowledge". It's possible to do what you want with a bit of work. You'd have to write your own "at"-like rule which would have to keep track of state information and cache the knowledge. Then if the parse is successful, consume the input, and trigger all of the required actions in the appropriate order.

I'd say, depending on how complex your grammar is, that it's kind of a toss-up as to whether or not it just makes more sense to parse the input the second time as is, however.

[skyrich62]

An easy way of visiting the nodes in an idiomatic way is to define your own node, inheriting from parse_tree::node, and adding a variant field.

Then simply use std::visit and the visitor pattern.

    using node_kind = std::variant< kind1, kind2, kind3 >;

    struct my_node : public parse_tree::node
    {
        node_kind   kind;
    };

    class visitor
    {
    public:
       virtual void visit(my_node &n, kind1& k1);
       virtual void visit(my_node &n, kind2& k2);
       virtual void visit(my_node &n, kind3& k3);

       void accept(node &n)
       {
            std::visit( [&n] (auto &&arg) {
                visit(n, arg);
            }, n.kind);
        }
   };

This will automatically dispatch to the appropriate handler based on what is in the variant. For this to work, you must have unique types in the variant. (e.g. you cannot have two or more std::string entities in the variant)

[skyrich62]

A way of defining "require" as a keyword in some contexts and as an identifier in others is to use an action rule that returns a bool, See the documentation here: https://github.com/taocpp/PEGTL/blob/main/doc/Actions-and-States.md#boolean-return and also here: https://github.com/taocpp/PEGTL/blob/main/doc/Actions-and-States.md#apply

This way it is possible to match it as a keyword or as an identifier based on parser states which are automatically passed to the action.

[skyrich62]

A way to reasonably distinguish between identifiers and keywords

Using this technique, you can use a grammar rule to specify a keyword where it must be that keyword, and still allow it to be used as an identifier in other contexts.

Consider a grammar where "require" is sometimes a keyword, but can be used as an identifier in other places, for example:

require_clause <- REQUIRE identifier
decl_clause <- DECLARE identifier

Where "identifier" has the usual meaning, and REQUIRE and DECLARE, (capitalized here to show them as terminal symbols in the PEG), have been declared as keywords as show below:

This could allow:

require xyzzy      // "require" used as keyword
declare require   // "require" used as identifier

Yes, it's a fabricated example, but I think it makes my point.

The details

template< Rule >
struct my_action :  tao::pegtl::nothing<Rule> { };

template<>
struct my_action<identifier>
{
    template <typename ActionInput, typename... States>
    static bool apply(const ActionInput& in, States&&... states)
    {
        static const std::set<std::string> keywords{"require", "option"};
        auto found = keywords.find(in.string());
        if (found == keywords.end()) {
            // not a keyword, must be an identifier.
            return true;
        }
        return false;    // must be a keyword.
    }
}; 

In this case the parse states aren't used, but you can use them to determine context, (passed in/changed by other actions), in order to alter the logic, (i.e. "require" is a keyword in context A, but an identifier in context B.

The down-side is that you must keep the set of keywords in two places, but this can be ameliorated by use of #include and #define like this:

/// keywords.def
xx(require)
xx(option)
xx(declare)
xx(next_keyword)
xx(and_so_on)
  ...
// end of file

/// grammar.h

// define grammar rules for the individual keywords.
#define xx(a) struct a : public TAO_PEGTL_KEYWORD( #a ) { };
#include "keywords.def"
#undef xx

// Define the set of keywords for later comparison in context.
static const set<std::string> keywords{
#define xx(a) #a,
#include "keywords.def"
#undef xx
};

[0x8000-0000]

Wow, thank you @skyrich62 - that is a lot of input, it will take me a bit to digest and see what works for me.

Thanks again!

[d-frey]

I currently don't have much time, so I just want to mention two things:

1. A "keyword" may contain spaces, so keyword<'f', 'o', 'o', ' ', 'b', 'a', 'r'> is perfectly fine.
2. Usually, the grammar should be build in a way to check for the keywords that are valid in a specific location first, if no keyword is matched, just match some alternative that might match an identifier.

[0x8000-0000]

Can a "keyword" contain arbitrarily many spaces between words? Yes, they should not be there, but it's hard to argue with an user that "foo bar" and "foo bar" are different (for good reason, too).

(2) is a very valuable hint; as I developed my grammar, the "identifier"-starting rules were written first, followed by the rules that start with keywords. Just before reading your reply things clicked between the power of sor<>, and at<> and figured I should try changing the order of the rules.

Thank you @d-frey !