2110316 Programming Languages Principles 3(3-0-6)

1st semester 2014

Prabhas Chongstitvatana

official course description

Principal lecturer: Twittee. This course is divided into three equal parts. Three parts are taught by three different lecturers.

1) Programming Language concepts, Twittee
2) Non-imperative programming language, Vishnu
3) Language and implementation, Prabhas

The goal of this course is to make you understand the languages you use. To make you appreciate diversity of ideas in programming and prepare you for new programming methods and paradigms. Theoretical foundations will be presented. You will know properties of language, not just syntax. Moreover, you will recognize the cost of presenting an abstract view of machine and understand trade-offs in programming language design.

Each part will be taught separately and independently. It is logical that the assessment will also be arranged according to this structure. There is no midterm exam (besides whatever assess by the lecturer at that time) and the final exam will contain all materials taught in the course.

Assessment

each part 20% by 3 = 60%
final exam 40%

the lecture schedule:
section 1: T, V, P
section 2: V, P, T
section 3: P, T, V

Language and implementation

This part concerns a compiler for a programming language. There are two aspects of learning this part: theory and practice. The theory will be given in the lectures. The practice is carried on as homework and classwork. To teach effectively I choose to design a toy language and implement its compiler. There are two implementation, in C and in Javascript. You will be studying actual compilers and modify them.

old lecture 2009 2010 2011 2012 2013

Announcement

11 Sept 2014 Project for section 3 is announced. Hand-in before 4pm 19 Sept 2014.
23 Sept 2014 Section 2, please do the homework 4 (write a grammar for a children story)
. . .

Study Plan

plan for 4 weeks, with one week to spare
each week has 2 sessions of 1 1/2 hrs. each.
a homework will be handed out each week.
one project will be issued on week 3.

workload

one small project
one in-class exam
weekly homework, running the code

Lecture sessions

1 structure of a compiler      Overview of the course   (from Stanford slide)
       Intro to Compiler (ppt) Supplement: Cross compiler (ppt)
       High Level Language to Low Level Language to Processor architecture
            Demonstrate the actual compiler of this course RZ.   Rz compiler on web
2 lexical analyser      Scanner (ppt)
--------------------------
3 grammar               Context Free Grammar (ppt)   Example of writing a grammar to specify a language
    3.1                        Recursive programming with List
4 parsing    Parsing (ppt)    top-down parsing   How to compute First and Follow set (by Prof. Kamin at UIUC)
                                LL parser at Wiki
----------------------------
5 actual parser         project announcement
6 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
---------------------------
8 actual code generator How to do code generation     Zero Assembler
   exam
-----------------
9-10 spare additional topics

Assessment for this part

homework        5%
one project       5%
exam              10%
total               20%

Classwork and Homework (other groups)

Classwork

Section 2

...

Homework

Section 2
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. For recommended free C compiler, see Tools section below.
3. Modify the compiler to run only as scanner then modify the scanner to accept a new word "system" in the source.

Here is the steps to modify the compiler to run only as "scanner".
3.1 Go "main()" in "compile.c" add the following line to call "lex()" (a scanner function) repeatedly.

readinfile(source);
prolog();
testlex();

exit(0);

3.2 in the same file delete comments (open up) "testlex()" (around line 48).

void testlex(void){
    mylex();
    while( tok != tkEOF ){
        printf(" ");
        prtoken(tok);
        mylex();
    }

3.3 You also need to open up the "prtoken()" (in "prtoken.c") by deleting "PRIVATE" keyword (line 16).

// print token
void prtoken(int tk){
. . .

        case tkIDEN: printf("%s",
        tokstring); break;

        case tkNUMBER: printf("%s",
        tokstring); break;

        case tkSTRING:
        printf("%c%s%c",34,tokstring,34); break;

        case tkEOF: printf("eof");
        break;

}
}

by now, you should have a "scanner" working properly. Here is what the session looks like (assuming your compiler is "rz33.exe"). Run it with "console" (called "cmd" in Windows). It is a black box that accept command lines (you interact with computers through "command" from the keyboard instead of using mouse and click).

C:\rz33-1\comp\lcc>rz33 fac.txt

       ( n ) { if ( n == 0 ) return 1 ; else return n * fac ( n - 1 ) ; }
      main ( ) { p

      rint ( fac ( 6 ) ) ; }

Notice that the first word has not been displayed properly. (it should show "fac"). Do you know why?

4. Write a grammar to cover this story. Please make it so that your grammar is neither too rigid, i.e. admit only this story, nor too loose, i.e. admit any story. Make your own judgement.

Here the story goes:

Mary has a little lamb. Its fleece is white as snow. Everywhere that Mary went, the lamb is sure to go. One day Mary goes to school. The lamb goes to school too.

Project

. . .

Reference Text

-- Aho, Sethi, Ullman, Compilers: Principles, Techniques, and Tools. Addison-Wesley, latest edition.
-- Louden, K.C., Compiler Construction: Principles and Practice. PWS Publishing Co., 1997.

The first one is the standard text book on compiler. It has been used in more than 100 universities in North America. It is a bit difficult to read as it contains a lot of theory. The second one (Louden) is much easier to read. I will update some chapter from my textbook from time to time as necessary.

Extra reading

A chart of genealogy of programming languages (pdf) (You need to zoom to 100% to see it)
Programming Recursion (to familiar yourself with recursive programming)

Tools

See my Rz language homepage
the compiler package with code generator for s-code rz33-1.zip
Zero Assembler source, example and executable (including som v2 vm) ( zas.zip )
Rz compiler on the web (by Kamoluk Suksen)
Recommended free C compiler for Windows lcc-win32 . (for Windows 7 and 8). 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).

How to use the compiler

Use rz33-1.zip to compile and run your programs. Here is what a session looks like. Go to rz33/test directory (that you unzip the package to). There are two executable files: rz33.exe and somv2x.exe. Try to compile "fac.txt". It is shown here:

// factorial

      

      fac(n){

        if( n == 0 ) return 1;

        else return n * fac(n-1);

      }

      

      main(){

        print(fac(6));

      }

Here is the command line and the output at the screen:

D:\prabhas\bag\rz\rz33\test>rz33 fac.txt

      fac

      main

      (fun main (print (call fac 6 )))

      (fun fac (else (== #1 0 )(return 1 )(return (* #1 (call fac (- #1 1 ))))))

      

      :main

          fun.1

          lit.6

          call.fac

          sys.1

          ret.1

      :fac

          fun.1

          get.1

          lit.0

          ...

You will get the file "fac.obj" as an output file. It is an object file that is executable under Som VM (a kind of virtual machine similar to JVM). You can "run" it under somv2x.

D:\prabhas\bag\rz\rz33\test>somv2x fac.obj

      720

That's it. Enjoy!

Prabhas Chongstitvatana
contact address: prabhas at chula dot ac dot th
office room 18-13 Engineering Building 4, floor 18. tel 02-2186982
research lab: Intelligent Systems, floor 20.

Last update 23 Sept 2014