Parsing XML with a context free grammar

Contents

1. Artifacts

Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.

Note: The grammar is based on the XML grammar in the fuzzingbook.

XML (and its relatives like HTML) is present pretty much everywhere at this point. One of the problems with XML is that, while the idea of XML is really simple, the implementation is fairly heavyweight, with Apache Xerces Java clocking at 127 KLOC of Java files.

Do we really need such a heavyweight machinery? especially if one is only interested in a subset of the functionality of XML? Similar languages such as JSON clock in at a few hundred lines of code.

XML is a context sensitive language, and hence, it is hard to write a parser for it. However, XML if you look at it, is a parenthesis language, and except for the open and close tag matching, doesn’t have long range context sensitive features. So, can we parse and validate XML using a parser that accepts simple context free parsers?

Turns out, one can! The idea is to simply use a context-free grammar that ignores the requirement that the closing tag must match the opening tag, and then use a secondary traversal to validate the open/close tags.

We define our grammar as below:

We use our PEG parser from the previous post to parse XML. First we define a convenience method that translate a derivation tree to its corresponding textual representation.

One thing we want to take care of is to translate our derivations trees to actual XML DOM. So, we define a translator for the tree as below.

Now, all that is left to validate the tags.

Finally, we define our parser.

Using

Artifacts

The runnable Python source for this notebook is available here.