CS5031: System Software

This is now out-of-date, as the syllabus for CS5031 changed for Autumn 2000

CS5031 was half-and-half Operating Systems and Compilers.

Compilers part of CS5031

Each session will consist of: a lab practical on unix workstations (using lex, yacc & gcc) or: a lecture followed by paper-and-pencil exercises. The exercises & lab practicals will be used both for reinforcement and for further exploration.

Session timetable	Activity & Handouts	Extra information
C1 - lec1	Introduction and Assemblers & Compilers	answers to exercises
C2 - lec2	Lexical analysis - Lex and example run of lex calculator	answers to exercises
C3 - lab1	Lex practical	flex manual hints: strings and comments ANSI C: characters, pre-processing, syntax
C4 - lec3	Syntactic analysis - Yacc & Parse Trees and example run of yacc calculator	answers to exercises (and see answers to lab2 below)
C5 - lab2	Yacc practical	byacc manual, including %left etc. & examples Answers: (a) multiple expressions 1: c & results 2,3,5: data & results 4 6,7 (b) (and see answers to lec3 above)
C6 - lec4	Semantic analysis - Dictionaries and example snapshots of dictionary	answers to exercises
C7 - lab3	Syntax-directed Translation practical
C8 - lec5	Syntax-directed Translation	[exercises?]
C9 - lab	catch-up	you can complete labs 1-3 (above) and start to think about the assessment exercise (below).
C10 - lab	catch-up

Assessment
2nd week timetable The deadline may be the end of term (17th/Dec) but you are strongly advised to finish by the end of the fortnight (3rd/Dec).	25%	Compiler: Lex, Yacc and C practical if you require help mail pjj@cs.man.ac.uk	hints: grammar, strings and comments, bonus work Get the basic exercise (worth 70%) marked as soon as you have completed it - preferably by the end of the week. I am happy to mark any bonus work separately.
	25%	Operating Systems: written report
January Exam (17th-28th 2000)	50%	Answer 3 questions from 4 in 2 hours	2 questions on Operating Systems In 1997/8, these were similar to those set in 1996/7. 2 questions on Compilers The 1996/7 compiler questions are only partly relevant owing to syllabus changes. The 1997/8 & 1998/9 questions are in this form: A question about using lex and yacc (and a dictionary or parse trees or similar) to recognise a simple grammar - similar to the lab exercises & examples sheets. A question about compiler phases and code generation - e.g. describe what happens in the phases, give ARM code for some C, etc. The syllabus has changed, so we are not going to cover code generation for the ARM. I will have to think of something a little different to ask instead of that part Here are the 1997/8 questions and answers and marking scheme.

what happened last year

Here are some hints about exam technique

Extra information about the practical exercises will appear here.
Handout: Debugging flex, byacc and make
If your program crashes at run-time, making a "core" file, and you want to find out what line it went wrong at etc., on Suns do:
dbx program_name where quit
or on Linux do:
gdb program_name core where quit
(This relies on using gcc -g, as with the makefiles I provide.)
Lab exercise 1 In the example output, I have picked up adjacent white-space characters to be a single lexeme using
[ \t\n]+
but in the problem description and in the starting code I only pick up single white space characters using
[ \t\n]
I would prefer to do the former, but I have to do the latter to be able to recognise preprocessor commands properly - can you see why? If not, try changing the rule for white space to see what happens - you should get lots of messages from the checker.
When you "make test" for the first time, you should see something like this:
echo your output is being redirected to "out1" your output is being redirected to out1 ./c_lexemes <data.c >out1 echo here are any error messages - look at "out1" for more details here are any error messages - look at out1 for more details grep OOPS out1 4 OOPS - #include <stdio.h> is a preprocessor_command (not white_space etc. - see following list) 4 OOPS - #define a(nasty)\ echo here is the final report, counting characters and lexemes here is the final report, counting characters and lexemes wc -c <data.c ; tail -20 out1 1197 numbers of lexemes & characters - 22/9/99 10:17 GMT 380 ignore(s) in 960 characters 0 float_number(s) in 0 characters 0 octal_int_number(s) in 0 characters 0 decimal_int_number(s) in 0 characters 0 hex_int_number(s) in 0 characters 0 preprocessor_command(s) in 0 characters 0 comment(s) in 0 characters 0 character(s) in 0 characters 0 keyword(s) in 0 characters 0 built_in_type(s) in 0 characters 0 identifier(s) in 0 characters 0 punctuation_or_operator(s) in 0 characters 0 punctuation(s) in 0 characters 0 operator(s) in 0 characters 0 string(s) in 0 characters 0 unknown(s) in 0 characters 237 white_space(s) in 237 characters total: 617 lexemes in 1197 characters
As you can see, the checker is over-enthusiastic about pre-processor commands.
There is a second, rather larger set of test-data: bigdata.c
You are welcome to try your program on this - remove the leading "#" characters from these 3 lines in the makefile to do so:
# ./c_lexemes <bigdata.c >out2 # -grep OOPS out2 # wc -c <bigdata.c ; tail -20 out2
Don't get bogged down trying to deal with some of the wierd things in this file before you have dealt with the simpler problems in the first data-file.

Extra information about the practical exercises will appear here.
Handout: Debugging flex, byacc and make
If your program crashes at run-time, making a "core" file, and you want to find out what line it went wrong at etc., on Suns do: dbx program_name where quit or on Linux do: gdb program_name core where quit (This relies on using `gcc -g`, as with the makefiles I provide.)
Lab exercise 1 In the example output, I have picked up adjacent white-space characters to be a single lexeme using [ \t\n]+ but in the problem description and in the starting code I only pick up single white space characters using [ \t\n] I would prefer to do the former, but I have to do the latter to be able to recognise preprocessor commands properly - can you see why? If not, try changing the rule for white space to see what happens - you should get lots of messages from the checker. When you "make test" for the first time, you should see something like this: echo your output is being redirected to "out1" your output is being redirected to out1 ./c_lexemes <data.c >out1 echo here are any error messages - look at "out1" for more details here are any error messages - look at out1 for more details grep OOPS out1 4 OOPS - #include <stdio.h> is a preprocessor_command (not white_space etc. - see following list) 4 OOPS - #define a(nasty)\ echo here is the final report, counting characters and lexemes here is the final report, counting characters and lexemes wc -c <data.c ; tail -20 out1 1197 numbers of lexemes & characters - 22/9/99 10:17 GMT 380 ignore(s) in 960 characters 0 float_number(s) in 0 characters 0 octal_int_number(s) in 0 characters 0 decimal_int_number(s) in 0 characters 0 hex_int_number(s) in 0 characters 0 preprocessor_command(s) in 0 characters 0 comment(s) in 0 characters 0 character(s) in 0 characters 0 keyword(s) in 0 characters 0 built_in_type(s) in 0 characters 0 identifier(s) in 0 characters 0 punctuation_or_operator(s) in 0 characters 0 punctuation(s) in 0 characters 0 operator(s) in 0 characters 0 string(s) in 0 characters 0 unknown(s) in 0 characters 237 white_space(s) in 237 characters total: 617 lexemes in 1197 characters As you can see, the checker is over-enthusiastic about pre-processor commands. There is a second, rather larger set of test-data: bigdata.c You are welcome to try your program on this - remove the leading "#" characters from these 3 lines in the makefile to do so: # ./c_lexemes <bigdata.c >out2 # -grep OOPS out2 # wc -c <bigdata.c ; tail -20 out2 Don't get bogged down trying to deal with some of the wierd things in this file before you have dealt with the simpler problems in the first data-file.

Resources

I teach a related undergraduate course CS2111: Design, Use and Implementation of Programming Languages, which you may find useful, including pointers to information about lex, yacc and C.

The content of this page and those it links to is copyright © Pete Jinks, except, obviously, for links that go to other web-sites, and pages that I have myself copied from elsewhere. (I hope I have correctly acknowledged any such copying - please let me know if I have missed any out.)

You are welcome to make educational, not-for-profit use of my work, but please give me credit when you do so.