Prof Avery's weblog

/var/spool/weblog

Prof Avery's weblog
dainty doo-dads for the despondent

<spool@kenytt.net>

Geek News

del.icio.us bookmarks

A Concise Introduction to Objective Caml

$ command line ruby cheat sheets

workingenv.py

google-code-prettify

Free Royalty Free Stock Photography

Gallery

Coppermine

Plogger

The Mathematical Atlas

align: text column alignment filter

Akadias Publications

This Essay Breaks the Law

Intellectual Property Run Amok

Building your very own web2.0 layout

The structure and function of complex networks

Knowledge Discovery and Data Mining

Graph Theory in Practice: Part I

Graph Theory in Practice: Part II

Internet Mathematics

RSS

Sat, May 21, 2005

Final Exam Date
Right you are -- the date on the syllabus page was wrong, but the outline was correct. The final exam is definitely next Friday, and I've updated the pages to match.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Fri, May 13, 2005

Outline updated
I've updated the Class Outline to show the reading for the material that we covered last week: Sections 6.1, 6.6, and 6.7.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Sat, May 07, 2005

Parser Test Programs
The programs I used to test Assignment 2 have been posted here.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Mon, May 02, 2005

Windows executable for 3AC Interpreter
Click here for a standalone version of the 3AC interpreter.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Sun, May 01, 2005

3AC Interpreter
I've posted a virtual machine written in Python that will execute the 3AC for Assignment 3. You can download a copy fo the 3AC factorial program here. Make sure that you have Python installed, then type

$ python 3vm.py factorial.3ac

You'll see a trace of memory accesses and the output of the program.

(Note: now that I've actually been able to run the program, I've updated the original factorial program and its corresponding 3AC code, and added a HLT instruction to the 3AC definition.)

/var/spool/courses/csuf/2005/spring/cpsc423 #

Example Parser and another Lexical Analyzer
If you had trouble finishing Assignment 2, you can download example.zip to start work on Assignment 3.

The parser was generated with the Coco/R compiler generator. To add semantic actions, you can either read the documentation, edit example.atg and re-generate the compiler, or you can modify the C code directly.

I chose Coco/R instead of YACC or Bison because it generates Recursive-Descent parsers instead of LALR(1) parsers. You are, of course, limited to LL(1) languges, but the resulting code is significantly easier to read and debug.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Fri, Apr 29, 2005

Assignment 3
Click here for Assignment 3 and here for the 3AC syntax.

/var/spool/courses/csuf/2005/spring/cpsc423 #

No class tonight
Class is canceled tonight. I apologize for the short notice, but at least you'll have Friday evening free. Please start reading Chapter 6 for next week, and check back here in a few hours for Assignment 3.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Tue, Apr 19, 2005

Example Lexical Analyzer
As you finish up working on the parser, if you're feeling shaky about your own scanner, you can grab lexer.zip.

This is a scanner generated by Flex, the GNU Fast Lexical Analyzer generator. You need the .c and .h files to compile a working program.

The file example.l is the Flex source file; you won't need this unless you want to change the scanner. The file lex.yy.c was generated with the command flex -l example.l.

Take a look at main.c to see how the lexical analyzer works. Call yylex() to get the next token. The value returned by yylex() will be one of the token types defined in y.tab.h. When yylex() finishes, the variable yytext will contain the corresponding lexeme.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Wed, Apr 13, 2005

For Windows people
I used py2exe to generate Windows executable that you can run without installing a Python interpreter. Download generate.zip and unzip it, then run generate.exe. If this doesn't work (and it may not -- I haven't written a Python program for Windows in nearly five years), go over to ActiveState and download ActivePython.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Test Generator
If you want to torture-test your parser, download this Test Generator written in Python.

While the code is a little complicated by the need to keep track of declared variables and indentation, really all it does is use the grammar the way Chomsky intended, in "reverse", to generate new programs.

Note too that while the programs are syntactically correct and obey the rules that I set down in the assignment for the use of identifiers, they're completely meaningless.

/var/spool/courses/csuf/2005/spring/cpsc423 #

I give up
I've updated the examples yet again. Sigh.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Yet another syntax error
Turns out that the WHILE loop in the factorial example program is missing parentheses:

WHILE i < 9 OR i = 9 DO

should be

WHILE (i < 9) OR (i = 9) DO

You're only allowed to leave off the parentheses if there's a single expression (as in the fibonacci program). What can I can say? Writing programs without a parser to check them isn't easy.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Tue, Apr 12, 2005

Using Context-Free Grammars for Evil
Oh dear. You realize that you can use CFGs to generate text, and not just to parse it, right?

Behold SCIgen - An Automatic CS Paper Generator

Disclaimer: if you try submitting one of these to a class and you get caught, don't blame me.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Fri, Apr 08, 2005

Syntax Error
Ok, so how long were you going to wait before telling me that one of the example programs had a syntax error?!?

/var/spool/courses/csuf/2005/spring/cpsc423 #

Fri, Mar 18, 2005

Assignment 2
The official version of Assignment 2 is available. Surprise: it's a parser.

There are also some minor semantic checks, preparatory to generating intermediate code in Assignment 3. Note that if we define the relational operators to return type INTEGER instead of a Boolean type (regarding 0 as false and non-zero as true the same way that C and C++ do), we obviate the need for type checking. You can thank me later.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Wed, Mar 16, 2005

Speaking of Donald Knuth...
NPR's Morning Edition ran an interview with him on Monday.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Fri, Mar 11, 2005

Class Outline Update
I'm making a slight change to the Course Outline. Skip Section 4.2 of the book. Operator-Precedence parsing is a waste of time -- we're not going to use it, and it doesn't make make it any easier to understand LR Parsing. For that matter, skip directly to Section 4.3. Once you feel comfortable with LR Parsing, come back to Section 4.1 -- at that point it should make sense.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Programming Assignment Submission
When you submit your assignment, I want both electronic and hard copies. To submit an electronic copy, either give me a floppy disk with the source code, or e-mail it to me. I will give you your diskette back. Do not include executable files, especially in e-mail.

The deadline for assignments is the end of class on the due date. By that time, you should have submitted either a printed or electronic copy. I would prefer that you submit both prior to the deadline, but as long as I have one by that time, you'll be ok. If you have not submitted at least one copy of your program to me by the deadline, you will not receive credit for the assignment. I do not accept late assignments.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Mon, Feb 28, 2005

Missing Course Notes
If you picked up my course notes after class Friday night, please e-mail me or drop them off in the Department office.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Mon, Feb 21, 2005

A clarification
I received an e-mail asking whether the example programming language is case-sensitive.

Well, err... yes, isn't everything these days case-sensitive? (Whaddaya mean "not Visual Basic?")

Yes, Pascal was case-insensitive, but subsequent languages in the Wirth family (e.g., Modula-2, Modula-3, Oberon, Component Pascal) have all been case-sensitive. I've updated the assignment to reflect that.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Sun, Feb 20, 2005

Compiler Construction using Flex and Bison
If you decide to use lex and yacc (or GNU flex and bison) for the programming projects this semester, you may find this book helpful.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Tue, Feb 15, 2005

Assignment 1
Click here for details.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Fri, Feb 11, 2005

Grammar and Examples
The grammar for this semester's programming assignments is available, as well as some examples.

/var/spool/courses/csuf/2005/spring/cpsc423 #

Sat, Feb 05, 2005

CpSc 423, Language Processor Techniques
Click here for the syllabus, outline, and other resources.

/var/spool/courses/csuf/2005/spring/cpsc423 #