---
id: CVE-2026-12876
aliases:
  - GHSA-ff5c-cp5c-9wjf
  - PYSEC-2026-3869
title: >-
  NLTK: Uncontrolled resource consumption in RecursiveDescentParser via
  ambiguous or left-recursive grammars
summary: >-
  NLTK: Uncontrolled resource consumption in RecursiveDescentParser via
  ambiguous or left-recursive grammars
severity: medium
vendor: nltk
product: nltk
ecosystem: pip
affected:
  - nltk < 3.10.3
patched:
  - nltk 3.10.3
published: '2026-09-02'
updated: '2026-09-10'
sourceUpdated: '2026-09-10T12:25:59.672261950Z'
source: OSV
sourceUrl: 'https://osv.dev/vulnerability/GHSA-ff5c-cp5c-9wjf'
references:
  - url: 'https://github.com/nltk/nltk/security/advisories/GHSA-ff5c-cp5c-9wjf'
  - url: 'https://github.com/nltk/nltk/pull/3649'
  - url: >-
      https://github.com/nltk/nltk/commit/43aaca1b9024138421c97f970bf13ee19ac8129d
  - url: 'https://github.com/nltk/nltk'
  - url: 'https://github.com/nltk/nltk/releases/tag/v3.10.3'
  - url: 'https://pypi.org/project/nltk'
  - url: 'https://github.com/advisories/GHSA-ff5c-cp5c-9wjf'
  - url: 'https://nvd.nist.gov/vuln/detail/CVE-2026-12876'
tags:
  - osv
  - pip
  - ghsa
cwe:
  - CWE-407
  - CWE-674
ingestedAt: '2026-09-02T14:45:30.389Z'
---

## Overview

`nltk.parse.RecursiveDescentParser` (and `SteppingRecursiveDescentParser`) enumerate parses top-down with no bound on the number of recursive steps. A small, crafted context-free grammar makes a short input consume unbounded CPU (and/or exhaust the Python recursion stack), pinning a process indefinitely — a denial of service.

## Proof of concept

Both of the following hang on a 24-token input (killed after 8s; growth is super-linear in input length), on NLTK develop:

```python
from nltk import CFG
from nltk.parse import RecursiveDescentParser

# (a) left recursion -> unbounded recursion
g = CFG.fromstring("S -> S S | 'a'")
list(RecursiveDescentParser(g).parse(["a"] * 24))   # hangs

# (b) ambiguous grammar -> exponential number of parses
g = CFG.fromstring("S -> 'a' S | 'a' S S | 'a'")
list(RecursiveDescentParser(g).parse(["a"] * 24))   # hangs
```

## Impact

An application that runs `RecursiveDescentParser` on a grammar (or an input) drawn from an untrusted source can be driven into an unbounded CPU / stack-exhaustion loop by a tiny payload. No confidentiality or integrity impact; single-process availability only.

## Sibling

The RegexpTokenizer ReDoS reported alongside this (CVE-2026-12875) is a different class (caller-supplied regex) and is addressed under GHSA-w3v8-gmh9-3wv7.

## Affected packages

- `nltk < 3.10.3`

## Remediation

Upgrade to a patched release:

- `nltk 3.10.3`