4
\$\begingroup\$

Below source code is my solution of the K&R exercise 1-24.

Exercise 1-24. Write a program to check a C program for rudimentary syntax errors like unbalanced parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.)

My program uses two kinds of state variables. Parentheses(( ), { }, [ ]) and punctuation(' ', " ", /* */). Parentheses are saved in nest[] and punctuation are saved in state. And conditions of if-statement mainly uses these two variables.

I didn't care a case of a curly brace after opening parenthesis and bracket.

I'm not sure there is a better variable naming, logic, style, etc. I don't know if my code can be written shorter with the same logic. Any suggestion will be so appreciated.

#include <stdio.h>

/* This program checks if there is unbalanced parentheses, curly braces or brackets.
 * This program doesn't check if there is a newline charcter between a single quote or a double quote.
 * This program doesn't check if there is non-terminated comment, single quote or double quote.
 */

#define NOTHING         0
#define COMMENT         1
#define SINGLE_QUOTE    2
#define DOUBLE_QUOTE    3

#define PARENTHESIS     1
#define CURLY_BRACE     2
#define BRACKET         3

#define MAX_NESTING_LEVEL 100

void check_paren(void);

void main(void)
{
    check_paren();
}

void check_paren(void)
{
    int c;
    int line;
    int state;
    int nest[MAX_NESTING_LEVEL] = {NOTHING};
    int n;

    n = 0;
    line = 1;
    state = NOTHING;
    while ((c = getchar()) != EOF) {
        if ( n > MAX_NESTING_LEVEL -1) {
            printf("error : line %d : exceed MAX_NESTING_LEVEL\n", line);
            return;
        } else if (c == '\n') {
            ++line;
        } else if (state != COMMENT) {
            if (c == '/') 
                if ((c = getchar()) == '*')
                    state = COMMENT;
        }
        
        if (state == NOTHING && n == 0) {
            if (c == '\'')
                state = SINGLE_QUOTE;
            else if (c == '\"')
                state = DOUBLE_QUOTE;
            else if (c == '(')
                nest[n++] = PARENTHESIS;
            else if (c == '{')
                nest[n++] = CURLY_BRACE;
            else if (c == '[')
                nest[n++] = BRACKET;
            else if (c == ')') {
                printf("error : line %d : unmatched )\n", line);
                return;
            } else if (c == '}'){
                printf("error : line %d : unmatched }\n", line);
                return;
            } else if (c == ']'){
                printf("error : line %d : unmatched ]\n", line);
                return;
            }
        } else if (state == NOTHING && nest[n-1] == PARENTHESIS) {
            if (c == ')')
                nest[--n] = NOTHING;
            else if (c == '(')
                nest[n++] = PARENTHESIS;
            else if (c == '[')
                nest[n++] = BRACKET;
            else if (c == '\'')
                state = SINGLE_QUOTE;
            else if (c == '\"')
                state = DOUBLE_QUOTE;
            else if (c == '}') {
                printf("error : line %d : ( + }\n", line);
                return;
            }
            else if (c == ']') {
                printf("error : line %d : ( + ]\n", line);
                return;
            }
        } else if (state == NOTHING && nest[n-1] == CURLY_BRACE) {
            if (c == '}')
                nest[--n] = NOTHING;
            else if (c == '(')
                nest[n++] = PARENTHESIS;
            else if (c == '{')
                nest[n++] = CURLY_BRACE;
            else if (c == '[')
                nest[n++] = BRACKET;
            else if (c == '\'')
                state = SINGLE_QUOTE;
            else if (c == '\"')
                state = DOUBLE_QUOTE;
            else if (c == ')') {
                printf("error : line %d : { + )\n", line);
                return;
            }
            else if (c == ']') {
                printf("error : line %d : { + ]\n", line);
                return;
            }
        } else if (state == NOTHING && nest[n-1] == BRACKET) {
            if (c == ']')
                nest[--n] = NOTHING;
            else if (c == '(')
                nest[n++] = PARENTHESIS;
            else if (c == '\'')
                state = SINGLE_QUOTE;
            else if (c == ')') {
                printf("error : line %d : [ + )\n", line);
                return;
            }
            else if (c == '}') {
                printf("error : line %d : [ + }\n", line);
                return;
            }
        } else {
            if (state == COMMENT && c == '*') {
                if ((c = getchar()) == '/') 
                    state = NOTHING;
            } else if (c == '\\') 
                getchar();
            else if (state == SINGLE_QUOTE && c == '\'') 
                state = NOTHING;
            else if (state == DOUBLE_QUOTE && c == '\"') 
                state = NOTHING;
        }
    }
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Next time, please document your test cases in the question as well. The specification of the task is deliberately vague and leaves room for interpretation. Your test cases should then describe and explain why you made the necessary choices. \$\endgroup\$ – Roland Illig Mar 14 at 14:50
  • 1
    \$\begingroup\$ Your description doesn't state whether nesting of various types of brackets is allowed ( "([{}])" vs. "([{)]}" ) or not. In typical real scenarios, it's not, but your program seems to check for the latter case only. \$\endgroup\$ – tofro Mar 14 at 15:54
3
\$\begingroup\$

You could assign a number to state instead of just keeping it at a char. You can still use the EOF / zero character value as "magic". It would make debugging a lot easier, and you can simply assign the read character to nest directly. That would remove a lot of code.

I'd also create a method to get rid of any strings and comments whenever they are encountered. Any parentheses and whatnot in strings should be skipped anyway. Just keep reading in characters until the end is encountered (and if it not encountered: well, there is your problem).

char and int can also be used in switch statements instead of if statements. When you think "state-machine" a loop with a switch is probably what comes first in mind (when not performing functional programming anyway).

E.g.

switch(c):
case '(':
case '[':
...
    nest[n++] = c;
    break;
...

In the end the main loop should be as short and intuitive as possible.

\$\endgroup\$
5
  • \$\begingroup\$ Do you mean the variable c is useless and then while ((c = getchar()) != EOF) can be rewritten by while ((state = getchar()) != EOF)? \$\endgroup\$ – op ol Mar 6 at 13:29
  • \$\begingroup\$ The fact that you can have escape sequences and two different two-character comments may require some workarounds. But that's the case with your current int as well I suppose. \$\endgroup\$ – Maarten Bodewes Mar 6 at 13:32
  • \$\begingroup\$ No, scratch that, lines such as else if (state == SINGLE_QUOTE && c == '\'') would not work; state depends on the past after all. But in many cases you could just perform state = c... \$\endgroup\$ – Maarten Bodewes Mar 6 at 13:37
  • \$\begingroup\$ I don't know I am 100% understand your comment. I think you're saying else if (c == '\"') state = DOUBLE_QUOTE; can be else if (c == '\"') state = c and else if (c == '(') nest[n++] = PARENTHESIS; can be else if (c == '(') nest[n++] = c; If my thought is right. You actually means that my macro definition can be replaced by the character variable(c). It would be a matter of style. The code length will not be changed. \$\endgroup\$ – op ol Mar 6 at 13:47
  • 1
    \$\begingroup\$ Added example... less conversion always means less code. For one, you could get rid of most #define statements. \$\endgroup\$ – Maarten Bodewes Mar 6 at 13:55
1
\$\begingroup\$

I have not read your whole programm and only a very small suggestion regarding readability:

n > MAX_NESTING_LEVEL -1

is the border check for your nest array. If you write it as

n >= MAX_NESTING_LEVEL

it has the same result but is more concise. You do not need to keep in mind that the defined size is shifted by one regarding index values.

You should maybe consider to use two different defines, one for the nesting table size and one for the max nesting level for readability.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.