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.
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 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
Announcement
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.
workload
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)
automaton
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
exam
-----------------
9-10 spare additional topics
submit project
Assessment for this part
homework 5%
one project
5%
exam
10%
total
20%
Classwork
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).
Homework
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.
Tools
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