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

1st semester  2011

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-imparative 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.


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 and to enrich your C programming skill, I choose to design a toy language and implement its compiler in C. You will be studying an actual compiler and modify it.

old lecture  2009  2010


4 August 2011  The quiz of section 2 will be on Thursday 11 August, 9:30 sharp.  There are three questions in 30 minutes. 
4 August 2011  Section 2 will change the classroom to Eng. Building 3, 407 starting 9 August.
1 September 2011  A new Rz compiler is uploaded  rz35.zip

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.


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

Lecture sessions

1  structure of a compiler      Overview of the course   (from Stanford slide)     Compiler (ppt)
   HLL to LLL to processor architecture
2  lexical analyser      Scanner (ppt)
   actual code           Session on how to use the tools
3  parser
4  grammar               Context Free Grammar  (ppt)
5  recursive descent     Parsing (ppt)    top-down parsing
6  actual parser         project announcement         
7  code generator        Code Generation 
   recursive evaluator                                          
8  actual code generator  How to do code generation              
9-10 spare  additional topics
  submit project

Assessment for this part

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


Section 3
1.  Practice recursive programming.  Let ax[n] be an array of integer, size n.  Write a recursive program (in your favourite language) to find the maximum value in this array without using global variables or static variables.

Section 2
1.  Write a grammar of the following language (you should generalise it a bit):
      a = b + c
      b = x[2]
      x[3] = 10
2.  Give a grammar, write a pseudo code parser.  The grammar is:
      asg :=  id = e
      e :=  e op e | vec | num | id
      op := +
      vec :=  id [ num ]

Section 1
1.  Have a feel of Rz programming language.  Using this tool  rz31.zip to compile and run programs:
     a)   Write a program to find a maximum element of an array ax[.] of integer.
     b)   Write a recursive version of the program in a).


Section 3
1.  Familiarize with the compiler tool.  Use rz31.zip to compile and run your find-max recursive in the classwork1. 
2.  Practice writing a program to emulate a Finite State Machine.  Draw a FSM of 4 states.  Write in Rz, a program that perform as an automata of that FSM.  (that read input and do state-transition etc.).  You can assume the input to be an array of 0/1.
3.  Project:   Design a "domain specific language".  Describe your motivation, the application of the language. Write a grammar of the language.  The whole report should be around 3-4 pages.

Section 2
1.   Explain the meaing of the following regular expression:     /* ([^*]*[^/]*) * */
2.   Write FA for the set (size of five) of the name and id of your friends.
3.   Project:  Compute  LL(1) parser table of a subset of a programming language.  Select a language from this set {Verilog, Java, C, C#, HTML}.  Write some examples of sentences of the subset language.  Write CFG from that subset.  Compute First set, Follow set and Parsing Table.  Make all necessary decisions such that your subset language is neither too big or too trivial.  The report is about 2-4 pages (real paper only please, I need to keep track of your work).  Hand-in by 15 Aug 2011.

Section 1
1.   Hand-on using the scanner of Rz compiler (rz31.zip) by modifying "mylex( )" that is used by the function "testlex( )" (the scanner part of the compiler) to output all capital letter of the tokens.  Here is an example of an original output on the screen (compiling "fac.txt"):
d:rz\rz31\test>rz31 fac.txt
fac ( n ) { if ( n == 0 ) return 1 ; else return n * fac ( n - 1 ) ; } main ( )
{ print ( fac ( 10 ) ) ; }
Use rz31.zip  dir comp and test.  Here is the "makefile" generated from Dev-C++  (makefile).  You may need to edit it somewhat for your C compiler.

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)
My other programming language and its virtual machine: Som
As promise, here is my "extremely small" compiler (in 128 lines).  You can get the fulltext paper describing it at: http://www.cp.eng.chula.ac.th/faculty/pjw/paper/2005/prabhas-sgs.pdf
John Backus, the father of FORTRAN compiler.  He invented Functional Programming.  I have a discussion here. (include the link to the original paper)
1977 ACM Turing Award lecture, John Backus, "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs", Communication of the ACM, vol.21, no.8, August 1978, pp.613-641.


See my Rz language homepage
the compiler  package:   rz31.zip,  with code generator for s-code  rz33-1.zip 
a new version of Rz use indentation as  { } and \n as ";"  rz35.zip   Here is the new look of Rz  fac.txt

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  5 Sept 2011