How to remove left recursion from a PEG grammar#

Your grammar says expr = expr "-" term / term, because that is how the specification writes it, and peggy refuses to generate a parser from it. The message says the rule calls itself without consuming input. A recursive descent parser would re-enter that rule until the stack ran out, so the generator stops before the parser can start.

What you get

You will end up with a rewritten rule that peggy accepts, an action that keeps subtraction left-associative, and the original rule running on ohm-js and nearley. This is for you if your grammar follows a specification that uses left recursion.

Short answer

Rewrite expr = expr "-" term / term as a head followed by a repeated tail, expr = term ("-" term)*, and fold the tail from the left in the action with reduce, so 1-2-3 is (1-2)-3. peggy then generates the parser it refused before. Keep the rule as written only if you move to an engine that accepts left recursion, such as ohm-js or nearley.

You will need

Node 22 or later, and a grammar with a rule that begins with itself. Verified 2026-09-25 against Node 22.22.2, peggy 5.1.0, ohm-js 17.5.0, and nearley 2.20.1. The restriction is not peggy’s invention. It belongs to parsing expression grammars as a class,¹ and the rewrite below is the standard way round it.

Approaches compared

The rewrite keeps the toolchain and changes the grammar. ohm-js keeps the grammar and adds a toolchain, with semantics in a separate object, which its documentation presents as a design decision rather than a gap. nearley accepts the rule because Earley parsing does not descend into rules at all. It charges for that in speed, and in the extra parses you get back when the grammar is ambiguous. Which cost you can carry depends on how many rules are left-recursive, not on which parser is fastest.

See what peggy refuses

The rule as the specification writes it, in a grammar of its own.

expr
  = left:expr "-" right:term { return left - right }
  / term

term
  = digits:$[0-9]+ { return parseInt(digits, 10) }

Ask peggy to generate a parser from it.

node left-recursion.mjs

GrammarError: Possible infinite loop when parsing (left recursion: expr -> expr)

error: Possible infinite loop when parsing (left recursion: expr -> expr)
 --> left.peggy:3:1
  |
3 | expr
  | ^^^^
note: Step 1: calls itself without input consumption - left recursion
 --> left.peggy:4:10
  |
4 |   = left:expr "-" right:term { return left - right }
  |          ^^^^

People describe this as an infinite loop, and it would be one: expr tries expr first, which tries expr first. peggy finds the cycle while generating the parser and reports it as a GrammarError, so nothing runs. That is the better failure. A generator that emitted the parser anyway would hand you a stack overflow on the first input. The same pass catches recursion that runs through another rule, and recursion through a prefix that can match nothing, and its notes list the steps in the cycle.

Rewrite the rule and fold from the left

A left-recursive rule says an expression is an expression, an operator, and a term. The rewrite says the same thing without the self-reference: a term, then any number of operator and term pairs.

expr
  = head:term tail:(_ "-" _ term)* {
      return tail.reduce((acc, t) => acc - t[3], head)
    }

term
  = head:factor tail:(_ "/" _ factor)* {
      return tail.reduce((acc, t) => acc / t[3], head)
    }

factor
  = digits:$[0-9]+ { return parseInt(digits, 10) }
  / "(" _ e:expr _ ")" { return e }

_ = [ \t]*

tail is an array with one entry per repetition, and each entry is the array [_, "-", _, term], so the operand sits at index 3. reduce starts from head and works rightward, which is what left-associative means: 1-2-3 becomes (1-2)-3. The grammar no longer says that. The action does, and that is the cost the table names: a property the specification stated in one line of grammar is a line of JavaScript you have to test.

The same shape handles division in term. Precedence survives the rewrite because it never depended on the recursion: expr is built from terms and term from factors, so / binds tighter than - exactly as before.

Run the rule as written on ohm-js and nearley

Two engines take the left-recursive rule as it stands. ohm-js supports left recursion directly, and says so on its front page. nearley builds a table of partial parses instead of descending into rules, so a rule that begins with itself has nothing to loop over.²

Arith {
  Exp    = Exp "-" Term     -- minus
         | Term
  Term   = Term "/" Factor  -- div
         | Factor
  Factor = "(" Exp ")"      -- paren
         | number
  number = digit+
}

The -- minus suffix names the alternative, and the semantics object binds an operation to that name. Ohm keeps actions out of the grammar on principle; its syntax reference calls the separation one of its defining features. A rule whose name is capitalized skips whitespace, so Exp accepts 1 - 2 without a rule for spaces.

const ohmGrammar = ohm.grammar(read('arith.ohm'))
const ohmSemantics = ohmGrammar.createSemantics().addOperation('eval', {
  Exp_minus(left, _op, right) { return left.eval() - right.eval() },
  Term_div(left, _op, right) { return left.eval() / right.eval() },
  Factor_paren(_open, e, _close) { return e.eval() },
  number(_digits) { return parseInt(this.sourceString, 10) },
})

nearley carries its actions inline as postprocessors, and id is the one it ships, returning the first element of the match.

expr   -> expr _ "-" _ term     {% ([left, , , , right]) => left - right %}
        | term                  {% id %}
term   -> term _ "/" _ factor   {% ([left, , , , right]) => left / right %}
        | factor                {% id %}
factor -> [0-9]:+               {% ([digits]) => parseInt(digits.join(""), 10) %}
        | "(" _ expr _ ")"      {% ([, , e]) => e %}
_      -> [ \t]:*               {% () => null %}

Compile it once. nearleyc writes a CommonJS module, so the output takes the .cjs extension in a package that is otherwise ES modules.

npx nearleyc arith.ne -o arith.cjs

The three engines on the same inputs: the two left-associative operators, and parentheses to force the other grouping.

node demo.mjs

peggy 5.1.0 | ohm-js 17.5.0 | nearley 2.20.1

input       peggy     ohm-js    nearley
1-2-3       -4        -4        -4
8/4/2       1         1         1
10-2-3-4    1         1         1
1-(2-3)     2         2         2
(8/4)/2     1         1         1
20/(4/2)    10        10        10

arith-right-fold.peggy on 1-2-3: 2 (should be -4)

Same answers everywhere, from three grammars that look nothing alike. The last line is the rewrite with its fold pointing the other way, and it is the subject of the failure section below.

Check it worked

The cases a right-leaning fold gets wrong, pinned for every engine, plus the refusal itself, with the Node test runner.

const CASES = [
  ['1-2-3', -4],
  ['8/4/2', 1],
  ['10-2-3-4', 1],
  ['1-(2-3)', 2],
  ['20/(4/2)', 10],
  ['7', 7],
]

for (const [name, parse] of Object.entries(ENGINES)) {
  test(`${name} folds subtraction and division from the left`, () => {
    for (const [src, want] of CASES) {
      assert.equal(parse(src), want, src)
    }
  })
}

test('peggy refuses the left-recursive grammar at generation time', () => {
  assert.throws(
    () => peggy.generate(read('left.peggy')),
    (err) => err.name === 'GrammarError' && /left recursion: expr -> expr/.test(err.message),
  )
})

node --test arith.test.mjs

1..6
# tests 6
# suites 0
# pass 6
# fail 0
# cancelled 0
# skipped 0
# todo 0
# duration_ms 213.776904

1-2-3 is the case to keep. A fold in the wrong direction passes every test with two operands, so a suite built from 1-2 and 8/4 never catches it.

When it goes wrong

1-2-3 evaluates to 2. The rewrite produced a flat list and the action folded it from the right, so 1-(2-3) is what got computed. arith-right-fold.peggy is that mistake, kept so it can be shown.

expr
  = head:term tail:(_ "-" _ term)* {
      const operands = [head, ...tail.map((t) => t[3])]
      return operands.reduceRight((acc, n) => n - acc)
    }

reduceRight is the give-away, and so is a recursive helper that handles the last pair first. Fold with reduce, from head, and keep 1-2-3 in the tests.

peggy reports left recursion where you wrote none. The cycle runs through another rule, or through a prefix that can match the empty string. expr = _ expr "-" term / term with _ = [ \t]* is left-recursive, because _ can consume nothing, and the error names expr -> expr all the same. Read the notes under the error from the top: each one is a step in the cycle, and the rule that reaches expr without consuming input is the one to change.

nearley returns two results for one input. The grammar is ambiguous, and Earley parsing reports every derivation rather than picking one. engines.mjs treats any count other than one as an error, which is the safer default: an ambiguity in an arithmetic grammar is a bug. Give each operator its own rule, which is also how nearley’s documentation says to settle precedence, and the second parse goes away.

When not to do this

Do not rewrite a grammar in which most rules are left-recursive. An expression grammar copied from a language specification has one such rule per precedence level, and a rewrite of ten rules is a new grammar wearing the old one’s name. Move to an engine that accepts the rule and keep the specification’s shape.

Do not switch engines to fix one rule. A second parser toolchain is a second grammar syntax, a second set of error messages and a second thing to teach. The rewrite is four lines and an action, and the test pins the property the action now owns.

Do not turn on peggy’s cache option to get past the error. The option caches match results to avoid exponential time on pathological grammars, and its documentation says it makes the parser slower. It does nothing for left recursion, which the generator refuses with the cache on or off.

Do not accept several results from nearley as a parse.³ Take the single result or fail, because a grammar that is ambiguous for 1-2-3 is ambiguous for every input that matters.

Related how-tos

• Attach parse actions to grammar rules by name

Last verified

Verified 2026-09-25 against Node 22.22.2, peggy 5.1.0, ohm-js 17.5.0, and nearley 2.20.1. Every output block is what the command preceding it printed.