CS 241 Fall 2013 Course Notes

13 Pages
Unlock Document

Computer Science
CS 241
Nomair Naeem

CS 241 - Foundations of Sequential Programming Kevin James Fall 2013 De▯nition Sequential programs are procedurally driven programs which only use a single process at a time. They are single-threaded and do not run processes concurrently. For this course, we are not interested in what those programs do, but simply in how they do it. These programs can be written in machine language, assembly, higher-level languages... whatever. Since each is an abstraction of a lower level to which we can build a compiler, all of them will give us the same ▯nal result. Data Representation A computer sees a string such as "10000011" as a sequence of bits, without regards to any sort of encoding. This could be binary, hexadecimal, decimal, ascii... pretty much everything, but the computer can not know which. Hexadecimal Representation Hexadecimal is represented with the characters "01234567899ABCDEF". We tend to write them in the form 0x2A, which is equal to 42 in decimal. Negative Numbers With n bits, we can represent 2 numbers in binary. To represent negative numbers we can use the sign and magnitude sign and magnitude: use the ▯rst bit as an indicator of sign and the remaining bits as magnitude method, though this is subject to some weirdness. We will end up with both a positive and a negative zero and will need specialized hardware for both addition and subtraction. A better method is to use two’s complement 1 two’s complement: uses the congruences of numbers to represent their negatives We can convert a number into two’s complement form by the following method: -6 can be converted by taking the absolute value in binary (0110), then ipping all of its bits (1001) and adding 1 (1010). Obviously this method can be used backwards: subtract 1, ip the bits, and add a negative number. Alternatively, subtract 2 if and only if the ▯rst bit is non-zero (to go from two’s complement to decimal). Parts of a Processor A processor is comprised of a control unit, which controls the execution of the program and keeps track of the next instruction to execute. It can interpret strings of binary as command instructions and controls the signals to and from any external devices. It contains a timing device for synchronised operations. The processor also contains an arithmetic logic unit, which is responsible for arithmetic and logic operations. The program counter (PC) is a 32-bit register which contains the address of the next instruction to be executed. The Instruction Register (IR) contains the current instruction address. We also have General Purpose Registersthirty-two zero-indexed registers which are 32-bits in size though they are somewhat slow. Range of Registers Our registers range from $0 ▯ $31. Register $0 always contains the value 0 and register $31 always contains the value of the return address. Register $30 contains the address of the top of the stack. How a Program is Executed The OS invokes the "loader" to load the program into memory starting at some given memory address, virtually always zero. The loader places the starting address in the PC: "PC ! 0x00". We then fetch, decode, and execute each instruction in order. In e▯ect: while(1) { fetch // IR expr op expr op -> +|-|*|/ expr -> term term -> a|b|c|d... can be used to derive the input string "a + b". Beginning with an expr we can use the following derivation: S expr expr -> expr op expr expr -> term term -> a op -> + expr -> term term -> b If we include a rule such as expr ! ( expr ), we ▯nd ourselves with a CFG which can accept a potentially in▯nte level of nested brackets. We formally specify CFGs as follows: each is a 4-tuple (N;T;P;S) where we have ▯ N is a ▯nite set of non-terminals ▯ T is a ▯nite set of terminals ▯ P is a ▯nite set of production rules ▯ S is a unique non-terminal with which we start Canonicity If we always expand the left-most terminal ▯rst, we will ▯nd ourselves with a left-most / left canonical derivation. Similarly, expanding the right-most terminals ▯rst gives us a right canonical derivation. 7 For any given input string, thes
More Less

Related notes for CS 241

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.