CS 503 - Advanced Programming I Programming Assignment 7

Programming Assignment 7 - Grammar Rule Ordering

Advanced Programming I, Spring 2007

Due Date

This assignment is due by 5:30 p.m. on Tuesday, 1 May.

See the assignment turn-in page (last modified on 14 January 2006) for instructions on turning in your assignment.

Background

A grammar defines a language by using a set of grammar rules. Each grammar rule has the form

nonterminal : ( nonterminal | terminal )*

Nonterminals are distinguished from terminals by appearing to the left of the colon in a rule; terminals do not appear to the left of a colon in any rule in a grammar. Here is a small portion of a grammar:

if-statement : if guard then statement
guard : expression rel-op expression
statement : if-statement

Given a grammar, there are (at least) two ways to print it out. One way is by alphabetical order on the nonterminal to the left of the colon in each rule. Ordering the rules alphabetically makes it easy to locate any particular rule, but makes it inconvenient to find the rules used by a particular rule because they may be widely separated by other rules.

The second way of organizing rules is group the rules using a nonterminal (appearing to the right of a colon) are near the rules defining the nonterminals (appearing the the left of a colon). This makes it hard to locate any particular rule, but easy to find the rules related to a particular rule.

The nearness of two rules in a list can be characterized by the distance between the rules, which is measured by the number of rules between the two rules. In the example above, the if-statement and statement rules are at distance 1; the guard and statement rules are at distance 0.

Given a list of rules, the list distance is the sum of the distances between every (unordered) pair of rules on the list. A pair of rules that are not related to one another (that is, neither rule uses a nonterminal defined by another) have distance 0.

The Problem

Write a program that reads a list of rules from std-in and writes to std-out the rule list re-ordered to have minimal list distance.

Input

Input is a list of grammar rules; each grammar rule appears on one line in the format given above and each line contains at most one grammar rule. Both nonterminals and terminals are words; adjacent words are separated by at least one non-newline space character, as is the colon and adjacent words.

Input not in the proper format should result in an informative error message followed by an immeidate end of the program with no futher output.

Output

The program should output the minimal list distance found followed by the list having the minimal list distance in the same format as the rules input (one per line, space separated words, and so on).

Error message should be printed to std-err preceeded by a "! " (that's a bang-space).

Testing

The program gen-grammar in the assignment directory /export/home/class/cs-503/a7 writes to std-out a randomly-generated set of grammar rules. Because gen-grammar creates new input each time it's run, you might find it more convenient to save the input in a file to provide your program with consistent input:

$ ./gen-grammar > input

$ ./order-rules < input

My solution order-rules is also available in the class assignment directory. Remember the purpose of this assignment is to implement a correct solution, not to copy the behavior of my solution. If my solution's wrong and you copy the incorrect behavior, you're going to lose points.

This page last modified on 27 April 2006.