Technology

Reminderer: a Grammar Parser


Some friends and I are coding a Remember-the-Milk inspired Android app called (for the moment) Reminderer. If you never used Remember the Milk, it’s a todo-list app. One of its appeals is that you can enter tasks using every-day language. For example, “Buy milk at 8pm” because a task that’s due at 8pm. We wanted our app to have the same functionality. That means that we should be able to enter tasks like “Buy milk on Monday” or “Mom’s birthday next Monday” and have the app auto-magically turn them into tasks. In order to do that, our app needed a context-free grammar and a grammar parser.

As its name implies, a context-free grammar encapsulates the idea of language, minus meaning or context. A grammar parser takes a string expression and tells you whether or not its part of the grammar, processing the expression as it goes along. Check out these two notebooks to learn more about grammars and grammar parsers: Context Free Grammars and Recursive Descent Parsers.

In order to write a grammar parser by hand (easily), the grammar needs to be non-left recursive. (Basically, in a non-left recursive grammar, the recursion, if any, occurs at the end of a grammar rule.) The reason the grammar should be non-left recursive is because it makes the job of coding the parser easier—each parser function is in an almost one-to-one correspondence with each grammar rule.

After some trial-and-error, this is the non-left recursive grammar we came up with for tasks:

expr: task | task commands
commands: command commands | NULL
command: time | date | next | repeats | repeatsEvery | location 
time: timeParser | "at" timeParser
date: "today" | "tomorrow" | dateParser | "on" dateParser
next: "next" dayParser
repeats: "repeats" occurrence 
occurrence: "hourly" | "daily" | "weekly" | "monthly" | "yearly"
repeatsEvery: "repeats" "every" S
S: timeDuration | dayParser | "hour" | "day" | "week" |  "month" | "year" 
location: "at" locationString

This snippet of code shows the correspondence between the parser functions and the grammar:

Task commands() {
  // save position
  int curPos = context.getPos();
  // command commands
  if (command() != null && commands() != null)
    return task;
  // undo cursor advance if no match found
   else context.setPos(curPos);
  //...
}
Task command() {
 int curPos = context.getPos();
 if (time() != null || date() != null || next() != null
     || repeats() != null || repeatsEvery() != null
     || location() != null)
     return task;
 else {
   context.setPos(curPos);
   return null;
 }
}

The expression if (command() != null && commands() != null) in commands() and the similar line in command() mimic the corresponding grammar rules:

commands: command commands | NULL
command: time | date | next | repeats | repeatsEvery | location

So that’s the grammar that we decided to use in Reminderer. In case you haven’t noticed, the grammar doesn’t express uniqueness. For example, “Buy eggs at 8pm at 10pm” is a perfectly valid sentence. (The parser handles this by using the last time stamp.)

If you’re wondering about “timeParser”, “dateParser”, and “dayParser”, these work in conjunction with Java’s DateFormat and SimpleDateFormat classes. That is, instead of encapsulating date and time formats in the grammar, we outsource that work to preexisting Java classes built for that purpose.

The Reminderer grammar parser is more or less done. Check it out at github: https://github.com/frankandrobot/Reminderer/. Make sure to check out the “newParserStrategy” branch. I’ll make sure to upload a debug build later this week. And yes, the app is open source—it’ll use an Apache-style license. We just haven’t had time to upload the license yet.

Advertisements

One thought on “Reminderer: a Grammar Parser

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s