How (not) to write a parser

One of my favorite subjects during college days was Parsing and compiler construction (remember The dragon book?). Ever since the first time I tried lex/yacc (flex/bison) it was a mysterious piece of software that I wanted to master using! 

Zoom forward 10 years, a lot has changed in the field: LR(1) is passé, GLR and LL(1) are in-vogue (thanks to tools like ANTLR) 

When I thought about venturing into writing a parser for the YANG modelling language (RFC 6020), I first did some study+survey, and I formed some new opinions about parsing: 

- Don't roll out a RDP in desperation  

- No separate tokenization phase (scanner-less) 

- Not LR(1) - too limited 

- Not ANTLR! (though its a fantastic tool - it leans a lot towards Java!) 

- Not Bison GLR! (no proper documentation!) 

- Use PEG (yet another learning opportunity :-)) 

- Not C! (more about it later) 

PEG is cool, and with a love for regex PEG attracted me way too much :-) I tried many PEG based parser generators. 

To start with I picked up Waxeye , though it has a choice of many targets, the C port is not optimal (author himself told, that more work's needed). 

Then I tried peg/leg, though its very similar to lex/yacc in usage, I was finding it hard to debug/modify the grammar. Part of the problem could have also been the YANG ABNF grammar (as defined in the RFC). There are no reserved words in YANG. I tried peg/leg much more than Waxeye, but eventually I gave up once I realized that I was getting nowhere! So, C is gone - as I had only 2 options that had a C target!

Lua/LPeg: Though I'm familiar with Lua, this was my first tryst with LPeg. I had heard a lot of praise for Roberto's work, and I got to know why, quite soon. Within a few hours I was able to create a matcher (deliberately avoiding the word parser here) that could recognize 80% of the YANG files at my disposal! (had to tweak the matcher for the remaining 20%). This time, I chose a different approach, instead of using the YANG ABNF grammar, I created some simple relaxed rules. 

Here is a brief description of the approach taken.

YANG statements can be either of the form:

1.   identifier [value];

Or:

2.   identifier [value] {

            One or more of 1. (depending on identifier)

  }

Note that value is optional. Since there are no reserved words, it leads to a simple matcher (~30lines!). Even though there are no reserved words, we have some keywords, and based on that we should be able to say whether the nesting is right or wrong – I call this as the validation phase. And, that too, can be simplified to triviality, if we keep the AST as a simple Lua array (table).

For e.g: A leaf can be under a container, but not vice-versa:

Valid:

container C1{

  leaf l1 {

     type string;

  }

}

Invalid:

 leaf l1 {

  container C1 {

  }

}

I keep a list of allowed-children for each type of node. Additional checks are performed with custom functions per node-type. And, since these children are arranged as arrays – we can also ensure order.

That’s it! :-) - take a look at: https://github.com/aniruddha-a/lyang

Comments/feedback welcome.

Oh! But how would I know without 'running' it, if its ok?

Have you come across your teammates, checking in scripts without running it, with syntax errors, malformed XML documents, broken Makefiles .... well, there is some hope, you could help (by sharing this link! :-) )

Mostly, if its code in a compiled language (like C), developers at least compile the code (might not test!) before checking into version control. But, in case of XML documents, scripts etc, the code gets checked in, and it will not error out until some test case is completely run, or in the nightly regressions!

Its not really difficult to do some basic validation of scripts, Makefiles, or even XML documents before a check-in. Most languages/tools have an option to do basic checks - syntax checks, dry run (without actually executing the commands), bytecode generation etc. Here are some, which I often use:

Make

make -n

Does a dry-run, shows which targets would get built on an actual run.

Perl

perl -c

Does a compilation and says if syntax is OK or not (there are caveats with BEGIN blocks, but at least there is something!)

Python

pycompile

This is good, there is a separate utility to do the compilation! (just run pycompile on your scripts once before you proceed)

bash

bash -n

Again, syntax checks without actually executing anything.

XML

xmllint

The name says it all! Even though there are plenty of options, you could just run once [without even options] on your XML docs to see if its well-formed.

Lua

luac

Lua bytecode compiler, like pycompile. Generates luac.out which you can delete :-)

Common config that can be utilized by multiple languages

Often, I would want to separate out some config/initial data out of a program, and keep it in a way that is accessible to different parts of the system. If all parts of the system are in the same language, then the config can be very simple - just the function invocation with values:

For e.g. in shell:

   # Format:
   # Employee name role department
   Employee "Bheem"  "Fighter"  "Security"
   Employee "Chutki" "Hiring"   "HR"

Then, the invoker would just have to define the function Employee and source this file!

So far, so good if all parts were in shell. But, what if I want to use this config in some C code, and in Lua scripts etc. ?

(Don't think file-read/parse/split/tokenize .. No no! yuck!)

Can we define (somehow), a common format which is usable by different environments (languages), with minimal or no effort!? Observe the calling conventions:

C function call looks like:

   Employee (arg1, arg2 /* ... */)

Shell (is the simplest):

     Employee "arg1" "arg2" # ...

Lua:

   Employee (arg1, arg2) -- ...

But, there is a special notation in Lua, when the argument is a string or a hash table - we can get rid of the parentheses! like:

   Employee "arg1"

OK, but what if we have more than 1 argument ? Now, we need to get a bit deeper into function-chaining:

    function Employee (name)
        return function (role)
            return function (department)
               add_to_db(name, role, department)
            end
        end
    end    

Without going into much details about anonymous functions, Lexical scoping, upvalues etc - the function returns a function, which returns yet another function - that means, when you invoke

    Employee "Bheem"  "Fighter"  "Security"

The first function reads the first value, and returns its inner function, which reads the second value and that in turn returns another function which finally does some work (and can access all the 3 values - this is what we want)! Cool, ain't it? :-)

Wait, we solved the problem for shell and Lua, what about C code ?

In case of C code, we can always use the well-documented Lua C APIs to read Lua config! :)
(after all, Lua evolved from data-description language)

If you think, all this is too much work - think again, know the DRY principle.

Recognize, and transform text

Many a times, I see some text, which is not in any known format. But, it looks vaguely familiar, or simple enough to transform. The reason I would want to transform, is of course to work with it, to load it into my scripting environment, to analyze, consume or apply some complex programmatic logic to it.

Here, I give some examples, and show the conversions. This could help in recognizing
raw text,  and transforming them to their closest [known] cousins.

Case 1

Lets start with something simple. If you see a file something like this:

Alice:
sal=20000
age=23 
role=engineer

Bob:
sal=21000
age=28           
role=engineer

and you want to load this into your preferred programming environment (like a
Python dict, Lua table, or a Perl hash) to work with it. As it stands, it is not in a format that is directly usable!, but if we can make a small change in the data, say change the line containing colon in the end, to [line].

[Alice]
sal=20000
age=23 
role=engineer
  
[Bob]   
sal=21000
age=28           
role=engineer

Now, this is a valid .ini file format (popular in the Windows world). And, there are libraries
for most languages to load and work with INI files!

What you need, is a little Perl, or sed regex to convert from the former to the latter!. And
dont think about Jamie's popular quote and be afraid (for such simple cases, regex is a
good fit, but make sure you really understand regexes to weild one when needed)

Case 2

If you have seen some router configs (like JUNOS config), or some BibTeX entries, then the following
will be faimilar:

interface {
    eth0 {
      ip4  10.1.1.2;
      bia  aa:11:22:11:00:11;
    }
}

Again, this may not be directly loadable into your environment, but see this again, doesnt it look
close to JSON ?, all you need to do is to ensure that the keys and values are quoted correctly

As JSON:

{
 "interface" : {
    "eth0" : {
      "ip4" : "10.1.1.2",
      "bia" : "aa:11:22:11:00:11"
    }
 }
}

Or, Lua table:

interface = {
    eth0 = {
      ip4 = '10.1.1.2',
      bia = 'aa:11:22:11:00:11'
    }
}

again, both of these can be achieved with minimal changes.

Case 3

This might look very similar to Case 1, but observe the nesting and a richer data set!

[Alice]
sal=20000
age=23
role=[current=engineer;previous=DevOps,TAC]

[Bob]  
sal=21000
age=28          
role=[current=engineer;previous=]

Now, converting this to .ini doesn't seem to fit!, can we convert it to something else? say, I do this:

Alice:
  sal: 20000
  age: 23
  role:
        current: engineer
        previous:
                 - DevOps
                 - TAC

Bob:
  sal: 21000
  age: 28
  role:
        current: engineer
        previous:

Aha, now this is valid YAML! YAML, like JSON, is also fat-free-XML! and you have libraries
for all languages to load and work with YAML.

Case 4

We all know CSV, if you have seen simple spread-sheet data (think MS Excel), that's valid CSV. Also, spread-sheet editors give you an option to save it as plain CSV.

But what if the data were like this:

 a:b:c:"d"
or
 a|b|"c"|d

isn't it simple to change the delimiter to comma (',')? so that, you can work with CSV libraries.
Bonus - if you have to send the data to a suit, just attach it and they can open in a spreadsheet-editor! you know, suits frown on plain text attachments! :-/

Note: the regex should be careful enough to handle quoting! (that applies to all cases listed above)

To summarize, you don't need complicated parser to load text into your favorite language, to analyze it, or to apply programmatic transformations to it. All you need, is to recognize the format, and check which is the closest known format to which you can convert it to, so that you can conveniently work with it. The following table might make it easier to remember:

       

Text	Easily converted to
Delimited (line oriented)	CSV
Grouped, and simple key-value	INI
Indented, multi level, with lists	YAML
Brace nested, and key-value	JSON/Py-dict/Lua-table

Using API docs as a test aid

I wrote about my custom documentation using Lua embedded in my C source. With the complete description of the function - its arguments [and their type], return type etc, can we do more with it?
I wanted some test stubs for the Lua APIs (that I am defining from my C back-end) and all I had to do, was re-define the mydoc function which will consume the same data, but instead of generating documentation, generate some Lua code to test the APIs.
i.e, if I have a function that takes a number and returns a string (on success) and nil on failure, I generate:

function Stub.test (n)
  assert(type(n) == 'number', 'n should be a number)
  if g_nil_path then return nil end
  return 'rand-str'
end 

With this, I can see and get a feel of the Lua APIs that my C functions are exposing, also I can invoke the user scripts just to check the argument types for correctness, and I can exercise the success path as well as the failure path by setting the global g_nil_path. And of course for more randomness, I use 

math.random

 when I return a number and

string.rep(string.char(math.random(65,90)), math.random(1,10)) 

when returning strings.

A simple documentation generator

No, I don't want to create yet-another documentation-generator like Doxygen, there are lots of them, each with their specific purpose, and strengths. But mostly (at least AFAIK), all of them are intended to be embedded in the host language, and to document the APIs of the same language. I.e, if one is writing some C code, and wants to document the APIs of the same C code - all is well!. But I wanted something different (ah! as usual!).
I am embedding Lua into our application, and I am writing libraries to be used by Lua, in C. And, I want to document those APIs [of Lua], which I am building, by adding the usual doxygen-like comments in the source files.
I have 2 choices at this point, either I define some comment format/tags (like @something \something-else) and then extract them out of the source, then parse and generate the docs), Or ... use something which is well suited for data-description. Aha!, I'm anyway learning/using Lua, which has its roots in data-description, why not embed Lua code into my C comments?
Of course!
All I need is, a brief description of what the function does, its arguments and return types, at the
minimum, I can capture it, in Lua, like:

   mydoc {

       name = "str_len", -- function name

       args =  { string = 's' }, -- input arg and its type

       ret = { len = 'i' }, -- return val and its type

       brief = "return the length of input string",

   }

And a way to quickly fetch it from the source - make the comment begin with '*!' (or something similar)

/*

 *!   mydoc {

 *!       name = "str_len", -- function name

 *!       args =  { string = 's' }, -- input arg and its type

 *!       ret = { len = 'i' }, -- return val and its type

 *!       brief = "return the length of input string",

 *!   }

 */

And how to convert this to doc ?  simple!, just grep out these comments from the C source, and then define the mydoc function in Lua:

  function mydoc (t) -- excluding err handling and formatting

    if t.name then

        print (libname .. ":" .. t.name , "\n") -- libname also from source

    end

    if t.brief then

        print (" -- ", t.brief, "\n")

    end

    if t.args then

        print ("\tTakes " .. tablelength(t.args)  .. " arguments")

        describeargs(t.args) -- writes the values and their types

    else

        print "\tTakes no arguments\n"

    end

    if t.ret then

        print ("\tReturns " .. tablelength(t.ret)  .. " values")

        describeargs(t.ret)

    end

  end

Run all of this (the mydoc function, and the extracted blocks) together in Lua, and there you go! Now, generating text doc was so easy, how difficult is it to generate Markdown?  I added both, as options (to the bash wrapper, which extracts the comments and runs Lua on it) :-)