This is going to be the first post based on what I get up to in my day job at Freestyle Interactive, working on the Partners team. There could be more to follow, particularly when I come across something generally interesting.
Skip to the code
Freestyle is a digital agency, and the core of an agency business model revolves around time spent on client projects. To track this time, we have an in-house time recording system called Traffic (not to be confused with the commercially available system by the same name). It’s a fairly old system now, and it was originally built in a combination of clasic ASP, SQL server stored procs returning XML, and XSLT for the presentation layer. You can guess how much I ‘love’ working with that system.
Now I’m rebuilding Traffic from the ground up inside Partners, the Digital Asset Management system that we produce. In the process I’m hoping to improve the interface and make people a little less resentful of having to record what they are doing.
The first phase of the redevelopment is to build the timesheet entry user interface, and supporting logic/data access layer.
The old timesheet interface required a start & stop time for each task, due to integration requirements with our 3rd party accounting system. In the new version, I hoped to get away from this to just recording the duration of a task.
Each person in the agency seems to use Traffic slightly differently. This includes how people prefer to record their time. I wanted to provide a way that people can quickly enter time against their tasks, including adding more time to a task already in their timesheet; so I came up with the idea of a single field supporting simple time arithemetic operations, with minute-level resolution.
2h + 5m + 1:05 = 03:10 (3 hours, 10 minutes)
Pass the Parser
As far as I was aware, there wasn’t anything out there designed to do this. Having done a module on compilers at Durham, I was keen to write a parser and interpreter to do the job. I’m now very much a .Net developer, and with it being quite a while since writing YACC grammars, I looked for a solution that allowed me to port the principles learnt aver 8 years ago to my favourite platform. I found exactly this in Irony.
Irony is a very clever bit of kit that allows the creation of a grammar using famililar C# syntax, which is then transformed into a parser/lexer. Not only that, but it also provides a framework for very easily writing an interpreter. It’s just so awesome.
It does, however, assume you know how compiler generators work, with all the associated terminology of parsing, lexing, tokens etc. Documentation is a bit thin on the ground, however the source comes complete with many examples and some utilities to test and run both the examples and any custom grammars you care to write. I used this tutorial on creating a calculator using Irony to help me figure it out, along with one of the samples.
Enough Chat, Show Me The Code!
It will take me far too long to explain how Compiler Compilers work to the uninitiated, so I’m going to assume that you know all that stuff already.
The grammar I’ve defined accepts time in different formats:
- Hour portion, alone, in english notation:
decimal part hours permitted, e.g. 1.5 hr = 1 hr 30 mins
- Minute portion, alone, in english notation:
- Hour & minute portions together, in english notation:
- Hour & minute portions in colon notation:
01:35 = 1 hr 35 mins
- Hour & minute portions in dot notation:
1.5 = 1 hr 50 mins
The first task is to separate the terminals from the non-terminals. So the above translates to this:
var number = new NumberLiteral("number", NumberOptions.AllowLetterAfter);
var HOUR_SINGLE = ToTerm("h");
var HOUR_SHORT = ToTerm("hr");
var HOUR_LONG = ToTerm("hour");
var HOURS_SHORT = ToTerm("hrs");
var HOURS_LONG = ToTerm("hours");
var MINUTE_SINGLE = ToTerm("m");
var MINUTE_SHORT = ToTerm("min");
var MINUTE_LONG = ToTerm("minute");
var MINUTES_SHORT = ToTerm("mins");
var MINUTES_LONG = ToTerm("minutes");
var COLON = ToTerm(":");
var PLUS = ToTerm("+");
var MINUS = ToTerm("-");
var hourSymbol = new NonTerminal("hourSymbol");
var minuteSymbol = new NonTerminal("minuteSymbol");
var hourValue = new NonTerminal("hourValue", typeof(HourValueNode));
var minuteValue = new NonTerminal("minuteValue", typeof(MinuteValueNode));
var colonTimeValue = new NonTerminal("colonTimeValue", typeof(ColonTimeValueNode));
var hourMinuteTimeValue = new NonTerminal("hourMinuteTimeValue", typeof(HourMinuteTimeValueNode));
var binExpr = new NonTerminal("binExpr", typeof(BinaryOperationNode));
var binOperator = new NonTerminal("binOperator");
var unExpr = new NonTerminal("unExpr", typeof(UnaryOperationNode));
var unOperator = new NonTerminal("unOperator");
var timeValue = new NonTerminal("timeValue");
var expression = new NonTerminal("expression", typeof(ExpressionNode));
var timePartSeparatorSymbol = new NonTerminal("timePartSeparatorSymbol");
Then the rules are defined on the non-terminals, declaring the pattern that terminals and other non-terminals are expected.
hourSymbol.Rule = HOUR_SINGLE | HOUR_SHORT | HOUR_LONG | HOURS_SHORT | HOURS_LONG;
hourValue.Rule = number + hourSymbol;
minuteSymbol.Rule = MINUTE_SINGLE | MINUTE_SHORT | MINUTE_LONG | MINUTES_SHORT | MINUTES_LONG;
minuteValue.Rule = number + minuteSymbol;
colonTimeValue.Rule = number + COLON + number;
hourMinuteTimeValue.Rule = hourValue + minuteValue;
timeValue.Rule = hourValue | minuteValue | colonTimeValue | hourMinuteTimeValue;
expression.Rule = timeValue | binExpr | unExpr;
binOperator.Rule = PLUS | MINUS;
binExpr.Rule = expression + binOperator + expression;
unOperator.Rule = PLUS | MINUS;
unExpr.Rule = binOperator + timeValue;
In the non-terminals section, you’ll notice that some of the definitions include the types of some classes. This is part of the interpreter framework that allows you to define custom nodes in the Abstract Syntax Tree. It all works using the visitor pattern. Here’s an example of one of the classes,
public class HourMinuteTimeValueNode : AstNode
private AstNode HoursNode;
private AstNode MinutesNode;
public override void Init(Irony.Ast.AstContext context, Irony.Parsing.ParseTreeNode treeNode)
HoursNode = AddChild("Hours", treeNode.ChildNodes);
MinutesNode = AddChild("Minutes", treeNode.ChildNodes);
protected override object DoEvaluate(Irony.Interpreter.ScriptThread thread)
return (int)HoursNode.Evaluate(thread) + (int)MinutesNode.Evaluate(thread);
Init method is called to transform the
ParseTree nodes (in the treeNode.ChildNodes collection) into a sub-tree in the AST. When the interpreter is run,
DoEvaluate executes the operations that allow you to ‘run’ your parsed input. On this node I’m simply combining the hours and minutes parts to return an integer value representing the combined whole number of minutes.
There are several general purpose helper AST node types included in Irony, such as
BinaryOperationNode. Using this class, for instance, I didn’t need to implement any addition/subtraction logic – it magically just worked. The only custom node classes I used were to convert each different form of acceptable duration expression into an integer value of minutes.
With the grammar and custom AST nodes written, the only thing left to do is use it.
First, the grammar is ‘compiled':
LanguageData language = new LanguageData(_grammar);
Parser parser = new Parser(language);
Next, the parser instance is fed the input string, and returns a
ParseTree parseTree = parser.Parse(expression);
If you don’t want to interpret, then you could stop at this point. I want to get a single value from the input expression, though, so:
ScriptApp app = new ScriptApp(language);
ScriptThread thread = new ScriptThread(app);
int minutes = (int)app.Evaluate(parseTree);
Et voilà! Note that you don’t always have to return a value – if you’re writing your own executable language, for example, there could very well be no returned result with all I/O, calculations etc. handled in your custom AST nodes.
Download the complete C# source code (you’ll need to set up a project, and include Irony via NuGet)
This code is provided with blessings from my boss. If you want to show your gratitude, and think your organisation could use a Digital Asset Management system, then please check out Freestyle Partners.