CS 327 Course Schedule and Homework


WEEK 1: 8/29 - 9/2

Reading: Dragon book, Chapter 1
Problems: (1) Translate the sample sentence from class into a language other than English two times (once each for the two ways of attaching the prepositional phrase) and create a parse tree in each case.
(2) Finish parsing the short piece of C code according to the Yacc Grammar for ANSI C.

WEEK 2: 9/5 - 9/9

Last day to drop without a "W": Friday, September 9th

Reading: Dragon book, Chapter 2.1-2.4
Problems: (1) Write the best grammar for English that you can, starting with the basic non-terminals we discussed in class, like NP, VP, and PP. Find examples of ambiguous sentences that don't involve problems with prepositional phrase attachment. Compare with the complexity of the Yacc grammar for C.

WEEK 3: 9/12 - 9/16

Reading: Dragon book, Chapter 2.5-2.9
Problems: Start work on Unix for Poets.

WEEK 4: 9/19 - 9/23

Reading: Dragon book, Chapter 3.1-3.3
Problems: Write "Eliza" as a Perl script.

WEEK 5: 9/26 - 9/30

Reading: Dragon book, Chapter 3.4-3.6
Problems: Implement backtracking regex matcher with backreferences.

WEEK 6: 10/3 - 10/7

Reading: Dragon book, Chapter 3.7-3.9
Problems: Continue work on regex matching.

WEEK 7: 10/10 - 10/14

Reading: Dragon book, Chapter 2
Problems: Implement (using shell commands) the Chomsky homomorphism from English to {a,b} discussed in class. Compute it's image on a large corpus of English texts. Discuss.

WEEK 8: 10/17 - 10/21

The midterm exam is Thursday, October 20th

Problems: Write a flex specification that tokenizes sed scripts.

WEEK 9: 10/24 - 10/28

No class Tuesday, October 25th (Fall Break)

Problems: Write an XML validator by writing a "DTD compiler" that converts to yacc. This compiler is a kind of "compiler compiler compiler".

WEEK 10: 10/31 - 11/4

Withdrawal deadline is Friday, November 4th


WEEK 11: 11/7 - 11/11


WEEK 12: 11/14 - 11/18


WEEK 13: 11/21 - 11/25

No classes Wednesday-Friday, November 23rd-25th (Thanksgiving)


WEEK 14: 11/28 - 12/2


WEEK 15: 12/5 - 12/9

Thursday, December 8th is the last day of class
The final is Tuesday, December 20th, 8:00-9:50AM

Practice Problems for the exam: you should expect to work out an example of an LR(1) parsing table and be able to use it to parse input strings. Make sure you understand the hierarchy of grammars and what fits where (ambiguous, regular, LL, LR, SLR, LALR, non-CF, etc), and are able to give examples where appropriate — this includes the ability to apply the pumping lemma to show certain languages are not context-free. You should understand how to do left factoring, how to eliminate left recursion, and how to compute First and Follow sets for a given CFG. The point of the exam is to focus on the theoretical aspects of the course, so it's unlikely I'll have you write lex/yacc specs or any Parrot assembly code.