2110316 Programming Languages
Principles 3(3-0-6)
1st semester 2016
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, Nattee + Pitchaya
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%
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 2012 2013
2014 2015
Announcement
8 Nov 2016 -- The class on 10 Nov is cancelled. Please do
the homework new 2.
15 Nov 2016 -- Quiz will be held on 17 Nov 2016, 10am at the
classroom.
21 Nov 2016 -- Project is posted, it is due 4pm, Friday 2
December 2016
22 Nov 2016 -- IMPORTANT The part code generation will not be present
in the final examination questions.
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
Lecture sessions
1 structure of a compiler
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
Recursive
programming with List extra
exercises
Context Free
Grammar (ppt) Example
of writing a grammar to specify a language
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 Example of writing a
recursive descent parser for a simple language
Example of
a parser with building parse tree
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
---------------------------
7 actual code generator How to do code generation
project announcement
Assessment for this part
one project
5%
exam
15%
total
20%
Classwork
3 Nov 2016 --
1. Write a grammar for this song
I'd
like to build the world a home
And furnish it with love
Grow apple trees and honey bees
And snow white turtle doves
I'd
like to teach the world to sing
In perfect harmony
I'd like to hold it in my arms
And keep it company
2. Write a recursive program for 1) reverse complex list, 2) clone(L) (ex 3
in lecture recursive programming)
Homework
Old
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. Try the example of ASM parser. Change the ASM language a
little bit, such as, make an op code to have three arguments (i.e. add
r1,r2,r3). Then, change your CFG to reflex this. Then, modify
the parser to parse it.
New
1. Try your hand on recursive programming. Do
ex 3 (clone). Do extra exercises.
2. Practice Grammar writing. Given the following sentences:
f(id)
f(f(id))
f(id,id)
f(f(id),id)
...
2.1 Write Grammar for this language.
2.2 Write a recursive-descent parser followed from
Grammar for this language.
2.3 Bonus: in your parser, construct a
parse-tree (see example "a parser with build
parse tree")
Project
1) Write a report on how a compiler or an interpreter of a computer
language works. You have to choose from three languages: LISP,
Python and Haskell (one from the past, one of the present and one in the
future). Choose the language you like most (or that has something
that you find interesting).
I want the content to be focused on compiler (interpreter) rather than
historical facts and other tidbits. You must write in your own word
(in Thai or in English). Do not cut and paste. You need to synthesize your
idea. The length of the report is around 4 pages. I expect this to
take you about 9 hours of work.
Hand in your report in paper. Put it in the inbox in front of my
office before 4pm, Friday 28 Oct 2016. Late submission will not be
accepted.
Here is some link for you to start (You don't have to use these
sources. You can find whatever you like)
LISP
compiler and interpreter
Python
is it an interpreter? PyPy
Haskell introduction
from the real source
inline
(heavy reading!)
New
Write a parser -- Given a language, write its grammar, computer its
First and Follow set, make the parsing table. Then, write its parser. You
must hand-in a report of length 4-5 pages contains the following:
1) Grammar, First and Follow set, parsing table
2) Pseudo code of your parser
3) Examples that show that your parser work
You don't need to send me the actual code for the parser.
Please hand-in your report before 4 pm, Friday 2 December 2016, at the
box in front of my office, building 4, floor 18, room 13. Late submission
will not be accepted.
The language :
------------------------------------
A language that "verbalise" programming. Imagine how to help a
blind person to write a computer program. We can use speech
recognition to "transcribe" sound to text. However it is cumbersome
to just spell out text of our conventional programing language. Try
to read this "hello world" aloud.
#include <stdio.h>
int main(void){
printf("hello world\n");
return 0;
}
Let us improve the "verbalisation" a little bit. We can use
"command" then follow by "parameters". When the number of parameters
is variable, we can use the word "stop" to delimit them. We can also use
that to say the end of the code block. Let us use this example:
square(x){
return x * x;
}
We can verbalise it like this:
function square parameter x stop block return expression x mul x
stop
Wow, this will be super good!
---------------------------------------
Now, back to your project, use this idea to design your small
language (you can use the above example, it is good enough to be used to
write a simple program with no data type). Give examples of your
program, both input "speech" and output (C like). Write the grammar
for your language. Implement a parser (no need to generate output),
a pure parser that parses proper input is sufficient.
Hope you enjoy this project. If you want any discussion, please use
Courseville of this class, or failing that Facebook messenger to me, find
me "Prabhas Chongstitvatana". I promise to check the channel once a
day.
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. 1997 is the latest edition, you can find it in
Amazon.
Extra reading
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, 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).
Example of building parse tree ex-parse-tree.zip
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 22 Nov 2016