代写COMP1711作业、代做C/C++,C#编程语言作业、代写C-like留学生作业、代做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:http://www.daixie0.com/contents/13/2211.html

./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)

 

因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱： 

微信：codinghelp