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

Jan-Apr 2022

Prabhas Chongstitvatana

Monday 13:00-16:00 online

official syllabus

lecturer: Prabhas Chongstitvatana

This course is divided into three equal parts.

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

The goal of this course is to make you understand computer 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 machines 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.


(home work + quiz) x 3         =  60% + 10%
final exam                              =  30%



Study Plan

each section lasts 4 weeks.
an in-class work will be handed out each week.
no midterm exam.


1. Theory of programming language

Evolution of programming language
Names, scope and binding
Control flow
Data types

2. Non-Imperative programming

see Aj Vishnu lecture

3. 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 classwork. To teach effectively I choose to design a toy language and implement its compiler. You will be studying actual compilers and modify them.

1  structure of a compiler  
Intro to Compiler  Supplement: Cross compiler
lexical analyser      Scanner   

2  grammar

Demonstrate the actual compiler of this course
Context Free Grammar   
Example of writing a grammar to specify a language
Recursive programming with List    extra exercises

3  parsing      

Parsing    top-down parsing  
How to compute First and Follow set  (by Prof. Kamin at UIUC)
LL parser at Wiki 
4  actual parser   
        a recursive descent parser for a simple language
        a parser with building parse tree   
        write a parser from a parsing table
        LL1 parser of grammar from lecture parsing page 25 (LL1-parser.zip)  (slide)  

   code generator
        Code Generation     Som v2.0 virtual machine   S-code
        Recursive evaluator, an interpreter of Rz parse tree    eval3.c  
        Code generation pptx (use in the video)

   summary of compiler part


(part theory and compiler, for part 2 alternative paradigm please visit Aj Vishnu)


1. Evolution of languages:    https://youtu.be/Zembnp_Cj7c
2. Naming and Scopes part 1/2:   Naming, stack management https://youtu.be/n4J4nHq6a1U
3. Naming and Scopes part 2/2: Heap, nested scope, static-dynamic binding. https://youtu.be/_FM3tqdda94
4. Control structure  https://youtu.be/44X5QL247mk
4.1  Control structure (optional) object method, functional, continuation.  https://youtu.be/NXNXKY1tdTg
5. Types. https://youtu.be/XV_r2iWRWOg


6. Intro to Compiler https://youtu.be/U_hGtz1UQt4  (updated)
6.1.  Demonstration of a real compiler:   RZ compiler  https://youtu.be/GPabkQnqvBY
7. Scanner  https://youtu.be/DfA-PXbi-1g
8. Grammar. https://youtu.be/6jOBVCbNw8w
9. Example of writing a grammar to specify a language.  https://youtu.be/UXgCL0QY5Xo
9.1  Recursive programming part 1:  language, object, exercises  https://youtu.be/PZRgH8MRn8Q
9.2  Recursive programming part 2:  concrete program using library  https://youtu.be/Ue2Q8ZTzVN8
10. Parsing  recursive-descent, simulate stack for left most derivation. https://youtu.be/O_nMvMUEFkw
11. Parsing. First and Follow set, construct a parsing table.  https://youtu.be/tEy7ZfpKZt0
12. Construct a parser from parsing table    https://youtu.be/x58vRak89BQ

Optional (code generation video to be redo, all three parts)

13. Code generation part 1/3:  Parse tree  https://youtu.be/1eJmVM-eL8A
14. Code generation part 2/3:  Abstract interpreter   https://youtu.be/pvZlecsItdg
15. Code generation part 3/3:  Machine instruction  https://youtu.be/XX0fW24M55A

Reference Text

-- Jaruloj Chongstitvatana, Programming Languages Principles and Processing, (local copy) Dept. of Math and CS, Chulalongkorn, 2017. (main 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 main text is Jaruloj.  It covers larger topics than required in this class.  Our presentation follows this textbook.  Aho,Sethi, Ullman is the standard textbook 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.   Louden is much easier to read.   The latest edition is 1997, you can find it in Amazon.

Extra reading


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

See my Rz language homepage
the compiler  package with code generator  rz36-3.zip
lexical analyser  (lex-35-3.zip,   extract from rz35-3 package)
Rz compiler on the web  (by Kamoluk Suksen)
Example of a recursive descent parser for a simple assembly language   asm-parser-2.zip
LL1 parser from lecture parsing page 25  LL1-parser.zip
the updated package  LL1-parser-2.zip  works on both Windows 10 and MacOS (I use xcode to compile on Mac). The executable file for Mac is used this way, on Mac opens a terminal:

$ ./xparser test.txt

To practice recursive programming in the lecture, you need this library  ailib2.zip  (in C).
Example of building parse tree   ex-parse-tree-2.zip  (clean up)

How to use the compiler

Use rz36  to compile and run your programs.   Here is what a session looks like.  Go to rz36/test directory  (that you unzip the package to).  There are three executable files:   rz36.exe, as21.exe, sim21.exe  .  Try to compile "fac.txt".  It is shown here:

// factorial

  if( n == 0 ) return 1
  else return n * fac(n-1)


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

D:\rz36\test>rz36 fac.txt
(fun main (print (call fac 6 )))
(fun fac (else (== #1 0 )(return 1 )(return (* #1 (call fac (- #1 1 ))))))


You will get the assembly file as an output file.  Then, use as21.exe to "assemble" (change assembly file into object code file).  You can "run" it under s2 simulator (execute machine code) s21.exe.

D:\rz36\test>sim21 fac.obj

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  7 April 2022