Nearley语法解析数学表达式遇重复匹配与循环问题求助

As someone who's worked through similar parsing headaches with Nearley, let's break down what's going wrong and how to fix it directly in your grammar.

The Root Problems #

Your issues stem from two key flaws in the grammar structure:

1. Ambiguous identifier matching: The parser first recognizes sin as a plain Symbol before it gets a chance to match it as a function name (FN). This leads to nested, incorrect nodes where sin appears both as a symbol and a function in the same tree.
2. Misconfigured recursive rules: The circular reference in a*sin(x)^y happens because your expression rules don't properly handle operator precedence or recursion termination. The parser ends up re-matching the same node over and over instead of building a valid right-associative tree for the exponent.

Step-by-Step Grammar Fixes #

1. Prioritize Function Names Over Plain Symbols

Nearley tries rules in the order they're defined, so we need to make sure function calls are matched before plain symbols. Define an explicit list of function names first, then build a function rule that takes precedence in your atom expressions.

For example:

# List all your supported function names first
fn_name -> "sin" | "cos" | "log" | "exp"

# Function call rule: name + parentheses + argument
fn -> fn_name "(" expr ")" {% (data) => ({
  type: 'Fn',
  properties: { name: data[0] },
  children: { argument: data[2] }
}) %}

# Plain symbol rule - only matches single letters (adjust if you need multi-char symbols)
symbol -> [a-zA-Z] {% (data) => ({
  type: 'Symbol',
  properties: { letter: data[0] },
  children: {}
}) %}

2. Restructure Expressions with Priority Layers

To avoid circular references and fix operator associativity, split your expression rules into layers based on math operator precedence (highest to lowest):

• Atoms: Function calls, symbols, parenthetical expressions (highest priority)
• Exponentiation: Right-associative (since a^b^c means a^(b^c))
• Multiplication/Division: Left-associative
• Addition/Subtraction: Left-associative

Here's how that looks in Nearley:

# Top-level expression starts with lowest priority operations
expr -> add_sub

# Addition/subtraction: left-associative
add_sub -> mul_div (("+" | "-") mul_div)* {% (data) => {
  // Fold left-associative operations into a tree
  let node = data[0];
  for (const [op, rhs] of data[1]) {
    node = { type: 'BinOp', properties: { op }, children: { left: node, right: rhs } };
  }
  return node;
} %}

# Multiplication/division: left-associative
mul_div -> pow (("*" | "/") pow)* {% (data) => {
  let node = data[0];
  for (const [op, rhs] of data[1]) {
    node = { type: 'BinOp', properties: { op }, children: { left: node, right: rhs } };
  }
  return node;
} %}

# Exponentiation: right-associative
pow -> atom ("^" pow)? {% (data) => {
  if (!data[1]) return data[0];
  return { type: 'BinOp', properties: { op: '^' }, children: { left: data[0], right: data[1][1] } };
} %}

# Atomic expressions: match functions FIRST, then symbols/parentheses
atom -> fn | symbol | "(" expr ")" {% (data) => data[0] %}

3. Remove Redundant Nested Rules

Your original error shows sin being nested inside a Symbol's right child, which suggests your old grammar might have had symbols directly embedding expressions (like symbol -> [a-zA-Z] expr?). This is unnecessary now that we have layered expression rules—each node (symbol, function, binop) stands on its own, and the operator rules handle combining them.

4. Debug with Nearley's Testing Tools

Use nearley-test to step through how your parser matches inputs. For example:

nearley-test your-grammar.ne -i "a*sin(x)*y"

This will show you exactly which rules are being triggered at each step. If you still see sin being matched as a symbol first, double-check that the fn rule comes before symbol in the atom rule.

Why This Works #

• By putting function rules first, we eliminate the ambiguity: sin( will always match as a function call, not a plain symbol.
• The layered expression structure ensures operators are parsed in the correct order, and right-associative operations (like exponentiation) don't create circular references.
• Each node type (Symbol, Fn, BinOp) has a clear role, so the parser won't accidentally nest nodes incorrectly.

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