将BNF语法转JavaCC遇正则循环错误，求转换为右递归的方法

算力阿峰

2026-5-28

Ah, I see the issue here! You've made a common mistake with JavaCC: you're trying to define syntactic non-terminals (NExpr, NTerm, NFactor) as TOKENs, but TOKENs are meant for lexical symbols (like operators, numbers, keywords) — not grammar rules. JavaCC's lexer can't handle recursive references in token definitions, which is why you're getting that "loop in regular expression" error.

Let's break this down and fix it step by step.

Step 1: Define Lexical Tokens

First, we need to define all the basic lexemes (the smallest meaningful units) as TOKENs. Based on your BNF, these would be:

TOKEN: {
  <ADD: "+">
| <SUB: "-">
| <MUL: "*">
| <DIV: "/">
| <LPAR: "(">
| <RPAR: ")">
| <DIGIT: (["0"-"9"])+> // Matches one or more digits (numbers)
| <REPCOUNT: "REPCOUNT"> // Adjust if this is a keyword or has a different pattern
| <PARAMETER: ["a"-"z","A"-"Z"] (["a"-"z","A"-"Z","0"-"9","_"])*> // Matches identifiers
}

Step 2: Define Syntactic Grammar Rules

Your original BNF is already in a right-recursive-friendly EBNF format (using {...} for repetitions), which fits perfectly with JavaCC's syntax for grammar rules. We'll implement these as void methods in JavaCC:

NExpr Rule

This matches an expression with addition/subtraction:

void NExpr() : {} {
  NTerm()
  (
    (<ADD> | <SUB>)
    NTerm()
  )* // Equivalent to your BNF's { ( "+" | "-" ) NTerm }
}

NTerm Rule

This matches terms with multiplication/division:

void NTerm() : {} {
  NFactor()
  (
    (<MUL> | <DIV>)
    NFactor()
  )* // Equivalent to your BNF's { ( "*" | "/" ) NFactor }
}

NFactor Rule

This matches factors (numbers, variables, parenthesized expressions, or negated versions):

void NFactor() : {} {
  [ <SUB> ] // Optional minus sign (matches the "-" in your BNF)
  (
    <DIGIT>
  | <REPCOUNT>
  | <PARAMETER>
  | <LPAR> NExpr() <RPAR> // Parenthesized expression, which references NExpr recursively
  )
}

Why This Works

We've moved the recursive grammar logic to JavaCC's parser (the void methods), not the lexer (TOKENs). The parser handles recursive grammar rules naturally, as long as they're right-recursive (or use EBNF repetition operators like *, which JavaCC translates to right-recursive under the hood).
Your original BNF already uses EBNF repetitions ({...}), which map directly to JavaCC's * operator — so you don't need to manually rewrite it into the X -> bX' form (though that's what the * is doing implicitly).

What Was Wrong With Your Original Code

You tried to encode the entire grammar (including recursive non-terminals) into TOKEN definitions. JavaCC's lexer uses regular expressions, which cannot handle recursive structures (since regular languages don't support recursion). The error message was pointing out the indirect recursion loop: NEXPR → NTERM → NFACTOR → NEXPR, which the lexer can't resolve.

By splitting lexer and parser responsibilities correctly, we eliminate that loop and create a valid JavaCC grammar.

内容的提问来源于stack exchange，提问作者Davide

将BNF语法转JavaCC遇正则循环错误，求转换为右递归的方法

Step 1: Define Lexical Tokens #

Step 2: Define Syntactic Grammar Rules #