CMSC--202 , Section Computer Science II for Majors
Fall 1997 27 October 1997 Homework 6
The purpose of this assignment is to give you some experience with stacks and to expose you to an important stack application. In this assignment, you will write a C program to test the ``balance'' of certain features of C programs. This is a task that is done by C compilers. The technique you will use is similar to the technique used by a typical C compiler.
There are many features in C programs that must be ``balanced'' to be
syntactically correct. For example, every ( must be balanced by
a corresponding ). Similarly for {} and [].
There are other (somewhat more complex) situations requiring balance.
/* must be balanced by
a */ The complication here is that the tokens being balanced
are not composed of single characters. Moreover, the ``closing
comment'' */ starts with a character that is used in other
ways (pointers, multiplication).
"This is a /* ' * quote" is legal, and the comment and
single-quote need not be balanced.
There are some balanced C programs you need not test. For example, some
balanced C programs contain character constants such as '\'' or
'\"'. These are inherently unbalanced and would require a bit
more work to catch. You need not worry about such problems for this
homework (unless you like the modest challenge).
The basic algorithm is contained in the ``Stacks and Queues'' handout.
As noted in the handout, simply counting the number of characters will
not work. For example,
the expression }abc{ has the correct number of balancing braces
(one opening brace and one closing brace), but it is not valid C code.
A stack provides the mechanism needed for the algorithm. Basically,
whenever a closing symbol (such as }) is seen, it must match the
nearest opening symbol of the same type (such as {).
The algorithm given in the handout provides a skeleton for your
homework. It is not useable as is; you must modify it in a number of
ways. One important point: do not write a large main file. Your
main file should simply get a file name, call a function to print the
file with line numbers, and then call a balance-checking function.
Your program prompts the user for the name of the C source file to test. If unable to open the file, the program issues an appropriate ``file not found'' error message, and exits. Before beginning the check, your program prints the file with line numbers. Every time your program pops the stack (to check for balance), it issues a message such as
pair matching [ and ]
As soon as a balance-error condition is found, the program issues a message such as
unmatched { symbol at line 16
and exits.
rewind on it.
/ character, it may be the opening of a
comment (as in /*), or it may be the division operator. You
will have to read the character after it to decide. If it's not the
opening comment, you may want to put back the following character.
You can use ungetc to do this.
* character, it may be the closing of a
comment (as in */), or it may be the multiplication operator or
a pointer operation. Once again, you may want to use ungetc.
/* and the closing-comment ``symbol''
*/ are composed of two characters. One choice for a single
character to push for a comment symbol might be an otherwise unused
symbol character (for example, the character c).
Submit your work in the usual way, using the submit command. For example, to submit the file foo.c, do:
submit cs202_01 hw6 foo.c
submit cs202_02 hw6 foo.c
Submit all the files required to successfully compile your homework using your submitted makefile. The only constraints on file names are that the executable must be named hw6 and the makefile must be named Makefile or makefile. Otherwise, you may name your files as you wish.
Here are some samples of the output generated by the hw6 program. Notice that the C-source code does not have to be legal C, it just has to meet balance conditions. The program begins by printing the file to be tested with line numbers. It then checks the balance and reports on the outcome.
>> hw6
Please enter filename for C code: good_balance.c
1 /*
2 good_balance.c
3 Test data for HW-6, CMSC-202, Fall 1997
4 Thomas Anastasio
5 Created: 24 October 1997
6 Current: 24 October 1997
7 */
8
9 #define FOO '"* /* */ foo'
10 #define BAR " /* ' "
11
12 int main(int argc, char * argv[])
13 {
14 char c = {'a';}
15 y = 3;
16 z = 4;
17 x = y * z;
18 y = x / z;
19 printf("Hello world\n");
20 }
21
pair matching /* and */
pair matching ' and '
pair matching " and "
pair matching [ and ]
pair matching ( and )
pair matching ' and '
pair matching { and }
pair matching " and "
pair matching ( and )
pair matching { and }
Balance is ok
>> hw6
Please enter filename for C code: bad_balance.c
1 /*
2 bad_balance.c
3 Test data for HW-6, CMSC-202, Fall 1997
4 This program has bad balance conditions.
5 Thomas Anastasio
6 Created: 24 October 1997
7 Current: 24 October 1997
8 */
9
10 #define FOO '"* /* */ foo'
11 #define BAR " /* ' "
12
13 int main(int argc, char * argv[])
14 {
15 char c = {'a';}
16 y = 3;
17 z = 4;
18 x = y * z;
19 y = x / z;
20 {
21 printf("Hello world\n");
22 }
23
pair matching /* and */
pair matching ' and '
pair matching " and "
pair matching [ and ]
pair matching ( and )
pair matching ' and '
pair matching { and }
pair matching " and "
pair matching ( and )
pair matching { and }
unbalanced { symbol on line 14
>> hw6
Please enter filename for C code: bad_balance2.c
1 /*
2 bad_balance2.c
3 Test data for HW-6, CMSC-202, Fall 1997
4 This program has bad balance conditions.
5 Thomas Anastasio
6 Created: 24 October 1997
7 Current: 24 October 1997
8 */
9
10 #define FOO '"* /* */ foo'
11 #define BAR " /* ' "
12
13 int main(int argc, char * argv[])
14 {
15 char c = {'a';}
16 y = 3; '
17 z = 4;
18 x = y * z;
19 y = x / z;
20 {
21 printf("Hello world\n");
22 }
23 }
24
pair matching /* and */
pair matching ' and '
pair matching " and "
pair matching [ and ]
pair matching ( and )
pair matching ' and '
pair matching { and }
unbalanced quote ' on line 16