Last time I introduced a general Definition Language (DL) I created for defining structured information. The end goal was an extension of DL, called Data Definition Language (DDL), intended for defining memory and file formats. It was intended for tools that examine that data, allowing them more knowledgeable output than a raw hex dump.

I mentioned that DL has been on my mind lately, and as it turns out I spent the day yesterday writing a DL parser in Python.

Here’s the BNF for DL; it’s very simple:

{definition} := {tag} {name} {content} "END" {tag}
             := {tag} {name} {content} ";"

{content} := NULL
          := {attribute}{content}
          := {definition}{content}

{attribute} := {tag} ":" {name}

{comment} := "--" {any-text} EOL

A {definition} is a nested object (much like an XML element) that can contain {attribute}s and more {definition}s. Unlike XML, there is no text content; any such content must go in an {attribute}.

Here’s a simple DL file:

module "My DL Demo"
    version: 1.0
    author: "Wyrd Smythe"

    section Header
        datetime created date:2021/11/11 time:16:40:42 ;
        datetime updated date:2021/11/11 time:19:58:11 ;
        email: thewyrdsymthe@foomail.net
        encoding: UTF-8
    end section

    section Body
        access: public
        section Signature
            type: byte
            count: 8
        end section
        section Parameters
            -- more definitions
        end section
        section ControlData
            -- more definitions
        end section
    end section
    --
    -- ....etc.....
    --
end module

Note that DL is just a format. Concrete use requires defining the {definition} and {attribute} tags meaningfully.

Such a simple format seems like it would be easy to parse, and it is.

§ §

To begin, we’ll break the text into a list of tokens for a recursive descent parser. We’ll strip comments in the lexer, so the parser will only need to concern itself with three types of objects: a {definition}, an {attribute} and the content of a {definition}. In fact there are only two types; the third is just a list of some mix of the first two.

The first item is the class that defines an InputToken. The lexer creates and returns a list of these; the parser takes one.

Very simple object: word is one or more characters; cpos is the character position in the file; lnbr is its line number. The add method appends characters to the word variable.

Of course, we always define __str__ so that we can pretty print an instance.

The lexer function, dl_parser, looks basically like this:

There are some constants and variables defined, we loop over the characters in the source file, and then return the list of tokens. Note that the last line of the loop, if we make it there, uses the current character to start a new token. As you’ll see, we only make it to the end of the loop if the character isn’t handled in any other way.

(The textfile class is my little set of file objects. It can easily be replaced with the standard Python open function.)

§

The guts of the parser, the body of the for loop, divides into three sections. The first one includes the line counter and string handlers. (Note that these three sections have two levels of indent I’m not showing here. They’re part of that for loop.)

The string handlers will make more sense once we see the last section. The middle section handles (and removes) comments. (A comment begins with two hyphen characters and continues to the end of line.)

The last section does some serious character handling. It recognizes whitespace (which will end any token we’re building), strings, and other special characters.

Now the first section should make more sense. In the two string-handling states we consume characters immediately until we exit the string.

You’ll note I make heavy use of the continue statement. There are purists who dislike any kind of “jump” in the code. A more common dislike along these lines is for multiple return statements in a function. The purist approach says there can be only one. I am not a purist, and I think multiple returns are more readable. Likewise the continue and break statements. Love them.

§

Now that we have a nice list of InputToken we can pass them to a recursive descent parser. As noted, we only need three functions, one for each BNF definition: {definition}, {attribute}, or {content}.

The first one, dl_definition, parses a {definition}, and it’s the first one called, because a {definition} is always the root object of the DL tree structure.

All three functions take a list of tokens. That list is consumed as the parsing progresses. Note the call to dl_content; it’s where the recursion begins.

Speaking of which, here’s that function:

Which just leaves dl_attribute:

And that’s all there is to it. Note that the dl_content and dl_attribute functions also take a define_object argument.

The output is the root dlDefinition object, and it contains the nested content of more dlDefinition objects. Each object has its attributes and children. These are defined:

That’s all there is to the code. Using it is as simple as:

The define_obj is the root {definition} object. QED!

§ §

Any questions?

To take this further I’ll need to define DDL precisely enough for the next stage, converting the object tree to a data definition that can be applied to some input stream of bytes.

I would like to see this mostly idle dream finally completed, if for no other reason than that it’s been in the back of my mind a very long time. I get distracted easily these days, and just as quickly bored, so we’ll see how that goes.

Ø