Grammatical Inference

Grammatical inference or Grammar Induction focuses on learning formal language rules from a series of observations of samples from the language under consideration.

If you are interested in learning some grammatical inference basics the video links below are well worth a look.



Grammatical Inference: a Tutorial

Colin de la Higuera

Also, there are several articles available through citeseer. Search on grammar inference or grammatical inference.


Finally, Amazon has several Grammatical Inference conference proceedings.

Protocol Reverse Engineering

Some reverse engineering ideas/resources are located here.

Another attempt at protocol reverse engineering to BNF is online at Rent A Coder.

A recent attempt at classifying encrypted traffic in SSH tunnels here.

How to specify the default installation prefix in configure.in/configure.ac?

Add the AC_PREFIX_DEFAULT(/usr/local) macro in configure.in/configure.ac. Where you replace /usr/local with the prefix you want to use.

See (here) for details.

Augmented BNF (ABNF)

While looking for Augmented BNF (ABNF) source for some of the common Internet protocols I came ac cross a perl script by Bill Fenner to extract ABNF from RFCs (here).

I used it to generate ABNF for RFC4234, RFC2821, and RFC2822 to use with APG an ABNF Parser Generator.

Standard ML New Jersey on OpenSUSE 10.3

I needed a version of Standard ML New Jersey to compile PADS but the smlnj version from binary RPM for OpenSUSE was configured to use files in it's build directory.

First, I followed the install instructions. I downloaded the files from the SourceForge file list, and went through the install process but the build was convoluted by assembly source problems.

Next, I took a whack at building from the source RPM.

I searched for "smlnj" at the OpenSUSE Build Service .
Downloaded the source RPM and copy it to /usr/src/packages/SRPMS.

Installed the source RPM with rpm -Uvh smlnj-110.65-10.src.rpm. This will result in smlnj.spec in /usr/src/packages/SPECS and /usr/src/packages/SOURCES.

Build the RPM:
cd to the /usr/src/packages/SPECS and build the SRPM and RPM with rpmbuild -ba smlnj.spec.
On my system this results in:

• /usr/src/packages/SRPMS/smlnj-110.65-10.src.rpm


• /usr/src/packages/RPMS/i586/smlnj-100.65-10.i586.rpm


• /usr/src/packages/RPMS/i586/smlnj-debuginfo-100.65-10.i586.rpm

Install the RPM:
cd to /usr/src/packages/RPMS/i586 and install the binary RPMS with rpm -Uvh smlnj-100.65-10.i586.rpm.

The end result... AHRGGG! Not surprisingly, the install is still looking for library files in /usr/src/packages/BUILD/smlnj-110.65/sml.boot.x86-unix.

Finally, I extracted the source from the RPM (rpm2cpio smlnj-110.65-10.src.rpm | cpio -ivmud), applied the patches and built the whole thing in /usr/local/lib/smlnj then added /usr/local/smlnj/bin to the PATH. Now PADS builds.

My code wasteland

Nearly forgot about the google code project hosting. My code wasteland is at http://code.google.com/p/mark-e-deyoung/.

Actually, I need to fire it up again for another project because my school's CVS is down for maintenance (and probably will be down the entire Christmas holiday.)

Approximating context-free grammars with regular grammars.

Got a version of the Mohri and Nederhof algorithm working with SWI-prolog. The prolog source (attached here) is from Implementation of Regular Approximation of Context-Free Grammars Through Transformation by Tapani Raiko at Helsinki University of Technology.

Raiko explains how to use the program in his write-up.

A similar idea is implemented by Tanaka Akira in abnf converter. It's a ruby program to convert Augmented BNF to Regexp.