CSC 420 Principles
of Programming Languages
- A sample quiz for
quiz 2 is now available.
- The solution to problem 10.7a is now posted at //recluse/shared$/CSIS/WEBERK/Handout/CSC420/prob10-7a.scm.
- Some clarifactions of the specifications for the Scheme
interpreter project are posted below in the
implementation notes section.
- The complete examples from April 16 are now available in apr-16-finished
in the CSC420 handout folder on the shared drive.
- We meet for the remainder of the semester in 057 KHIC,
starting on Monday, April 14, with the exception of Quiz 2 on
April 25 and the final exam, which is Monday, May 5, from 1 to 4
- Read chapter 7, which will be the last chapter of the textbook
that we will discuss. You only need to read through the end
of section 7.2, and section 7.4.
- Quiz 2 will be on Friday, April 25. It will cover
chapters 4, 10 and 11.
- Read chapter 6.
- Work on these practice problems from chapter 11: 11.3,
11.6, 11.7, 11.11.
- Work these practice problems from chapter 10: 10.3, 10.7ab
- I've added an Interpreter
Implementation Notes section to the Project
specifications. Those who are implementing the interpreter
should check this location daily for new tips and other
information on how to implement the subset-Scheme interpreter.
- We meet in 057 KHIC on Wednesday, April 9.
- We will meet in 057 KHIC on Friday, April 4.
- Examples from March 31 are posted at //recluse/shared$/CSIS/WEBERK/Handout/CSC420/tail-recursion.scm
- Chapter 11 is next on the reading list.
- The project description has been posted below.
- Read chapter 10.
- Specifications for the project
will be posted tonight (March 26). You can either write a
5-page paper on one of the topics in the Explorations
sections of the exercises (using ACM
SIG Proceedings Templates), or you can create an
interpreter for a subset of Scheme. You should be thinking
of a partner to work with...
- We will meet in 057 KHIC on Wednesday, March 26.
- There is a new homework assignment posted below.
- The midterm, scheduled for Friday, March 21, will be twice as
long as Quiz 1. Details on topics for midterm test:
Remember that you are allowed a 5.5 in x 8 in sheet of notes for
- Same topic list as on Quiz 1
for chapters 1-2.
- Be able to work with flex and Bison as in assignments 2
- From chapter 3, know the concepts listed below, and be
able to work problems similar to those in assignment 4.
- Binding time
- Scope and extent (i.e., lifetime)
- Static, heap and stack allocation
- Garbage collection
- Dangling references
- Static and dynamic scope rules, including for nested
- Nested blocks
- Modules, namespaces, and packages
- First, second, and third class objects
- Closures of subroutines passed as parameters, including
deep vs shallow binding
- Start reading chapter 4.
- We will meet in 057 KHIC on Friday, March 14.
- The midterm test will be on Friday, March 21. It will
cover material from chapters 1-3 and assignments A1-A5.
Stay tuned for more details...
- There is a new homework assignment posted below. Note that one of the
problems has been eliminated from the original list.
- Read chapter 3.
- Friday's examples have been posted below.
- See the new assignment below.
- Read chapter 3 of the flex & bison book, up to the section
titled An Advanced Calculator on p. 61.
- We will be starting on chapter 3 of the textbook soon, so
start reading that chapter.
- We will meet in the lab on Wednesday, Feb. 19.
- Quiz 1 will be held on Friday, Feb
14. Remember that you are allowed to prepare a 3" x 5" card of
notes. Take a look at a quiz from
2012 to get a feel for the quiz format.
Here is a list of the important topics:
- Chapter 1:
- Compilation & interpretation: understand the
differences between these two techniques and recognize
that lots of translation schemes use some blending of
- Compilation overview: Understand Figure 1.3 and
know the purpose of each main phase.
- Chapter 2:
- Regular expressions
- Be prepared to write a regular expression, using
the Flex extended regular expression metasymbols,
for the tokens of a language described in English
- Be able to "read" a regular expression to
determine whether a given string is a valid token or
- Be able to create an "optimized" DFA given a
simple regular expression, following the three step
process outlined in the textbook.
- Context free grammars
- Be able to draw a syntax tree and a rightmost
derivation for a sentence in a language given by a
- Know the definition of ambiguous grammar
- Be able to explain the basic difference between
bottom-up (LR) and top-down (LL) parsing
- Be able to show that a simple CFG is LL(1) or not
- Trace through a recursive-descent or table-driven
- You will not be asked any questions about
shift-reduce parsing on this quiz (this topic will
be left for the midterm)
- There is a new homework assignment posted below.
- Quiz 1 will be on chapters 1 and 2. Stay tuned to this
channel for the actual day it will be given.
- We will meet in 036 KHIC (our usual classroom) for class on
Friday, Jan 31.
Section 2.1 of the flex and bison book. It will help
with the assignment due Friday.
- We will meet in 057 KHIC for class on Wednesday, Jan 29.
- You should be done reading Chapter 2 of the textbook by Monday
- Read Chapter 1 by Wednesday 1/15 and start on Chapter 2 of the
- A6: due 3/24
- Modify your solution for assignment 4 to create an interpreter
for the expression calculator language from the textbook.
In order to make it easier to handle variables, you may restrict
variable names to one letter. An uppercase letter should
represent a different variable than a lowercase letter. To
read statement, use the C
function. The following line will read a value into the
- A5: due 3/12
- Turn in your solutions to problems 3.1,
3.4, 3.6, 3.7b, 3.9, 3.11, 3.15, 3.19 from chapter 3 (pp 163ff)
of the textbook. Remember that it will not help you on the
test if you rely on the solutions floating around the
internet. In order to help you resist temptation. I will
return submissions containing one or more solution from the web
marked with a score of 0 and no opportunity for resubmission.
- A4: due 2/26
- Add productions and actions to these bison and flex input files to create a
parser for the expression calculator example in the
textbook. Fig. 2.24 on p. 88 gives all the LR productions
necessary. The parser should accept any legal "sentence"
by issuing the output
Accepted when the
end-of-file has been reached. It should also print the
name of the non-terminal that has been matched at the end of the
production on which it appears on the left of the arrow.
You'll find that you will need to compare strings in order to
terminals. The function that compares strings in C is
Issue the command
man strcmp to get information
about this function.
Email me the modified bison and flex input files, as well as all
the .h and .c files generated by bison and flex. It is not
necessary to email me the executable (i.e., the a.out file).
- A3: due 2/10
- Turn in your solutions to problems 2.9, 2.12, 2.13, 2.17, and
2.18 from chapter 2 of the textbook. For problem 2.17, only
extend the grammar for
while statements and not
- A2: due 1/31
- Create flex input that specifies the regular expressions for
the tokens of the calculator language in example 2.9 on p. 52,
then use flex to generate a C program that will read in a stream
of characters and group the characters into tokens, printing the
name of the tokens assign, plus, minus, times, div,
lparen, rparen, id and number. Any comment
tokens should just be dropped. Also, for number
and id, print the actual number or the actual id as
well as the token name.
For example, given the input
a := 15 + 7 // Comment here.
your C program would produce
Turn in the flex input file and the C source code program that
your input file produces.
- A1: due 1/29
- Turn in written answers to exercises 2.1ae, 2.2ae, and 2.4.
You have two options for your project.
Select a topic from the Explorations sections of the
exercises at the end of the textbook chapters that are listed
in the syllabus as ones we covered
or plan to cover, and write a 5 page paper on the topic.
You must follow the formatting rules supplied by the ACM
SIG Proceedings Templates; either Word or LaTeX2e
is OK. Also, your paper must have a list of references
with at least 10 citations in the body of your paper, from at
least 5 separate sources.
Register the topic with me (it will have to be one not chosen
by someone else and I will have to approve the topic) by April
2 at class time. Topic registration is
first-come-first-served. Papers must be written by
individuals only; no teams.
Topics registered so far:
- Exploration 1.8 on page 37
- Exploration 1.13 on p. 39
- Exploration 2.33 on p. 108.
- Exploration 7.46 on p. 380
- Exploration 7.49 on p. 380
- Exploration 8.51 on p. 446
- Exploration 8.53 on p. 446
- Exploration 11.22 on p. 573
Pair up with one other student and write an REPL interpreter
for a subset of Scheme. You do not have to use C/C++ and
flex/bison to do this project; other platforms, such as C# and
Java may be better choices. Note that there are tools
like flex (jflex) and
that work with Java, as well as some other languages.
Register your team and intended programming platform by April
2 at class time. (I will have to approve the platform
before you can start.)
Your interpreter should behave in a manner similar to the
mit-scheme interpreter; the user starts the interpreter and
then can type in S-expressions that will be Read, Evaluated,
and the result Printed. The interpreter will Loop to
allow the user to enter another S-expression after that, until
the user signals an end to the input.
Your code must be properly documented, well organized and
nicely formatted. You must also provide a short user
manual (only a paragraph or two would be necessary) to explain
to the user how to run the interpreter. You may assume
the user knows Scheme or can look up Scheme stuff
elsewhere. The user manual could be included in the
interpreter and printed when the interpreter first starts, if
the team so desires.
Your interpreter must be able to:
- recognize atoms (i.e., lisp-identifiers) and boolean
Numbers, such as
should be recognized as atoms, but do not need to be
associated with any special meaning
- parse and evaluate nested S-expressions, including lists
- handle the
if special form.
- provide the following built-in functions:
Extra credit will be given if your interpreter correctly
define (3% of the project total possible
lambda (4% of the project total possible
Note that going for the extra credit may involve a totally
different design than if you were just planning to implement
the required features, so you should decide in advance whether
you want to tackle the extra credit.
Whichever option you choose, the project is due, in its final
form, on Monday, April 28. It should be submitted
electronically. Submission of an interpreter should include
all source code. You may wish to take advantage of receiving
feedback on a draft. If you submit a draft by the end of
Friday, April 18, I will do my best to give feedback by the
- Clarification/simplification: the scanner only needs to handle
base-10 nonnegative integers (i.e., strings of base-10 digits
with no minus sign in front).
- Clarification/simplification: the basic non-extra-credit
version of the interpreter only needs to handle quoted nested
s-expressions; it doesn't need to try to evaluate the nested
- Use this
web page for an "official" definition of the Scheme
grammar. The Lexical structure section describes
tokens; you'll need to translate the context-free grammar
productions to regular expressions for flex/jflex to
understand. You don't need to bother with
<string> from the
rule. Also, you can leave out the
<peculiar identifier> symbol from
<identifier> rule, as well as ignore
whichever of the
<syntactic keyword> and
keyword> words that you aren't implementing.
The rest of the sections are on the actual grammar. You
can eliminate any productions that don't apply to the parts of
Scheme you are implementing.
- You will need a symbol table for the interpreter. It can
be something as simple as a Java List object. Typically a
hash table is used to implement a symbol table
"commercial-grade" compilers and interpreters.