The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 1.24 on page 34
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.)
Solution by Rick Dearman (Category 0)
/****************************************************** KnR 1-24 -------- Write a program to check the syntax of a C program for matching {} () "" '' [] Author: Rick Dearman email: rick@ricken.demon.co.uk ******************************************************/ #include <stdio.h> #define MAXLINE 1000 /* max input line size */ char line[MAXLINE]; /*current input line*/ int getline(void); /* taken from the KnR book. */ int main() { int len=0; int t=0; int brace=0, bracket=0, parenthesis=0; int s_quote=1, d_quote=1; while ((len = getline()) > 0 ) { t=0; while(t < len) { if( line[t] == '[') { brace++; } if( line[t] == ']') { brace--; } if( line[t] == '(') { parenthesis++; } if( line[t] == ')') { parenthesis--; } if( line[t] == '\'') { s_quote *= -1; } if( line[t] == '"') { d_quote *= -1; } t++; } } if(d_quote !=1) printf ("Mismatching double quote mark\n"); if(s_quote !=1) printf ("Mismatching single quote mark\n"); if(parenthesis != 0) printf ("Mismatching parenthesis\n"); if(brace != 0) printf ("Mismatching brace mark\n"); if(bracket != 0) printf ("Mismatching bracket mark\n"); if( bracket==0 && brace==0 && parenthesis==0 && s_quote == 1 && d_quote == 1) printf ("Syntax appears to be correct.\n"); return 0; } /* getline: specialized version */ int getline(void) { int c, i; extern char line[]; for ( i=0;i<MAXLINE-1 && ( c=getchar()) != EOF && c != '\n'; ++i) line[i] = c; if(c == '\n') { line[i] = c; ++i; } line[i] = '\0'; return i; }
Solution by Tim Conrad (Category 0)
/* checksyntax.c: Basic C syntax checker */ #include <stdio.h> #define MAXLINE 1000 #define TRUE 1 #define FALSE 0 int getTheLine(char line[], int maxline); void syntaxCheck(); int inComment, openCommentLine, openBraceLine, openBrace, error; int main() { inComment=openCommentLine=openBraceLine=openBrace=error=0; printf("\nChecking for basic syntax errors.\n\n"); syntaxCheck(); if (inComment) { printf("%3d | Error: Unclosed comment found\n", openCommentLine); error=TRUE; } if (openBrace) { printf("%3d | Error: Unclosed brace found\n", openBraceLine); error=TRUE; } if (!error) printf("No basic syntax errors found. Well done!\n"); putchar('\n'); return 0; } int getTheLine(char s[], int lim) { /* slightly modified from K & R */ int c, i; for (i=0; i<lim-1 && (c=getchar())!=EOF && c!='\n'; ++i) s[i] = c; if (c == '\n') { s[i] = c; ++i; } s[i] = '\0'; return i; } void syntaxCheck() { int currChar, prevChar, nextChar, quote, doubleQuote, openParen, closedParen; int openBracket, closedBracket; openBrace=openBracket=closedBracket=FALSE; int currLine; char inputline[MAXLINE]; char from[MAXLINE]; int escaped; int constant; extern int inComment, openCommentLine, openBraceLine, openBrace, error; openCommentLine=openBraceLine=openParen=closedParen=FALSE; currLine=1; while (getTheLine(inputline, MAXLINE) > 0) { doubleQuote=quote=FALSE; for (currChar=0;inputline[currChar]!='\0';++currChar) { prevChar=(currChar-1); nextChar=(currChar+1); escaped=FALSE; constant=FALSE; if (inputline[currChar]!='\\' && inputline[prevChar]=='\\') escaped=TRUE; if (!escaped) { if (inputline[currChar]=='/' && inputline[nextChar]=='*' && !inComment) { inComment=TRUE; openCommentLine=currLine; } if (inputline[currChar]=='/' && inputline[prevChar]=='*' && inComment) inComment=FALSE; } if (inputline[prevChar]=='\'' && inputline[nextChar]=='\'') constant=TRUE; if (!inComment && !escaped && !constant) { if (inputline[currChar]=='{' && openBrace && !doubleQuote) ++openBrace; if (inputline[currChar]=='{' && !openBrace && !doubleQuote) { ++openBrace; openBraceLine=currLine; } if (inputline[currChar]=='}' && !openBrace && !doubleQuote) { printf("%3d | Error: Orhpaned closing brace\n", currLine); error=TRUE; } if (inputline[currChar]=='}' && openBrace) --openBrace; if (inputline[currChar]=='\"' && doubleQuote) { ++doubleQuote; doubleQuote=0; ++currChar; } if (inputline[currChar]=='\"' && !doubleQuote) ++doubleQuote; if (inputline[currChar]=='\n' && doubleQuote) { printf("%3d | Error: Unbalanced double quotes\n", currLine); doubleQuote=0; error=TRUE; } if (inputline[currChar]=='\'' && quote && !doubleQuote) { ++quote; quote=0; ++currChar; } if (inputline[currChar]=='\'' && !quote && !doubleQuote) ++quote; if (inputline[currChar]=='\n' && quote) { printf("%3d | Error: Unbalanced single quotes\n", currLine); quote=0; error=TRUE; } if (inputline[currChar]=='(' && !doubleQuote) { ++openParen; } if (inputline[currChar]==')' && !doubleQuote) ++closedParen; if (inputline[currChar]=='\n' && (openParen!=closedParen)) { printf("%3d | Error: Unbalenced parentheses\n", currLine); openParen=closedParen=0; error=TRUE; } if (inputline[currChar]=='[') ++openBracket; if (inputline[currChar]==']') ++closedBracket; if (inputline[currChar]=='\n' && (openBracket!=closedBracket)) { printf("%3d | Error: Unbalanced brackets\n", currLine); openBracket=closedBracket=0; error=TRUE; } } } ++currLine; } }
Solution by Xggggg (Category 0)
#include <stdio.h> #define MAXLINE 5000 #define TRUE 1 #define FALSE 0 #define abs(A) ((A) > 0 ? (A) : -(A)) int getline(char s[], int lim); void syntaxCheck(char *); int main(void) { char line[MAXLINE]; while (getline(line, MAXLINE) > 0) syntaxCheck(line); return 0; } int getline(char s[], int lim) { int c, i = 0; while (i < lim - 1 && (c = getchar()) != EOF) s[i++] = c; s[i] = '\0'; return i; } void syntaxCheck(char *s) { char open[] = "([{"; char close[] = ")]}"; int inCnt[3] = {}; char err, inC = FALSE, inQ = FALSE, inDQ = FALSE, inC99 = FALSE; for (int i = 0; s[i]; i++) { if (!inC && !inC99 && !inDQ && i > 0 && s[i] == '/' && s[i - 1] == '/') inC99 = TRUE; if (!inC && !inC99 && !inDQ && i > 0 && s[i] == '*' && s[i - 1] == '/') inC = TRUE; if (inC99 && s[i] == '\n') inC99 = FALSE; if (inC && s[i] == '*' && s[i + 1] == '/') inC = FALSE; if (!inC && !inC99 && !inDQ && s[i] == '\'' && (!i || s[i - 1] != '\\')) inQ = !inQ; if (!inC && !inC99 && !inQ && s[i] == '\"' && (!i || s[i - 1] != '\\')) inDQ = !inDQ; if (!inQ && !inC & !inDQ && !inC99) for (int j = 0; open[j]; j++) if (s[i] == open[j]) { inCnt[j]++; break; } else if (s[i] == close[j]) { inCnt[j]--; break; } } err = inC || inQ || inDQ; for (int i = 0; !err && open[i]; i++) err = inCnt[i]; if (err) { printf("There are mismatched:\n"); if (inC) printf("-> Comments\n"); if (inQ) printf("-> Single Quotes\n"); if (inDQ) printf("-> Double Quotes\n"); for (int i = 0; open[i]; i++) if (inCnt[i]) printf("-> %d \"%c %c\"\n", abs(inCnt[i]), open[i], close[i]); } else printf("Syntax appears to be correct.\n"); }
Solution by Scopych (Category 0)
#include <stdio.h> #define TRUE 1; #define FALSE 0; /* Author: scopych * Date: 23.12.2018 * Purpose:check C program for rudimentary * syntax errors like unbalanced parentheses, * brackets and braces, quotes,both single * and double,escape sequences,and comments. */ int goahead; int c; int parentheses; int braces; int brackets; void goToEnd(int end); int isComent(void); void goToEndComent(void); void mark(int ch); void check(int ch); int main(void) { extern int c; extern int goahead; goahead = TRUE; while (goahead) { if (c != '/') { c = getchar(); } if (c == '"' || c == '\'') { goToEnd(c); } else if (isComent()) { goToEndComent(); } else if (c == '(' || c == '{' || c == '[') { mark(c); } else if (c == ')' || c == '}' || c == ']' || c == EOF) { check(c); } } printf("Done!\n"); return 0; } void goToEnd(int end) { extern int c; extern int goahead; while ((c = getchar()) != end) { if (c == EOF) { printf("There is no closing %c charact er\n", end); goahead = FALSE; break; } } } int isComent() { extern int c; if (c == '/') { if ((c = getchar()) == '*') { return 1; } else { return 0; } } return 0; } void goToEndComent(void) { extern int c; extern goahead; int notend = TRUE; while (notend) { c = getchar(); if (c == '*') { if ((c = getchar()) == '/') { notend = FALSE; } } if (c == EOF) { printf("There are no closing '*/' char acters\n"); goahead = FALSE; break; } } } void mark(int ch) { extern int parentheses; extern int braces; extern int brackets; if (ch == '(') { parentheses++; } else if (ch == '{') { braces++; } else if (ch == '[') { brackets++; } } void check(int ch) { extern goahead; extern int parentheses; extern int braces; extern int brackets; if (ch == ')' && parentheses > 0) { parentheses--; } else if (ch == EOF && parentheses > 0) { printf("UNBALANCED PARENTHESES\n"); goahead = FALSE; } else if (ch == '}' && braces > 0) { braces--; } else if (ch == EOF && braces > 0) { printf("UNBALANCED BRACES\n"); goahead = FALSE; } else if (ch == ']' && brackets > 0) { brackets--; } else if (ch == EOF && brackets > 0) { printf("UNBALANCED BRACKETS\n"); goahead = FALSE; } else if (ch == EOF) { goahead = FALSE; } }
Solution by Stefan Farfeleder (Category 1)
/* 1-24.c */ #include <stdio.h> #include <stdlib.h> #define MAX_STACK 1024 enum { CODE, /* nothing of the following */ COMMENT, /* inside a comment */ QUOTE1, /* inside '' */ QUOTE2 /* inside "" */ }; int main(void) { int ch; int state = CODE; char stack[MAX_STACK]; size_t top = 0; /* points to the top of the stack :-) */ size_t line = 1; int error = 0; /* for ok-message */ while ((ch = getchar()) != EOF) { if (ch == '\n') { line++; } switch (state) { case CODE: if (ch == '\'') { state = QUOTE1; } else if (ch == '"') { state = QUOTE2; } else if (ch == '/') { int second = getchar(); if (second == '*') { state = COMMENT; } else { ungetc(second, stdin); } } else if (ch == '(' || ch == '[' || ch == '{') { if (top < MAX_STACK) { stack[top++] = ch; } else { printf("Stack too small!\n"); return EXIT_FAILURE; /* exit gracefully :-) */ } } else if (ch == ')' || ch == ']' || ch == '}') { if (top == 0) /* found closing brace but stack is empty */ { printf("Line %lu: Closing '%c' found without " "counterpart.\n", (unsigned long)line, ch); error = 1; } else { char open = stack[--top]; if ((ch == ')' && open != '(') || (ch == ']' && open != '[') || (ch == '}' && open != '{')) { printf("Line %lu: Closing '%c' does not match " "opening '%c'.\n", (unsigned long)line, ch, open); error = 1; } } } break; case COMMENT: if (ch == '*') { int second = getchar(); if (second == '/') { state = CODE; } else { ungetc(second, stdin); } } break; case QUOTE1: if (ch == '\\') { (void)getchar(); /* an escaped char inside '' throw it away */ } else if (ch == '\'') { state = CODE; } break; case QUOTE2: if (ch == '\\') { (void)getchar(); /* an escaped char inside "" throw it away */ } else if (ch == '"') { state = CODE; } break; } } if (state == COMMENT) { printf("Code ends inside comment!\n"); } else if (state == QUOTE1) { printf("Code ends inside single quotes!\n"); } else if (state == QUOTE2) { printf("Code ends inside double quotes!\n"); } else if (top == 0 && error == 0) { printf("Code seems to be ok.\n"); } if (top > 0) /* still something in the stack */ { size_t i; for (i = 0; i < top; i++) { printf("Opening '%c' found without counterpart.\n", stack[i]); } } return 0; }
Solution by Stig Brautaset (Category 1)
/* This is my first rudimentary C syntax checker. It checks for syntax errors, * like closing a set of brackets using the wrong type. It is not *very* good * at it, but it does not bother about comments, and it does know something * about escape sequences and character strings/constants. * * It uses a simple static stack to keep track of the braces, and it also uses * a stack to keep track of the errors on each line. Someday I might change * that to use a queue for the error-tracking, because as it is now, it outputs * the rightmost error on the line first, and then it steps leftwards (if there * is more than one error on each line). * * I might also implement my dynamically allocated stack and queue implementa- * tions, so that running out of space in the stack is not an issue. I might * also skip it, since it has little to do with the exercise in question. * * The program is especially bad at error-recovery. If it finds an error, (or * something it believes to be an error) subsequent errors reported might be a * bit dubious. */ #include <stdio.h> #define MAXVAL 1000 #define MAXLINE 1000 typedef struct { int top; int val[MAXVAL]; int pos[MAXVAL]; } stackstr; /* very simple stack push function */ int push(stackstr *stk, int foo, int bar) { if (stk->top == MAXVAL) { printf("stack overflow. NOT putting more values on the stack.\n"); return 1; } stk->val[stk->top] = foo; stk->pos[stk->top] = bar; stk->top++; return 0; } /* very simple function to pop values off a stack */ int pop(stackstr *stk, int *foo, int *bar) { if (stk->top == 0) { return 1; } stk->top--; *foo = stk->val[stk->top]; *bar = stk->pos[stk->top]; return 0; } /* we go through the input one line at a time, and this function * gets the line to test */ int getline(char *s, int lim) { int i, c; for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++) *(s + i) = c; if (c == '\n') *(s + i++) = c; *(s + i) = '\0'; return i; } void scanline(stackstr *stk, stackstr *errstk, char *s, int len) { int i, c, d, foo; static int string = 0, comment = 0, isconst = 0, escape = 0; for (i = 0; i < len; i++) { c = *(s + i); if (!comment) { if (c == '\\') { /* we have an escape */ /* test for a valid escape sequence */ if ((d = *(s + ++i)) == '\\' || d == 'n' || d == '0' || d == 'r' || d == '?' || d == 't' || d == '\'' || d == '\"' || d == 'b' || d == 'x') { continue; /* ok, valid escape sequence -- don't bother about it */ } else { push(errstk, 5, i); /* illigal escape sequence */ } } else if (c == '\"') { /* is it a text string then? */ if (!string) string = 1; else string = 0; } else if (c == '\'') { /* is it a constant? */ if (!isconst) isconst = 1; else isconst = 0; } } if (!isconst && !string && !comment && c == '/') { if ((d = *(s + ++i)) == '*') comment = 1; } else if (comment && c == '*') { if ((d = *(s + ++i)) == '/') { comment = 0; continue; /* done with the comment stuff -- start over */ } } /* only bother about ({[ ]})'s that's not in * a string, constant or comment */ if (!isconst && !string && !comment) { if (c == '(' || c == '{' || c == '[') { push(stk, c, 0); } else if (c == ']' || c == '}' || c == ')') { if (pop(stk, &d, &foo)) { push(errstk, 4, i); } if (c == ')' && d != '(') { push(stk, d, 0); push(errstk, 1, i); } else if (c == ']' && d != '[') { push(stk, d, 0); push(errstk, 2, i); } else if (c == '}' && d != '{') { push(stk, d, 0); push(errstk, 3, i); } } } } } /* print errors on the line (if there were any) */ void print_err(stackstr *errstk, int lineno) { int errno, pos; /* yes I know... this way the errors come "backwards" :) */ while (!pop(errstk, &errno, &pos)) { printf("on line number %d: ", lineno); switch(errno) { case 1: printf("closing unopened parantheses, column %d\n", pos+1); break; case 2: printf("closing unopened square bracket, column %d\n", pos+1); break; case 3: printf("closing unopened curly braces, column %d\n", pos+1); break; case 4: printf("trying to close unopened block/control structure, column %d\n", pos+1); break; case 5: printf("illigal escape sequence, column %d\n", pos+1); break; default: printf("undeterminable error\n"); break; } } } int main(void) { stackstr errstk = {0}, stk = {0}; int c, linenbr = 0, errcount = 0, linelen; char line[MAXLINE]; while ((linelen = getline(line, MAXLINE)) > 0) { linenbr++; scanline(&stk, &errstk, line, linelen); if (errstk.top) { print_err(&errstk, linenbr); errcount++; } } if (errcount) printf("%d lines contained error(s)\n", errcount); else printf("Well, *I* didn't find any syntax errors, but don't take my word for it...:)\n"); return 0; }
Solution by ivan (Category 2)
#include <stdio.h> #define MAX_INPUT_LENGTH 10000 #define NORMAL 0 #define SINGLE_QUOTE 1 #define DOUBLE_QUOTE 2 #define SLASH 3 #define MULTI_COMMENT 4 #define INLINE_COMMENT 5 #define STAR 6 int state_from_normal(char symbol, char prev_symbol) { int state = NORMAL; if (symbol == '\'' && prev_symbol != '\\') state = SINGLE_QUOTE; else if (symbol == '"') state = DOUBLE_QUOTE; else if (symbol == '/') state = SLASH; return state; } int state_from_single_quote(char symbol, char prev_symbol, char pre_prev_symbol) { int state = SINGLE_QUOTE; if (symbol == '\'' && (prev_symbol != '\\' || pre_prev_symbol == '\\')) state = NORMAL; return state; } int state_from_double_quote(char symbol, char prev_symbol, char pre_prev_symbol) { int state = DOUBLE_QUOTE; if (symbol == '"' && (prev_symbol != '\\' || pre_prev_symbol == '\\')) state = NORMAL; return state; } int state_from_slash(char symbol) { int state = SLASH; if (symbol == '*') state = MULTI_COMMENT; else if (symbol == '/') state = INLINE_COMMENT; else state = NORMAL; return state; } int state_from_multi_comment(char symbol) { int state = MULTI_COMMENT; if (symbol == '*') state = STAR; return state; } int state_from_star(char symbol) { int state = STAR; if (symbol == '/') state = NORMAL; else if (symbol != '*') state = MULTI_COMMENT; return state; } int state_from_inline_comment(char symbol) { int state = INLINE_COMMENT; if (symbol == '\n') state = NORMAL; return state; } int state_from(int prev_state, char symbol, char prev_symbol, char pre_prev_symbol) { if (prev_state == NORMAL) return state_from_normal(symbol, prev_symbol); else if (prev_state == SINGLE_QUOTE) return state_from_single_quote(symbol, prev_symbol, pre_prev_symbol); else if (prev_state == DOUBLE_QUOTE) return state_from_double_quote(symbol, prev_symbol, pre_prev_symbol); else if (prev_state == SLASH) return state_from_slash(symbol); else if (prev_state == MULTI_COMMENT) return state_from_multi_comment(symbol); else if (prev_state == INLINE_COMMENT) return state_from_inline_comment(symbol); else if (prev_state == STAR) return state_from_star(symbol); else return -1; } char opening_symbol(char symbol) { if (symbol == ')') return '('; else if (symbol == ']') return '['; else if (symbol == '}') return '{'; else return '\0'; } int is_valid_closing(char symbol, char nests[], int nest_index) { return nest_index > 0 && nests[nest_index-1] == opening_symbol(symbol); } int main(void) { char nests[MAX_INPUT_LENGTH] = { '\0' }; int nest_index = 0; char input; char symbol = '\0'; char prev_symbol = '\0'; char pre_prev_symbol; int state = NORMAL; int prev_state; int line = 1, column = 0; while ((input = getchar()) != EOF) { column++; pre_prev_symbol = prev_symbol; prev_symbol = symbol; symbol = input; prev_state = state; state = state_from(prev_state, symbol, prev_symbol, pre_prev_symbol); if (symbol == '\n') { line++; column = 0; } else if (state == NORMAL) { if (symbol == '(' || symbol == '[' || symbol == '{') { nests[nest_index++] = symbol; } if (symbol == ')' || symbol == ']' || symbol == '}') { if (is_valid_closing(symbol, nests, nest_index)) { nests[--nest_index] = '\0'; } else { printf("Unexpected '%c' at line %d, column %d\n", symbol, line, column); return 1; } } } } if (nest_index > 0) { printf("Unbalanced '%c'", nests[0]); for (int i = 1; i < nest_index; i++) { printf(", '%c'", nests[i]); } printf("\n"); return 1; } else { printf("Balanced\n"); } }
Solution by CakeOFTrust
This one borrows part of its core from Uncomment (1.23). It is able to mark typos such as } { as mistakes. It also can check for nested braces, brackets and parentheses such as { [ } ] marking these 2 brackets as a typo. It IS big and not easy to grasp at the first second but it does what it has to. Also it uses recursion because it helps to eliminate needs for more parameters and external variables. This concept has nothing to do with K&R as it is used in many other areas than programming.
#include <stdio.h> #define NOESC 3 #define YES 1 #define NO 0 #define ESC 2 #define MAX 2048 #define START 0 char cr; int unbc, unbk, unpa, bk, pa, bc; void sortar(char ar[], int end, int start); int main(void) { int c[2], bs = 0, eoc = 0, i = -1; extern int unbc, unbk, unpa, bk, pa, bc; char string, chr, comm[2], bap[MAX], owfl; extern char cr; unbc = unbk = unpa = bk = pa = bc = 0; c[1] = getchar(); c[0] = '\0'; string = chr = comm[0] = comm[1] = owfl = NO; cr = '\n'; while (c[1] != EOF && owfl == NO) { if (string == YES || chr == YES || (comm[0] == NO && comm[1] == NO && (c[1] == '\"' || c[1] == '\''))) { if (c[1] == '\\') ++bs; else if (bs > 0 && c[1] != '\"' && c[1] != '\'') bs = 0; if (c[1] == '\"' && string == NO && chr == NO) string = YES; else if (c[1] == '\'' && chr == NO && string == NO) chr = YES; else if ((c[1] == '\'' || c[1] == '\"') && bs - (bs / 2) * 2 == 0) { if (c[1] == '\"' && string == YES) string = NO; else if (c[1] == '\'' && chr == YES) chr = NO; } if ((c[1] == '\'' || c[1] == '\"') && bs > 0) { bs = 0; } } else if (comm[0] == YES || comm[1] == YES) { if (c[0] == '*' && c[1] == '/' && comm[0] == YES) comm[0] = NO; else if (c[1] == '\n' && comm[1] == YES) comm[1] = NO; } else { if (c[1] == '{' || c[1] == '}' || c[1] == '(' || c[1] == ')' || c[1] == '[' || c[1] == ']') { if (i < MAX - 1) { ++i; bap[i] = c[1]; if (c[1] == '}') ++bc; else if (c[1] == ']') ++bk; else if (c[1] == ')') ++pa; } else owfl = YES; } else if (c[1] == '/') { if (c[0] == '*') ++eoc; else { c[0] = c[1]; c[1] = getchar(); if (c[1] != '*' && c[1] != '/') comm[0] = NOESC; else if (c[1] == '*') comm[0] = ESC; else comm[1] = ESC; } } } if (comm[0] != ESC && comm[1] != ESC && comm[0] != NOESC && c[1] != EOF) { c[0] = c[1]; c[1] = getchar(); } else if (comm[0] == ESC) comm[0] = YES; else if (comm[1] == ESC) comm[1] = YES; else if (comm[0] == NOESC) comm[0] = NO; } if (i != -1 && owfl == NO) sortar(bap, i, START); if (unpa != 0) printf("\nYou have %d of unmatched parentheses pairs.\n", unpa); if (unbk != 0) printf("\nYou have %d of unmatched brackets pairs.\n", unbk); if (unbc != 0) printf("\nYou have %d of unmatched braces pairs.\n", unbc); if (eoc != 0) printf("\nYou have %d of unmatched comment tails.\n", eoc); if (comm[0] == YES) printf("\nNo comment tail.\n"); if (string == YES) printf("\nNo string end.\n"); if (chr == YES) printf("\nNo end of character constant.\n"); if (owfl == YES) printf("\nNot enough memory, please increase the value of MAX.\n"); else if (chr == NO && string == NO && comm[0] == NO && eoc == 0 && unbc == 0 && unbk == 0 && unpa == 0) printf("\nNo problems spotted. Good job.\n"); return 0; } void sortar(char ar[], int end, int start) { int i = 0, k = 0, tls[3]; extern int unbc, unbk, unpa, pa, bc, bk; extern char cr; for (; k < 3; ++k) tls[k] = end + 1; if (start == MAX) ; else if (cr != '\0') { for (k = start; bc > 0 && ar[k] != '}'; ++k) ; if (bc > 0) tls[0] = k; for (k = start; bk > 0 && ar[k] != ']'; ++k) ; if (bk > 0) tls[1] = k; for (k = start; pa > 0 && ar[k] != ')'; ++k) ; if (pa > 0) tls[2] = k; if (tls[0] + tls[1] > tls[1] + tls[2]) { if (tls[1] > tls[2]) i = tls[2]; else i = tls[1]; } else if (tls[0] > tls[1]) i = tls[1]; else i = tls[0]; if (i == end + 1) cr = '\0'; else { cr = ar[i]; if (cr == '}') --bc; else if (cr == ']') --bk; else --pa; } if (cr != '\0') { if (cr == ')') { for (k = i - 1; k >= start && ar[k] != '('; --k) { if (ar[k] == '{') ++unbc; else if (ar[k] == '[') ++unbk; ar[k] = '\0'; } if (k >= start) { ar[k] = '\0'; if (k > start) ar[i] = '\0'; else ar[i] = '\n'; } else { ar[i] = '\n'; ++unpa; } } if (cr == ']') { for (k = i - 1; k >= start && ar[k] != '['; --k) { if (ar[k] == '{') ++unbc; else if (ar[k] == '(') ++unpa; ar[k] = '\0'; } if (k >= start) { ar[k] = '\0'; if (k > start) ar[i] = '\0'; else ar[i] = '\n'; } else { ar[i] = '\n'; ++unbk; } } if (cr == '}') { for (k = i - 1; k >= start && ar[k] != '{'; --k) { if (ar[k] == '(') ++unpa; else if (ar[k] == '[') ++unbk; ar[k] = '\0'; } if (k >= start) { ar[k] = '\0'; if (k > start) ar[i] = '\0'; else ar[i] = '\n'; } else { ar[i] = '\n'; ++unbc; } } if (ar[i] == '\n') start = i + 1; } sortar(ar, end, start); } else for (; start <= end; ++start) if (ar[start] == '{') ++unbc; else if (ar[start] == '[') ++unbk; else if (ar[start] == '(') ++unpa; }
Solution by i9383
If have suggest or wrong please tell me
#include <stdio.h> main() { int c, state, line, column, i, j, state0; char s[1000]; /*Array string s store parentheses brackets braces*/ int sp[1000], sp0[1000]; /*Array sp s position store string s line number sp0 for column count*/ state = 0; /*Store quotes and comments state*/ state0 = 0; /*Store state for parentheses brackets braces*/ line = 1; /*Count current line*/ column = 0; /*Count current string position*/ for (i = 0; i < 1000; ++i) { /*Set all string to '\0'*/ s[i] = '\0'; sp[i] = '\0'; sp0[i] = '\0'; } i = -1; /*i = -1 then will add 1 equal 0 for array beginning*/ while ((c = getchar()) != EOF) { if (c == '\n') { /*If have meet newline character ++line and character position to 0*/ ++line; column = 0; } else /*If c is '\n' not count column*/ ++column; if (state == 0 && c == '\'') state = 1; else if (state == 1 || state == 4 || state == 5) { if (c == '\\') state = 4; else if (state == 4) state = 5; else if (c == '\'') state = 0; } else if (state == 0 && c == '\"') state = 2; else if (state == 2 || state == 6 || state == 7) { if (c == '\\') /*If in quotes and comments pass through*/ state = 6; else if (state == 6) state = 7; else if (c == '"') state = 0; } else if (state == 0 && c == '/') state = 3; else if (state == 3 || state == 8 || state == 9) { if (c == '*') state = 8; else if (state == 8) { if (c == '*') state = 9; } else if (state == 9) { if (c == '/') state = 0; else state = 8; } else state = 0; } else { /*Transform parentheses brackets braces to number*/ if (c == '[') s[++i] = 1; else if (c == ']') s[++i] = 2; else if (c == '(') s[++i] = 4; else if (c == ')') s[++i] = 5; else if (c == '{') s[++i] = 7; else if (c == '}') s[++i] = 8; else if (c == '\n') /*If c == '\n' set to -1 for later use if between [] have '\n' is not pair*/ s[++i] = -1; sp[i] = line; /*Record s[i] current line*/ sp0[i] = column; /*Record s[i] current position*/ } } s[++i] = '\0'; /*Set string s last character is '\0' for loop end*/ for (i = 0; s[i] != '\0'; ++i) { if (s[i] == 7 || s[i] == 8) /*7 is { 8 is }*/ state0 = 7; else if (s[i] == 4 || s[i] == 5) /*4 is ( 5 is )*/ state0 = 4; else if (s[i] == 1 || s[i] == 2) /*1 is [ 2 is ]*/ state0 = 1; if (state0 == 7) { /*If is '{' or '}'*/ for (j = i + 1; s[j] != '\0'; ++j) /*If some like { { ) } { ( [ ) ] } ( ) will loop 11 times*/ if (s[i] - s[j] == -1) { /*If '{' - '}' equal -1 is a pair*/ s[i] = -7; /*Set pair to -7 Later will count if it is negative will not output message*/ s[j] = -7; } state0 = 0; } else if (state0 == 4) { /*If is '(' or ')'*/ for (j = i + 1; s[j] >= -1 && s[j] <= 5 && s[j] != '\0'; ++j) /*Some like ( [ ) i is 0 s[0] is 3 Between -1 and 5 j is 1 s[1] is 1 Betwenn -1 and 5 s[i] is '(' s[j] is '[' when subtract is not -1 is not a pair on second loop when i is 0 j is 2 i is 0 s[i] is 3 j is 2 s[j] is 4 3 - 4 = -1 s[i] and s[j] is pair set to nagative number Will not output message If some like { ( ( } ) ) When i is 1 s[i] is 3 j is 2 s[j] is 3 not is a pair Between -1 and 5 j is 3 s[j] is 8 not Between -1 and 5 Will end then loop i is 2*/ if (s[i] - s[j] == -1) { /*If '(' - ')' equal -1 is a pair*/ s[i] = -1; s[j] = -1; } state0 = 0; } else if (state0 == 1) { /*If is '[' or ']'*/ for (j = i + 1; s[j]>=1 && s[j]<=2 && s[j]!='\0'; ++j) /*s[j] between 1 and 2 and not is '\n' If false will end some like [ ] [\n] When j == 1 Will end loop When some like { ( ] } } When i == 1 j == 3 Will end loop When i == 2 j == 3 Will end loop When some like { [ } ] When i == 0 j == 2 '{' and '}' Transform to -7 When i == 1 j == 2 s[j] == -7 Will end loop*/ if (s[i] - s[j] == -1) { s[i] = -1; s[j] = -1; } state0 = 0; } } for (i = 0; s[i] != '\0'; ++i) { if (s[i] == 1) s[i] = '['; if (s[i] == 2) s[i] = ']'; if (s[i] == 4) /*Transform back*/ s[i] = '('; if (s[i] == 5) s[i] = ')'; if (s[i] == 7) s[i] = '{'; if (s[i] == 8) s[i] = '}'; } putchar('\n'); for (i = 0; s[i] != '\0'; ++i) if (s[i] != -1 && s[i] != -4 && s[i] != -7) /*If s[i] not is negative not is pair and not is '\n' Output message*/ printf("line %d, column %d unbalanced %c\n", sp[i], sp0[i], s[i]); return 0; }
Solution by codybartfast (Category 0)
This uses a modified Ex1-23 to blank out comments and quotes so it need only check correctness of tags.
/* This ONLY checks that tags are balanced and correctly nested. It assumes the contents of comments and quotes can be ignored. However, a modified version of exercise 1-23 can replace the contents of comments and quotes with spaces, together they can be used like this: cat source.c | ex23replace | ex24 E.g., if tags are properly nested/balanced: ch1> cat source1.c [{ ([{( /∗]∗∗/ ']' '\'' "\"" "]" )}]) }] ch1> cat source1.c | ex23replace [{ ([{( /∗ ∗/ ' ' ' ' " " " " )}]) }] ch1> cat source1.c | ex23replace | ex24 Shiny! no issues discovered :-) ch1> (Asterisks '*' have been replaced with the unicode asterisk operator symbol '∗'.) and if the tags are not properly nested/balanced (first two swapped): ch1> cat source2.c {[ ([{( /∗]∗∗/ ']' '\'' "\"" "]" )}]) }] ch1> cat source2.c | ex23replace {[ ([{( /∗ ∗/ ' ' ' ' " " " " )}]) }] ch1> cat source2.c | ex23replace | ex24 Error: expected ']' but got '}' [line:1, col:55] ch1> The contents of comments are replaced (instead of removing the comments) to prevent the line and column values changing. */ #include <stdio.h> #define NOTAG '\0' #define CONTINUE 2 #define STOP 3 int line = 1; int col = 0; int next(char exptag); int parse(char exptag, char c); int open_tag(char prevexptag, char closetag); int check_closing_tag(char exptag, char acttag); void report_eof_status(char exptag); int main(void) { next(NOTAG); return 0; } int next(char exptag) { int c; if ((c = getchar()) == EOF) { report_eof_status(exptag); return STOP; } else if (c == '\n') { ++line; col = 0; } else { ++col; } return parse(exptag, c); } int parse(char exptag, char c) { if (c == '(') return open_tag(exptag, ')'); else if (c == '[') return open_tag(exptag, ']'); else if (c == '{') return open_tag(exptag, '}'); else if (c == ')' || c == ']' || c == '}') return check_closing_tag(exptag, c); else return next(exptag); } int open_tag(char prevexptag, char closetag) { if (next(closetag) != STOP) return next(prevexptag); return STOP; } int check_closing_tag(char exptag, char acttag) { if (exptag == acttag) return CONTINUE; if (exptag == NOTAG) printf("Error: '%c' was unexpected", acttag); else printf("Error: expected '%c' but got '%c'", exptag, acttag); printf(" [line:%d, col:%d]\n", line, col); return STOP; } void report_eof_status(char exptag) { if (exptag == NOTAG) printf("Shiny! no issues discovered :-)"); else printf("Error: expected '%c', but at end of file.", exptag); putchar('\n'); }
Solution by Foowar
/* exercise 1-24 * * Write a program to check for a C programf 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). * * if something is wrong tell me at: ayoubkhater at protonmail dot com */ #include <stdio.h> /* better to use enums */ #define S_CODE 0 #define S_CHAR 1 #define S_ESC_CHAR 2 #define S_STRING 3 #define S_ESC_STRING 4 #define S_OPENING_SLASH 5 #define S_ASTERISK 6 #define S_COMMENT 7 #define S_ENDING_SLASH 8 #define S_UNDEFINED 9 #define IS_OPENING(c) ((c) == '{' || (c) == '[' || (c) == '(') #define IS_CLOSING(c) ((c) == '}' || (c) == ']' || (c) == ')') #define DO_MATCH(a, b) (((a) == '{' && (b) == '}') || ((a) == '[' && (b) == ']') || ((a) == '(' && (b) == ')')) #define STACK_SIZE 1000 int handle_code(int c) { if (c == '/') return S_OPENING_SLASH; else if (c == '\'') return S_CHAR; else if (c == '"') return S_STRING; else return S_CODE; } int next_state(int state, int c) { if (state == S_CODE) { /* CODE */ return handle_code(c); } else if (state == S_CHAR) { /* CHAR */ if (c == '\\') return S_ESC_CHAR; else if (c == '\'') r\ eturn S_CODE; else return S_C\ HAR; } else if (state == S_ESC_CHAR) { /* ESC_CHAR */ return S_CHAR; } else if (state == S_STRING) { /* STRING */ if (c == '\\') return S_ESC_STRING; else if (c == '\"') return S_CODE; else return S_STRING; } else if (state == S_ESC_STRING) { /* ESC_STRING */ return S_STRING; } else if (state == S_OPENING_SLASH) { /* OPENING_SLASH */ if (c == '*') { return S_COMMENT; } else { return handle_code(c); } } else if (state == S_ENDING_SLASH) { /* ENDING_SLASH */ return handle_code(c); } else if (state == S_ASTERISK) { /* ASTERISK */ if (c == '/') { return S_ENDING_SLASH; } else if (c == '*') { return S_ASTERISK; } else { return S_COMMENT; } } else if (state == S_COMMENT) { /* COMMENT */ if (c == '*') return S_ASTERISK; else return S_COMMENT; } return S_UNDEFINED; } int main(int argc, char *argv[]) { int c, old_c, line, col; int state; int stack[STACK_SIZE], top; state = S_CODE; old_c = EOF; top = 0; line = 1; col = 0; while ((c = getchar()) != EOF) { state = next_state(state, c); ++col; if (state == S_UNDEFINED) { /* this should not happen */ printf("bug in the program: undefined state"); return 1; } if (state != S_OPENING_SLASH && state != S_ENDING_SLASH && state != S_COMMENT && state != S_ASTERISK) { if (c == '\n' && old_c != '\\') { if (state == S_STRING) { printf("%d:%d:error: reached the end of the line but a string" " was not closed\n", line, col); return 1; } else if (state == S_CHAR) { printf("%d:%d:error: reached the end of the line but a character" " constant was not closed\n", line, col); return 1; } } } if (state == S_CODE && IS_OPENING(c)) { stack[top++] = c; } else if (state == S_CODE && IS_CLOSING(c)) { if (top == 0) { printf("%d:%d:error: unmatched '%c'\n", line, col, c); return 1; } else if (!DO_MATCH(stack[top-1], c)) { printf("%d:%d:error: reached '%c' but '%c' was not closed\n", line, col, c, stack[top-1]); return 1; } else { --top; } } if (c == '\n') { ++line; col = 0; } old_c = c; } if (state == S_COMMENT) { printf("error: reached EOF but a comment was not closed\n"); return 1; } else if (state == S_STRING) { printf("error: reached EOF but a string was not closed\n"); return 1; } else if (state == S_CHAR) { printf("error: reached EOF but a character constant was not closed\n"); return 1; } if (top != 0) { int i; for (i = 0; i < top; ++i) { printf("error: reached EOF but '%c' was not closed\n", stack[i]); } } return 0; }
