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

Private fields and methods are not private in groovy

I used to code in Java before I met groovy. Like most of you, groovy attracted me with many enhancements. This was to my surprise to discover that method visibility in groovy is handled different than Java!

Consider this example:

class Person {
private String name
public  String surname

private Person() {}

private String signature() { "${name?.substring(0, 1)}. $surname" }

public String toString() { "I am $name $surname" }
}

How is this class interpreted with Java?

  1. Person has private constructor that cannot be accessed
  2. Field "name" is private and cannot be accessed
  3. Method signature() is private and cannot be accessed

Let's see how groovy interpretes Person:

public static void main(String[] args) {
def person = new Person()   // constructor is private - compilation error in Java
println(person.toString())

    person.@name = 'Mike'       // access name field directly - compilation error in Java
println(person.toString())

    person.name = 'John'        // there is a setter generated by groovy
println(person.toString())

    person.@surname = 'Foo'     // access surname field directly
println(person.toString())

    person.surname = 'Bar'      // access auto-generated setter
println(person.toString())

println(person.signature()) // call private method - compilation error in Java
}

I was really astonished by its output:

I am null null
I am Mike null
I am John null
I am John Foo
I am John Bar
J. Bar

As you can see, groovy does not follow visibility directives at all! It treats them as non-existing. Code compiles and executes fine. It's contrary to Java. In Java this code has several errors, pointed out in comments.

I've searched a bit on this topic and it seems that this behaviour is known since version 1.1 and there is a bug report on that: http://jira.codehaus.org/browse/GROOVY-1875. It is not resolved even with groovy 2 release. As Tim Yates mentioned in this Stackoverflow question: "It's not clear if it is a bug or by design". Groovy treats visibility keywords as a hint for a programmer.

I need to keep that lesson in mind next time I want to make some field or method private!