I'm trying to write a (scannerless) recursive descent parser with a catch all rule for the following Mustache template grammar (simplified here):       content : (variable_tag | section_tag | static)*  variable_tag : mustache_open id mustache_close   section_tag : mustache_open '#' id mustache_close                 content mustache_open '/' id mustache_close mustache_open : '{{'mustache_close : '}}'            id : [azAZ$_][azAZ09$_]*        static : .+  // catch allThe static production would have to stop before the next matched production. And I can't come to a solution for this that would not break the grammar structure.A valid input is:You have just won {{value}} dollars!{{#in_ca}}Well, {{taxed_value}} dollars, after taxes.{{/in_ca}}The output for that would be an abstract syntactic tree like:                           +-------+                           |Content|                           +-------+                               |        +---------------+------+--------+--------------+        |               |               |              | +--------------+  +-----------+  +-------------+  +----------+|Static        |  |VariableTag|  |Static       |  |SectionTag||\nYou...won |  |value      |  | dollars\n|  |in_ca     |+--------------+  +-----------+  +-------------+  +----------+                                                       |                                                    +-------+                                                   |Content|                                                   +-------+                                                       |                                    +-------------+----+--------------+                                    |             |                   |                              +----------+  +-----------+  +---------------------+                              |Static    |  |VariableTag|  |Static               |                              |\nWell, |  |taxed_value|  | dollars...taxes.\n|                              +----------+  +-----------+  +---------------------+Any reference to a implementation of a catch all rule for a recursive descent parser?
Hand written recursive descent parser with catch all rule
algorithms;parsing;grammar
Your grammar will be correct if your catch-all rule only consumes a single character and if you use prioritized choice in the grammar so that static is only attempted as a last resort. Of course, these single-character tokens are terribly inefficient. There are two ways to fix this:let the catch-all rule be static : [^\{]+ | .have your parser store a pointer to the previous token. If you are reading a static token and the previous token was static, then append the string rather than creating a new item in your AST. This can actually be a bit tricky to pull off, since in a RecDesc parser each rule would usually fail or return an AST subtree. It might make sense to introduce a pseudo-token signifying success, but no action needes since the token would already reside in the AST in case of a fixup and should not be added two times.There is a problem with this: since at no point do you commit to one alternative, this parser involves a lot of backtracking. I would expect this to cause exponential complexity, unless you use a Packrat strategy (or use a parsing technique that is actually suited for ambiguous grammars). Here's an example input for such behaviour:{{#foo}} {{#a}} {{#a}} {{#a}} {{/foo} sic!According to your grammar, this input would be completely static, but the parser would recurse four times into the section rule.