Defining Automatas with XML

We recently started classes at my lame University and one of the courses I'm taking this semester is Formal Languages, Compilers and Automatas. We had a heavy start with some (badly explained) Automata examples and (trivial) applications. As usual, our professors output a lot more homework than information, so I quickly had a couple of problems to do for homework. They all asked to design an automata that would accept some particular language and then do the diagram, regular rules and the function matrix. Of course, I was only interested in designing stuff... for everything else there were deterministic algorithms to produce those parts, so I inmediatly thought about programming that out.

First thing I needed was a way to describe the Automatas I designed. While at classes, I thought of using my own description language, similar to a switch command on C, yet when I came back home I remembered two main principles of modern programming: build over previous work and use XML for data definition. I then Googled to see if there was  some standard (or standard candidate) definition of an XML Document for defining Automatas. And there it was :) I found the Vaucanson Project which includes the FSMXML subproject to define automatas and regular expressions internally. The FSMXML project includes a documentation file that can give you a good idea of what you can do with the specification, yet I found some errors on it and although I already submitted required changes to the mailing list, I haven't got a reply  :'( (If you are interested in using the project contact me to receive the changes needed on the documentation).

After getting the grips of the FSMXML project (it let me do a lot more than what I needed), I needed a way to take that XML file and produce all the different renderizations I needed (a diagram, a matrix and a list). I inmediatly thought it was a good time to test out a language specification I once read about: the XSLT. I learned about XSLT while looking for something else (an Xpath library on C++) on the Apache Project when I came accross Xalan. So I got an XSLT book from my Safari (I already had Xalan installed on my Sabayon system) and I started trying out examples and building the first of my three transformations: the diagram renderer. I used XSLT to convert the original automata to a Graphviz DOT file (which took me a lot of time because I had to learn all three DOT, XSLT and Xpath languages at once) and I finally managed to get an alpha verson working.

I then went on to work on the function matrix transformations for which I wanted to implement an stylesheet that would create some LaTeX code to create the matrix, but I stumbled accross a big problem: there were some extremely useful XPath functions on my book that just wouldn't work on my Xalan. I browsed the project specificatiosn and learned that Xalan is still stuck at XSLT 1.0 and XPath 1.0, but the functions I needed were defined at XPath 2.0. I then checked on the introductory examples of my book for other alternatives to Xalan, and read about Saxon, confirmed that it implemented XPath 2.0 and installed the package on my Sabayon system. After understanding this new tool and getting things working again, I noticed I still didn't have support for that particular function I needed. I then checked Sabayon's version of the project: it was at 6.5.5, and by checking the project's home page I learned that the 6.5.5 was the last stable version based on XPath 1.0. So next I downloaded the files directly from the Saxon web site (currently at 9.2) and things went out smoothly this time.

I finally created my third transformation, the regular rules renderer, which was pretty straighforward given the fact that I had been fighting with XSLT for more than 6 hours. I aslo implemented that one on LaTeX so I could glue everyting up and create a single LaTeX document containing all requested representations of the automata.

The results are here: FSMXML2Graphviz, FSMXML2Matrix and FSMXML2RegularRules. They are highly unpolished, so I may be updating those to support all kinds of stuff on the  FSMXML specification.