Living Systems_

(E)BNF parser for parts of the Galaxy ToolConfig syntax with ANTLR

As blogged earlier, I’m currently into parsing the syntax of some definitions for the parameters and stuff of command line tools. As said in the linked blog post, I was pondering whether to use the Galaxy Toolconfig format or the DocBook CmdSynopsis format . It turned out though Well, that cmdsynopsis lacks the option to specify a list of valid choices, for a parameter, as is possible in the Galaxy ToolConfig format (see here ), and thus can be used to generate drop-down lists in wizards etc. which is basically what I want to do … so, now I’m going with the Galaxy format after all.

Enter the Galaxy format then. Look at an example code snippet:

<tool id="sam_to_bam" name="SAM-to-BAM" version="1.1.1">
  <description>converts SAM format to BAM format</description>
  <requirements>
    <requirement type="package">samtools</requirement>
  </requirements>
  <command interpreter="python">
    sam_to_bam.py
      --input1=$source.input1
      --dbkey=${input1.metadata.dbkey}
      #if $source.index_source == "history":
        --ref_file=$source.ref_file
      #else
        --ref_file="None"
      #end if
      --output1=$output1
      --index_dir=${GALAXY_DATA_INDEX_DIR}
  </command>
  <inputs>
    <conditional name="source">
      <param name="index_source" type="select" label="Choose the source for the reference list">
        <option value="cached">Locally cached</option>
        <option value="history">History</option>
      </param>
      <when value="cached">
      ... cont ...

Here I’ve got some challenges. XML parsing is easy, even in Java (I use the Java XPath libs for that). But look inside the <command> tag … that’s some really non-xml stuff, no? (it is instructions for a python based template library, used in galaxy). I have to parse this though, in order to replicate the logic of it … so what to do? … well, I turned to the ANTLR Parser Generator .

ANTLRWorks works nicely out of the box

I heard a lot of good things about ANTLR , like that it is more easily debugged than typical BNF parsers etc, so the choice wasn’t that hard. I tried the ANTLR for Eclipse, but though it looks nice, it that was quite buggy, and I couldnt get it to work properly in neither Eclipse 3.5 or 3.6. So, finally I went with the easy option and developed my EBNF grammar in ANTLRWorks , which is an integrated Java App, with the correct ANTLR lib already installed etc. Turned out to work really good!

The grammar I came up with so far (only for the syntax inside the tag so far, though!) is available on GitHub … and below (in condensed syntax to save some space), for you convenience :)

grammar GalaxyToolConfig;
options {output=AST;}

command    : binary (ifstatement param+ (ELSE param+)? ENDIF | param)*;
binary     : WORD;
ifstatement
        : IF (STRING|VARIABLE) EQTEST (STRING|VARIABLE) COLON;
param   : DBLDASH WORD* EQ (VARIABLE|STRING);
WORD    : ('a'..'z'|'A'..'Z')('a'..'z'|'A'..'Z'|'.'|'_'|'0'..'9')*;
VARIABLE
        : '$'('{')?WORD('}')?;
STRING  : '"'('a'..'z'|'A'..'Z')+'"';
IF      : '#if';
ELSE    : '#else';
ENDIF   : '#end if';
EQ      : '=';
EQTEST  : '==';
DBLDASH : '--';
COLON   : ':';
WS      : (' '|'\t'|'\r'|'\n') {$channel=HIDDEN;};

Suggestions for improvements? :) … Then go ahead and mail me … samuel dot lampa at gmail dot com)

Also, see a little screenshot from ANTLRWorks below:

As you can see in the screenshot, the different parts have correctly been identified as “param”, “if statement” and so forth. You can se also how I can click in the test syntax, to see where in the parse tree that actual part appears.

When done, I just exported the resulting parser code in ANTLRWorks with “Generate > Generate Code”, copied the code from the “output” folder into my Eclipse project, added the antlr-3.3 jar into the build path of it, and then ran the Test.java file that comes with the output.

I wanted to do a little more parsing in my test though, so I ended up with this little test code:

package net.bioclipse.uppmax.galaxytoolconfigparser;
import org.antlr.grammar.v3.*;
import org.antlr.runtime.ANTLRStringStream;
import org.antlr.runtime.CharStream;
import org.antlr.runtime.CommonTokenStream;
import org.antlr.runtime.RecognitionException;
import org.antlr.runtime.TokenStream;
import org.antlr.runtime.tree.CommonTree;
import org.antlr.runtime.tree.DOTTreeGenerator;
import org.antlr.runtime.tree.Tree;
import org.antlr.runtime.tree.TreeAdaptor;
import org.antlr.stringtemplate.StringTemplate;

public class ParseTest {
    // Generated stuff from ANTLR, which I can use to recognize token types
    public static final int EOF=-1;
    public static final int ELSE=4;
    public static final int ENDIF=5;
    public static final int WORD=6;
    public static final int IF=7;
    public static final int STRING=8;
    public static final int VARIABLE=9;
    public static final int EQTEST=10;
    public static final int COLON=11;
    public static final int DBLDASH=12;
    public static final int EQ=13;
    public static final int WS=14;

    public static void main(String[] args) throws RecognitionException {
        String testString = "    sam_to_bam.py"
                + "      --input1=$source.input1\n"
                + "      --dbkey=${input1.metadata.dbkey}\n"
                + "      #if $source.index_source == "history":\n"
                + "        --ref_file=$source.ref_file\n"
                + "      #else\n"
                + "        --ref_file="None"\n"
                + "      #end if\n"
                + "      --output1=$output1\n"
                + "      --index_dir=${GALAXY_DATA_INDEX_DIR}\n";
        CharStream charStream = new ANTLRStringStream(testString);
        GalaxyToolConfigLexer lexer = new GalaxyToolConfigLexer(charStream);
        TokenStream tokenStream = new CommonTokenStream(lexer);
        GalaxyToolConfigParser parser = new GalaxyToolConfigParser(tokenStream, null);

        System.out.println("Starting to parse ...");
        // GalaxyToolConfigParser.command_return command = parser.command();
        CommonTree tree = (CommonTree)parser.command().getTree();
        System.out.println("Done parsing ...");

        int i = 0;
        while (i<tree.getChildCount()) {
            Tree subTree = tree.getChild(i);
            System.out.println("Tree child: " + subTree.getText() + ", (Token type: " + subTree.getType() + ")");
            i++;
        }

        // Generate DOT Syntax tree
        //DOTTreeGenerator gen = new DOTTreeGenerator();
        //StringTemplate st = gen.toDOT(tree);
        //System.out.println("Tree: \n" + st);

        System.out.println("Done!");
    }
}

… generating this output:

Starting ...
Done executing command ...
Subtree text: sam_to_bam.py, (Token type: 6)
Subtree text: --, (Token type: 12)
Subtree text: input1, (Token type: 6)
Subtree text: =, (Token type: 13)
Subtree text: $source.input1, (Token type: 9)
Subtree text: --, (Token type: 12)
Subtree text: dbkey, (Token type: 6)
Subtree text: =, (Token type: 13)
Subtree text: ${input1.metadata.dbkey}, (Token type: 9)
Subtree text: #if, (Token type: 7)
Subtree text: $source.index_source, (Token type: 9)
Subtree text: ==, (Token type: 10)
Subtree text: "history", (Token type: 8)
Subtree text: :, (Token type: 11)
Subtree text: --, (Token type: 12)
Subtree text: ref_file, (Token type: 6)
Subtree text: =, (Token type: 13)
Subtree text: $source.ref_file, (Token type: 9)
Subtree text: #else, (Token type: 4)
Subtree text: --, (Token type: 12)
Subtree text: ref_file, (Token type: 6)
Subtree text: =, (Token type: 13)
Subtree text: "None", (Token type: 8)
Subtree text: #end if, (Token type: 5)
Subtree text: --, (Token type: 12)
Subtree text: output1, (Token type: 6)
Subtree text: =, (Token type: 13)
Subtree text: $output1, (Token type: 9)
Subtree text: --, (Token type: 12)
Subtree text: index_dir, (Token type: 6)
Subtree text: =, (Token type: 13)
Subtree text: ${GALAXY_DATA_INDEX_DIR}, (Token type: 9)
Done!

… seemingly I have the stuff I need, for doing some logic parsing now! :)

Some words about BNF

ANTLR is an (E)BNF parser generator. I had heard a little about BNF before, and was more or less scared off from the topic, thinking it looked too advanced, but really, I found it isn’t that hard at all!

It strikes me that BNF is quite much RegEx but with functions added, which allows for recursive pattern matching, which you’ll need for anything more advanced, such as nested braces/xml tags etc … but as you can see in the example above also, much of the pattern matching syntax actually has big similarities to RegEx.

In terms of tutorials, for the (E)BNF/ANTLR combo at least, I’d highly recommend this set of screencasts on using ANTLR in Eclipse . Though I didn’t use the Eclipse version, these screencasts quickly give you an idea of how it all works … I watched at least a bunch of them, and I’m happy I did.

Links