Informatics 102 Spring 2012
Assignment #5: Implementing a Domain-Specific Language in Java

Due date and time: Sunday, June 10, 11:59pm


In the previous assignment, you were asked to write two Java programs that communicated with one another through a file — one program wrote to the file while the other read from it. To make the communication work, the two programs had to agree on a format for the file. Rather than designing our own custom file format and implementing code to read it and write it from scratch, we instead used a domain-specific language called Protocol Buffers, in which we described the structure of the information to be stored in the file, then relied on the Protocol Buffers implementation to automatically generate the code, based on our description, that reads and writes that information.

While the previous assignment asked you to use a domain-specific language, this assignment focuses on the task of designing and implementing a new one. As Protocol Buffers does, our language will focus on making it easy to specify a narrow area of functionality in a larger program, generating what would otherwise be repetitive, boilerplate code that you would have to write from scratch. We'll concentrate our efforts on a different domain, but our needs will be similar: we'll need a compiler that reads our language and generates Java as its output; we'll also need a runtime library that implements the code that would be common in any use of our language.

You'll proceed with the design and implementation of this language by performing a few tasks:

An example of following these steps to design and implement a domain-specific language is given in the Code Examples section.

The problem domain

It's likely in past coursework that you've been asked to write Java programs with console-mode user interfaces, where all input comes from and all output goes to System.out. You may have noticed that these programs are often very similarly structured, offering a "menu" of commands that the user can enter, each of which is handled by asking the user for additional input parameters, making some changes to the program's underlying state, and printing some output confirming the action taken. Furthermore, you may have noticed that there is duplication of information in the code you write — for example, the code that prints the menu has to print commands that match the ones implemented elsewhere.

Let's embark on designing a domain-specific language called Menuba that can be used to describe the menus typically used in console-mode user interfaces. Menuba should allow us to describe relevant information about each command, with no duplication of effort; its compiler will generate Java code that does some of the tedious work of implementing a user interface like this.

Part 1: Prototyping Menuba (30 points)

Finding the boundaries

Our first step in implementing our new language is to decide more precisely what problem it solves: what it will allow me to say and what will happen as a result of me saying it. Our goal is to use our language to take some of the tedium out of building console-mode user interfaces in Java, while preserving Java's usefulness in solving the business problem that underlies our user interface. We're not trying to replace Java; we're just trying to augment it, so that we can do one very particular thing better than we could before.

Programs written using Menuba will be broken into three discrete parts:

Before we can embark on our implementation of Menuba, we'll have to do some prototyping; the exact split between what belongs in the command menus, the runtime library, and the business logic will not necessarily be obvious to us at first. Instead, we'll need to work out a prototype design for a typical program built using Menuba and Java, keeping the three discrete parts separate. We'll write our whole prototype in Java, since we don't have a Menuba compiler yet; we'll also try to write our prototype in such a way that it would be possible to generate the command menus automatically using a compiler, so we should err on the side of being more pattern-oriented than creative.

Considering Menuba's mandate

A typical console-mode user interface provides a user experience much like the one demonstrated below. (In the example, boldfaced text is input from the user, while non-boldfaced text is output.)

[A] Add a player to team
[R] Remove a player from team
[L] List the players on team
[G] Generate team lineup
[S] Save team to file
[Q] Quit
[?] Help

Command: A

Add Player
Player Name: Alex Thornton
Player Position: 1B
Alex Thornton (1B) added to team

Command: S

Save Team
Team Filename: team.txt
Team information saved to team.txt

Command: B

B is not a valid command; please try again or type ? for help

Command: ?

[A] Add a player to team
[R] Remove a player from team
[L] List the players on team
[G] Generate team lineup
[S] Save team to file
[Q] Quit
[?] Help

Command: Q


As we consider the example above, we see some patterns emerge:

What happens when a particular command is executed is specific to a particular program. But there are plenty of features that are recurrent in every program like this one: showing the menu, asking the user to enter command strings, matching those command strings to commands on the menu, associating a description with every command string, and offering commands like "help" that would be useful in every program. It is these recurrent features that we should be able to encode using Menuba, leaving only the business logic — what happens when each command is executed? — to be written using Java.

Menuba's mandate, then, is to describe a command menu. A Menuba script will be written that describes, for each command on a command menu: what its command string is, what its description is, and what Java code should be called when it is executed.

It's important to note that we're not going to consider Menuba's syntax yet. We can, of course, but we don't need to; as long as we understand what kind of information will go into a Menuba script, we can always design the syntax later. (Part of why it's not a bad idea to postpone our syntax decision is that we might discover that we left important details out; these might have a dramatic impact on our syntax. So why commit to a syntax early when we can put it off until we're more comfortable with where we're trying to go?)

The prototype program

For this part of the assignment, write a prototype program with a console-mode user interface that maintains a list of names. It provides six commands:

Be sure that you're maintaining a focus on the design of your prototype as you work. The objective here is not to write just any Java program that meets the requirements; the challenge is in finding a design that keeps the three necessary parts (the command menu, the runtime library, and the business logic) separate.

Once you have an implementation of the program that you believe is designed well enough for this purpose — with the three parts separate — you'll be ready to proceed to Part 2.

Part 2: Implementing Menuba (50 points)

Considering a syntax for Menuba

Now that we've successfully defined the boundaries between the command menu (i.e., the code that our Menuba compiler will generate), the runtime library, and the business logic, we'll be able to begin our implementation of Menuba. Before we can get too much farther, we'll have to decide what Menuba will look like. We'll need to find a syntax that encodes all of the information that we identified as necessary to describe a command menu, based on the design from Part 1:

With that information in mind, a Menuba script will look like this:

    // This is an example Menuba script, describing a program -- which you
    // will not have to write -- that does Google queries from the console.

    package inf102.assignment5.example;
    menu ExampleMenu -> CurrentQueryState
        "Q": "Execute a search query"       -> ExecuteQuery;
        "S": "Show next 10 results"         -> ShowPastResults;
        "C": "Clear the current query"      -> ClearQuery;
        "X": "Exit"                         -> Exit;

From the example, we see that Menuba has a somewhat Java-like syntax, including its support for Java packages and its use of curly braces for grouping, semicolons for termination, and two slashes to indicate a comment. It also uses a colon to separate the command string from its description, as well as an "arrow" (a dash followed by a greater-than) to separate the command from the name of a class containing the code that handles it. Like most (though not all) languages, big and small, whitespace is considered irrelevant, except when it separates words from one another (e.g., between "menu" and "ExampleMenu"), though the amount of whitespace and the layout of the Menuba code is not important for any reason other than a stylistic one.

A grammar for Menuba follows, with non-terminal symbols italicized and terminal symbols appearing as normal text. The word empty is a special one, indicating that a non-terminal symbol can expand to nothing.

A couple of lexical rules

The lexical rules of a language describe what kinds of tokens (i.e., individual words, symbols, etc.) can appear legally in that language. Our lexical rules are:

Writing a Menuba compiler

For this part of the assignment, you will write a Menuba compiler, which takes a Menuba script and generates a Java class that implements the menu it describes. Note that you'll need your code from Part 1, particularly the code you identified as being in your runtime library. Beyond that, you'll need the following components:

Use packages to organize your code in the following way:

There are no absolute requirements on the code that you generate, other than it can be combined with your runtime library and business logic to write a command-line user interface. Specifically what you generate depends on the design of your runtime library, which I've left as an open issue for you to solve.

Part 3: Using Menuba (20 points)

Rewrite your program from Part 1 using a combination of Menuba and Java. Compile your Menuba script(s) and combine them with your runtime library and business logic, ensuring that the program still works as it did.

If you're able to do this, you're in business! Menuba is complete.


For Part 1, submit a zip archive containing all of the .java files that make up your prototype.

For Part 2, submit a zip archive containing all of the .java files that make up your compiler and runtime library.

For Part 3, submit a zip archive containing your Menuba script and your business logic. We will combine this with your runtime library from Part 2 and use the compiler to generate the necessary code from the Menuba script.

Follow this link for a discussion of how to submit your assignment via Checkmate. Be aware that I'll be holding you to all of the rules specified in that document, including the one that says that you're responsible for submitting the version of the assignment that you want graded. We won't regrade an assignment simply because you submitted the wrong version by accident.