Digital Systems: 1st semester 2016 (Aug)

There are two parts in this class. The first part is the relationship between the computer language compiler and the instruction set (teach by Prabhas). The second part is the asynchronous design (teach by Arthit).

my old lecture 2015

Compiler and Instruction Set

classroom : Tue 13:00-14:30 room 3404, Thu 9:30-11:00 room 3403

Aim (Prabhas)

Compilation is very common task in Information Technology. Understanding the process of compiling is important as it reveals some fundamental limitation of our Digital Technology. This part is divided into two sections: compiler and its effects on instruction set. The first section aims to train students to be able to write a formal specification of language that is suitable to be compiled by a simple procedure. The second section is about code generation and the optimization of instruction set. The second part explores instruction set design (especially for domain-specific language).

Lecture

Compiler:

Cross compiler (ppt), Scanner (ppt)
Context Free Grammar (ppt)   small example of grammar
Parsing (ppt) How to compute First and Follow set (by Prof. Kamin at UIUC)
LL parser at Wiki
To write a parser you need to be able to program in recursive style:
   Recursive programming with List    Extra exercises
Example of writing a recursive descent parser for a simple language
Code generator        Code Generation Som v2.0 virtual machine   S-code
    recursive evaluator    here is the source code in C for an interpreter of Rz parse tree    eval3.c
Example of writing a parser and build parse tree

Tools

I use Rz language as an example language.
See my Rz language homepage
Demonstrate the actual compiler of this course RZ.   Rz compiler on web
The compiler package with code generator for s-code rz33-1.zip
Recommended free C compiler for Windows lcc-win32 . (for Windows 7, 8, 8.1 and 10). Please also download and install "User Manual". You need it to look up the library function of this C. (for OS X you need xcode, also free).
Library for recursive programming practice   ailib.zip
ASM parser   asm-parser.zip
Example of building parse tree ex-parse-tree.zip

Homework

1 Learn how to write in Rz by reading Quick Start Rz.
2 Download and compiler the compiler used in this class (rz33-1.zip). Use whatever compiler for C that you are familiar with and compile it. Try it out to compile some simple program.
3 Write a scanner for your set of words.
4 Write grammar of your language.
5 Code the parser for your language, using Recursive Descent method.

Project

I define the following language which is easy to compile.
(do s1 s2 ...)                                  sequential s1 s2 ...
(= a b)                                           assignment a = b
(== a b)                                          equality test a == b
(ifelse cond T-action F-action) if..then..else
(def fun-name formal body)           function definition
(print ex)                                     print integer to screen

with this simple language I can write a program like this:

(def fac n 

          (ifelse (== n 0) 

             1

             (* n (fac (- n 1)))))

      (def main ()

          (print (fac 6)))

Write a compiler for this language. Your work is in three parts:
1)   specification:   Write regular expression for words in this language. Write CFG of this language.
2)   parser:   Write scanner and parser using Recursive Descent method.
3)   code generation:   Write a code generator to translate Parse Tree into S-code.

You can extend or change this minimal language to include interesting construct (such as for..loop, or array). You can define your own machine code (you don't have to use S-code).

Write your compiler and your report of the work. The report should describe all three parts with adequate explanation so that I can follow how you design your compiler. You should also give some example of input/output of your system. Do not include the source code of your compiler in the report. Expect the report to be read by an undergraduate student in computer engineering.   Email your code to me so I can inspect it. I expect you to spend in average 20-30 man-hours for this project.

(will be online til 15 Nov 2016)

Partial compiler (parser) for the project
<n-parser package>
I clean up the whole source to make it smaller and easier to read (it is now 1100 lines). Now the parser generates parse tree. It also includes rudimentary symbol table. It is worth reading the parser part.
<n-parser with parse tree>

Here is a sample output:



      C:\rz33c\test>rz33c n-input.txt

      (def double (+ x x ))

      symbol table(2): double.1 x.0

      (def asg (= a 10 ))

      symbol table(4): double.1 x.0 asg.1 a.0

      ...

      (def sum (ifelse (== n m )s (sum (- n 1 )m (+ n s ))))

      symbol table(13): double.1 x.0 asg.1 a.0 sub.2 b.0 seq.1 ...

      yes

      C:\rz33c\test>

The symbol shows function name with its arity (the number of parameters). The parser is in the file ex.c. The action routines are in the file action.c.

Report from your works

Tawan
Tongjai
Teerapat
Kanut

last update 15 Nov 2016