Writing an Assembler for CMinus using Antlr 3 and String Templates

Recently I wrote an assembler for DLX architecture using Antlr 3 as an assignment of the Advance architecture course module.
 

Target 

Main target of this assemble is to generate an optimized assembly code by filling delayed branch slots. It can take High level language code segment as a input. First it should generate unoptimized assembly code and then optimized it to fill delayed branch slots.


Why Antlr ?

Antlr supports String template which is a java template engine that can be used to generate any type of formated texts ( source codes, emails, etc). So using string template we can perform language transformation very easily. For example Java to C#, C++ etc. For more details look at Here .

you can find antlr 3 samples at github.  I modified the cminus sample available at github for this project. 


About project

I used Cminus as High level language and DLX (RISC architecture) as target platform. It used Antlr version 3.

This project is available at Google-code svn repository.


Limitations of the Code

• Fills only delayed branched that occurs after unconditional jump. ( j )
• Supports multiple for, while and doWhile loops in high level language.
• supports only addition.
• supports only == and < 
• do not support variable = variable + variable type assignments

and more.



Main Development Steps

1. Building Lexer and Parser using lexer rules.
• used Antlr IDE ( downloaded via antlr site) to generate lexer and parser.
2. Unoptimized code generation using string template.
3. Wrote optimizer  and Optimized code generation. 
4. Mavenized the project. 

Building Project and Run

you can build project using maven3. ($mvn clean install) .
Maven build will execute assembler after the build and generate optimized code for sample.txt. asem_optimized.txt and asem_unoptimized.txt will be created after the build.


Improvements to the Code base

I warmly welcome your suggestions and ideas to improve this assembler.

[Tip] Avoiding Shift/Reduce conflict

consider following grammar for C-minus;

selection_stmt      ::= IF '(' expression ')'  statement
                        | IF '(' expression ')' statement ELSE statement ;

This is a "Dangling else" problem that leads to Shift/Reduce conflict when generating a parser ( I am using CUP ).

Warning : *** Shift/Reduce conflict found in state #72
  between selection_stmt ::= IF '(' expression ')' statement (*) 
  and     selection_stmt ::= IF '(' expression ')' statement (*) ELSE statement 
  under symbol ELSE
  Resolved in favor of shifting.

you can solve this problem by two ways. ( or you can re-define the if-else grammar rule with unambiguous if-else rules. I am working on it, hope to update this post after it)

1) adding precedence ELSE:

eg: modify code as given bellow.

precedence left  PLUS, MINUS;
precedence left  TIMES, DIVIDE;
precedence left  ELSE;

2) Allow to resolve in favor of shifting:

you can generate parser code expecting 1(or more) shift/reduce conflict.


eg: add "-expect 1" option to tell expect one shift/reduce conflict.

cup -expect 1 -parser CMinusParser cminus.cup