Programming Assignment #1
Simple Music Synthesizer Language

Due by 12PM Eastern Time on Tuesday, February 17, 2009.

Late Policy:  No late assignments will be accepted.

Introduction

In this assignment, you will implement a very simple music synthesizer language SYNTH.  SYNTH has three basic musical operators:  PLAYNOTE, REST, CHANGE_INSTRUMENT.  PLAYNOTE plays a specified "musical note" for a given number of "beats" (a beat is a musical term for the basic unit length of time).  The synthesizer is monophonic which means only one note can be played at any given time.  REST specifies the number of consecutive beats that the synthesizer should be silent.  The CHANGE_INSTRUMENT operator specifies the instrument that the synthesizer should set as its current instrument.  The synthesizer has 16 different instruments (many of them will sound very similar).   In addition to the musical operators, SYNTH includes variables, simple integer arithmetic operators,  and a REPEAT loop construct.  A SYNTH program specifies an algorithm for constructing a sequence of notes and rests to be played on your machine.

Your implementation of SYNTH will have two distinct phases:
1. The compilation phase:  You will parse and compile a program written in SYNTH into a lower-level language miniSYNTH which only has three instructions (PLAYNOTE, REST, CHANGE_INSTRUMENT) and no additional language constructs.  Your compiler will incorporate a recursive descent parser written in Perl or Python (your choice).
2. The interpretation phase:  You will interpret the "intermediate" miniSYNTH program by writing an interpreter in Java.  The interpreter will produce the audible musical sequence specified by the original SYNTH program code.

PHASE I: SYNTH Recursive Descent Parser & Compiler (written in Perl or Python)

The grammar for SYNTH is as follows:
< synth_program>    -->  < declaration_list>  < statement_list> eof
< declaration_list> --> < declaration> < declaration_list> | e
< declaration>  --> DECL identifier
< statement_list> --> < statement> < statement_list> | e
< statement> -->  < music_operation> | < repeat_statement>  | < variable_operation>
< music_operation> --> PLAYNOTE < argument> < argument>
                           |REST < argument>
                           |CHANGE_INSTRUMENT < argument>
< repeat_statement> --> REPEAT < argument> < statement_list> END_REPEAT
< variable_operation> --> ASSIGN identifier < argument>
                           | ADD identifier < argument>
                           | SUB identifier < argument>
                           | MUL identifier < argument>
                           | DIV identifier < argument>
< argument> --> identifier |integer

The boldface symbols represent the language operator, e represents the empty string, and eof represents the end-of-file character.  Note that this is a free format language, so tokens can be separated by one or more whitespaces, tabs and end of line characters.   Your parser should be case-sensitive.  The two literals identifier and integer are generated by the following regular expressions:

< identifier> --> < letter> { < letter> | < digit> | _ } *
< integer> -->[+|-] < digit> { < digit> } *

The semantics of the SYNTH language are relatively straightforward.   There are 128 possible notes on the synthesizer with '0' corresponding to the lowest and '127' to the highest (for the musically inclined, a value of 60 typically represents a middle C note on a piano and consecutive integers represent half-steps).   The synthesizer has 16 instruments mapped to the integer values of 0 to 15.  The default instrument will be '0'.  The semantics of the music operators are:

1. PLAYNOTE arg1 arg2  : Plays (and holds) the note corresponding to the value of (arg1 mod 128) for arg2 consecutive beats.  A beat corresponds to 50 milliseconds.  If arg2 is zero or negative, then the PLAYNOTE instruction will be ignored.  The following example plays a note corresponding to 2 for one second:
* PLAYNOTE 130 20

2. REST arg1 : maintains silence on the synthesizer for arg1 consecutive beats.  The following example maintains 100 milliseconds of silence:
* REST 2

3. CHANGE_INSTRUMENT arg1 : changes the current instrument to the instrument corresponding to the value (arg1 mod 16).  For example, the following example instruction changes the current instrument to 3:
* CHANGE_INSTRUMENT 19

SYNTH has variables that hold integer values.  All variables must be declared in the declaration section (if a variable is used without being declared, you should output a syntax error).   During the declaration of a variable it is assigned a default value of 0. Each variable operator receives two parameters, a variable name and an argument.  The result of the operation is stored in the variable.  Note that the DIV operator divides the variable value by the specified argument.  Furthermore, the real portion of the resulting quotient is truncated, so that the stored value is integer.  For instance,

DECL A
DECL B
ASSIGN B 4
ASSIGN A 10
DIV A B

has variable A equal to 2 and variable B equal to 4 after execution. 

The semantics of the REPEAT ... END_REPEAT block is to execute the nested code block for the number of times specified in the argument.

Your recursive descent parser should be able to correctly parse any syntactically correct SYNTH program.  If the parser is supplied a syntactically incorrect program, it should output a descriptive syntax error message.  The result of your parser/compiler when supplied a SYNTH program should be a syntactically correct miniSYNTH program.  The grammar for miniSYNTH is:

< mini_synth_program>    --> < music_statement_list> eof
< music_statement_list> --> < music_operation> < music_statement_list> | e
< music_operation> --> PLAYNOTE integer integer
                           |REST integer
                           |CHANGE_INSTRUMENT integer

The SYNTH program is basically compiled into a sequence of musical operations.  Here is an example SYNTH program;  this is the miniSYNTH output from the parser/compiler.  It is up to you to design and use the algorithms/data structures to successfully compile a SYNTH program into miniSYNTH code.  

The parser/compiler should be invoked by

perl synth.pl program_name

OR

python synth.py program_name

where program_name is the name of the file containing the SYNTH source code.  The resulting miniSYNTH code should be written to standard output.

PHASE II: miniSYNTH Interpreter (written in Java)

The miniSYNTH interpreter generates sound based on the sequence of music operator commands it reads from an input miniSYNTH program.   The job of the interpreter is to create the audio from this sequence of music operator commands.  I have provided the following Java package algo_music.ToySynthesizer to produce the sounds.  The ToySynthesizer class has four public subroutines:

1. ToySynthesizer(); //constructor
2. void PlayNote(int note, int num_beats);
3. void Rest(int num_beats);
4. void ChangeInstrument(int instrument_num);

The semantics of the ToySynthesizer API are exactly the same as the music operations of SYNTH.  Therefore, it should be very straightforward to implement the interpreter for miniSYNTH.  Here is an example Java program that uses algo_music.ToySynthesizer.   (It will be a good idea to compile and run the test program to ensure that your machine supports the needed sound hardware/software.  Please contact me immediately if you have trouble with producing sound with this test program.  Though it is possible to complete the assignment without having sound capabilities, it will not be as fun or rewarding.)

There should be two possible ways to invoke your interpreter.  The first is to read a miniSYNTH file:

java minisynth -f mini_program_file

The second reads the miniSYNTH program directly from the output stream of the SYNTH compiler:

perl synth.pl synth_program_file | java minisynth
OR
python synth.py synth_program_file | java minisynth

What to Hand-in:

You should send me an email titled "COMP524 Program1" and attach a zip file called yourlastname.zip containing the following files:

1.The Perl source program that implements the parser/compiler.  The program file name should be synth.pl or synth.py .

2. The Java source program that implements the interpreter.  The program file name should be miniSYNTH.java.

3. A document (one or two pages, at most) describing your solution for both the parser/compiler and interpreter.  The document should also contain any special instructions on running your code. 

4. A SYNTH program that plays the sequence of the first 40 fibonacci numbers.  (Do not hardcode the sequence - use the SYNTH language constructs).

5. Another SYNTH program of your choosing (either an original composition or a previously published song).  I'm not grading the composition on the content; so this is your chance to be really creative!

Software:

Your parser/compiler should be written for Perl 5.8.8 (obtainable from  www.perl.org) or Python 2.5.1 (obtainable from  www.python.org) .  The interpreter written in Java should run on Java 2 Standard Edition 5 (J2SE 1.5.0) .  You can obtain this from:

http://java.sun.com/javase/downloads/index_jdk5.jsp

I cannot grade assignments that I cannot compile.  Therefore, please ensure that your code compiles using the above software.  In particular, note that major changes in the Python language accompanied its very recent version 3 release.  Please use only version 2 for this assignment if you choose to implement your parser/compiler in Python.   Further links to documentation for Perl, Python, and Java languages are maintained on the respective sites.

Grading:

Your assignment will be graded not only on the ability to be correctly compiled and produce the correct output, but also on the correct and efficient use of language constructs provided by Perl/Python, Java, and SYNTH.  For instance, for matching the tokens you should use Perl/Python's pattern matching and string manipulation functionality instead of writing your own.  I will grade both the quality of the source code (design and documentation) and the output. Collaboration is encouraged, but you cannot share source code. The Honor Code applies to this program. Please, read
http://www.cs.unc.edu/Admin/Courses/HonorCode.html
for more details.
-- GOOD LUCK AND HAVE FUN --