Friday, December 21, 2012

6. Wally ground work

Parts: 1 2 3 4 5 6 7

So, we've got the lexer, parser and tree-walker done for Wally. However, during the parsing phase, we've ignored functions, objects and use statements. We're going to handle them in this part of the tutorial. We'll also start with the implementation of Wally's data types.

We'll put the functions and objects in two instance variables in the parser (java.util.Maps) when we parse them. And we'll create a method handleUse(String name, String fileName) that will parse another Wally script when it is used.

grammar Wally;

// code omitted for brevity

  private File file;
  private Map<String, Function> functions = new LinkedHashMap<String, Function>();
  private Map<String, Obj> objects = new LinkedHashMap<String, Obj>();

  public WallyParser(File f, CommonTokenStream stream) {
    file = f;

  public Map<String, Function> getFunctions() {
    return functions;

  public Map<String, Obj> getObjects() {
    return objects;

  private void handleUse(String name, String fileName) {
    try {
      File newFile = new File(file.getParentFile(), fileName);
      WallyParser parser = Wally.getParser(newFile);

      Map<String, Obj> objs = parser.getObjects();
      Map<String, Function> fns = parser.getFunctions();

      if(name.equals("*")) {
      else {
        Obj obj = objs.get(name);

        if(obj != null) {
          objects.put(name, obj);
        else {
          Function f = fns.get(name);

          if(f == null) {
            throw new RuntimeException("no such object or function: " + 
                                        name + " in: " + newFile);

          functions.put(name, f);
    } catch(Exception e) {
      throw new RuntimeException(e);

// code omitted for brevity

 : Use (t=Id | t='*') From Str EOL+ {handleUse($t.text, $Str.text);}

As you can see in the code above, I introduced some extra classes: Function and Obj. Let's define some more Wally-specific data-type, and related classes:


As the name suggests, a class that encapsulates a Wally-function. Below is a UML diagram of it:


A class holding all variables in a certain scope.


A class representing the "blue print" of a Wally object-instance.


A WNode is a simple interface all our AST classes will implement. It has just a single method defined in it:


A WValue is an abstract class that has mostly abstract methods:

Most methods are implemented so that they throw an exception when being invoked. Every "real" Wally value extends this class and only overrides those methods that make sense to that particular value, ignoring the other methods (causing an exception to be thrown when invoked).

For example, the boolean-Wally type would (at least) override not(), and(WValue) and or(WValue), but not mult(WValue), causing code like true * false to throw an exception.


Wally's numerical type:


Wally's boolean type:


Wally's string type:


Wally's list type:


The instance of a Wally object:

Tree walker

We will also adjust the constructor of the tree walker to take a Scope (the global scope) and the Map<String, Obj> and Map<String, Function> the parser built from the input script:
tree grammar WallyEvaluator;

// ...

@members {
  private Map<String, Obj> objects;
  private Map<String, Function> functions;
  private Scope globalScope;
  private Scope currentScope;

  // constructor used in the Function class
  public WallyEvaluator(CommonTreeNodeStream nodes, 
                        Scope s, 
                        Map<String, Obj> os, 
                        Map<String, Function> fns) {
    globalScope = s;
    currentScope = globalScope;
    objects = os;    
    functions = fns;

  public WallyEvaluator(CommonTreeNodeStream nodes, 
                        Map<String, Obj> obj,
                        Map<String, Function> fns,
                        String[] params) {
    objects = obj;
    globalScope = new Scope();
    functions = fns;
    int num = 1;

    // add command line parameters to the global scope, put a `$` in front of it
    for(String param : params) {
      String name = "$" + num;
      WValue value = param.matches("[-+]?\\d+(\\.\\d*)?") ? 
          new WNumber(Double.valueOf(param)) : new WString(param);
      globalScope.put(name, value);

    // let the parent scope of all function-scopes be the global scope of the 
    // Wally script that is being evaluated at this moment
    ObjInstance globalFunctions = new ObjInstance("@functions", null, fns, null);
    Scope functionScope = new Scope();
    functionScope.put("this", globalFunctions);
    globalScope.put("this", globalFunctions);
    for(Function f : functions.values()) {
    currentScope = globalScope;

walk returns [WNode root] 
@init{$root = null;}
 : ^(BLOCK file_atom* return_stat)
 // ...

If you now create a jar file of the project by executing the Ant task ant jar, and then execute the Wally script src/scripts/Test.wy, containing a simple script like this:

a = 2 + 40

like this:

ant jar
java -jar Wally.jar src/scripts/Test.wy

you would get a java.lang.NullPointerException, but don't worry, that was expected. After all, the walk rule in tree walker simply returns null, where it's supposed to return an instance of a WNode. We will have to implement the AST nodes that actually evaluate the input. But that will be the subject of the next part of this tutorial.

Download the source of the project here created so far.


Bùi Đình Ngọc said...

Hi .

I have question about this project

I build all you code to a jar file .
But the question is how to parse a liquid template to html string ?
Base on your example
String test = "{% for image in product.images %} \n" +
" {{ image | product_img_url | img_tag }} \n" +
"{% endfor %}

Now , how to get output ?

I need full implement Liquid template parser in java .
Please help me

Bart Kiers said...

Hi Bùi,

I only provided a parser that creates an AST from Liquid-input. If you want to emit HTML output, you need to walk the AST and produce the HTML yourself.

How to do this exactly cannot be explained quickly (at least no in a comment box).

Good luck & regards,


Ricardo Fabio said...

I create a language similar to the tiny language you implemented but in spanish so i can use it in my programming course. My question is where I can find more information about how to implement an onlina interpreter like you did with your Wally language. Any ideas sources, sites or books on how i do this.

Thanks in advance

Bart Kiers said...

Hi Ricardo,

I have a Google App Engine servlet running in the background which, upon pressing the escape key, receives a POST request from the webpage. The GAE-servlet then evaluates the srctip that got POSTed and returns the outcome back in the jQuery-ajax call (check the source of the webpage).

Good luck!