Architecture and Compilers

News Handouts Labs Resources References Old News

This is the homepage for CS 353: Architecture and Compilers, a course offered by Fritz Ruehr at the Computer Science Department of Willamette University.

Learning to program in Java or Python can be fun and empowering, but it may still leave you mystified about how computers really work: what are the components of a physical computer? How does the computer “know” what to do when it runs a program? What connects abstract ideas like objects and methods to the silicon hardware?

This hybrid course in computer architecture and high-level language processing (compilers) will provide you with the answers to these questions. The course is a “soup-to-nuts” overview of the various levels of structure embodied in a physical computer, as well as the various stages by which high-level languages are translated into a form which the computer can directly execute. In traditional curricula, these two topics are often covered in separate courses—we have combined them into a single comprehensive overview in order to expedite Willamette's pedagogical goals.

We will start our journey with basic facts about binary encodings, how they are used to represent data and how logical operations can be used to transform these data. We will then see how basic electrical components called gates can be used to realize these operations on digital signals, and how they can be combined into circuits which will implement more complex processes. Finally, we will see how these circuits are used to build higher-level components which constitute a typical computer, and how digital data stored inside the computer can be used to control its operation. In the second phase of our studies, we will start with the strings of characters which comprise a program file, and see how it can be analyzed in successive stages until the internal structure of the program is exposed. We will then see how this internal structure can be translated into the low-level codes which a computer can execute, in a way which respects the meanings of the original program. Finally, as time permits, we will survey a few important concepts which inform the design of high-level languages both like and unlike Java or Python.

News

• Here are some handy regular expression resources for Python in particular:

  • the official python (3.9) documentation on the re regular expression library;

  • a handy “how to” guide, also from the official python (3.9) documentation;

  • the w3schools.com section on regular expressions in Python, complete with embedded, interactive examples.

• Check out thus truth table generator generously provided by a class at Stanford, or this generator from Michael Rieppel at Syracuse University, … or this one with a purple monster and a psychic duck (!) from Christian Gottschall at the University of Vienna.

• Here is the Fall 2020 syllabus (note that I am not distributing this or many other documents on paper this semester, due to issues with the Covid-19 pandemic).

Hereafter starts the old news part of the section …

• Here are the new Fall 2019 final exam review notes!

• An animated version of stack machine compilation, is here, but it doesn't seem to work well in FireFox (try Chrome or IE).

• Here are some links relevant to the code generation part of the compiler:

  • some code templates for a stack-machine-based approach;
  • sample multiplier code;
  • sample outputs for a long expression (naive and optimized);
  • some extremes in approaches to compilation.

• For those of you who use a lot of emoji, check out this keyboard (but it doesn’t have all of Unicode, unfortunately …).
• OK, here is a new set of notes on the Shunting Yard algorithm, which we will follow in lecture.

• Check the following links for examples of context-free grammars:

  • A much simplified Java grammar.

  • A somewhat more realistic Java grammar (and in a slightly different notational style).

• Someone on reddit.com/r/programmerhumor posted this (critical) meme about RegExpr syntax.
• Here's an on-line , interactive regex tester for Java (hmm: broken link?) from the people at ocpsoft.org,
  part of their Guide to Regular Expressions in Java.
  Here’s another one, at regexr.com.
  Here are parts one and two, of a tutorial specifically about Java’s API for RegExprs.
  And here are 10 regular expression examples in Java from M Kyong.
  (You can find many other examples and tutorials by using Google.)
• Here's a real-world example of practical regular expression use (using the sed unix tool)
  and a sample from my text editor (for pulling out student rosters).
• Here's Sun's Java regular expression tutorial.

• Here are the new Fall 2019 midterm review notes, all ready for the exam on Friday 25 October.

• Fall 2019 student David Vitez provides this PC-231 data scratch sheet to help you keep track of things when you program the PC-231. (Specifically, it can help you track the history of changes to registers and RAM —in conjunction with “chatty” mode, it should be all you need!)

• Get started on your midterm exam studying now with this set of sample problems to practice for the exam.
  Let’s agree that we will do these as a self-graded assignment due on Mon 14 Oct for “grading” in class.
  (Meaning: be prepared to share your answers, perhaps on the board, and to understand how other people solved them.)
• Here is a convenient “top-of-the-News” link to a design for a PC-353 machine,
  the ideas for a PC-231 GUI interface, and
  a version of the multiplier we worked up in class (remember, this one ignores signs).

• Regarding near-term scheduling:

  • the mid-term exam has been scheduled (by class vote) for Fri 25 Oct:

    

  • remember that there is no class on Fri 18 Oct, as it is the college-wide mid-semester break day;

  • a mid-term exam review outline will be posted soon—we will spend Mon 21 and Wed 23 in lecture reviewing for the upcoming exam.

• OK, some things related to Lab 4: the Hidden Circuit Simulator.

  • I fixed a few things in the lab write-up itself (see link above) and in the advice on structuring (see the next link). Specifically, I changed the way I would recommend doing the syntax for lights in the lab write-up and added a remark about GUI elements and their proxies. In the structuring advice, I fixed a bug in the code where I wasn’t calling the hash table’s get method enough times in the sample code.

  • Here is the revised advice on structuring the hidden circuits lab.

  • And finally, here are the bonus graphics of lights; feel free to use them in your GUIs (or just use standard (e.g.) Swing components).

• Now that we are all a little more familiar with bits and bytes, check out this game design video that David Vitez brought to my attention—back in the day, it was all about squeezing out a few more bytes (but even today, performance still matters … ).

• As we get into learning about computer architecture and the PC-231, you’ll want to use the big, teal computer icon on the right or just this link to access the PC-231 description file.

• I’m going to recommend for Lab 3 that you use the LogicLy (free trial); circuit simulator. Some alternative simulators available for { free, trial usage, cost } include the following:

  • Logic Lab from Neuro Productions) [requires Flash];

  • Simulator.io (on-line);

  • the Do Circuits vitrtual lab (on-line);

  • the Logic Gate Simulator from Academo (only single output!).

• Here is a 51-page document from summer of 2019 explaining the (then current) Unicode approach to emoji.
• Unicode is described here, the UTF-8 encoding is here, and you can read about the latest in Unicode, including controversial Japanese emoji characters, here.
  Finally, you can read about the Swift programming language’s approach to various Unicode woes in this blog post from Ole Begemann (an extract from a new book on Advanced Swift).
• We’ll use this ancient lecture on data representation on Friday 6 Sep (or soon thereafter).
• a visual key to bits, ints and chars
• the Tengwar ("elvish") Unicode proposal / ConScript registry, and the Klingon one
• Read what every programmer should know about Unicode (from Joel Spolsky: don't let him put you in a submarine, peeling onions).
  (And you might as well read about HTML 5 while your at it, here from Mark Pilgrim.)

• The on-line version of the Fall 2019 syllabus is here.

• Someday soon we should talk for a bit about storage costs for Java objects, as relevant to Lab 2 especially.

• OK, as of the first week of class, you should be working on Lab 1: Numerals, numbers and strings, a basic warm-up exercise. (If it seems to simple to you, concentrate your best efforts on issues of code modularity, error-checking, corner cases, etc.)
  But everyone should make sure that their program checks that the digits in the input numeral are in range for the given base.

• Need help with all that base-conversion and two’s complement stuff? See these links for some help:

  • check out this graphic to convert bases using Horner’s technique (to go the opposite direction, produce digits from right to left using the mod operator (%), updating the total using division (/) by the base);

  • you can find the two’s complement “clock graphic” here;

  • and see the two’s complement conversion instructions in this PDF file.

• Just for fun, here is a nice little computer for counting in binary.
  (Psst! There’s also a link down below to a wood and marbles adding machine.)

• Check out the new Fall 2018 final exam review notes!

• Read about the Swift programming language’s approach to various Unicode woes in this blog post from Ole Begemann (an extract from a new book on Advanced Swift).

• In the news today, and relevant to our current topics, here is a thread on StackOverflow about why different associations in a Java expression lead to different run-time results.

• Following Turkey Day break we will be going over Dijkstra’s Shunting Yard Algorithm, using these notes.

• Here are the new Fall 2018 midterm review notes, all ready for the exam on Monday 29 October.

• As we move into use of the PC-231 abstract computer for our labs, you will need a good terminal emulator: on a Mac, this can be just the Terminal app located in the Utilities sub-folder of your Applications folder. On Windows, you can use the stalwart PuTTY, but it’s pretty old-fashioned; for some alternatives, check out these web pages (found via a simple Google search):
  • This list from MakeTechEasier;
  • this list from Slant;
  • this list from Softonic;
  • and this discussion at Quora;

• Alex Lockwood, your intrepid Lab Assistant, has kindly supplied some sample inputs for Lab 4 here (as a ".txt" file), for use in your demos.

• Weekend Update: since a number of people were gone for various athletic events and illness this past Friday (14 Sep), I thought I would consolidate information for them here on the homepage as to what went on in class. Specifically, we talked about the nature of low-level switches (such as transistors), and how they can be used to implement common logic gates; see this graphical explanation. In lab, we saw how truth tables can be used to determine the “logical” way to add two numerals in binary. This is also now discussed and illustrated at the end of the revised Lab 2 write-up

  Also, for the latest scoop on Unicode, see this blog post on Unicode 8.0 and this one on Unicode 9.0.

• As promised in lecture, I have updated the Lab 2 write-up to include more detail (and accurate binary numerals …); you can find the resulting new write-up here.

• The new Archive section can be found below by clicking on this link right here. (More material will be added from these News links soon; use “find in page” for now.)

• Just in time for the upcoming final exam review, here is a very detailed explanation of Horner’s technique in the context of evaluating numerals (in an arbitrary base).

• Here‘s a shorter version of multiply I worked up in class the other day year—this one is simpler than the one we saw Friday since it ignores signs.

• Alden sends this link to a 10-minute take on computer architecture from “LosT” at DEF CON 24. (Maybe we should have just watched this and then taken the rest of the semester off until the final, eh?)*

  * Fritz’s near-Canadian roots are showing …

• I will try really hard to remember to show you all a “gated SR-latch” on Wednesday (this is here to remind me):

  gated SR-latch circuit.

  (Here‘s how it looked in the older “Logg-o” tool: less room to draw, but real gate shapes.)

• Stop the presses! There is a new version of the Lab 2 main picture available here; in particular, it corrects some errors in the original lab 2 graphic, so check it out!
  (Oh, and by the way, here’s a more convenient link to the “two’s complement clock”; thanks and a “hat tip” to Elizabeth for reminding me to add this link!)

• OK, just to start off the semester right, WU CS and CS 353 alumnus Nathaniel Garst sent me this page from Ken Shirriff’s blog which shows what an Intel 8008 processor looks like on the “inside” (where the “Intel” is, I suppose).

  Thanks, Nathaniel!

• And, continuing this trend of focus on processors, here is a little video on How a CPU is Made.
  (This one is a much higher-level, non-technical run-down wit focus on materials and manufacturng processes.)

• A more realistic sample circuit … for use on the final exam?
• The 2014 final (ahem) review notes are now available.
• Here's a circuit diagram for you!
• Here's a sample implementation of binary trees in C (from The Geek Stuff).
• The 2014 midtem review notes are now available.
• Here's Wikipedia on the gated D latch.
• At this link you can find a possible alternative for use in the circuits lab (The Logic Lab from Neuro Productions).
• Here's the the course syllabus as a PDF file.
• Here are links to Nick Parlante’s Essential C at Stanford and to my Lightbot project in C.
• Here you can read a story (or is it a poem?) about Mel, a Real Programmer.
• Here's a link to that news report video I mentioned about Paul Allen’s computer museum.
• Check out the hints on programming the circuit simulator.
• Philosoraptor goes meta on programming.
• Forget coconuts and palm trunk troughs, here's how you can make logic gates out of DNA plasmids!
• And here's that gated D latch I was looking for BROKEN LINK.
• News from slashdot re hacking PROMs with microscopes.
• Eoin says: “306 9ea c20 200 211 1e0 601 9e0 d10 91e 428 e24 000”!
• Eoin Sinclair found a possible alternative for use in the circuits lab (The Logic Lab from Neuro Productions).
  Another possibility (commercial, but with a free trial period) is Logic.Ly.
• Maybe magnetic switches aren‘t such an old-fashioned idea after all.
• My wife spotted this on-line via Facebook, where user Eliyahu wrote:

  “...did you see the bottom line? I programmed my first computers in binary, using toggle switches. I always think of how my code turns into electrical signals, even when it's "written" by connecting pictures in XCode that are compiled into Obj-C that is compiled into C that is compiled into LLVM that is compiled into Assembler that is assembled into object code that is linked into binaries that becomes executable code that is dispatched through the pipelines and routed through the logical arrays of gates ... and then back out into representations that eventually have a meaning assigned by humans. ”

  (and here you thought I was just making this stuff up as we went along ...)
• Fritz wouldn't do this, would he?
• At least this isn't me!
• This diagram details building gates from switches.
• Happy Programmers’ Day!
• The controversy continues (!) in Yacc is Not Dead
• IBM is apparently making great strides in light-based (optical) computing (I have to say that “silicon nanophotonics” sounds like something out of Star Trek).
• Straight from the Unicode horse's mouth (is there a character for that?) comes this FAQ about UTF encodings.
• Just in time for our discussion in class here's a blog post about relocatable code.
• Some say that Yacc is dead (but not everyone agrees).
  Also, check out this paper, "Pure and Declarative Syntax Definition: Paradise Lost and Regained" with a distinctly biblical introduction (!).
• Here are some links about more realistic architecture issues:
  • processor pipelines;
  • microcode (below the level of machine code!);
  • RISC (versus CISC);
  • register files.
• ...and here are some links about issues of evaluation order in various languages:
  • people are a bit dismayed about how this works in C;
  • Java at least seems definite about things;
  • ... even for method arguments (which is strictly speaking a separate issue);
  • Python goes left to right (for operators, at least);
  • APL goes strictly right to left.
• Here are some links about register allocation, graph coloring and related issues:
  • some stats on memory costs;
  • graph coloring at Wikipedia;
  • liveness analysis at Wikipedia;
  • Leonidas Fargas' notes of register allocation;
  • Wikipedia on register allocation;
  • a paper with a claimed improvement (generalization of) register allocation, by Smith, Ramsey and Holloway.
• Warning! The relative operator precedence of bitwise masks and shifts in Java means that you will likely need to parenthesize your masks when doing both.
  So:

  ... ( inst & 0x0F0 ) >>> 4

  
  rather than:

  ...   inst & 0x0F0   >>> 4

• You can read about Chuck Peddle and the 6502 processor in this article which questions who really started the personal computer revolution
  (of course, the story isn't quite that simple, but still, have you ever heard of Chuck Peddle? (I mean, anyone other than Collin?)
• Study for the midterm (Wed 20 Oct 2010) using these notes
  And here is a sample exam (from CS 231, Intro Programming) to give you a sense of the format (of course, the content will be different!).
• Here's an explanation of the use of transistors to build NAND and NOR gates using serial and parallel connections.
• Oh, and the version of multiply I showed in class the other day was here.
• Read about the latest in Unicode, including controversial Japanese emoji characters, here.
• By request, we have here a a few sample problems to practice for the exam.
  These will be self-graded; I'll post a separate solution sheet soon.
• The swapping multiply program we developed in class on Friday is here.
  Thanks to Ben for the transcription!
• Here's a scanning electron microscope picture of the surface of a silicon microchip (I assume this has been artifically colorized);
  you can see other items close up in this article from the Daily Mail.
• Learn about null-terminated strings so that you don't become the butt of Java jokes!
  ... and look at some old computers.
• For those who read Reddit, there is now a subreddit for CPU design.
• As we move into discussion of computer organization and architecture, the following links may prove useful:
  • the Wikipedia article on (gated SR) latches
  • a picture of a gated SR latch
  • a working version of a gated SR latch (NOT YET!)
  • the description of and the "working picture" of the old PC-101 machine
  • a 16-bit ALU created inthe game Minecraft (!)
  • some ideas for a PC-231 GUI interface
  • a design for a PC-353 machine

• Here are some links about the women who pioneered programming on the ENIAC computer, as we discussed the other day in class:
  • Wikipedia article on the ENIAC and its programmers
  • Wired News article: Women Proto-Programmers Get Their Just Reward
  • WITI (Women in Technology International): Hall of Fame
• Check out this description of one programmer (Jeff Minter)'s first brush with assembler and it's speed compared to higher-level langauges (I daresay the comparison with Java or Python would be even more remarkable ... not that you really want to write in assembler, though).
• Some fine people at Visual6502.org have written a full 6502 chip simulator in Javascript, runnable on the web (also available in Python). We'll have to try this out when we get to that point in class! (They have more info, slides, a research paper, etc., on their project homepage.)
• Here's an on-line truth table generator, kindly provided by Professor Lawrence Turner.
  (Here's another one, by Brian Scott Borowski, and a bit more elaborate, although I had trouble getting it to work.)
• Is C really just a portable assembly language? Apparently opinions on this matter differ.
  (Context: this was the subject of some remarks in lab today, Wed 15 Sep 2010.)
• Here are Sam's diagrams (that's two links there) showing the "two's complement clock";
  or, if you prefer, here's my own version

• A binary-decimal converter

• A binary counter graphic

• A Virginia Tech tutorial (look at I, II.A and II.B)

• Here's a wood and marbles adding machine.
• another kind of very little machine
• some real-world timing data, albeit circa 2001
• here are some nice, thorough course notes on computer organization by Grant Braught at Dickinson College
• Here are some advanced tips on "real-life" regular expressions.
• Here's are some old notes on about converting DFAs/NFAs to regular expressions.
• So, as you can read here, the Java programming language spec does guarantee that operator arguments are evaluated from left to right ... but despite this guarantee, they recommend against any dependence on order of evaluation (!) .

• Check out Oliver Steele's regular expression visualizer (edit the pattern itself on the upper left, input on the upper right)

• I made a small (but important) change to the description of the shunting-yard approach to parsing in the description of lab 9. More specifically, Sam noticed that I had assumed there that we were doing operators of equal precedence right-associating, whereas this semester we are using left-association. This means that operators of strictly greater precedence would cause a shift instead of a reduction.
  See the lab 9 write-up for more details (the change I made is in bullet point 3 of the "Parsing Strategy" section.)
  Thanks, Sam!

• Check out this graphical overview of the Java Virtual Machine.

• Here's a better (i.e., actually works) link to the Java Virtual Machine spec (the one on the class handout apparently suffers from bit-rot).

CS 353 Handout Archive

This section of the homepage (inaugurated Spring 2017) will be a growing collection of handouts for the class, organized by topic, in chronological order. The files are, for the most part, in PDF format, which should be easily readable in a browser or with other tools if downloaded.

(Note: some, but not all, of these handouts are already linked from the course homepage, or from individual labs.)

• Homework and quizzes

• a sample homework assignment
• an old midterm makeup quiz

• Numerals and numbers

• more detailed visual on Horner‘s technique
• ... and the “opposite” Horner‘s technique

• Hardware

• using switches (transistors) to build gates

• Bit manipulation

• the 5-bit two’s complement clock
• some notes on storage costs of Java structures
• inter-conversion between Java ints and PC-231 integers

• Circuit simulator

• notes on a possible class structure for the Circuit Simulator lab

• Machine architectures

• a description of the old, 8-bit PC-101 machine
• a layout/worksheet for the PC-101 machine
• a short description of the PC-231 machine
  (This is used as an “appendix” for exams.)
• design ideas for making a PC-231 GUI interface
  (The course homepage has an interactive, “animated” HTML version.)
• some notes on the design of a more advanced PC-353 machine architecture

• Assembly language

• some ideas on implementing sub-routines
• some hints on how to write the assembler for Lab 7
• ... and yet more hints on the assembler for Lab 7!

• Expression language and trees

• a diagram showing the phases of translation (i.e., compilation or interpretation).
• a quick decription of the language used for the compiler labs
  (rather like the PC-231 description, this was used as an exam appendix.)
• some notes on how to represent syntax trees in Java
  (special thanks to Anna for inspiring these notes with a question!)
• suggestions for a class design for expression trees
  (Note how this looks a lot like (an extended version of) the circuit simulator.)
• an overview of the structure and goals of the later course labs

• Scanning and parsing

• ideas on how to structure the lexer and lexer-parser interface
• more hints—possibly a variant version of the above
  (Also known as the infamous “Pac-man poops tokens” handout.)
• longer decription of the shunting-yard parsing algorithm

• Code generation

• a breakdown of decision points in code generation strategies
• an outline of notes on code generation issues
  (Note: this seems to be poorly formatted, with a page break down the middle.)
• overview of code generation process
• templates for generating stack-machine based code
• a sample of a simple approach to register allocation
  (This needs a reference to the river-structure terminology.)
  Aha! See the Wikipedia page on Strahler numbers!

Labs (in chron. order) NB: due dates may be updated as we go!

(I have added “abstract due dates” below for each of the labs. What does this mean? Well, first of all, they are stated in terms of the weeks of the semester rather than the days and months of any specific year (this mean less bother about updating for me, but requires you to be at least somewhat aware of how far into the semester we are “currently” if you wish to gague your own progress). But the due dates are also abstract in that they are a little vague and soft: you are not required to finish the lab by the expected date, but should expect to do so, or perhaps strive to do so. As stated in lecture, if you let these things go too long, you will have a Bad Time™ at the end of the semester.)

• Lab 1: Numerals, numbers and strings (due 2^nd week or so)
  A simple lab to get you started thinking about strings and numbers as they are represented inside the computer in binary.

• Lab 2: Binary addition with two's complement (due 3^rd week or so)
  (The old version of the Lab 2 write-up is here.)
  Building on the last lab, you will now implement some simple operations on binary "words" (i.e., sequences of bits).
  Special note: make sure your program can be reconfigured for different word sizes (8, 16, 32). (You're allowed to re-compile if you wish.)

• Lab 3: Building circuits in a GUI (due 4^th week or so)
  Use the graphical circuit simulator to build some simple circuits that could be used to implement a computer. Use the Analytical engine circuit simulator Logic Lab from Neuro Productions (or other options listed in the News section).

• Lab 4: Hidden circuit simulator (due 5^th week or so)
  Implement a circuit simulator like the one you used last week, but without showing the circuit graphically. (Your input will be textual: you will "build" a circuit internally in Java and run it to produce boolean outputs from boolean inputs.)

  By the way, here is the revised advice on structuring the hidden circuits lab.

• Lab 5: Writing PC-231 Programs (due 6^th week or so)
  For this lab you will write several programs in for the PC-231 computer, in PC-231 assembly code (in the next few labs you will implement the tools you used for this one).

• Lab 6: PC-231 Simulator (due 8^th week or so)
  Write a simulator for the PC-231 computer: it should read in hex codes and execute the program directly, reading, storing, printing, etc. as it goes.

• Lab 7: PC-231 Assembler (due 10^th week or so)
  Write a PC-231 assembler: it should behave like the version supplied by me, i.e., it should read assembly codes and generate hex codes.

• Lab 8: An Evaluator for Extended Expressions (due 11^th week or so)
  Write an evaluator which will interpret (or execute "on the fly") programs in the extended expression language, given as abstract syntax trees (already formed, i.e., built with constructors in your Java code).

• Lab 9: A Parser for Extended Expressions (due 13^th week or so)
  Write a parser, using standard techniques or "canned" parser generation software, which will read in programs in the extended expression language and produce abstract syntax trees.

• Lab 10: A Compiler for Extended Expressions (due end of class (or thereabouts ☺))
  Write a code generator which will take an abstract syntax tree in the extended expression language and generate PC-231 machine code from it (of course, the code should run and produce the same results that the high-level program would have). You should hook up this code generator with your parser so as to make a complete compiler.

Some useful resources, etc.

• Here are some links to popular compiler and architecture books which might be useful for further study:
  • the traditional "dragon book" (now a bit out of date);
  • a newer edition of the "dragon book";
  • a "mixed text" which covers programming language issues as well;
  • an "advanced text" with considerable depth;
  • a text with an example compiler written in Java;
  • a standard text on computer organization (architecture);
  • another book by the same authors;
  • another popular text on computer architecture.
• Here's some notes on a decompilation system, which show some examples of real assembly code and the correspondence to high-level code.
• Some info on new features in Java 5
• Here's a version of binary tree sort in C,
  and an in-lined version which uses a loop for insertion.
• Look here for a tutorial on regular expressions in Java
• Here's an Introduction to C Programming you might find useful.
• The PC-231 architecture description
• Joel Spolsky and Schlemiel the painter on Java, C and what you need to know to succeed ... (Thu 14 Sep)
  (and more from Spolsky here, plus discussion from readers, and some other thoughts)
• See a good version of the adder circuit here

Some information about C and other miscellanea

• You can get the C compiler (gcc) on our local (hydra) system as /opt/sfw/bin/gcc. To make this easier, you might want to set up an alias in your ~/.cshrc file; just add a line like this:

  alias gcc /opt/sfw/bin/gcc

• You can get the also fix up your backspace key by adding this to your .login file:

  stty erase ^H

  (that last character is a backspace key: if your backspace is currently set to erase, this is hard to enter, but in the vi editor you can use a Control-V Control-H sequence (the Control-V escapes the next character to be entered in as a literal character)

• You can find the sample C programs we looked at in class here:
  ccode directory

• You can find the "hypertrm" program for terminal emulation (the one Duke mentioned in class) on WIndows machines under C:\Program Files\Windows NT\hypertrm.exe (note: no vowel in "trm"). You can also just enter "hypertrm" in the "Run ..." command line feature of the Start menu.

Current work archive

Remember to start studying for the midterm exam, scheduled for Friday 16 October; you can do so using the Fall 2020 midterm review notes, and check out this sample exam for the format and to test your software.

Reading/study: review lectures on the PC-231 computer and try the new homework assignment found here. Also, we will develop some code for a multiplier in class (see this older file for actual PC-231 code).

Coding: work on Lab 3: Building circuits in a GUI as listed in the Labs section below.

Current work (2nd week): review class notes and work on Lab 1

Reading: review your class notes on semiotics, digits and bases, and Horner’s technique (for the last, see the more detailed visual … document in the Handout archive below.

Coding: work on Lab 1: Numerals, numbers and strings as listed in the Labs section below. Don’t worry about making a GUI interface (unless you want to), but use the description’s white and grey boxes style to understand which items are inputs (white boxes) and which are outputs (grey boxes). This is not really due at any specific time—I also want to be able to gauge your coding level and style.

Topical references (in chron. order)

We won't be using a formal textbook this semester, so I will be trying to gather links to relevant on-line material. A lot of good-quality articles are available on Wikipedia, the free on-line "open source" encyclopedia (you might want to consider donating some portion of your textbook savings to their efforts).

• Computing hardware in general
  • Computers (in general) at Wikipedia
  • History of computer hardware at Wikipedia
  • Computer hardware at Wikipedia
  • Computer storage at Wikipedia

• Data representation
  • Digital systems at Wikipedia
  • Analog signals at Wikipedia
  • Digital media at Wikipedia
  • Codes at Wikipedia
  • Binary numerals at Wikipedia
  • Binary files at Wikipedia
  • Hexadecimal at Wikipedia
  • ASCII code at Wikipedia
  • Unicode at Wikipedia
  • Raster graphics at Wikipedia
  • Radix notation at Wikipedia
  • Two's complement at Wikipedia
  • Logarithms at Wikipedia

  • NEW! UTF-8 encoding at Wikipedia
  • NEW! Parity bits at Wikipedia
  • NEW! Check digits at Wikipedia (just for fun, not for tests)

• Boolean logic and digital circuitry
  • Boolean logic at Wikipedia
  • Digital circuits at Wikipedia
  • Switches at Wikipedia
  • Transistors at Wikipedia
  • Logic gates at Wikipedia
  • Adder circuit at Wikipedia
  • Multiplexer at Wikipedia
  • Flip-flop at Wikipedia

  • NEW! Analytical engine circuit simulator

• Computer architecture and organization
  • Von Neumann architecture at Wikipedia
  • Computer architecture at Wikipedia
  • CPU at Wikipedia
  • CPU design at Wikipedia
  • RISC at Wikipedia
  • ALUs at Wikipedia
  • Memory hierarchy at Wikipedia
  • Registers at Wikipedia
  • Memory address at Wikipedia
  • Random-access memory (RAM) at Wikipedia
  • Addressing modes at Wikipedia

  • NEW! How a real chip is made

• Assembly languages and instruction sets
  • Instruction set architecture at Wikipedia
  • Machine code at Wikipedia
  • Assembly language at Wikipedia
  • Opcodes at Wikipedia

  • NEW! Randall Hyde's The Art of Assembly Language Programming
  • NEW! Gavin's Guide to 80x86 Assembly
  • NEW! using bitwise operators in Java (from Vipan Singla)
  • NEW! an article about PowerPC assembley

• NEW! C programming language tutorials, etc.
  • Wikipedia on C
  • the classic book on C (by Kernighan and Ritchie)
  • "How STuff Works" intro to C
  • C courseware from A. D. Marshall
  • Drexel C tutorial
  • Steve Holmes' C tutorial
  • The C Book, on-line, by Banahan, Brady and Doran
  • Stanford CS library Essential C
  • Stanford CS library on Pointers and Memory
  • Peter Hosey's Everything you need to know about pointers in C

• High-level language implementation (overviews)
  • Programming languages at Wikipedia
  • Compilers at Wikipedia
  • Interpreters at Wikipedia

• Lexical analysis, tokens and regular expressions
  • Finite state machines at Wikipedia

• Abstract syntax trees, parsing and context-free grammars
  • Parsing at Wikipedia
  • Formal grammars at Wikipedia
  • Parse tree at Wikipedia
  • Abstract syntax tree at Wikipedia
  • Context-free grammars (CFGs) at Wikipedia
  • PEGs at Wikipedia (an alternative to CFGs)

  • NEW!
  • Wikipedia on LL parsers
  • Wikipedia on LR parsers
  • Wikipedia on operator-precedece parsers
  • Wikipedia on Dijkstra's shunting-yard algorithm
  • Wikipedia on recursive descent parsers
  • Homepage for the JavaCC parser generator

• Compilers and code generation
  • Intermediate language at Wikipedia
  • Semantic analysis at Wikipedia
  • Symbol table at Wikipedia
  • Type systems at Wikipedia
  • Code generation at Wikipedia
  • Code optimization at Wikipedia

  • NEW!
  • Wikipedia on 3-Address Code
  • Wikipedia on Register Allocation
  • Wikipedia on Compiler Optimization
  • Wikipedia on Run-time stack

• Java and the Java Virtual Machine
  • Java programming language at Wikipedia
  • JVM at Wikipedia
  • Java bytecode at Wikipedia

  • NEW! The official JVM Specification