Creating a simple parser with ANTLR

Recently, I’ve faced a task of developing a tool which allows the application to have base of (not very complex) logical rules. There were three demands:

  1. The rules were to be written by non-programmers, so using of the languages which the program is written in (Java/Scala), wasn’t very good.
  2. The rule base should be changeable without redeployment of the application, ideally, should be stored in a database.
  3. We should have control on compilation and error emission.

The first and the second demand could be met by developing some kind of Scala- or Groovy-based DSL, extremely simple. But I’ve come with several arguments against:

  • The third requirement might be hard to meet.
  • The rules are quite simple, so embedding an interpreter of a general-purpose language might be overkill.
  • The language which rules consumer is written in might be changed (from Java/Scala to Python e.g.)

So, I’ve decided to write a very simple rule parser/compiler. After I’d created a prototype I decided to write this post, hope it’ll be useful. I say in advance that you can see the code adapted for this post here.
Continue reading

Finding a cycle in a linked list

There is a popular task at software developer job interviews: having a singly linked list, write a piece of code which tells if the list has a cycle.

In a linked list, each element is a structure which contains the value of an element and the link to the next element. The next-link of the last element has a special value which marks the end (usually, null). If a list has a cycle, the last element points to some element inside the list.

Linked list types

Continue reading

Z algorithm

Introduction

There are some algorithms of exact substring searching (e.g. Knuth-Morris-Pratt, Boyer-Moore etc.) I want to explain one of them which is called Z algorithm in some sources.

Z-boxes and Z-values

Let’s consider the concept of Z-box. Take the string S = "abcxxxabyyy". We have an internal part "ab" in the string which repeats its prefix. The internal "ab" is a Z-box. It has the beginning at the position with index 6 and the end in 7 (0-based). Z-boxes are substrings which match string prefixes with the same length. For the Z-box, let’s call the corresponding prefix the prototype (it’s my term but I think it’s OK to use it.)

Z algorithm

Continue reading