Tuesday, May 13, 2014

A simple LL1 expression parser written in C#

If you just want the code and want to skip the details go to the bottom of the page.

The Problem

Recently I had this need to translate some simple SQL Server formulas to another language. The last time I had built a parser was more than 20 years ago in the pre-internet era. From what I can recall, that time I used C++ and I probably relied heavily on macro expansion to simplify the syntaxis. This time I needed to use C# since I was going to integrate the Parser as a function in SQL Server and also because C# is my favorite language to develop nowadays, but it doesn't have macro expansion which was going to make writing the grammar definition a little tortuous.

The LL1 grammar I needed to implement looks a little bit like this:

So I needed to write this grammar in C#. The logic can be written using basic functions you find in every language like ifs and the operators && and ||. But I needed to write it in a way that still resembled the grammar above for easier debugging and further enhancement. Therein laid the problem, how to write elegant C# code that behaves and looks like a grammar and do it in just a few hours.

There are tools out there that can take a grammar like that and generate the code for you. I gave a couple a quick try but realized the learning curve would take me longer than I could afford for this project so I looked for a simpler alternative using just C#.

The Solution

My solution is based on delegates. Delegates are values that represent functions which then you can call. The neat thing is that they can be stored in variables and passed as parameters. This is the declaration for my delegates:

delegate bool rule();
delegate bool ruleL(int L);

They both return a boolean and one takes an integer. So I declare a variable for each one of my rules:

ruleL expr, expr2;
rule wexpr, mexpr, whexp, whexp2, id2, list, list2;

The second element of the solution is using Lambda Expressions which is a very compact way of defining functions with a truly minimal syntax. There is no type declaration for the function or the parameters. no brakets, not even a return statement. The compiler inferrs all that from context. The syntax goes like this:

expr2   = (L) => L < 4;

Now expr2 is a function that returns true when the parameter is less than 4. With Lambda Expressions I can define the rule expr2 something like this (compare with grammar above):

expr2  = (L) => ( L < 4 && Token == "+"  && expr(4) && expr2(L)    )
       || ( L < 4 && Token == "-"   && expr(4) && expr2(L)    )
       || ( L < 5 && Token == "*" ...                                  
                                                                        ...        );
Looks promising, this syntax is functional in C# and is close enough to the grammar definition. But, it is missing the part that detects and handles errors in the input. For that I created the P function that wraps around each rule line. P stands for parser but I use the short name to keep the syntax as uncluttered as possible. Here is how it is used:

expr2  = (L) => P(() =>  L < 4 && Token == "+"  && expr(4) && expr2(L)    )
       || P(() =>  L < 4 && Token == "-"   && expr(4) && expr2(L)    )
       || P(() =>  L < 5 && Token == "*" ...                                     
                                                                        ...        );

A little bit more cluttered but not too bad. 
Here is how my grammar looks in C# now:

Notice how the P function is passed a lambda expression as a parameter. 
Here is my P function:

It is pretty simple really. The variable Position holds the current position in the input string. If the rule R fails and the position changed it means some Tokens were consumed which means the parser failed and should stop.

The Lexer

A simple parser deserves a simple lexer. The lexer is the part of the code in charge of reading the string and extracting the tokens. Writing one from scratch is tedious and laborious. The code needs to skip spaces and comments, recognize identifiers, numbers, strings and symbols. Fortunately .NET has a powerful Regex class that makes it much easier.

In the C# grammar above the lexer are the calls to the functions C() for matching symbols and W() for matching whole words. But the core of the lexer is the R function for matching any Regex, here is the code:

Again very simple If the pattern matches then the token is saved in the variable Token and the Position is advanced.  Functions C and W just call R.

The only part missing is the skipping of spaces and comments, again using Regex:


That's it, that's all. All put together in one class called Parser:

Notice the definitions for ID, NUMBER, EOS & NIL.

To test it create a Form with 2 textboxes and a button and call it like this:

Next post how to add semantics...

Thursday, March 8, 2012

Face Detection & Tracking using OpenCV

Download source code and executable: FaceDetect

This is implemented using OpenCV v1.
It's actually a simple combination of two of the samples that come with the library:
 -Face Detect
 -Feature Tracking.

Since Face Detection takes much more time & processing than Feature Tracking, it tracks the face on each frame but it only tries to detect a face every 100 milliseconds and then only in the currently tracked area. Red frame indicates an actual face detected, blue frame indicates just feature tracking so rapid flickering between red/blue is a good sign, solid blue not so much.

When it cannot detect a face it keeps tracking the dots until they degrade too much or too much time (1.5 seconds) elapses since last face was detected in which case it tries to find a new face in the whole picture.

Little kids love to play with this program as it is. They compete trying to get their face captured by the program and trying to take the capture from whomever has it.

It can be used as input to play games when coupled with GlovePie. It sends detection results to the IP indicated as the first parameter into port 54934 (hardcoded).

I use this as an improvement on my virtual gaming experience (see old video below) I replaced one wiimote & the IR cap with this program as the virtual game controller. It's a poor man's Kinect.

This is the old video where I was using two wiimotes to play N.O.L.F.

Tuesday, March 6, 2012

Helicopter Auto Pilot - Helicopter Control

Back to Helicopter Auto Pilot - Introduction

Download source code & runtimes: Heli Control

Helicopter Control (d-L-i)
For controlling the helicopter I developed a program in C# called IR_HeliAutoPilot.exe you can find it in folder HeliComm.

(WORK IN PROGRESS more to come later)

Monday, March 5, 2012

Helicopter Auto Pilot - Infrared Emitter

Back to Helicopter Auto Pilot - Introduction
Download source code & runtimes: Heli Control

Infrared Emitter (L-i-h)
In the original video I posted I was using the USB IR Toy together with a simple circuit that amplifies the IR signal with some extra IR Leds. In version 1 of the USB IR Toy couldn't do this so I had to reprogram the IR Toy to send the signal through the TX serial pin which had a header on the board where you could connect the amplifier circuit. This was a rather complicated development that required using the MPLAB IDE and C compiler to reprogram the PIC18F2550 at the heart of the IR Toy. Unfortunately for me during testing that part of the circuit was fried.

Based on a suggestion posted on the original video I decided to use instead the laptop's headphone jack to send the signal to a homemade IR emitter.

I must warn you, my knowledge of electronics is pretty limited so I'm sure this circuit can be improved upon and I'm open to suggestions. This circuit was designed with the assistance of the nl5 circuit simulator by Alexei Smirnov: http://nl5.sidelinesoft.com/.

The circuit is simple enough:
  • T3 & T4 form a classical BJT astable multivibrator (oscillator) at ~ 32KHz. 
  • T1 & T2 perform an AND operation with the incoming signal (Base).
  • D1 & D2 serve to create a constant current driver for the IR Leds (D3-5).
To connect this circuit to the audio jack connect the Left wire to Base, Right to ground and ignore the ground wire.

PS. With a small modification this circuit also becomes compatible with the  i-Helicopter app for Androids and iPhone. The app is free and it uses the same protocol as my FalconX helicopter .

Helicopter Auto Pilot - Decoding Helicopter Protocols

Back to 
Helicopter Auto Pilot - Introduction
Download source code & runtimes: Heli Control

Decoding Helicopter Protocols
For deciphering and decoding the specific protocols for each helicopter I used a tool called the USB IR Toy from Dangerous Prototypes: http://dangerousprototypes.com/docs/USB_Infrared_Toy version 1. It allows you to receive and send infrared signals. Although the emitter in version 1 was not strong enough to cover a big area.

I also used my program IR_HeliAutoPilot.exe that communicates with the IR Toy and helps decode the signals. This program was written in C# using Visual Studio 2005 and it's in the folder HeliComm. The subfolder hcomm has some of the definitions (.hcomm files) and trials I've made for different models.

This video explains the process of discovering the protocol, if you have questions you can post them in the comments section here:

Scripting the protocol
Once you know the details of the protocol the helicopter uses it can be scripted into the program and saved as an .hcomm file. That entails entering the different pulse lengths in microseconds in the IR Protocol tab and scripting the variables in the Heli Protocol and Script tabs.

(WORK IN PROGRESS, will expand later)

Helicopter Auto Pilot - Camera Tracking (h-c-d-L)

Back to Helicopter Auto Pilot - Introduction
Download source code & runtimes: Heli Control

Camera Tracking (h-c-d-L)
For tracking the helicopter I'm using a Logitech HD 1080 webcam capable of 30 fps. After processing the images it slows down to approximately 27 fps.

For processing the image I adapted, in a very rudimentary fashion, a C++ program I found somewhere in the internet that can read the frames from the camera and processes them trying to find the brightest spot in the picture. For that reason the best situation to use this is indoors and at night when no sunlight can penetrate the room. You don't need to have the lights off but you must avoid having any strong light source like lamps, leds, screens or some reflective surfaces.

The program is in the folder called HeliFind. It was compiled using C++ Express 2010.
The program requires OpenCV 2.2.

Same as the wiimote script this program sends the tracking information to a specific ip and port.
The current version has the IP and port hardcoded in Video.CPP:

RecvAddr.sin_port = htons(53525);
RecvAddr.sin_addr.s_addr = inet_addr("");

If someone is interested I can change this so it's a parameter when you run the program. Otherwise you can change it yourself.

After you run the program an empty window opens, click on Help/About and it starts to track the brightest point in the image. For better performance turn off all automatic processing from the camera like True Light, True Sound, Auto White Balance, Auto Focus, and reduce exposure and brightness to a minimum. Your image should be almost black except for the LED in the helicopter.

Back to Helicopter Auto Pilot - Introduction

Helicopter Auto Pilot - Wiimote Communication (w-d)

Back to Helicopter Auto Pilot - Introduction
Download source code & runtimes: Heli Control

Wiimote communication (w-d)
To connect the wiimote with the desktop (w-d) I use a Bluetooth connection and the program GlovePie from Carl Kenner: https://sites.google.com/site/carlkenner/glovepie
Glove Pie is an easy to use program (I love that it doesn't require installation) that can read the wiimote and send information to other programs. It comes with it's own special scripting language.

Download my script called HeliWii.PIE.

In particular I'm using it to send commands from the wiimote to the laptop program. The first two lines of the script indicate the IP and port to send the information to:

OSC.port = 53525
OSC.ip = ""

Change them to suit your environment.

Wiimote  controls:
  • Home: Toggle IR transmission on/off
  • B: Go from No Power mode to Manual Power mode. (led 1 on)
  • Nunchuk Pitch: Controls power in Manual Power mode.
  • Nunchuk Joystick: Turn Left/Right, go Forward/Backward.
  • C & Z together (nunchuk) : 
    • First time: Auto Power! Go from Manual Power to Auto Power mode (4 leds on)
    • Second time: Emergency stop! go from Auto Power to No Power mode (leds 1 & 4 on).
  • minus (-)/plus (+): Adjust drift left/right.
  • (1)/(2): Adjust elevation set point up/down when in Auto Power mode.

Helicopter Auto Pilot - Introduction

Download source code & runtimes: Heli Control

You may have seen my video on how to control a Helicopter using the computer:

Since many people have shown interest in this little project of mine I wanted to share more in depth information in this blog for those who want to replicate and/or expand on this.

Let's start with a schematic of the solution:

Notice I have two control loops, a manual loop h-w-d-L-i-h:
  • (h)elicopter
  • Human with (w)iimote
  • (d)esktop computer
  • (L)aptop computer
  • (i)nfrared emitter
  • (h)elicopter
 and an automated loop h-c-d-L-i-h:
  • (h)elicopter
  • Web (c)am
  • (d)esktop computer
  • (L)aptop computer
  • (i)nfrared emitter
  • (h)elicopter
Notice I use two computers because my laptop is not terribly powerful and also it's easier to place the web cam and infrared emitter in different places. You can just as well use one computer.

I'll be adding new sections and expanding existing ones according to your questions and comments.

Friday, February 11, 2011

VMWare ESXi back to life

So after my computer (which I use as a VMware ESXi virtualization host) resuscitated from the dead and started booting up I got the following messages:

Failed to load tpm
Failed to load lvmdriver

TPM apparently stand for Trusted Platform Module and since my new motherboard coincidentally had a header for a tpm module for a moment I considered buying one. Turned out it wasn't necessary because the tpm is not important for ESXi.

But lvmdriver is; lvmdriver means that it could not find a compatible network card and this stops completely the boot up process. ESX and ESXi are targeted for high end servers and so VMware has not added support for desktop NICs.

There are two solutions to this problem, the easiest one and probably the best one is to get a compatible Intel card. Apparently Intel makes the best cards and most are fully compatible with ESXi. Mine is on the way.

The long way home
The other solution is to use a third party driver for your card. I tried this solution first.
My new motherboard came with an onboard Realtek 8111C NIC. So now I had to find a custom driver for it and install it in my unbootable ESXi installation without destroying it in the process. Bear in mind that my Unix/Linux skills are not that great.

Google is your friend, with it you can find practically anything in the Internet and if there is something you don't understand then Wikipedia is your other friend. With those friends I found this forum http://www.vm-help.com/forum/ where they specialize in this sort of thing. Turns out that you can take a Linux driver compatible with your NIC make some changes to adapt it to ESXi, compile it, copy some files here and there and you're good to go. Easy.

Since I cannot do that I used some precompiled and prepackaged solutions posted in the same forum. It basically involved booting up the computer (with Puppy Linux from a pen drive in my case) and replacing a file called oem.tgz in one of the partitions.
The first time I tried it I got a Pink Screen of Death which was something new to me (different from the BSOD in this one you can still interact with a debugger).
So I just got a different oem.tgz (thank you geppi) and this time success!

vSphere Client
At least partial success: ESXi booted up and it worked OK but since there was a change in hardware the VMs would not start right away. For each VM,  ESXi needed me to answer a pending question: did you move or did you copy the VM?. Until I could answer that question the VMs would not start.

It had been a while since I had used the vSphere client and by then it was broken. Apparently an update in .NET made the previous version inoperative. I was getting this error message:

Error parsing the server "IP" "clients.xml" file

The solution was to download the version 4.0U1 of the vSphere client. For some reason getting a direct link to this new version is not possible. The way the VMware website is constructed it's very difficult to find the link. When you seem to be getting closer it keeps eluding you.

Finally I realized you had to login with your user and get a license key to go to the download pages and there you can find a link to the client. Why is a much required update hidden so deep into web bureaucracy is a mystery to me.

Changing the virtual NIC
Before starting the VMs, and following advice found in vm-help/forum, I replaced the Virtual Network Card in each of the Windows VMs from type Flexible to VMXNET3. Without this change Remote Desktop Connection to the VM would be completely unusable. Also I was experiencing great instability with NeoRouter (great tool BTW). vSphere client worked well though.

Unfortunately, even after those changes, RDC proved to be still very unstable (much better than before but still not good, specially when browsing the web) so that's why I eventually decided to go for solution one (see above).

UPDATE: Afterwards I disabled the UDP & TCP Checksum Offload (IPv4) options in the Advanced properties of the vmxnet3 Ethernet Adapter in the Windows VMs, this seemed to fix all the stability issues.

Upgrading to ESXi 4.1
Since I was doing all this tinkering with ESXi I decided to also upgrade from 4.0 to 4.1.

- First I downloaded the upgrade-from-ESXi4.0-to-4.1.0-0.0.260247-release.zip package.
- Then I downloaded and installed the latest version of vSphere Host Update Utility for ESXi 4.0.
 I clicked on the button marked Upgrade Host, boom! got this fine message:

Failed to read the upgrade package metadata: Could not find file 'metadata.xml'

Back to google, turns out the Update Utility doesn't work for this upgrade.
I had to download the vSphere CLI which is based on Perl. This opens a command prompt (in Windows).
According to the upgrade guide I have to issue the following commands:

vihostupdate --server <hostname or IP> -i -b "location of upgrade-from-ESXi4.0-to-4.1.0-0.0.260247-release.zip"

vihostupdate --server <hostname or IP> -i -b "location of upgrade-from-ESXi4.0-to-4.1.0-0.0.260247-release.zip" -B ESXi410-GA-esxupdate

Except that doesn't work either for two reasons, first the command prompt is not in the correct directory so first we need to go there:
cd bin
Second in Windows the commands need to have .pl appended:

vihostupdate.pl --server <hostname or IP> --username <username> --password <password> -i -b "location of upgrade-from-ESXi4.0-to-4.1.0-0.0.260247-release.zip"

vihostupdate.pl --server <hostname or IP> --username <username> --password <password> -i -b "location of upgrade-from-ESXi4.0-to-4.1.0-0.0.260247-release.zip" -B ESXi410-GA-esxupdate

After that reboot the ESXi host and install the new vSphere Client..

If you had the console activated in 4.0 upgrading to 4.1 will deactivate it. In 4.0 it used to be a hidden feature, in 4.1 it's called Tech Support Mode and you can activate it for local and remote connection through ssh. Fortunately it's very easy to turn it on.
Using the vSphere Client go to: Configuration  >Security Profile > Properties
click on Local Tech Support and/or Remote Tech Support,
click on Options, click on Start,
select Start and Stop with Host (Start Automatically probably works too).

One good news with the new motherboard is that it has support for VT-d which the older motherboard (or its BIOS) didn't have. So I decided to test it, sure enough in Configuration >  Advanced Settings where before I would get a:

 Warning: Host does not support passthrough configuration 

now it offered to configure some devices for VMDirectPath passthrough. I was this close to selecting every USB device for passthrough and clicking ok but this message gave me pause:

Warning: configuring host hardware without special virtualization features for virtual machine passthrough will make it unavailable for use except dedicating it to a single virtual machine. In particular, configuring a device needed for normal host boot or operation can make normal host boot impossible and may require significant effort to undo. See the online help for more information.

Long message, isn't it?  Even after reading that message I was still tempted to ignore it, but considering for a moment how difficult normal things are with vmware I decided to google it and sure enough there were horror stories of people that tried just that and ended up having to reinstall everything. I just couldn't afford it, maybe some other day.

Thinning disks

I wanted to convert some thick drives to thin drives for that I followed Kent's blog steps. This is the key step for me:

vmkfstools -i <source file> -d thin <target file>

It clones a virtual drive using the specified mode.

Moving things (disks) around

Something else I wanted to do is to make things more efficient in terms of speed and space, but mostly speed. I have a modest installation with 3 Windows VMs constantly on (though not necessarily constantly in use) and some other Windows and Linux (Ubuntu and Puppy Linux) VMs mostly for experimental use. The fact is whenever two of the VMs were doing some work performance suffers terribly. So I decided to move the disks around to test better configurations. I'll update as I get results.

In conclusion things are never easy with VMware but after much trial and error and googling a lot you eventually get there.

Thursday, February 10, 2011

First entry: Dealing with a dead computer

Dead Computer
So after a blackout last week I found my 18 month old  HP Pavilion m9650f  in a comatose state. The computer was in an infinite cycle of 4 seconds On - 4 seconds Off. All fans (power source, CPU, Graphic card), drives and LEDs seemed to work but inexplicably the computer would turn itself off after 4 seconds only to restart 4 seconds later. No Video signal. No beeping sounds.

So I started the typical procedure: open the computer case fumble with the graphic card, hard drives and any and all components. Clearing the BIOS CMOS memory, replacing the depleted CMOS battery (which was supposed to last 7 years). Nothing.

Is it the BIOS?
Only when removing the memory dimms did I notice a change. With fewer memory dimms the cycle was faster and with no memmory dimms I could hear some beeping which told me that the BIOS initial test was working and either was purposely turning the computer off or it was deffective.

So I removed a jumper (yellow arrow) on the board marked rom_recovery which is on a SPI programming header for the BIOS EEPROM memory. Partial success! This stopped the On/Off cycle. But nothing else happened.
So I suspected the BIOS was corrupted. I could download the BIOS firmware from the HP website but programming it in a non-bootable computer would require some specialized equipment that I don't have. Researching on the subject I found anything from expensive commercial equipment to DIY projects. The prospect seemed too daunting for me and I wasn't even sure it was the BIOS.

Or the capacitor?
During all that fumbling I had noticed that a capacitor (red arrow) had a little bulge but with my limited electronic knowledge I didn't think it was important. Out of frustration I finally googled the subject and it turns out it's been a well known cause of motherboard failure for years. My "Truckee" motherboard in particular (I had version 1.01, bad sign!) is well known to have all kind of issues, although, mine had been working flawlesly for 18 months.

Calling support
Replacing a capacitor in a motherboard is completely out of my depth so I finally decided to call HP support and have it repaired. After verifying that my one year warranty had expired and that I hadn't purchased the extended warranty (which I never, ever do) the support rep wanted me to buy a one-incident-phone-support contract for 50$  or a one-year-phone-support contract for 100$. At this point I was sure there was nothing that could solve this problem over the phone so I declined.

I asked if they had a service center in my city where I could drop off the computer to be picked up later but they don't offer that possibility. I was quoted and estimate of between 250$ to 350$ and they were going to send a box to ship the computer via UPS. So I agreed but the process of getting this started over the phone took an unusually long time where mostly I had to wait on the phone and occasionally give some information, in the final steps they transferred me to a supervisor but by then I was already late for a meeting so I told him I would call again later. On the second call I had to go over the whole process again with another rep, this time I made sure to ask them to replace the motherboard not just the capacitor, but then the called was dropped. At this point I realized that if all that was required is to replace the motherboard maybe I could do it myself.

Replacing the motherboard
I've never done it before, but I've always been tempted with building my own computer. After all, how hard could it be? By now I've practically disassembled my PC and I have all the components already, the only thing I needed is a new motherboard. After some research I chose the X58M from MSI which had the closest specs to my old board (I almost went for the ASUS Sabertooth until I realized that my old board had MicroATX format).

Four days later (including a weekend) I got the new board and went to Fry's to get me some Thermal Paste for the CPU and possibly the Northbridge heatsink (several reviewers complained the Norhtbridge runs hot and some just reapplied thermal paste to correct it). I dutyfully disconnected and labeled every cable from the old board. I was surprised how easy it was to move the Intel Core i7 920 CPU from the old board to the new. From a previous unpleasant experience with an old Pentium 4 I was expecting this to be very difficult, having to align countless pins with their holes. It turns out there are no pins, just contact plates that are kept in place with a pressure latch. Nice.

Heatsink snag
Next I had to install the old Heatsink-Cooler Fan assembly on top of the CPU. Here I hit my first snag. Although the holes to mount the heatsink were in the same place, the new motherboard expected a heatsink with hooks that clip into the holes, the heatsink I had was screwed to the CPU socket assembly. My solution? take the socket assembly from the old motherboard to the new one, easy (or so I thought).

After this I screwed the new motherboard in the case and reconnected all the cables (except the front panel). I should have done some test with a partially assembled setup instead of connecting everything, but ever the optimist (the impatient, really), I said let's go for it.

Shorted motherboard
So I turn on the computer and I see a blue flash and everything goes dead. No beeps, no fans, no nothing. Uh oh! What could it be? Try again, same thing. Start disconecting, keep trying, same result. Disconnect everything except the motherboard and CPU, try again, blue flash, dead.

Go to the MSI troubleshoot page. They recommend testing "...the motherboard outside of the case to verify that the motherboard is not shorting to the case". Aha! That sounds a likely cause, I knew I should have done some testing before. Take out the motherboard, try again, same result. Take out memory, disconnect CPU fan, try again, same.

At this point I got to thinking, the only thing that is not "kosher" is the CPU socket assembly that I took from the old motherboard, so I unscrewed the heatsink, removed the CPU, removed the socket assembly and sure enough the back plate of the socket assembly was bigger and it's making contact with the pins of three capacitors.

Going rustic
So my options were: order a new Heatsink-Cooler, find some compatible screws (unlikely) or buy a drill. It was 1am so I went to Walmart got me some safety goggles, a new drill, some drill bits and a Dremel accessory. Two hours later (those back plates are made of solid metal) I had a rustic looking back plate with a 1 inch by 1/4 inch section removed. This time I tested thoroughly and everything was working fine. An hour later I had a fully functioning computer again (or so I thought, that story in the next post).