辅导COMP1711、讲解C/C++,C#编程语言、辅导C-like留学生、讲解C/C++
- 首页 >> C/C++编程University of Leeds School of Computing
Procedural Programming COMP1711
Semester 1, 2018-2019
Assignment 3
40 Marks
To be submitted before 17/12/2018 at 12:00pm
The Brief
You will write a program to process plain text files containing source code written in C-like
programming languages, such as C, C++, and C#.
The Details
The Problem
Write a program to process source code files of C-like programming languages by:
1. removing all comments from a source code,
2. checking that all brackets in a source code are balanced, i.e. for any opening bracket there
exists a closing bracket of the proper type in a proper position.
In C-like programming languages there are two types of comments: single line comments which are
initiated with a double slash // and terminated at the end of the current line of code; and multiple
line comments which are initiated by /* and terminated with */. The program should remove both
types of comments from a source file.
Brackets used in C-like programming languages are of three kinds, namely:
1. the curly brackets {}, also called braces,
2. square brackets [], and
3. round brackets (), also called parentheses.
For simplicity, in the remainder of this brief, the word bracket will be used to refer to any of these
kinds.
In a syntactically well-formed (correct) program, every opening bracket must have a matching
closing bracket at the correct position. Here are some examples of well-formed and badly formed
code fragments:
int foo (int a[], int n) { for (int i = 0; i< (n-a[10]); i++) {// loop body} } // well formed
int foo (int a[), int n) { for (int i = 0; i< (n-a[10]); i++) {// loop body } } // badly formed at [)
int foo (int a[], int n) { for (int i = 0; i< (n-a[10]); i++) {// loop body} // badly formed, missing one final }
int foo (int a[], int n) { for (int i = 0; i< (n-a[10]); i++) {// loop body}}} // badly formed, one extra } at end
void voo (b(b(c))) {{a[0][i]--; {{{t++;}}}}} // well formed
int a]100][100[; // badly formed
2
Bracket matching can be achieved very easily with
the help of a stack. A stack is a data structure for
storing data items (integer numbers for example) so
that the last item stored (topmost item) is retrieved
before other items. We say that a stack obeys the Last
In First Out (LIFO) principle. Stacks are often
encountered in daily life. Imagine the pile (stack) of
plates in a restaurant. Staff put clean plates on top of
the pile (stack) of plates, while customers can only
remove plates from the top of the pile. Hence, the last
plate to be placed on top is the first one to be
removed. In programming, placing a data item on top of a stack is called a push operation, and
removing the top item is called a pop operation.
Implementing a stack
A stack can be implemented with either an array or a linked list. You can use either solution, as long
as the array or the linked list is stored in the heap, and there is no pre-defined limit to the number of
elements that it can contain. Linked lists have been studied in class, and we refer to the lectures on
pointers for further details on the addition and deletion operations.
The rest of this section covers the implementation of stacks with arrays. The array is used to store
the actual data of the stack, as in the following illustration. In addition to the array itself, an
additional integer variable is needed to determine the location of the top item at any time. This
variable is called the Stack Pointer (sp). Note that the, in case of arrays, the stack pointer is NOT a
pointer variable. It is simply an integer variable that contains the index of the top item.
When illustrating stacks, we usually draw the array vertically to resemble our intuitive conception
of stacks in real life. The above illustration shows a stack that can store up to 12 integer numbers
because it uses an array of maximum size = 12. The illustration shows the stack after 6 numbers
have been pushed into it (these are shown in green). As you can see, the value of the stack pointer
Existing stack elements
Empty locations available
for adding new items
(contain junk)
3
(sp) is 5. This is the index of the top item in this case. Do not confuse the top of the stack (the
number in position 5) with the top (limit) of the entire array (position 11). Note that array positions
‘above’ the top of the stack will have some previous ‘junk’ data (the numbers in blue), but these are
not part of stack data. The stack data in the above example extend from the item in position 0 up to,
and including, the topmost item in position 5.
Clearing the stack
To clear or initialize a stack, the stack pointer sp is set to a negative value
(usually -1). Setting sp to 0 cannot be used to indicate an empty stack,
because when sp=0, the topmost element in the stack is in position 0 and
the stack actually contains one item. The illustration to the right shows a
clean (empty) stack. Notice that there is no need to clear any previous junk
data in the array, as these will be gradually overwritten with actual stack
data as numbers are pushed into it.
The push function
To push a new item onto a stack, the following two steps are performed:
1. The stack pointer (sp) is incremented so that it ‘points’ to (indexes)
a new location on top of existing stack data.
2. The new item is stored in the array location now pointed at by sp.
The illustration shows how to push 35 into a stack. The previous value of
sp was 5, so this is first incremented to 6, and 35 is stored in position 6.
The pop function
To pop an item, the following three steps are performed:
1. The value pointed at by sp is copied to a temporary variable.
2. The stack pointer (sp) is decremented so that it now points at the
element which was below the top item, but has now become the
top one.
3. The value of the temporary variable is returned.
The illustration to the right shows how a stack is popped. The top value in
position 6, which is pointed to by sp is first copied into a variable (called
tmp in this example). The sp is then decremented by 1 so it is now
pointing to position 5 which is the new top of stack. Finally the value in
tmp is returned by the pop function.
What is a stack overflow?
Stack overflow occurs when we attempt to push a new item into a full
stack, as in the illustration to the right. This is clearly an impossible
operation. Hence, before attempting to push any new item into a stack we
must first check that the stack is not already full. Since there must be no
explicit limit to your stack, if the next push operation would cause a stack overflow, the memory
containing the stack must be reallocated on a larger memory area.
What is a stack underflow?
Stack underflow occurs when we attempt to pop an empty stack as shown in
the illustration to the right. To protect against this, we should always check
that the stack is not empty before attempting to pop anything out.
Checking matching brackets with a stack
For simplicity, in this project we will skip and ignore all characters in a source code except brackets
and comments: we will not check the code for any kind of syntactic correctness other than matched
brackets.
In general, when checking an input string for matching brackets, we can only encounter three cases
of mismatched brackets:
1. A closing bracket is encountered but there are no unmatched opening brackets to match this
closing bracket with, such as the last closing brace in this statement “int foo () }”. We will
refer to this case as ‘type 1 error’.
2. A closing bracket is encountered but the last opening bracket is of a different type, e.g. “int
foo ( ] {}”. We will refer to this as ‘type 2 error’.
3. An opening bracket is encountered but it is never closed, e.g. “int foo ({}“. We will refer to
this as ‘type 3 error’.
A stack can be used make sure that all brackets are matched. The following table shows some
examples of the method. For simplicity the stack is shown horizontally with the top of the stack to
the right.
Case Input string
(The character
being read is
shown in red)
Stack contents
(top of stack to
the right)
Comment
Well-formed string { [ g ] }
{ [ g ] }
{ [ g ] }
{ [ g ] }
{ [g ] }
{ [ g ] }
{
{[
{[
{
Stack is initially empty
‘{‘ pushed on stack
‘[‘ pushed on stack
‘g’ ignored
‘]’ in input matched to ‘[‘ on stack
‘}’ in input matched to ‘{‘ on stack
Stack is finally empty hence string is OK
Type 1 error [ g ] }
[ g ] }
[ g ] }
[ g ] }
[ g ] }
Stack is initially empty
‘[‘ pushed on stack
‘g’ ignored
‘]’ in input matched to ‘[‘ on stack
Error: stack is empty, ‘}’ in input cannot be
matched to anything
Type 2 error ( [ g ] }
( [ g ] }
( [ g ] }
( [ g ] }
( [ g ] }
( [ g ] }
Stack is initially empty
‘(‘ pushed on stack
‘[‘ pushed on stack
‘g’ ignored
‘]’ in input matched to [ on stack
Error: ‘}’ in input does not match ‘(‘ on
stack
Type 3 error { [ g ]
{ [ g ]
{ [ g ]
{ [ g ]
{ [ g ]
Stack is initially empty
‘{‘ pushed on stack
‘[‘ pushed on stack
‘g’ ignored
‘]’ in input matched to ‘[‘ on stack
Error: all the string has been read but the
stack still contains some brackets
The Task
Write a program that opens a plain text file containing C-like source code, reads it, and outputs a
file with the same content as the first, except that all comments are removed. Furthermore, the
program must check that all brackets match, and if they do not, the program should display an error
message, showing the type of error and the line number where this error was encountered. The input
and output files are passed to the program as command line parameters, as in:
./your_executable inputfile.txt outputfile.txt
General Guidelines
Write the program in standard C. If you write your code in any other language, it will NOT
be assessed and you will get a zero mark.
This is an individual project, and you are not supposed to work in groups or pairs with other
students.
Be aware that plagiarism in your code will earn you a zero mark and will have very serious
consequences. It is much better to submit your own partially finished work, than to fall into
the trap of plagiarism.
We use fairly sophisticated software which can identify whether two pieces of code are
nearly identical (modifications such as renaming variables and reshuffling the positions of
functions do not deceive it). If two (or more) students have large portions of their files
nearly identical they will be accused of plagiarism or collusion. If found guilty, all parties
involved will incur the penalty, regardless of who was the author of the code. For this
reason, never show, or give access to, your code to anyone. Do not help a colleague by
sharing your code, or you will both be found guilty of collusion.
It is your responsibility to make sure that nobody has access to your code. Lock the session
if you leave your computer unattended.
6
Submission
Submit a single text file with extension .c through Minerva.
Download and check the submitted file, to make sure that it is the correct version. We will
not accept late submissions if you realise you uploaded the wrong file, or the file appears to
be corrupted.
Binary files (rather than text), and generally files that cannot be compiled, will earn zero
marks.
Writing and testing your program
Part of the submission will be automatically evaluated by using the attached test harness. In order
for the tests to work, your code must contain some predefined functions. You can find those
functions along with their documentation, in the file template.c, which should therefore be your
starting point. Rename this file, and implement the functions in it one by one. To run the tests,
unpack the zip file containing the test harness in the same directory where your program is, and
compile it with the following command:
gcc -lm -std=c99 –o tests unity.c test.c your_program.c
where your_program.c is the name of your program file. Each executable can have a single
main(int argc, char **argv) function, therefore, when compiling the tests, rename your main
function into mymain(int argc, char **argv). If the test program compiles correctly, you can
then execute it by running:
./tests
Initially, when all the functions are empty, all the tests will fail. Once you have successfully
implemented the body of the functions, all the tests will be passed.
Once you are satisfied with the tested functions, you can develop the rest of the functionality and
the main function. The functions that are automatically tested, that is the ones you initially found in
the file template.c, must not contain any interactive component. This means that they must not use
printf or scanf and must run without user input. Otherwise, the tests will not run automatically.
Support
Please take advantage of lab sessions to get support from the instructors, especially on being able to
run the tests, since this is critical to passing the assignment.
Marking Scheme
The program passes the test_stack test (4 marks)
The program passes the test_remove_single_line_comment test (4 marks)
The program passes the test_remove_multi_line_comment test (4 marks)
The program reads and writes the input and output file correctly (3 marks)
The program uses the heap correctly, with no memory leak (4 marks)
The program correctly checks for matching brackets (5 marks)
The program display error messages correctly, including line numbers (5 marks)
The program is well structured, clear, and efficient (9 marks)
The program uses comments properly (2 marks)