Invisible XML

<!DOCTYPE html>     <html class="no-js" lang="en">  <head> <meta charset="utf-8" /> <meta http-equiv="X-UA-Compatible" content="IE=edge" /> <title>Invisible XML</title> <meta name="description" content="Norm Tovey-Walsh introduces Invisible XML, a language for describing the implicit structure of data, and a set of technologies for making that structure explicit as XML markup."/> <meta name="viewport" content="width=device-width, initial-scale=1" /> <link rel="icon" type="image/x-icon" href="/static/favicon.ico"/> <link rel="stylesheet" href="/static/CACHE/css/output.7ac6b21eee6a.css" type="text/css"> <link href="https://fonts.googleapis.com/css?family=Lato|Roboto" rel="stylesheet"/> <link rel="stylesheet" type="text/css" href="/static/css/print.css" media="print" /> <script async src="https://www.googletagmanager.com/gtag/js?id=G-6Z87ZDEY5E"></script> <script> window.dataLayer = window.dataLayer || []; function gtag(){dataLayer.push(arguments);} gtag('js', new Date()); gtag('config', 'G-6Z87ZDEY5E'); </script> <script async='async' src='https://www.googletagservices.com/tag/js/gpt.js'></script> <script> var googletag = googletag || {}; googletag.cmd = googletag.cmd || []; </script> <script> googletag.cmd.push(function() { googletag.defineSlot('/21754636678/xml.com-1', [[160, 600], [120, 240], [300, 250]], 'div-gpt-ad-1550450394815-0').addService(googletag.pubads()); googletag.defineSlot('/21754636678/xml.com-2', [[300, 250]], 'div-gpt-ad-1550513522284-0').addService(googletag.pubads()); googletag.pubads().enableSingleRequest(); googletag.pubads().disableInitialLoad(); googletag.enableServices(); }); </script> <script> //load the apstag.js library !function(a9,a,p,s,t,A,g){if(a[a9])return;function q(c,r){a[a9]._Q.push([c,r])}a[a9]={init:function(){q("i",arguments)},fetchBids:function(){q("f",arguments)},setDisplayBids:function(){},targetingKeys:function(){return[]},_Q:[]};A=p.createElement(s);A.async=!0;A.src=t;g=p.getElementsByTagName(s)[0];g.parentNode.insertBefore(A,g)}("apstag",window,document,"script","//c.amazon-adsystem.com/aax2/apstag.js"); //initialize the apstag.js library on the page to allow bidding apstag.init({ pubID: '32676f4f-8458-484f-b742-dcd7ad80a504', //enter your pub ID here as shown above, it must within quotes adServer: 'googletag' }); apstag.fetchBids({ slots: [{ slotID: 'div-gpt-ad-1550450394815-0', //example: 'div-gpt-ad-1475102693815-0' slotName: '21754636678/xml.com-1', //example: '12345/box-1' sizes: [[160,600], [300,250], [120,400]] //example: [[300,250], [300,600]] }, { slotID: 'div-gpt-ad-1550513522284-0', //example: 'div-gpt-ad-1475185990716-0' slotName: '21754636678/xml.com-2', //example: '12345/leaderboard-1' sizes: [[300,250]] //example: [[728,90]] }], timeout: 2e3 }, function(bids) { // set apstag targeting on googletag, then trigger the first DFP request in googletag's disableInitialLoad integration googletag.cmd.push(function(){ apstag.setDisplayBids(); googletag.pubads().refresh(); }); }); </script> </head> <body class="homepage"> <div class="title-bar hide-for-print" data-responsive-toggle="menu" data-hide-for="large"> <button class="menu-icon" type="button" value="Menu" data-toggle></button> <div class="title-bar-title">XML.com</div> </div> <div class="row"> <div class="top-bar hide-for-print" id="menu"> <div class="top-bar-left"> <a href="/"><img src="/static/img/XML_com_logo.svg" alt="XML.com logo"/></a> </div> <div class="top-bar-right"> <ul class="menu vertical medium-horizontal" data-responsive-menu="drilldown medium-dropdown" role="menubar"> <li class=""><a href="/">Home</a></li> <li class=" "> <a href="/articles/">Articles</a> </li> <li class=" "> <a href="/authors/">Authors</a> </li> <li class=" "> <a href="/news/">News</a> </li> <li class=" "> <a href="/job-board/">Job Board</a> </li> <li class="has-submenu "> <a href="/about/">About</a> <ul class="submenu menu vertical"> <li class=""> <a href="/about/contribute/">Contribute</a> </li> <li class=""> <a href="/about/style-guide/">Style guide</a> </li> <li class=""> <a href="/about/copyright/">Copyright</a> </li> <li class=""> <a href="/about/contact/">Contact</a> </li> <li class=""> <a href="/about/privacy/">Privacy Policy</a> </li> </ul> </li> <li class="has-form" style="background: transparent;"> <form id="cse-search-box" action="https://google.com/cse"> <input type="hidden" name="cx" value="partner-pub-9264479583913780:3063344556"/> <input type="hidden" name="ie" value="UTF-8" /> <input type="text" placeholder="Search" name="q" title="Google Search"/>  </form> </li> </ul> </div> </div> </div> <div class="row"> <div class="medium-9 columns"> <nav aria-label="You are here:" role="navigation"> <ul class="breadcrumbs"> <li><a href="/">Home</a></li> <li><a href="/articles/">Articles</a></li> <li class="current">Invisible XML</li> </ul> </nav> <div id="content"> <div class="medium-12 columns" role="content"> <ul class="share-buttons hide-for-print"> <li> <a class="button tiny radius facebook" href="http://www.facebook.com/sharer.php?u=/articles/2022/03/01/invisible-xml/" target="_blank">Share on Facebook</a> </li> <li> <a class="button tiny radius twitter" href="https://twitter.com/share?url=/articles/2022/03/01/invisible-xml/">Tweet</a> </li> <li> <a class="button tiny radius linkedin" href="http://www.linkedin.com/shareArticle?mini=true&url=/articles/2022/03/01/invisible-xml/" target="_blank">LinkedIn</a> </li> <li> <a class="button tiny radius mail" href="mailto:?subject=Invisible XML&body=/articles/2022/03/01/invisible-xml/" target="_blank">Email</a> </li> <li> <a class="button tiny radius print" href="javascript:window.print()" target="_blank">Print</a> </li> </ul> <article class="article"> <div class="callout small"> <h1>Invisible XML</h1> March 1, 2022 <a href="/authors/norm-tovey-walsh/">Norm Tovey-Walsh</a> <div id="tags" class="hide-for-print"> <a class="fancy radius button small" href="/articles/?tag=invisible XML">invisible XML</a> </div> <div class="summary">Norm Tovey-Walsh introduces Invisible XML, a language for describing the implicit structure of data, and a set of technologies for making that structure explicit as XML markup.</div> </div> <div class="body"> Invisible XML is a language for describing the implicit structure of data, and a set of technologies for making that structure explicit as XML markup. It allows you to write a declarative description of the format of some text and then leverage that format to represent the text as structured information. That sounds a bit abstract, so let’s start with an example: Suppose you have a document, <code class="filename">contacts.txt</code>, where you keep the names, email addresses, and other details of friends and colleagues. It might look something like this: <pre class="programlisting language-none">John Doe john@example.com 555-1234 Mary Smith m.smith@estaff.example.com +1-222-555-2344 Jane Doe (512) 555-9999 Nancy Jones nancy@example.org</pre> This is obviously a toy example, but it will work to illustrate a few points. First of all, those of us who are used to working with marked up data (such as XML or JSON) are likely to think of this as “unstructured” data. But that’s not really true. There is structure there, it’s just indicated with whitespace and other informal conventions, rather than with angle brackets or curly braces. The real world is full of data marked up using different conventions. We use files like this every day: email headers, ical and vcard files, CSS, Java property files, Windows “ini” configuration files, BibTeX, Markdown, etc. At finer levels of granularity, we find even more examples: ISO 8601 dates and times, XPath expressions, CSS selectors, and so on. And then we have our own ad hoc formats in countless text files: diaries, todo lists, calendars, event planners, etc. There are probably a dozen or so files like this within easy reach wherever you’re reading this. This is fine when the important consumers are human readers looking at the text. But what happens when we want to use that data in some other system? What happens when we want to extract the information out of these documents structured by conventions of spacing and punctuation? A common approach would be to write a script to read the format: <table class="codehighlighttable"><tr><td class="linenos"><div class="linenodiv"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19</pre></div></td><td class="code"><div class="codehighlight"><pre>#!/usr/bin/env python3 contacts = [] with open('contacts.txt', 'r') as infile: contact_id = 0 expect_name = True for line in infile.readlines(): line = line.strip() print(contact_id, line) if line == "": contact_id += 1 expect_name = True elif expect_name: contacts.append({ "name": line }) expect_name = False elif "@" in line: contacts[contact_id]["email"] = line else: contacts[contact_id]["phone"] = line </pre></div> </td></tr></table> That’s horrible, and not just because it’s a bit of sloppy code I banged out in a few short minutes. (Way more of the world’s infrastructure relies on code someone put together for a prototype or a demo than you’d care to think about.) The real problem here is that this tells you nothing about the file format beyond what you can glean from the source code. These kinds of procedural or imperative definitions of a file format, even if they’re backed up by some sort of prose description (that you hope is up-to-date with the latest version of the code, even though you know it isn’t), are difficult to understand, difficult to test, and difficult to reason about. Can I put an address in this file? Is it ok if I have two blank lines? If I have a phone number but not an email address, can I just put in a blank line for the email address? For anything bigger than a toy example, these are not easy questions to answer. You would be much better off if you had a declarative description of the format. Declarative descriptions are more accessible, easier to reuse, and generally require less coding. So why, you might ask, don’t we use them all the time? We do. Your XML processor, your JavaScript engine, your JSON tooling, the compilers that built your web browser and your operating system, are all driven by parsers that take declarative descriptions of a system plus some input, construct an abstract representation of that system, and operate on it. Under the hood, our favourite software is making constant use of declarative descriptions. Okay, but why don’t we use them all the time? There are a couple of reasons. Historically, it was expensive. I mean computationally expensive. But <a href="https://en.wikipedia.org/wiki/Moore%27s_law">Moore’s Law</a> has pretty much sorted that out. The other reason, the real reason, is because it’s hard work. Off-the-shelf tools are mostly designed to build incredibly efficient parsers that can analyze huge amounts of data, unambiguously and efficiently, with only a character or two of lookahead. Writing format descriptions for those tools is a specialized skill that few of us have. But it doesn’t actually have to be hard. Or at least, nowhere near that hard. What makes it a specialized skill, and what makes it hard, is fitting your declarative description into those very tight requirements: no ambiguity and no (or only a small, fixed amount of) lookahead. Luckily, that’s not the only way to approach the problem. Techniques for parsing that are tolerant of ambiguity and prepared to engage in (more-or-less) arbitrary lookahead have been around for decades. They are not as fast, or as memory efficient, as traditional parsers, but they can be competitive in many cases. And we have Moore’s Law on our side! Those problems are no longer significant in many environments. Invisible XML provides a specific syntax for declarative description that’s easy to use and easy to understand. Combined with a parser that understands Invisible XML, you can apply those descriptions to your data and get structured data out. No (imperative) coding required. Before we dig in deeper, let’s establish a little bit of vocabulary. An Invisible XML document is a grammar. As a term of art in computer programming, a grammar is essentially a set of rules. Each rule describes a symbol in terms of some other symbols. If you’ve ever used regular expressions, you’re familiar with these ideas, even if you didn’t use this exact vocabulary. If you’re matching data in Python or XPath, or any language with regular expressions, and you say that an integer is a string that matches <code class="code">[-+]?[0-9]+</code>, you’ve created a grammar rule: <code class="code">integer: [-+]?[0-9]+</code>. Invisible XML collects these rules together. Each rule has a “left hand side” and a “right hand side”. The left hand side is a single symbol, the one being defined, and the right hand side is a list of one or more symbols that define it. A symbol is either the name of something, in which case there must be a further rule that defines it, one that has it as the rule’s left hand side; or it’s something that literally matches characters in your input. With these rules, the processor will work out whether it’s possible to match the whole input string that you gave it by applying these rules in some order. Let’s take a very small example. Suppose we want to match sentences of three letter words like “see cat sat”. We could write an Invisible XML grammar like this: <pre class="programlisting language-none line-numbers">sentence : word+" " . word : consonant, vowel, consonant; consonant, vowel, vowel. vowel : ["aeiouy"] . consonant : ["bcdfghjklmnpqrstvwxyz"] .</pre> We’ll come back to the specific details about syntax and how to write an Invisible XML grammar in the next article, for now we’ll just do a little hand waving. That grammar has four rules and you can read them like this: <div class="orderedlist"><ol style="list-style: decimal;"> <li>A sentence is one or more occurrences of word separated by a single space.</li> <li>A word is a consonant, followed by a vowel, followed by a consonant or a consonant followed by two consecutive vowels.</li> <li>A vowel is literally “a”, “e”, “i”, “o”, “u”, or “y”.</li><li>A consonant is literally any one of the other lowercase, English language letters, and also “y”.</li></ol> </div>Note that there’s nothing procedural here. There’s no attempt to say how you do anything with a word or any of its constituent parts. The grammar just declaratively describes the format. It’s easy to answer questions about this format. Are numbers allowed? Can words be more or less than three letters long? Is punctuation allowed? No, no, and no, respectively. And it’s easy to imagine writing tests to ensure that this grammar does match what you want. Of course, there is software that’s going to process it. The first thing a processor, or parser, is going to do is determine whether the input string you gave it matches the grammar (you’ll sometimes see this written as “checking if the input is a sentence in the grammar”). In order to do that, it has to know where to start, so you need to nominate one of the symbols as the “start symbol”. In Invisible XML, that’s the symbol in your first rule, so “sentence” in this case. We can imagine a parser, given this grammar and the one word sentence “cat”, doing something like this:<div class="orderedlist"> <ol style="list-style: decimal;"><li>Does the input match sentence? I don’t know, what’s a sentence? </li> <li>A sentence is one or more words separated by spaces. Does the input match word? I don’t know, what’s a word? </li> <li>A word is either:<div class="itemizedlist"><ul><li>A consonant, followed by vowel, followed by a consonant, or </li><li>a consonant, followed by a vowel, followed by another vowel. </li></ul></div>Does the input match that? I don’t know, what’s a consonant? </li><li>A consonant is one of a set of letters. Ok. Does the first letter match one of those? Yes, “c” is one of those letters. Great. </li> <li>Does the rest of the input match the rest of the “right hand side”? The next thing is vowel. Does the rest of the input match that? I don’t know, what’s a vowel? </li><li>A vowel is one of a set of letters. Ok. Does the next letter match one of those? Yes, “a” is one of those letters. Great. </li> <li>And on it goes, matching symbols against rules until it runs out of symbols or runs out of input. In this case, it will run out of input after it matches the “t”. </li> <li>There’s no input left. If we stop here, are we finished with the right hand side of the rule for the start symbol? Yes? Great. Yes, “cat” is a sentence. </li></ol> </div>As you can see, the parser uses the rules to replace symbols with what those symbols can be in a kind of recursive process that “bottoms out” when it reaches something that has to match the input. Sometimes you’ll see the class of symbols that can be replaced by other symbols identified as “nonterminals” as distinct from the symbols that literally match against the input, the “terminals”. What happens if it doesn’t match? What happens, for example, if we give this grammar the input “frog”? In that case, the parser will tell you it couldn’t match your grammar (“the input is not a sentence in the grammar”). Something like this: Parse failed. At position 2, found unexpected “r”. Would have permitted: ["aeiouy"]. So your grammar also functions as a validator for your input! On a successful parse, the other thing an Invisible XML parser has to do is tell you how it matched the input. This is the part that gives you back the structured information. For our word parser, it’s pretty simple and obvious: <div class="codehighlight"><pre><sentence> <word> <consonant>c</consonant> <vowel>a</vowel> <consonant>t</consonant> </word> </sentence> </pre></div> Broadly speaking, Invisible XML makes each nonterminal in your grammar into an XML element. In fact, it offers you a number of ways to control how the results are constructed, including which nonterminals should be output, which things should be elements and which should be attributes, and even which things to elide altogether. We’ll come back to those topics when we talk about writing grammars in the next article. There are two other things to bear in mind. First, the grammar only validates against its rules. According to this grammar “xeq bei” is a perfectly fine sentence. Second, an input may be ambiguous with respect to a grammar. Consider the sentence “hey bee”. If you parse that with our sentence grammar, you’ll get: <div class="codehighlight"><pre><sentence xmlns:ixml="http://invisiblexml.org/NS" ixml:state="ambiguous"> <word> <consonant>h</consonant> <vowel>e</vowel> <vowel>y</vowel> </word> <word> <consonant>b</consonant> <vowel>e</vowel> <vowel>e</vowel> </word> </sentence> </pre></div> Or maybe you’ll get: <div class="codehighlight"><pre><sentence xmlns:ixml="http://invisiblexml.org/NS" ixml:state="ambiguous"> <word> <consonant>h</consonant> <vowel>e</vowel> <consonant>y</consonant> </word> <word> <consonant>b</consonant> <vowel>e</vowel> <vowel>e</vowel> </word> </sentence> </pre></div> There are two different ways to parse the input because our grammar says that a “y” can be either a consonant or a vowel. The word “hey” therefore matches both the pattern “consonant-vowel-vowel” and the pattern “consonant-vowel-consonant”. That makes the results ambiguous. The Invisible XML processor is required to tell us that, and it’s required to return one of the valid parses. (Implementations may give you more control than that, but that’s all that’s required for conformance.) You might now be asking yourself, what about the word “gym”? Would that be ambiguous too? It is, in some sense “ambiguous” because it’s either “consonant-vowel-consonant” or “consonant-consonant-consonant”. But it’s not ambiguous in this grammar because “consonant-consonant-consonant” isn’t a possible match. Ambiguity is ok, and sometimes it’s necessary. The ambiguity in this grammar is an inherent property of the English language rule that “y” sometimes represents the sound of a vowel and sometimes it represents the sound of a consonant. That said, the more ambiguity there is, the more possibilities the parser may have to consider when it’s looking for matches. That can make the process slower. We’ll look more at ambiguity when we start writing grammars in the next part. Here, finally, is a grammar for the contacts format: <pre class="programlisting language-none line-numbers">contacts: (contact, NL*)+ . contact: name, NL, (email, NL)?, (phone, NL)? . name: letter, ~[#a; "@"]* . email: username, "@", domainname . phone: ["+0123456789()- "]+ . -username: (letter; ["+-."])+ . -domainname: (letter; ["+-."])+ . -letter: [L] . -NL: -#a ; -#d, -#a .</pre> It can be read like this: <div class="orderedlist"><ol style="list-style: decimal;"><li>A contacts file consists of one or more contact items followed by zero or more newlines.</li> <li>A contact is a name followed by a newline, optionally followed by an email followed by a newline, optionally followed by a phone followed by a newline. </li> <li>A name is a letter followed by any characters except newline or “@”. </li> <li>An email is a username followed by “@” followed by a domainname. </li> <li>A phone is one or more digits or the “+”, “(“, “)”, “-”, and space punctuation characters. </li> <li>A username is one or more occurrences of letter or any of the characters “+”, “-”, and “.”. </li> <li>A domainname is one or more occurrences of letter or any of the characters “+”, “-”, and “.”. </li> <li>A letter is any character in the Unicode character class “L” (letters). </li> <li>A NL is a newline or the sequence carriage return followed by newline. </li></ol></div> If you give that grammar and the contacts file to an Invisible XML processor, it will return: <div class="codehighlight"><pre><contacts> <contact> <name>John Doe</name> <email>john@example.com</email> <phone>555-1234</phone> </contact> <contact> <name>Mary Smith</name> <email>m.smith@estaff.example.com</email> <phone>+1-222-555-2344</phone> </contact> <contact> <name>Jane Doe</name> <phone>(512) 555-9999</phone> </contact> <contact> <name>Nancy Jones</name> <email>nancy@example.org</email> </contact> </contacts> </pre></div> Or the author of the processor might allow you to ask for the output in JSON instead: <div class="codehighlight"><pre>{ "contacts": { "contact": [ { "name": "John Doe", "email": "john@example.com", "phone": "555-1234" }, { "name": "Mary Smith", "email": "m.smith@estaff.example.com", "phone": "+1-222-555-2344" }, { "name": "Jane Doe", "phone": "(512) 555-9999" }, { "name": "Nancy Jones", "email": "nancy@example.org" } ] } } </pre></div> Or maybe in CSV: <pre class="programlisting language-none">"name","email","phone" "John Doe","john@example.com","555-1234" "Mary Smith","m.smith@estaff.example.com","+1-222-555-2344" "Jane Doe",,"(512) 555-9999" "Nancy Jones","nancy@example.org",</pre> Every Invisible XML processor begins by creating a basic XML representation of your input data. That’s why it’s called Invisible XML. But what’s really going on here is that we’re turning input with implicit structure into explicitly structured data that can be transformed into whatever output format we require. And we’re doing it by describing that format in a compact, understandable, reusable, testable way. Join us next time for a detailed look at the syntax of Invisible XML. </div> <div class="copyright"> Article contents © 2022 Norman Tovey-Walsh </div> </article> </div> </div> </div> <aside id="sidebar" class="medium-3 columns hide-for-print"> <div class="text-center"> <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>  <ins class="adsbygoogle" style="display:inline-block;width:300px;height:250px" data-ad-client="ca-pub-9264479583913780" data-ad-slot="1017007355"></ins> <script> (adsbygoogle = window.adsbygoogle || []).push({}); </script> </div> <div class="text-center"> <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>  <ins class="adsbygoogle" style="display:inline-block;width:160px;height:600px" data-ad-client="ca-pub-9264479583913780" data-ad-slot="1629348156"></ins> <script> (adsbygoogle = window.adsbygoogle || []).push({}); </script> </div> </aside> </div> <div class="row column"> <hr class="dotted"/> </div> <footer class="row column"> © Textuality Services, Inc. except for those articles with named authors or copyright holders. All trademarks and registered trademarks appearing on XML.com are the property of their respective owners. </footer> <script src="/static/CACHE/js/output.d5b0ccff8392.js"></script> </body> </html>

CINXE.COM

Invisible XML