DDevelopment & Design

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.

— Previous article

What is NoSQL good for?

Next article —

Weird Oracle

You May Also Like
DDevelopment & Design

Log4j and MDC in Grails

Log4j provides very useful feature: MDC - mapped diagnostic context. It can be used to store data in context of current thread. It may sound scary a bit but idea is simple.

My post is based on post http://burtbeckwith.com/blog/?p=521 from Burt Beckwith's excellent blog, it's definitely worth checking if you are interested in Grails.

Short background story...


Suppose we want to do logging our brand new shopping system and we want to have in each log customer's shopping basket number. And our system can be used at once by many users who can perform many transactions, actions like adding items and so on. How can we achieve that? Of course we can add basket number in every place where we do some logging but this task would be boring and error-prone. 

Instead of this we can use MDC to store variable with basket number in map. 

In fact MDC can be treated as map of custom values for current thread that can be used by logger. 


How to do that with Grails?


Using MDC with Grails is quite simple. All we need to do is to create our own custom filter which works for given urls and puts our data in MDC.

Filters in Grails are classes in directory grails-app/conf/* which names end with *Filters.groovy postfix. We can create this class manually or use Grails command: 
grails create-filters info.rnowak.App.Basket

In result class named BasketFilters will be created in grails-app/conf/info/rnowak/UberApp.

Initially filter class looks a little bit empty:
class BasketFilters {
    def filters = {
        all(controller:'*', action:'*') {
            before = {

            }
            after = { Map model ->

            }
            afterView = { Exception e ->

            }
        }
    }
}
All we need to do is fill empty closures, modify filter properties and put some data into MDC.

all is the general name of our filter, as class BasketFilters (plural!) can contain many various filters. You can name it whatever you want, for this post let assume it will be named basketFilter. 

Another thing is change of filter parameters. According to official documentation (link) we can customize our filter in many ways. You can specify controller to be filtered, its actions, filtered urls and so on. In our example you can stay with default option where filter is applied to every action of every controller. If you are interested in filtering only some urls, use uri parameter with expression describing desired urls to be filtered.

Three closures that are already defined in template have their function and they are started in these conditions:

  • before - as name says, it is executed before filtered action takes place
  • after - similarly, it is called after the action
  • afterView - called after rendering of the actions view
Ok, so now we know what are these mysterious methods and when they are called. But what can be done within them? In official Grails docs (link again) under section 7.6.3 there is a list of properties that are available to use in filter.

With that knowledge, we can proceed to implementing filter.

Putting something into MDC in filter


What we want to do is quite easy: we want to retrieve basket number from parameters and put it into MDC in our filter:
class BasketFilters {
    def filters = {
        basketFilter(controller:'*', action:'*') {
            before = {
                MDC.put("basketNumber", params.basketNumber ?: "")
            }
            after = { Map model ->
                MDC.remove("basketNumber")
            }
        }
    }
}

We retrieve basket number from Grails params map and then we put in map under specified key ("basketNumber" in this case), which will be later used in logger conversion pattern. It is important to remove custom value after processing of action to avoid leaks.

So we are putting something into MDC. But how make use of it in logs?


We can refer to custom data in MDC in conversion patter using syntax: %X{key}, where key is our key we used in filter to put data, like:
def conversionPattern = "%d{yyyy-MM-dd HH:mm:ss} %-5p %t [%c{1}] %X{basketNumber} - %m%n"


And that's it :) We've put custom data in log4j MDC and successfully used it in logs to display interesting values.