手动实现LL(1)解析器出现StackOverflow，求语法问题诱因

Hey there! Let’s tackle that StackOverflowError in your Java LL(1) parser—you’re spot-on suspecting left recursion is the culprit here. Recursive descent parsers (which LL(1) implementations typically use) absolutely hate left-recursive grammars because they trigger infinite recursive calls, blowing the stack before they can make any progress. Let’s break down how to fix this step by step.

Why Left Recursion Causes Stack Overflow #

First, let’s clarify the two types of left recursion that might be biting you:

• Direct left recursion: A rule where the non-terminal starts with itself, e.g., statement → statement SEMICOLON assign_var | assign_var. Your parseStatement() method would immediately call itself again without consuming any tokens, leading to an infinite loop.
• Indirect left recursion: A chain of rules that circles back to the starting non-terminal, e.g., start → assign_var statement and statement → start. Here, parseStart() calls parseStatement(), which calls parseStart() again—another infinite loop.

Step 1: Eliminate Direct Left Recursion #

The standard fix for direct left recursion is to rewrite the rule into a right-recursive form with a helper non-terminal (often marked with a prime '):

Before (Left-Recursive) #

statement → statement SEMICOLON assign_var | assign_var | ε

After (Right-Recursive) #

statement → assign_var statement'
statement' → SEMICOLON assign_var statement' | ε

This way, parseStatement() first consumes tokens (via parseAssignVar()) before possibly calling the helper parseStatementPrime(), avoiding infinite recursion.

Corresponding Java Code Adjustment #

Instead of this broken code:

void parseStatement() {
    parseStatement(); // Infinite recursive call—stack overflow!
    match(SEMICOLON);
    parseAssignVar();
}

Use this corrected version:

void parseStatement() {
    parseAssignVar();
    parseStatementPrime();
}

void parseStatementPrime() {
    Token lookahead = getCurrentToken();
    if (lookahead.getType() == TokenType.SEMICOLON) {
        match(TokenType.SEMICOLON); // Consume the semicolon token
        parseAssignVar();
        parseStatementPrime(); // Recurse only if another statement follows
    }
    // If not a semicolon, we hit the empty production—just return
}

Step 2: Fix Indirect Left Recursion #

If your grammar has a circular chain (like start → assign_var statement and statement → start), follow these steps:

1. Order your non-terminals (e.g., start, statement, assign_var).
2. Replace any non-terminal in a rule with its definition from earlier in the order.
3. Check if the new rule has direct left recursion, then eliminate it using the method above.

For example, substituting start into the statement rule:

statement → assign_var statement

This becomes a direct left recursive rule, which we can rewrite to:

statement → assign_var statement'
statement' → statement' | ε

Bonus: Left Factoring (For LL(1) Compatibility) #

While your stack overflow is caused by left recursion, you’ll also need to eliminate left factors to make your grammar LL(1)-valid. Left factors happen when two rules for the same non-terminal share a common prefix, e.g.:

assign_var → DATATYPE VARIABLE ASSIGNMENT NUMBER | DATATYPE VARIABLE ASSIGNMENT STRING

Rewrite this to:

assign_var → DATATYPE VARIABLE ASSIGNMENT assign_var'
assign_var' → NUMBER | STRING

This ensures your parser can pick the correct rule based on the next token, avoiding conflicts in the LL(1) prediction table.

Quick Validation Checks #

After modifying your grammar:

• Verify no rule starts with its own non-terminal (no direct left recursion).
• Trace through all rule chains to ensure no circular dependencies (no indirect left recursion).
• Test your parse() method with a small input—if the stack overflow is gone, you’re on the right track!

内容的提问来源于stack exchange，提问作者Paul Steven Fantonalgo Nadera