32leaves.net

State machine compiler

As mentioned in one my previous posts, next semester I’m going to participate in a project where we’re supposed to build a new interface to existing roboting hardware. To describe the protocol that is spoken between the computer and that hardware interface, I wanted to use some sort of DFA. I also wanted avoid having to implement that DFA in the different programming languages involved in the project. Especially since such implementations tend to diverge over time.
So I sat down and wrote something I call the state machine compiler. It allows the specification of a so called predicate deterministic finite automaton. Such a PDFA can be compiled to C or Java code – or to whichever language one writes a backend for. I won’t go into detail here, as I’ve written a manual which explains everything in detail.
You can grab the source code from subversion (username: guest, password: guest). As usual it’s published under CC-BY-SA. Be aware that this is considered work in progress, so the generated code may still be far from being optimal.

Generating syntax diagrams from Scala parser combinators

Scala parser combinators are a powerful concept which allow you to write parsers with the standard Scala distribution. They’re implemented as an internal DSL which makes them feel naturally in the language. As mentioned before I’m currently writing some sort of a state machine compiler. As I plan to write some documentation for that software (which actually is kind of rare :-P) I need some way to describe the syntax. Besides EBNF, syntax diagrams are a neat way to do that. The external DSL which is used to describe the state machines is directly written using the parser combinator, so I had figure out a way to generate syntax diagrams as well as EBNF out of them.
My first approach was to pattern match the resulting Parser structure. But unfortunately the combinators themselves are mostly modeled as a function, thus do not appear in the resulting object graph. So I decided to write a Scala compiler plugin and run thru the AST. Basically all this software does is to transform trees from the AST to some intermediate expression structure to a graphing tree one. This approach suffers some limitations and I made some assumptions as well:

  • The name of the class which contains the production rules must equal the filename without “.scala”
  • Production rules must not be named: “stringWrapper”, “literal”, “regex”, “Predef”, “r” or “accept”
  • def production rules must not have parameters, otherwise they’re not considered to be production rules
  • production rules defined via val will appear twice (this is most likely a bug)

All in all this implementation works in my case, but might not work for others. This more of a quick hack than carefully engineered software, but it proofs the concept and gets the job done.

With the ability to draw syntax diagrams and having the expression tree structure at hand (which can be seen as an AST for EBNF) writing an EBNF parser (which is semi ISO/IEC 14977 : 1996(E) compatible) and feeding the diagram generator with the result was a snap.
So let’s consider the following example (which actually is the EBNF parser I wrote):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def start: Parser[List[ProductionRule]] = syntax_rule*
def syntax_rule = meta_identifier ~ '=' ~ definitions_list ~ ';' ^^ {
  case name ~ _ ~ expr ~ _ => ProductionRule(name, expr)
}
def meta_identifier = """[a-zA-Z0-9]+"""r
def definitions_list:Parser[Expression] = (single_definition ~ (('|' ~ single_definition)*)) ^^ {
  case t ~ o => OrExpression(t :: o.map(_ match { case _ ~ x => x }))
}
def single_definition = (primary ~ (((","?) ~ primary)*)) ^^ {
  case t ~ o => SeqExpression(t :: o.map(_ match { case _ ~ x => x }))
}
def primary: Parser[Expression] = optional_sequence | repeated_sequence | grouped_sequence | terminal_string | meta_identifier ^^ {
  case s => RuleRefExpression(s)
}
def optional_sequence = "[" ~ definitions_list ~ "]" ^^ {
  case _ ~ os ~ _ => OptionExpression(os)
}
def repeated_sequence = "{" ~ definitions_list ~ "}" ^^ {
  case _ ~ rs ~ _ => ZeroToManyExpression(rs)
}
def grouped_sequence = "(" ~ definitions_list ~ ")" ^^ {
  case _ ~ gs ~ _ => gs
}
def terminal_string = (""""[^"\\\r\n]*(?:\\.[^"\\\r\n]*)*" """r) ^^ {
  case s => LiteralExpression(s)
}

The corresponding EBNF expression generated by this software is:

1
2
3
4
5
6
7
8
9
10
start = { syntax_rule };
syntax_rule = ( '[a-zA-Z0-9]+' '=' ( single_definition { ( '|' single_definition ) } ) ';' );
meta_identifier = '[a-zA-Z0-9]+';
definitions_list = ( ( primary { ( [ ',' ] primary ) } ) { ( '|' single_definition ) } );
single_definition = ( ( optional_sequence | repeated_sequence | grouped_sequence | terminal_string | meta_identifier ) { ( [ ',' ] primary ) } );
primary = ( ( '[' definitions_list ']' ) | ( '{' definitions_list '}' ) | ( '(' definitions_list ')' ) | '"[^"\\\r\n]*(?:\\.[^"\\\r\n]*)*" ' | '[a-zA-Z0-9]+' );
optional_sequence = ( '[' ( single_definition { ( '|' single_definition ) } ) ']' );
repeated_sequence = ( '{' ( single_definition { ( '|' single_definition ) } ) '}' );
grouped_sequence = ( '(' ( single_definition { ( '|' single_definition ) } ) ')' );
terminal_string = '"[^"\\\r\n]*(?:\\.[^"\\\r\n]*)*" ';

And of course the syntax diagrams we wanted:

So far the syntax diagram generator understands two options:

  • -P:virtual:rule01,...,ruleN: declares rule01,…,ruleN to be virtual rules which causes them to be resolved wherever they’re referenced. Be aware that recursive virtual rules are only resolved to one level
  • -P:depth:N: resolve rule references until a depth of N (recursive rules are only resolved for one level)
If you’re interested in the code you can grab it from this SVN repository (username: guest, password: guest). You’ll need Scala as well as Batik to run it.
Creative Commons License
SyntaxDiagramGenerator is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License

Visualizing Sorting Algorithms – my shot

These days I have to write some sort of reference card for basic sorting algorithms. Of course I wanted some sort of visualization of those algorithms on that card. The coolest sorting algorithm visualization I’ve seen so far has been created by Aldo Cortesi. He used Cairo to draw his stuff (according to his post learning Cairo was the whole point of this excercise).
Personally I still found those diagrams pretty hard to read if you really wanted to follow the algorithm. And of course I wanted to do something with Cairo, too. So I decided to rewrite the whole thing in C. My version shows distinct sections for each loop iteration (as most of those algorithms can be followed by thinking in that iterative loop way). In the diagrams below each number denotes the loop nesting level while B stands for being and E for end.
The source can be downloaded here and is under CC-BY-SA.

Controlling a robot arm using an ez430 Chronos

A few days ago the ez430 Chronos I ordered from Farnell was delivered. This particular piece of hardware is an evaluation platform for the MSP430 (or the MSP430 as a CC430F6137 SoC to be more precise) which comes as a sports watch. It’s got some pretty neat features such as a temperature sensor, accelerometers on all three axis (which is why I’m using it here) and an RF transceiver built in. The first thing I did to it was to enable the watch to display the current time binary encoded.
After getting this to work (which was not that hard at all) I moved on to trying to get some data using the RF link. In the ez430 Chronos Wiki someone posted a Python program which polls the RF hub for accelerometer data. Having a Mac and not wanting to spend hours on getting pyserial to work, I wrote my own version in Ruby.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
require 'rubygems'

# on my machine a simple require does not work for this library
Kernel.require 'serialport'


SERIAL = SerialPort.new ARGV[0], 115200
SERIAL.read_timeout = 1000
def serial(data); data.each {|c| SERIAL.putc(c) }; SERIAL.flush end

# start access point
serial([0xFF, 0x07, 0x03])

while(true)
  # request the data
  serial([0xFF, 0x08, 0x07, 0x00, 0x00, 0x00, 0x00])

  accel = SERIAL.read(7)
  unless accel.nil?
    accel = accel.scan(/./).map {|c| c[0] }

    if accel[3] == 1
      puts accel[4..6].join(" ")
      STDOUT.flush
    end
  end
end

SERIAL.close

That’s pretty nice, but I wanted some real time graphs of the data, so a half an hour later I got a short Processing sketch running which does exactly that.

Next semester I’ll participate in a project in which we’ll built a new hardware interface to some pretty old robot arm hardware (it states “Made in West Germany”, that’s quite some time ago). In order to do that we need some sort of protocol to communicate with the new hardware interface. In preparation for that project I wrote a simulator for the robot (actually that’s supposed to be a part of the project, but I simply couldn’t resist) which uses an early draft of that particular protocol. Just to have that mentioned, the protocol itself is described as a state machine in a DSL which can be compiled to virtually any programming language. I’ll probably write a post about that nice piece of Scala code at some later time.
So with a working robot arm simulator, a watch which has accelerometers built in and is capable of wireless communication what else could I’ve done than to combine those two. That said I got to work and enhanced the script above to communicate with the simulator. About an hour later I got the first movements controlled by the accelerometer data of the watch. You might have seen the video already, if not go and watch it :-)
Update: We had some spare time to spent and did some really basic proof of concept with the real hardware. Here we go:

Fork me on GitHub