Introduction

Cavy is a heavily restricted subset of C. As Cavy is a subset of C, Cavy programs can be compiled and executed using gcc.

Your program will be given as input a Cavy program. Its must output Emu Assembly Language which is equivalent to the Cavy program.

Your program does not have to execute the Cavy program. It only has to output equivalent Emu Assembly Language.

This Emu Assembly Language can be tested by executed it using the emulator /home/cs1721/bin/emu. When executed it should behave exactly as the Cavy program does when compiled and executed using gcc.

The Emu subset has been extended from that described for assignment 1 by including the AVR's S bit (status register bit 4). This simplifies generating code for comparison operations (<, >, <=, >=). The MUL instruction has also been added. This is useful for Cavy(4+).

Cavy Description

Each version is a larger subset of C than previous versions. Each version contains all previous versions.

Note, a program can only be a valid Cavy programs if it is a valid C program.

Cavy(0)

A Cavy(0) program consists of a single function, main

This main function has no arguments. There is no way to pass command-line arguments to Cavy programs.

No return type is specified for main.

A Cavy program can not contain top-level variables.

The body of the main function can contain only: variable declarations, assignment statements and calls to certain functions.

All variable declarations must occur at the start of the function before statements of any other type.

A Cavy(0) program can not contain compound statements formed with braces {}.

Statements can not be empty.

Statements can not have labels.

A variable declaration can only be the declaration of single variable of type char. There is no initialization of variables in declarations.

A Cavy(0) program will contain no more than eight variable declarations.

Variables must be assigned a value before they are used.

Only five functions may be called: get_c, get_i, put_c, put_h, put_i.

char get_c(void) reads an character (byte) from standard input

char get_i(void) reads an integer in the range -128..127 from standard input

void put_c(char c) prints a character (byte) on standard output.

void put_h(char c) prints a hexadecimal integer in the range 0x00..0xff on standard output.

void put_i(char c) prints a decimal integer in the range -128..127 on standard output.

The left of an assignment statement can contain only a variable name. The right of an assignment statement can contain only a single expression.

An expression can contain only variables, constants, calls to get_i & get_c and the 3 operators: +, -, *.

All operator must have two operands. +,- can not be used as unary operator. For example, x = -42 is not a legal Cavy(0) statement. However, x = 0 - 42 is a legal Cavy(0) statement.

Expressions can not contain brackets or type casts.

Expressions can not contain more than one operator. For example, x = y + z + 2 and a = b * 2 - 7 are not a legal Cavy(0) statements because both expressions contain more than one operator.

A constant can be a decimal integer (e.g. 42), a hexadecimal integer (e.g. 0x2a) or a character (e.g. '*').

There is one difference between Cavy and C. Cavy constants are of type char, i.e. 8 bits. In C unless otherwise specified, integer constants are of type int. This has no impact on most programs. But if constants or intermediate arithmetic results overflow a char (8 bits) then a Cavy program may behave differently when compiled with gcc.

There is only 1 keyword which can appear in Cavy(0) program: char.

Here are some examples of Cavy(0) programs.

Below is a grammar describing the syntax of Cavy(0) programs.

Note that not all requirements for Cavy(0) program are captured by this grammar. For example, all variables must be declared.

Program	-->	main ( ) { Declarations Statements }
Declarations	-->	Declaration Declarations
	-->
Declaration	-->	char Identifier ;
Statements	-->	Statement Statements
	-->
Statement	-->	FunctionCall ;
	-->	Assignment ;
Assignment	-->	Identifier = Expression
FunctionCall	-->	get_c ( )
	-->	get_i ( )
	-->	put_c ( Expression )
	-->	put_h ( Expression )
	-->	put_i ( Expression )
Expression	-->	Operand Operator Operand
	-->	Operand
Operand	-->	Constant
	-->	FunctionCall
	-->	Identifier
Operator	-->	+ - *

Cavy(1)

Cavy(1) programs may contain while and if statements.

If statements can not contain an else part.

While statements can not contain break or continue.

Compound statements may be formed with braces {}.

Cavy(1) programs may contain up to 32 variable declarations.

Cavy(1) expressions may also contain the operators ==, !=, <, >, >=, <=, &, |, ^

As in Cavy(0), expressions can not contain more than one operator.

There are only 3 keywords which can appear in a Cavy(1) program: char, while, if.

Here are some examples of Cavy(1) programs.

Below is a grammar describing the syntax of Cavy(1) programs.

Program	-->	main ( ) { Declarations Statements }
Declarations	-->	Declaration Declarations
	-->
Declaration	-->	char Identifier ;
Statements	-->	Statement Statements
	-->
Statement	-->	FunctionCall ;
	-->	Assignment ;
	-->	if ( Expression ) Statement
	-->	while ( Expression ) Statement
	-->	{ Statements }
Assignment	-->	Identifier = Expression
FunctionCall	-->	get_c ( )
	-->	get_i ( )
	-->	put_c ( Expression )
	-->	put_h ( Expression )
	-->	put_i ( Expression )
Expression	-->	Operand Operator Operand
	-->	Operand
Operand	-->	Constant
	-->	FunctionCall
	-->	Identifier
Operator	-->	+ - * & | ^ != == < <= > >=

Cavy(2)

Cavy(2) is the exactly the same as Cavy(1) except as indicated below.

Cavy(2) programs may contain up to 2048 variable declarations.

Cavy(2) programs may contain for, break and continue statements.

The initialization and step parts of a for loop must be a single assignment statement. They can not be empty.

The control expression of a for loop can not be empty.

An else part may be present on if statements.

As in Cavy(1), expressions can not contain more than one operator

There are only 7 keywords which can appear in a Cavy(2) program: char, while, if, else, break, continue for.

Here are some examples of Cavy(2) programs.

Below is a grammar describing the syntax of Cavy(2) programs.

Program	-->	main ( ) { Declarations Statements }
Declarations	-->	Declaration Declarations
	-->
Declaration	-->	char Identifier ;
Statements	-->	Statement Statements
	-->
Statement	-->	FunctionCall ;
	-->	Assignment ;
	-->	break ;
	-->	continue ;
	-->	if ( Expression ) Statement
	-->	if ( Expression ) Statement else Statement
	-->	while ( Expression ) Statement
	-->	for ( Assignment ; Expression ; Assignment ) Statement
	-->	{ Statements }
Assignment	-->	Identifier = Expression
FunctionCall	-->	get_c ( )
	-->	get_i ( )
	-->	put_c ( Expression )
	-->	put_h ( Expression )
	-->	put_i ( Expression )
Expression	-->	Operand Operator Operand
	-->	Operand
Operand	-->	Constant
	-->	FunctionCall
	-->	Identifier
Operator	-->	+ - * & | ^ != == < <= > >=

Cavy(3)

Cavy(3) is the exactly the same as Cavy(2) except as indicated below.

One dimensional char arrays may appear in Cavy(3) programs. Their size must be an integer constant in the range 1..127.

Arrays can not be used in Cavy(3) statements without an index.

The operators &&, || and ! can appear in Cavy(3) expressions.

The operators + and - can be used as unary operators, i. e. they may have only one operand. For example, x = -y is a legal Cavy(3) statement.

As in Cavy(1), expressions can not contain more than one operator.

There are only 7 keywords which can appear in a Cavy(3) program: char, while, if, else, break, continue, for.

Below is a grammar describing the syntax of Cavy(3) programs.

Program	-->	main ( ) { Declarations Statements }
Declarations	-->	Declaration Declarations
	-->
Declaration	-->	char Identifier ;
		char Identifier [ Constant ] ;
Statements	-->	Statement Statements
	-->
Statement	-->	FunctionCall ;
	-->	Assignment ;
	-->	break ;
	-->	continue ;
	-->	if ( Expression ) Statement
	-->	if ( Expression ) Statement else Statement
	-->	while ( Expression ) Statement
	-->	for ( Assignment ; Expression ; Assignment ) Statement
	-->	{ Statements }
Assignment	-->	Identifier = Expression
		Identifier [ Expression ] = Expression
FunctionCall	-->	get_c ( )
	-->	get_i ( )
	-->	put_c ( Expression )
	-->	put_h ( Expression )
	-->	put_i ( Expression )
Expression	-->	Operand Operator Operand
	-->	PrefixOp Operand
	-->	Operand
Operand	-->	Constant
	-->	FunctionCall
	-->	Identifier
	-->	Identifier [ Expression ]
PrefixOp	-->	+ - !
Operator	-->	+ - * & | ^ != == < <= > >= && ||

Cavy(4) (Bonus)

The types short, char [] and short [] may appear in variable declarations.

Shorts are 16 bits in Cavy(4) programs. A Cavy(4) function put_s prints a short. Note, there is no corresponding Emu system call.

Cavy(4) expressions may contain any number of operators.

Cavy(4) expressions may contain brackets.

There are only 8 keywords which can appear in a Cavy(4) program: char, short, while, if, else, break, continue, for.

Declaration	-->	char Identifier ;
		short Identifier ;
		char Identifier [ Constant ] ;
		short Identifier [ Constant ] ;
Statements	-->	Statement Statements
	-->
Statement	-->	FunctionCall ;
	-->	Assignment ;
	-->	break ;
	-->	continue ;
	-->	if ( Expression ) Statement
	-->	if ( Expression ) Statement else Statement
	-->	while ( Expression ) Statement
	-->	for ( Assignment ; Expression ; Assignment ) Statement
	-->	{ Statements }
Assignment	-->	Identifier = Expression
		Identifier [ Expression ] = Expression
FunctionCall	-->	get_c ( )
	-->	get_i ( )
	-->	put_c ( Expression )
	-->	put_h ( Expression )
	-->	put_i ( Expression )
	-->	put_s ( Expression )
Expression	-->	Expression Operator Expression
	-->	PrefixOp Expression
	-->	( Expression )
	-->	Operand
Operand	-->	Constant
	-->	FunctionCall
	-->	Identifier
	-->	Identifier [ Expression ]
PrefixOp	-->	+ - !
Operator	-->	+ - * & | ^ != == < <= > >= && ||

Cavy(5) (Bonus)

Cavy(5) is the exactly the same as Cavy(4) except as indicated below.

A Cavy(5) program may contain multiple functions.

A Cavy(5) program will still consist only of a single file.

A Cavy(5) program may contain struct definitions. These will appear only at the top level before any function definitions.

Cavy(5) program can not contain top-level variable declarations.

The type void may appear in Cavy(5) programs. structs may appear in Cavy(5) programs.

The allowed types for function parameters and the return values of function are the same as variables. Except structs can not be passed as function parameters or returned by functions. and arrays can not be returned by functions.

Arrays can not apper without indices in Cavy(5) expressions, except they may be passed as function parameters.

Cavy(5) function definitions always appear before the functions are used.

Functions may called themselves but indirect recursion is impossible in Cavy(5).

return statements may appear in Cavy(5) programs.

The operators ++ and -- may appear in expressions but only as postfix operators at the top-level.

The operator . (structure member) may appear in expressions.

There are only 11 keywords which can appear in a Cavy(5) program: char, short, while, if, else, break, continue, for, void, struct, return.

Program	-->	Structs Functions
Structs	-->	Struct_Def Structs
Structs	-->
Struct_Def	-->	struct Identifier { Fields } ;
Fields	-->	Type Identifier ; Fields
Fields	-->
Functions	-->	Function_Def Functions
Functions	-->
Function_Def	-->	Type Identifier ( Parameters ) Function_Body
	-->	main ( ) Function_Body
Function_Body	-->	{ Declarations Statements }
Parameters	-->	Declaration MoreParameters
	-->
MoreParameters	-->	, Declaration MoreParameters
	-->
Declarations	-->	Declaration ; Declarations
	-->
Declaration	-->	Type Identifier
	-->	Type Identifier [ Constant ]
Type	-->	struct Identifier
	-->	char
	-->	short
	-->	void
Statements	-->	Statement Statements
	-->
Statement	-->	FunctionCall ;
	-->	Assignment ;
	-->	break ;
	-->	continue ;
	-->	return Expression ;
	-->	return ;
	-->	if ( Expression ) Statement
	-->	if ( Expression ) Statement else Statement
	-->	while ( Expression ) Statement
	-->	for ( Assignment ; Expression ; Assignment ) Statement
	-->	{ Statements }
Assignment	-->	Expression = Expression
	-->	Expression ++
	-->	Expression --
FunctionCall	-->	get_c ( )
	-->	get_i ( )
	-->	put_c ( Expression )
	-->	put_h ( Expression )
	-->	put_i ( Expression )
	-->	put_s ( Expression )
	-->	Identifier ( Arguments )
Arguments	-->	Expression MoreArguments
	-->
MoreArguments	-->	, Expression MoreArguments
	-->
Expression	-->	Expression Operator Expression
	-->	PrefixOp Expression
	-->	( Expression )
	-->	Operand
Operand	-->	Constant
	-->	FunctionCall
	-->	Identifier
	-->	Identifier [ Expression ]
PrefixOp	-->	+ - !
Operator	-->	+ - * & | ^ != == < <= > >= && || .

Cavy I/O

Your compiler must translate calls to the these functions to the appropriate Emu instructions. Note, there is an appropriate system call for each.

When preparing test data, you may wish to compile and run Cavy programs using gcc. The file cavy_lib.c allows you to do this. It provides C implementations of get_c, get_i, put_c, put_h and put_i

Note, you do not need cavy_lib.c to complete the assignment. Your compiler should not use the functions in cavy_lib.c.

There is a header file cavy_lib.h which you must include in Cavy programs if you wish to compile them with gcc. The #include will be removed by the lexical analysis software you have been given, so it will not affect your translation of the Cavy program to Emu assembler.

Lexical Analysis

The first step when compiling a program is lexical analysis. This is the task of grouping characters into symbols. Fortunately this has been done for you.

The file cavy_syntax.c contains functions which implement lexical analysis for Cavy programs. It is strongly recommended, but not required that you use these functions. Note the functions in cavy_syntax.c are automatically generated and not intended to be human readable.

The functions in cavy_syntax.c read the characters from a file containing a Cavy program and translate them into symbols. Each symbol is represented from by an object from struct token. Examples of symbols are variable names, keywords and integer constants.

These are three functions in cavy_syntax.c which you may wish to use:

• token *get_token(void)

  Returns a struct token representing the next symbol in the Cavy program. The symbol is consumed. The next call to this function will return the next symbol. A struct token with type T_EOF is returned if there are no more symbols in the program.

• token *view_token(char n)

  Returns a struct token representing the symbol which is n symbols ahead. No symbols are consumed. view_token(0) will return the same struct token as get_token() would, but no symbols are consumed.

• char *token_type_to_string(token_type t) Convert a token type into a string - only needed for debugging.

You will need to use get_token.

You may not need to use view_token or token_type_to_string. They may or may not be convenient depending on how you write your program.

Here is the definition of struct token from cavy_syntax.h

typedef struct token token;

struct token {
    token_type      type;
    int             line_number;
    char            *text;
    int             int_value;
};

• type The category of the symbol. It will be one of the constants in enum token_type. See the table below
• int_valueThe value (as an int) of tokens of type CONSTANT.
• text The characters of the Cavy program which produced this token. Useful for tokens of type IDENTIFIER.
• line_number Indicates the line of the Cavy program which this token came from. May be convenient for error messages or debugging.

Note, the functions in cavy_syntax.c performs two useful tasks for you. They skip over comments and they convert each of the three type of integer constants to the appropriate value.

Do not change cavy_syntax.c or cavy_syntax.h.

These constants are the possible value of enum token_type.

Type	Symbol	Cavy level required for
T_CHAR	char	0
T_IDENTIFIER	name of variable or function	0
T_CONSTANT	e.g 42, 0x2a, '*'	0
T_ASSIGNMENT	=	0
T_LEFT_BRACE	{	0
T_RIGHT_BRACE	}	0
T_LEFT_PARENTHESIS	(	0
T_RIGHT_PARENTHESIS	)	0
T_MINUS	-	0
T_MULTIPLY	*	0
T_PLUS	+	0
T_SEMICOLON	;	0
T_GETC	get_c	0
T_GETI	get_i	0
T_PUTC	put_c	0
T_PUTH	put_h	0
T_PUTI	put_i	0
T_PUTS	put_s	4
T_EOF	end of file	0
T_IF	if	1
T_WHILE	while	1
T_AND	&	1
T_OR	|	1
T_EXCLUSIVE_OR	^	1
T_EQUALS	==	1
T_GREATER_THAN	>	1
T_GREATER_THAN_EQUALS	>=	1
T_LESS_THAN	<	1
T_LESS_THAN_EQUALS	<=	1
T_NOT_EQUALS	!=	1
T_BREAK	break	2
T_CONTINUE	continue	2
T_ELSE	else	2
T_FOR	for	2
T_LEFT_SQUARE_BRACKET	[	3
T_RIGHT_SQUARE_BRACKET	]	3
T_NOT	!	3
T_LOGICAL_AND	&&	3
T_LOGICAL_OR	||	3
T_SHORT	short	4
T_COMMA	,	5
T_DECREMENT	--	5
T_DOT	.	5
T_INCREMENT	++	5
T_RETURN	return	5
T_STRUCT	struct	5
T_VOID	void	5

A working compiler for Cavy(0-2) has been provided to assist you.

Your compiler does not have to translate a Cavy program to the same Emu instructions as this compiler. Nor is attempting to copy this compiler's behaviour necessarily a good idea. A shallow attempt to copy this compiler's behaviour is likely to fail. The techniques employed by this compiler are not necessarily the best.

Your task is to correctly translate Cavy programs to Emu instructions. The output from the supplied compiler may give you some inspiration.

Here is an example of the compiler in operation.

% /home/cs1721/bin/example_cavy_compiler /home/cs1721/public_html/05s2/cavy/examples/1/iota.c
% cat code.asm
...

Please report any compiler bugs you encounter.

Note you have to put your assembler in the file code.asm just as the code you have been given does.

Developing Your Program

The file cavy.c contains a starting point for this assignment.

You will need to change the C already in cavy.c.

You may add other top-level variables and functions to cavy.c program if you wish. You may create other .c or .h files .

You may use any functions from the standard C library.

Getting Started

% cd
% mkdir ass2
% chmod 700 ass2
% cd ass2
% ln -s /home/cs1721/public_html/05s2/cavy/cavy_syntax.[ch] .
% cp /home/cs1721/public_html/05s2/cavy/cavy.c .
% /home/cs1721/bin/dcc cavy.c cavy_syntax.c
% cp /home/cs1721/public_html/05s2/cavy/examples/0/0a.c .
% cat 0a.c
#include "cavy_lib.h"

main() {
    put_c('H');
    put_c('e');
    put_c('l');
    put_c('l');
    put_c('o');
    put_c(' ');
    put_c('W');
    put_c('o');
    put_c('r');
    put_c('l');
    put_c('d');
    put_c('\n');
}
% ./a.out 0a.c
% cat code.asm
        LDI R26, 72
        LDI R24, 3
        LDI R31, 0x70
        LDI R30, 0x00
        ICALL
...
% /home/cs1721/bin/emu_run code.asm
Hello World
% edit cavy.c

Optional Component

Up to 5 bonus marks are available for implementing compilation of Cavy(4) and Cavy(5) programs.

This optional component is very difficult and will require a great deal of work. Little assistance will be available for students attempting the optional component.

Hints

Translating Cavy(2) programs is difficult and complex. Don't be intimidated. Start by considering the translation of Cavy(0) programs. This is a much simpler task.

Look at very small Cavy(0) programs and work out what Emu instructions that they must be translated to.

Only when you can compile Cavy(0) programs correctly, consider the larger subsets.

Note, a Cavy(0) can contain at most 8 variables so you can store each variable in a register. You'll have to keep track of which register each variable is stored in.

If even Cavy(0) seems too complex, first try just extending the code you've been given to handle some more cases.

The number of variables in a Cavy(1) program can exceed the number of Emu registers so you will have to store variables in data space (SRAM) using the Emu LDD and STD instructions.

It may be helpful to write functions corresponding to each language structures, e.g a function to handle a statement, a function to handle an expression, etc. For Cavy(4) and above you may it useful if some of these functions are recursive.

Allow though you do not have to check for errors in the Cavy program, such error messages can assist in debugging your compiler.

Assumptions

You can assume the input you are given is a valid Cavy program. so, for example, you do not have to check for syntax errors and you do not have to check that variables are declared before used.

You can assume there is a single main function in every Cavy source code file.

You can assume that the program will execute correctly without runtime errors.

You can assume that each Cavy subsets contain only the features explicitly indicated as belonging to that subset, or the subsets it contains. Hence, for example, you can assume no Cavy programs contain typedefs, function pointers, initialization of variables in declarations, ...

You can assume that a feature excluded by the grammar is absent from the subset.

You can assume that a feature excluded by the written description is absent from the subset.

There is no penalty for your compiler handling input programs which are not valid Cavy programs. You may compile programs beyond the specified Cavy subsets.

You can emit any Emu assembler which correctly implements the program. For example, given this fragment of Cavy:

    x = 20;
    y = 22;
    z = x + y;
    put_i(z);

    LDI R26, 42
	LDI R24, 3
	LDI R31, 0x70
	LDI R30, 0x00
	ICALL

The assembler you produce does not have to be readable. It will be (auto)marked only for correctness. You will find debugging easy if you generate well formatted assembler with (automatically generated) comments.

Marking

The assignment is worth 15% of your final COMP1721 mark. The marking scheme for this assignment will recognise its difficulty. 80% of the marks for this assignment will come from testing your program automatically on a number of Cavy programs You will receive marks according to how many Cavy programs your compiler handles correctly.

Your program will receive marks for correctly compiling a test program even if it has incorrectly compiled a program from a lower subset. For example, even if your program fails to compile some Cavy(3) programs correctly, you can receive marks for correctly compiling a Cavy(4) program. Some test programs will try to test parts of each subset in isolation. This should ensure you receive marks for implementing only part of a subset.

The testing will check only that the Emu code produced is correct. The efficiency or size of the Emu code does not matter. There are no marks for the formating the Emu code neatly but you will find debugging easy if you generate well formatted assembler with (automatically generated) comments.

The test programs used will be different to the ones you have been supplied.

20% of the marks for this assignment will come from hand marking by your tutor. These marks will be awarded on the basis of clarity, commenting, elegance and style. In other words, your tutor will assess how easy it is for a human to read and understand your program.

Here is an indicative marking scheme (out of 15).

Programs which compile few or noCavy programs but contain some correct useful C will be entirely hand-marked and will likely receive marks between 5/15 and 7/15.

The lecturer may vary the above marking scheme after seeing the assignment submissions.

Implementation Diary

You must keep a record of all work on your assignment. The entries should include date, starting time, finishing time, general category, and a brief (one or two line) description of the work carried out. For example:

Your implementation diary should be placed in a file named diary.txt. The diary will not be marked but there is a 20% penalty if you fail to provide it.

Testing and Defect History

You also should also keep a record of your testing of your programs and a defect history for your work. This should give the general approach to testing you used and the results of your testing.

This description should also contain a bug tracking report. This should describe when major bugs appeared and were removed from your program.

Your testing description should be placed in a file named testing.txt. Again there is a 20% penalty if you fail to provide this section.

Originality of Work

The work you submit must be your own work. Submission of work partially or completely derived from any other person or jointly written with any other person is not permitted. The penalties for such an offence may include negative marks, automatic failure of the course and possibly other academic discipline. Assignment submissions will be examined both automatically and manually for such submissions.

Relevant scholarship authorities will be informed if students holding scholarships are involved in an incident of plagiarism or other misconduct.

Do not provide or show your assignment work to any other person - apart from the teaching staff of Higher Computing 1B. If you knowingly provide or show your assignment work to another person for any reason, and work derived from it is submitted you may be penalized, even if the work was submitted without your knowledge or consent. This may apply even if your work is submitted by a third party unknown to you.

Note, you will not be penalized if your work is taken without your consent or knowledge.

Submission

You must submit your assignment using the give command, e.g.:

         give cs1721 cavy a.h b.h a.c b.c c.c d.c

Note, all files must be submitted together.

Your assignment is due at 23:59pm Monday October 31

Note, submission even one second after this deadline is considered as one day late.

If your assignment is submitted after this date, each day it is late reduces the maximum mark it can achieve by 20%. For example if an assignment worth 76% was submitted one day late, the late submission would have no effect. If the same assignment was submitted 2 days late it would be awarded 60%, the maximum mark it can achieve at that date.

Bonus marks are not available for late assignments.