Grammar parser in C++

Recently I stumbled upon implementing a simple parser in C++. The task is very classic, however, I couldn’t find any good resources on the web to help me out.
I tried different tools (including ANTLR), but finally, the easiest way I found was bison + flex. It’s unbelievable that this technology from 1989 is still actively developed. The latest stable release is from May 14, 2011. Moreover, many essential projects make use of it. Among them are Ruby, PHP, Google Go, and Bash shell.
So I decided to create a minimalistic example that works from scratch.
I published the code on GitHub Calculator, so you can check it out.
The whole example is 88 lines long and evaluates common expressions, like 2+2*2-13*(7+19/2).
Let’s start with lexer. In flex, you need to define regular expressions, which produce tokens. Such tokens are later processed by a scanner. So we have to define calculator.lex, like this:
Flex will generate yylex() function, which we can call later to produce tokens. Next, we need to create a scanner (calculator.y), which specifies a grammar. It’s simple like that:
Here, we specify types for all tokens using C/C++ union like structure. Variable $$ is used to store result of particular reductions.
Additionally, we need to specify %left precedence for +, -, *, / operators to resolve shift / reduce conflicts between them.
And that’s basically it. We have a working expression parser.
I implemented it so that executable takes a file name containing expressions as an argument.
So you can try ./calculator input.txt to see the result.

You May Also Like

Spock, Java and Maven

Few months ago I've came across Groovy - powerful language for JVM platform which combines the power of Java with abilities typical for scripting languages (dynamic typing, metaprogramming).

Together with Groovy I've discovered spock framework (https://code.google.com/p/spock/) - specification framework for Groovy (of course you can test Java classes too!). But spock is not only test/specification framework - it also contains powerful mocking tools.

Even though spock is dedicated for Groovy there is no problem with using it for Java classes tests. In this post I'm going to describe how to configure Maven project to build and run spock specifications together with traditional JUnit tests.


Firstly, we need to prepare pom.xml and add necessary dependencies and plugins.

Two obligatory libraries are:
<dependency>
<groupid>org.spockframework</groupId>
<artifactid>spock-core</artifactId>
<version>0.7-groovy-2.0</version>
<scope>test</scope>
</dependency>
<dependency>
<groupid>org.codehaus.groovy</groupId>
<artifactid>groovy-all</artifactId>
<version>${groovy.version}</version>
<scope>test</scope>
</dependency>
Where groovy.version is property defined in pom.xml for more convenient use and easy version change, just like this:
<properties>
<gmaven-plugin.version>1.4</gmaven-plugin.version>
<groovy.version>2.1.5</groovy.version>
</properties>

I've added property for gmaven-plugin version for the same reason ;)

Besides these two dependencies, we can use few additional ones providing extra functionality:
  • cglib - for class mocking
  • objenesis - enables mocking classes without default constructor
To add them to the project put these lines in <dependencies> section of pom.xml:
<dependency>
<groupid>cglib</groupId>
<artifactid>cglib-nodep</artifactId>
<version>3.0</version>
<scope>test</scope>
</dependency>
<dependency>
<groupid>org.objenesis</groupId>
<artifactid>objenesis</artifactId>
<version>1.3</version>
<scope>test</scope>
</dependency>

And that's all for dependencies section. Now we will focus on plugins necessary to compile Groovy classes. We need to add gmaven-plugin with gmaven-runtime-2.0 dependency in plugins section:
<plugin>
<groupid>org.codehaus.gmaven</groupId>
<artifactid>gmaven-plugin</artifactId>
<version>${gmaven-plugin.version}</version>
<configuration>
<providerselection>2.0</providerSelection>
</configuration>
<executions>
<execution>
<goals>
<goal>compile</goal>
<goal>testCompile</goal>
</goals>
</execution>
</executions>
<dependencies>
<dependency>
<groupid>org.codehaus.gmaven.runtime</groupId>
<artifactid>gmaven-runtime-2.0</artifactId>
<version>${gmaven-plugin.version}</version>
<exclusions>
<exclusion>
<groupid>org.codehaus.groovy</groupId>
<artifactid>groovy-all</artifactId>
</exclusion>
</exclusions>
</dependency>
<dependency>
<groupid>org.codehaus.groovy</groupId>
<artifactid>groovy-all</artifactId>
<version>${groovy.version}</version>
</dependency>
</dependencies>
</plugin>

With these configuration we can use spock and write our first specifications. But there is one issue: default settings for maven-surefire plugin demand that test classes must end with "..Test" postfix, which is ok when we want to use such naming scheme for our spock tests. But if we want to name them like CommentSpec.groovy or whatever with "..Spec" ending (what in my opinion is much more readable) we need to make little change in surefire plugin configuration:
<plugin>
<groupid>org.apache.maven.plugins</groupId>
<artifactid>maven-surefire-plugin</artifactId>
<version>2.15</version>
<configuration>
<includes>
<include>**/*Test.java</include>
<include>**/*Spec.java</include>
</includes>
</configuration>
</plugin>

As you can see there is a little trick ;) We add include directive for standard Java JUnit test ending with "..Test" postfix, but there is also an entry for spock test ending with "..Spec". And there is a trick: we must write "**/*Spec.java", not "**/*Spec.groovy", otherwise Maven will not run spock tests (which is strange and I've spent some time to figure out why Maven can't run my specs).

Little update: instead of "*.java" postfix for both types of tests we can write "*.class" what is in my opinion more readable and clean:
<include>**/*Test.class</include>
<include>**/*Spec.class</include>
(thanks to Tomek Pęksa for pointing this out!)

With such configuration, we can write either traditional JUnit test and put them in src/test/java directory or groovy spock specifications and place them in src/test/groovy. And both will work together just fine :) In one of my next posts I'll write something about using spock and its mocking abilities in practice, so stay in tune.

Simple trick to DRY your Grails controller

Grails controllers are not very DRY. It's easy to find duplicated code fragments in default generated controller. Take a look at code sample below. It is duplicated four times in show, edit, update and delete actions:

class BookController {
def show() {
def bookInstance = Book.get(params.id)
if (!bookInstance) {
flash.message = message(code: 'default.not.found.message', args: [message(code: 'book.label', default: 'Book'), params.id])
redirect(action: "list")
return
}
[bookInstance: bookInstance]
}
}

Why is it duplicated?

There is a reason for that duplication, though. If you move this snippet to a method, it can redirect to "list" action, but it can't prevent controller from further execution. After you call redirect, response status changes to 302, but after method exits, controller still runs subsequent code.

Solution

At TouK we've implemented a simple trick to resolve that situation:

  1. wrap everything with a simple withStoppingOnRender method,
  2. whenever you want to render or redirect AND stop controller execution - throw EndRenderingException.

We call it Big Return - return from a method and return from a controller at once. Here is how it works:

class BookController {
def show(Long id) {
withStoppingOnRender {
Book bookInstance = Book.get(id)
validateInstanceExists(bookInstance)
[bookInstance: bookInstance]
}
}

protected Object withStoppingOnRender(Closure closure) {
try {
return closure.call()
} catch (EndRenderingException e) {}
}

private void validateInstanceExists(Book instance) {
if (!instance) {
flash.message = message(code: 'default.not.found.message', args: [message(code: 'book.label', default: 'Book'), params.id])
redirect(action: "list")
throw new EndRenderingException()
}
}
}

class EndRenderingException extends RuntimeException {}

Example usage

For simple CRUD controllers, you can use this solution and create some BaseController class for your controllers. We use withStoppingOnRender in every controller so code doesn't look like a spaghetti, we follow DRY principle and code is self-documented. Win-win-win! Here is a more complex example:

class DealerController {
@Transactional
def update() {
withStoppingOnRender {
Dealer dealerInstance = Dealer.get(params.id)
validateInstanceExists(dealerInstance)
validateAccountInExternalService(dealerInstance)
checkIfInstanceWasConcurrentlyModified(dealerInstance, params.version)
dealerInstance.properties = params
saveUpdatedInstance(dealerInstance)
redirectToAfterUpdate(dealerInstance)
}
}
}