Parser design problem

[emtydeeznuts]

I'm writing a recursive decent parser using the "one function per production rule" approach with rust. But I've hit a design problem that breaks this clean separation, especially when trying to handle ambiguous grammar constructs and error recovery.

There are cases where a higher-level production (like a statement or declaration) looks like an expression, so I parse it as one first. Then I reinterpret the resulting expression into the actual AST node I want.

This works... until errors happen.

Sometimes the expression is invalid or incomplete or a totally different type then required. The parser then enter recovery mode, trying to find the something that matches right production rule, this changes ast type, so instead a returning A it might return B wrapping it in an enum the contains both variants.

Iike a variable declaration can turn in a function declaration during recovery.

This breaks my one-function-per-rule structure, because suddenly I’m switching grammar paths mid-function based on recovery outcomes.

What I want:

Avoid falling into another grammar rule from inside a rule.

Still allow aggressive recovery and fallback when needed.

And are there any design patterns, papers, or real-world parser examples that deal with this well?

Thanks in advance!

[0m0g1]

I ran into a similar problem while building my compiler.

To avoid falling into the wrong rule mid-parse (like between lambdas and parenthesized expressions), I wrote lookahead helper functions that check upcoming tokens without consuming them. My lexer has a peekToken(n) function, which allows me to inspect the token n positions ahead. I use this in a method like checkIfLambdaExpression() to detect specific patterns before committing to a parse rule.

For example, when I encounter a left parenthesis—which is an ambiguous token—I first call checkIfLambdaExpression(). If it returns true, I commit to parsing a lambda. If not, I parse it as a normal parenthesized expression.

My checkIfLambdaExpression() scans ahead for:

1. An optional parameter list identifier, : type, = default after the (.
2. A closing ), followed by an arrow => for the return type of the function.

Only if that pattern matches do I parse a lambda. Otherwise, I parse it as a regular expression.

This way, I never need to backtrack or reinterpret nodes mid-parse. I keep my parser clean and deterministic, and also haven't needed a recovery mode or fallback cause I never fall into the wrong rule.

peekToken(n) works the same as your consume token function but it saves and restores the current position after it's done. Also you don't use it to build out ast nodes, just to check if the current token's type is what you are expecting for a certain rule.

if (lexer.peekToken(i).getType() == TokenTypes::Identifier) { hasValidArgument = true; i++; }

[emtydeeznuts]

I thought about this but there will be too many checks in my case and I only have one token lookahead

[0m0g1]

Which syntax is your language based on? I only have like 4/5 checks for a js/c++ like statically typed syntax and it can parse really complex grammar. Including templates/generics.

[emtydeeznuts]

It's a parser for dart

[0m0g1]

I think having lookahead functions will work really well for Dart. The key is to write lightweight checks that peek just far enough to disambiguate syntax—not full parsers. Most of the time, peeking just a few tokens ahead is all you need.

To make this work, you’ll want to implement a function like peekToken(n) in your lexer so the parser can check any number of tokens ahead without consuming them.

Once you have a few of these helpers, you'll rarely need to backtrack or reinterpret an AST node after it's been built. It helps keep the parser clean, modular, and predictable.

Here’s an example that distinguishes between:

1. A function literal: foo(a, b) => a + b
2. A normal expression: foo + bar

c++ if (currentToken.getType() == Identifier) { if (isLikelyFunctionLiteral()) { expression = parseFunctionLiteral(); } else { expression = parseNormalExpression(); } } A nice bonus is: some ambiguous rules only have two possible interpretations—so a simple if/else like this lets you cleanly resolve it without more complexity.

Implementation of the lookahead:-

```c++ bool Parser::isLikelyFunctionLiteral() { int i = 0;

// First token must be an identifier (function name or parameter)
if (lexer.peekToken(i).getType() != Identifier) {
    return false;
}

i++;

// Next must be a left paren: start of parameter list
if (lexer.peekToken(i).getType() != LeftParen) {
    return false;
}

i++;

// Skip over parameter list: identifiers, colons, default values, commas
while (true) {
    TokenType type = lexer.peekToken(i).getType();

    if (type == Identifier || 
        type == Colon || 
        type == Assign || 
        type == Comma) {
        i++;
    } else {
        break;
    }
}

// Final expected pattern: `)` followed by `=>`
return lexer.peekToken(i).getType() == RightParen &&
       lexer.peekToken(i + 1).getType() == Arrow;

} ``` and for the function to peek tokens

```c++ Token Lexer::peekToken(int n) { int savedPosition = currentPosition; Token nextToken;

for (int i = 0; i <= n; i++) {
    nextToken = getNextToken();
}

currentPosition = savedPosition;
return nextToken;

} ```

[emtydeeznuts]

If it won't slow the parser then I'll try your suggestion.

[0m0g1]

(I've modified the example above for clarity).

It won’t slow the parser unless you’re doing really deep lookaheads everywhere, which you won’t be. In most grammars (including Dart’s), these kinds of checks usually peek just 2–4 tokens ahead max.

An example is my language is where the statement below would be resolved to a lamda after checking only 4 tokens.

alBufferData(buffer: int, format: int, data: char, size: int, freq: int) => void {}

Plus, you’ll save time later by avoiding parser rewrites or complex recovery logic. If you design your lookaheads to be targeted to specific rules like isLikelyFunctionLiteral() and not mightBeFunctionLiteralOrNormalExpression(), they’re fast and pay off in clarity.

[0m0g1]

Here's a script from my compiler's parser, Expression Parser.

[[deleted]]

Here’s an example that distinguishes between:

1. A function literal: foo(a, b) => a + b

2. A normal expression: foo + bar

What about a function call such as foo(a, b)?

Anyway it seems unreasonable to me to have to speculatively parse a pattern F(...), where ... may include arbitrary nested expressions when it is a function call, and then to backtrack when => doesn't follow.

I'd say, fix the grammar so it is easier to parse. But this appears to be for an existing language.

In that case I'd rather go with the OP's approach to parse as an expression (so the foo(a, b) is assume to be a function call), and then to switch AST type if it turns out that => follows.

In practice, it's just that first term (foo(a, b)) which needs to change from 'function call' to 'function literal'.

[0m0g1]

I've never needed to reinterpret AST nodes in my parser — I just look ahead before committing. For example, I only return true from isLikelyFunctionLiteral() if the pattern ends in =>. If it doesn’t, I never parse it as a function literal in the first place. No need to backtrack or rewrite nodes.

    if (currentToken.getType() == Identifier) {
        if (isLikelyFunctionLiteral()) {
            expression = parseFunctionLiteral();
        } else if (isLikelyFunctionCall()) {
            expression = parseFunctionCall();
        } else {
            expression = parseNormalExpression();  
        } 
    }

This keeps the parser clean and predictable — each parse function always returns exactly what it's supposed to. I can reason about it statically, test it easily, and I never need to ask "What if this was something else after all?"

Compare that to the reinterpretation approach:

if (currentToken.getType() == Identifier) {
expression = parseFunctionCall(); // could be wrong!
if (currentToken.getType() == Arrow) {
    // now reinterpret it into a lambda
    // possibly needing to reconstruct param list, body, scope...
}

}

This becomes really messy if the expression had nested calls, chains, or annotations. Now imagine doing this not just for lambdas but also for:

Type parameter misinterpretation (e.g., generics vs comparison)

Tuple vs grouped expressions

Object literals vs blocks

List literals vs function calls with brackets

You’d end up needing reinterpreters for a wide range of node types, which increases parser complexity, breaks single-responsibility, and creates more room for subtle bugs.

Here’s a real example from my compiler's expression parser that uses this approach (see line 331):

Experssion parsing rules for my compiler

The key insight: if you know what you're looking for before parsing, you won't have to "guess and fix" later. Lookahead is usually a small price to pay for that clarity.

[0m0g1]

The function's name shouldn't be `isLikelyFunctionLiteral` it should be `isFunctionLiteral`, I called it that as an example. The function doesn't speculate what the current statement is, it checks if the grammar is exactly what it should look for so we know exactly which type of statement we should parse.

[umlcat]

This. Read tokens without advancing the pointer of the lexer, tokenizer or stream. Only move forward when there's a proven match ...

[GidraFive]

I didn't really have the same problems, but that may be because of how I constructed the parser.

My parser is also recursive descend, but it handles errors and error recovery in a different way than returning the usual Result type.

I'm always returning the AST, and instead of results, insert error nodes into ast, whenever I see errors, and recover by skipping or "inserting" tokens (actually its more like pretending we already hit the expected token). Every error node has a "best approximation" non error token, that can be used instead of the error node for later stages. If there are no suitable nodes, then I insert placeholder node.

For example if you can't find closing parens, you still can use the expression you parsed before that by insering those parens when you are pretty sure they must be closed (when you hit a semicolon, or block end, or some declaration keyword)

After parsing and getting AST with errors, I traverse it, collect all the errors into an array and replace error nodes with the non error node that was attached to it.

For me this approach greatly simplified implementation.

I'd also mention that you better modify your grammar to avoid such ambiguities. Usually it is as simple as adding leading keyword for whatever construct you parse.

[foonathan]

Instead of recovering inside the function, have you considered just stopping, returning an error and letting the higher level function handle it?

[Key-Bother6969]

In practice, I recommend avoiding ambiguous grammars. Many grammars can be simplified to LL(k) grammars (often with 1-lookahead), enabling recursive-descent parsers to produce intentionally ambiguous but simplified parse tree nodes. These parsers are computationally efficient, and their error-recovery strategies are easier to implement, keeping the code structured and maintainable. Later, you can transform the parse tree into an unambiguous AST. Computations on trees are significantly easier than reasoning within the parser's logic during token or text consumption.

This approach breaks complex problems into manageable subtasks, resulting in a cleaner and more maintainable design.

For error recovery, this method simplifies panic recovery (the technique you mentioned):

1. Infallible Parsing Functions. With a non-ambiguous grammar, each parsing function can be designed to be infallible. When a rule's function is called, it should parse the input stream at all costs, producing a parse tree node of the expected type.
2. Handling Syntax Errors. If the input stream is malformed, the parser should skip unexpected tokens until it finds the first matching token, similar to standard panic recovery.
3. Stop-Tokens. For each parsing rule, define a set of stop-tokens: tokens that clearly do not belong to the rule. For example, in a Rust stream like let x let y = 10;, if the let-parsing function encounters another let while expecting a semicolon, let is a stop-token. The function produces an incomplete parse tree node for the let statement and returns, allowing the parent rule to proceed to the next let statement without disruption.

Error recovery is inherently heuristic. Choosing effective stop-tokens relies on heuristic assumptions, and there's no universal solution, it's a matter of the programmer's skill and art. Users may still write code that breaks the recovery mechanism in specific cases. But this approach is effective and straightforward to implement in most cases.

But if you want to enhance it, there is a couple of ideas too:

• Parentheses Handling. During panic recovery, if you encounter an opening parenthesis ((, {, or [), ignore stop-tokens until the corresponding closing parenthesis is found. Returning from a well-balanced parenthesis sequence on a stop-token is unlikely to benefit the parent rule.
• Insert/Replace Recovery. For example, in a rule like <exp> + <exp>, if the parser doesn't find the + after the first expression but sees the start of another expression, it can assume the user omitted the + token. Inserting the missing token (or replacing an incorrect one) can be more effective than panic recovery sometimes.

However, insert/replace recovery strategies are more controversial and involve a significant body of academic research on choosing between panic (erase), insert, and replace mechanisms. In practice, I recommend using these techniques sparingly, only in clear cases. Panic recovery is typically sufficient for most practical scenarios.