# How to remove left recursion from a PEG grammar > Rewrite a left-recursive rule so peggy accepts it, fold the action from the left to keep subtraction left-associative, and compare with ohm-js and nearley. Source: https://voxgig.com/howto/remove-left-recursion-from-a-peg-grammar - Audience: library-maintainer - Level: intermediate - Languages: typescript - Verified: 2026-09-25 - Published: 2026-09-25 ## 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,[^1] and the rewrite below is the standard way round it. ## Approaches compared | Approach | When it fits | What it costs you | When to pick something else | | --- | --- | --- | --- | | [nearley](https://nearley.js.org/docs/grammar) | The grammar is left-recursive or ambiguous as written and you want it accepted verbatim | An Earley parser rather than recursive descent, a compile step, and every ambiguity comes back as extra parses | The grammar is unambiguous and a generated recursive descent parser already runs it | | [ohm-js](https://ohmjs.org/docs/syntax-reference) | You want the rule as the specification writes it, with the semantics kept out of the grammar | A second toolchain with its own grammar syntax, and actions in a separate object rather than beside the rule | One rule is left-recursive and the rest of the grammar already runs on peggy | | [peggy, with the rule rewritten](https://peggyjs.org/documentation.html) | One or two left-recursive rules in a grammar that otherwise works | The rule no longer reads like the specification, and associativity moves into an action you have to test | Most rules are left-recursive, so the rewrite touches everything | 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. ```text title="left.peggy" 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. ```bash node left-recursion.mjs ``` ```text output 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`](https://peggyjs.org/documentation.html#error-messages), 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. ```text title="arith.peggy" 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`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/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](https://ohmjs.org/). nearley builds a table of partial parses instead of descending into rules, so a rule that begins with itself has nothing to loop over.[^2] ```text title="arith.ohm" 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](https://ohmjs.org/docs/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. ```ts title="engines.mjs" 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. ```text title="arith.ne" 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. ```bash 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. ```bash node demo.mjs ``` ```text output 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](https://nodejs.org/api/test.html). ```ts title="arith.test.mjs" 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), ) }) ``` ```bash node --test arith.test.mjs ``` ```text output 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. ```text title="arith-right-fold.peggy" expr = head:term tail:(_ "-" _ term)* { const operands = [head, ...tail.map((t) => t[3])] return operands.reduceRight((acc, n) => n - acc) } ``` [`reduceRight`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/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](https://nearley.js.org/docs/how-to-grammar-good#operator-precedence-is-not-black-magic), 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.[^3] 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](/howto/attach-parse-actions-by-rule-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. [^1]: The restriction is as old as the name. Bryan Ford's [packrat parsing page](https://bford.info/packrat/) records that he coined the modern terms parsing expression grammar and packrat parsing, in a 2002 ICFP paper and a 2004 POPL paper. The same sentence adds that much of the formal theory existed earlier, and that the more recent work is by others. The related work it lists includes [Packrat parsers can support left recursion](https://web.cs.ucla.edu/~todd/research/pepm08.pdf), from 2008, by Warth, Douglass and Millstein. The first of those three names is also the first name on [Ohm's copyright line](https://github.com/ohmjs/ohm/blob/main/LICENSE), which is one route by which a paper reaches production. [^2]: The algorithm is Jay Earley's, and the tool's name is the algorithm's with one letter changed. The nearley documentation sends anyone who wants the algorithm explained to a post by the tool's author titled [Better Earley than never](https://hardmath123.github.io/earley.html), so the pun stands on both sides of the link. The post says an Earley parser will parse anything you give it, and lists infinite loops caused by left recursion among the ways the parsers everyone uses break instead. [^3]: nearley's guide to writing grammars has a section headed [Don't shy away from left recursion](https://nearley.js.org/docs/how-to-grammar-good#dont-shy-away-from-left-recursion). It says a naive recursive descent parser would loop forever on `a -> a "something"`, that nearley does not, and that left recursion is very slightly faster than right. The section immediately after it is headed "Do shy away from left recursion," and runs to one line: where the EBNF repetition operators make more sense. The advice is consistent, and the headings are a matched pair.