Writing a Wikipedia XML Parser in Plain C

Quick Summary

We’re using all the math we know to compete in the Hutter Data Compression prize (and fund LeetArxiv). This is part 3.

LeetArxiv teaches programmers how to turn complex math papers into C and Python code. Subscribe.

Our Journey

Sorting Algorithms:Burrows-wheeler transform.Gumbel-Sinkhorn sorting neural network.

MediaWiki Parsing:

(we are here) PEG Parser. Parser approach and XML parser.

HTML and Markdown Parser.

1.0 Getting Started

This tutorial started out as a PEG parser for the MediaWiki grammar (Mediawiki, 2026) 1 that defines Wikipedia pages.

We pivoted to a simple state machine to align with our data compression needs.

This article oscillates between the Enwik8/Enwik9 datasets: the first 10 9 bytes of the English Wikipedia dump on Mar. 3, 2006 (Mahoney, 2025) 2 all through the tutorial.

Be warned however, Wikipedia’s text has a long history of poorly designed additions carelessly piled on top of each other (Portström, 2018) 3. The gravity of this side project weighs on me lol.Subscribe now

1.1 Acquiring the Dataset

One can download the dataset at this link.

• Observe that ZIP compresses the dataset to 300 MB.

After downloading and unzipping the dataset, one should observe:

Enwik9 is exactly 1 billion bytes ie 1 GB

1.2 Dataset Loading, Character Indexing Helpers

Next, we write a dataset loader in C. We shall use Linux memory mapping. Here’s the link to this section's code.

We write a function to get the file size and another to map to memory:

GetFileSize and LoadData functions

Now we can print the data in our main function:

Printing Enwik9 to the terminal

2.0 Parsing Wikipedia Data

A MediaWiki parser demands us contend with a (rather bizarre) mélange of markdown, XML, HTML and overall nondescript formatting rules.

This section attempts to make sense of it all.

2.1 Recursive Descent Parsing Failed

Initially, our goal was to write a recursive PEG parser just to make the haskell-lovers (that’s a slur in my books) hap…