Team Members

• Thomas Fuhrmann: tfuhr (at) cosy .sbg .ac . at
• Bernhard Neuhofer: bneu (at) cosy . sbg . ac . at
• Markus Rabenberger: mraben (at) cosy . sbg . ac . at

Project Status:

1. Scanner: finished
2. Parser: finished
3. Codegeneration: nearly complete
4. Self compilation:not complete

Characteristics

Input Language:

Subset of existing programming language Pascal (therefore with defined semantics)

We used GNU Pascal version 20040516, based on gcc-3.4.4

• Control Structures:
  • while loop
  • if then else

• Encapsulation:
  • procedures
  • units: not entirely

• Data Types:
  • simple types:
    • boolean: 4 byte
    • integer: 4 byte
    • char: 4 byte

  • structured types:
    • array
    • records
    • pointers

Reserved Words:

Input Language in EBNF

    
letter	= 'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'|'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z'.

blank	= ' '|CR LF|CR|LF.

String-element	= ':'|'<'|'>'|'#'|';'|','|"."|"!"|"["|"]"|"("|")"|"\".

boolean	= true|false.

digit	= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'.

identifier	= letter{ letter|digit} .

digit-sequence	= digit {digit}.

sign 	= '+'|'-'.
integer 	= [sign] digit-sequence.

characterstring	= letter|digit|string-element|blank {letter|digit|string-element|blank}.

string	= "'" characterstring "'".

comment	= "{" characterstring "}".

programheader	= "program" identifier.

typedenoter	= "integer"|"char"|"string"|"boolean".

identifierlist	= identifier {"," identifier}.

variabledeclaration	= identifierlist":" typedenoter.

variabledeclarationpart	= ["var" variable-declaration ";" {variabledeclaration ";"}].

procedureidentifier	= identifier.

procedureheading	= "procedure" procedureidentifier [formalparameterlist].

procedureblock 	= block.
	
formalparameterlist 	= "(" [var] variable-declaration ";" { [var] variabledeclaration ";"} ")".


proceduredeclaration	= procedureheading ";" procedureblock.

proceduredeclarationpart	= {proceduredeclaration ";"}.

program	= programheader ";" programblock ".".

block	= variabledeclarationpart proceduredeclarationpart statementpart.

statementpart	= "begin" statementsequence "end".

statementsequence 	= statement { ";" statement }.

statement 	= simplestatement|structuredstatement.

simplestatement	= emptystatement|assignmentstatement|procedurestatement.

structuredstatement	= compoundstatement|conditionalstatement|whilestatement.

emptystatement	= .
assignementstatement	= indentifier ":=" simpleexpression.

procedurestatement	= procedureidentifier ().

conditionalstatement	= "if" booleanexpression "then" statement  [elsepart].

elsepart	= "else" statement.

booleanexpression	= simpleexpression [relationaloperator simpleexpression].

relationaloperator	= "<"|">"|"="|"<="|">="|"<>".

addingoperator 	= "+"|"-".

mulitplyingoperator	= "*"|"/".

simpleexpression 	= [sign] term {addingoperator term}.

term	= factor {multiplyingoperator factor].

factor  	= integer| parseidentifier | "(" simpleexpression ")".

whilestatement	= "while" booleanexpression "do" statement.

compoundstatenment	= "begin" statementsequence "end".

program 	= programheading {procedure} programblock.

parseidentifier = identifier ['[' parseidentifier | integer ']' ]  [ '^' ] ['.' parseidentifier ] [ '^' ]


array-type = 'array' '[' subrange-type { ',' subrange-type } ']' 'of' typedenoter .
subrange-type = parseidentifier '..' parseidentifier

record-type = 'record' field-list 'end' .

field-list = variabledeclaration { ';' variabledeclaration }.

 

Virtual Machine:

Registers and Memory

Our VM architecture provides 32 general-purpose registers of 32 bits each that are named R0 - R31. Two of these registers have special roles:

• The value of register R0 is always zero.
• Branch instructions to subroutines implicitly use register R31 to store the

   return address.

Memory is 1024 Kbytes divided into words of 32 bits and is word-addressed.

Runtime Environment

In our case, the following rule applies (in addition to the special handling of R0 and R31):

• By convention, register R29 is used as the frame pointer.
• By convention, register R30 is used as the stack pointer.

Instruction Formats

Instructions are 32 bits in length and start with a 6-bit opcode. The remaining bits depend on the nature of the opcode and follow one of three instruction formats that we call F1, F2, and F3.

Example Program

        i:=0;
        while (i<b) do
        begin
                if (i<5) then
                begin
                        i:=i+1;
                end
                else
                begin
                        i:=i+5;
                end;
        end;

        a(10);

 LDW a: 29 b: 0 c: 0

 LDW a: 30 b: 0 c: 0 

 BEQ a: 0 b: 0 c: 25 

 PSH a: -1 b: 30 c: 4 

 PSH a: 29 b: 30 c: 4  

 ADD a: 29 b: 0 c: 30  

 SUBI a: 30 b: 30 c: 0  

 STW a: 0 b: 29 c: -36  

 LDW a: 1 b: 29 c: -36  

 LDW a: 2 b: 29 c: 8   

 CMP a: 1 b: 1 c: 2   

 BGE a: 1 b: 0 c: 12 

 LDW a: 1 b: 29 c: -36 

 CMPI a: 1 b: 1 c: 5 

 BGE a: 1 b: 0 c: 5 

 LDW a: 1 b: 29 c: -36 

 ADDI a: 1 b: 1 c: 1 

 STW a: 1 b: 29 c: -36 

 BEQ a: 0 b: 0 c: 4

 LDW a: 1 b: 29 c: -36

 ADDI a: 1 b: 1 c: 5

 STW a: 1 b: 29 c: -36

 BEQ a: 0 b: 0 c: -14

 ADD a: 30 b: 0 c: 29

 POP a: 29 b: 30 c: 4

 POP a: -1 b: 30 c: 8

 RET a: 0 b: 0 c: 31

 ADDI a: 1 b: 0 c: 0

 LSHI a: 1 b: 1 c: 11

 ADDI a: 1 b: 1 c: 0

 LSHI a: 1 b: 1 c: 12

 ADDI a: 1 b: 1 c: 10

 PSH a: 1 b: 30 c: 4

 BSR a: 0 b: 0 c: -30

Downloads:

• Slides: presentation.pdf

• Project Documentation SyntacticSugarDocu.pdf

• Virtual Machine Docu VirtualMachineforSyntacticSugar.pdf

• Compiler Source Code + Executable syntacticsugar.tar.gz

• Compiler Data Structures DataStructures.pdf

• VM Source Code + Executable VMSugar.tar.gz

• Internal Structure structure.dia

( Can be viewed with Dia )