Verifying absence of brackets and parentheses

Hi People, good morning. The program has to output curly brackets, square brackets and/or parentheses in case of absences. E.g.:

Code:

1)  [thames  --> [thames] 
2)  thames]  --> [thames]
3) (thames[thames{thames --> (thames)[thames]{thames}
4) thames --> (thames) or [thames] or {thames} (what I choose)

I only know how to deal with the first case. I wish you could explain me how I can deal with the other three.

Code:

#include <stdio.h> 
#include <stdlib.h> 

#define MAXLINE 100

enum syntax_states { 
    
  NORMAL_CHAR = 0, 
  PARENTHESES_BEGIN,
  PARENTHESES_END, 
  SQUARE_BRACKETS_BEGIN, 
  SQUARE_BRACKETS_END,
  CURLY_BRACKETS_BEGIN,
  CURLY_BRACKETS_END
  
};    

int main(void) 
{ 
  int c;
  int i = 0;
  char s[MAXLINE];
  
  enum syntax_states state = NORMAL_CHAR;
  
  while(EOF != (c = fgetc(stdin)))
  { 
    if(c != '\n') 
    { 
      s[i++] = c;    
    }     
    switch(state) 
    { 
      case NORMAL_CHAR: 
        if(c == '[') 
            state = SQUARE_BRACKETS_BEGIN;
        else if(c == '{') 
            state = CURLY_BRACKETS_BEGIN;
        else if(c == '(') 
            state = PARENTHESES_BEGIN;     
       break;           
      
      case SQUARE_BRACKETS_BEGIN: 
        if(c == '\n' && s[i-1] != ']') 
        {    
           s[i++] = ']';
           state = NORMAL_CHAR;
        }
      break;
      
      case SQUARE_BRACKETS_END: 
        // ??
      
      case CURLY_BRACKETS_BEGIN: 
        if(c == '\n' && s[i-1] != '}')
        { 
          s[i++] = '}'; 
          state = NORMAL_CHAR; 
        }      
      break;
      
       case PARENTHESES_BEGIN: 
        if(c == '\n' && s[i-1] != ')') 
        { 
          s[i++] = ')'; 
          state = NORMAL_CHAR; 
        }
       break;        
    }
  }
  s[i] = '\0';
  fputs(s, stdout);            
  return 0;     
}

you need more states than a single NORMAL_CHAR. try states NORMAL_CHAR_SQUARE, NORMAL_CHAR_CURLY and NORMAL_CHAR_PARENT. so when you encounter a '[', go to the NORMAL_CHAR_SQUARE state. then keep reading normal characters until you encounter a [,{ or (. when you see one of those, print the closing brace, and go to the appropriate NORMAL_CHAR_... state.

You can simplify your logic by using the fact that you have delimiter pairs surrounding your content.

You essentially have just two states: within content, and between content. The identity of the delimiters is just a data point you keep in helper variable(s). (This is the laziness bit I mentioned in another thread, when designing state machines.)

When you always progress through the states in order, and have significant work to do in the state transitions, it is better to split each state into a separate code block.

In pseudocode, with comments naming which part of the code handles which state and transition between states:

Code:

read char

Loop:

    # State "Between content":

    # Read and flush white-space as is.
    while char is neither white-space nor end-of-file:
        output char
        read char
    end while

    if char is end-of-file:
        break out of loop
    end if

    # Transition to state "Content":

    if char is (:
        set opener to (
        set closer to )
        read char
    else if char is [:
        set opener to [
        set closer to ]
        read char
    else if char is {:
        set opener to {
        set closer to }
        read char
    else:
        # Not decided yet. Set to a sentinel value (never read):
        set closer to end-of-file
    end if

    set string is empty

    # State "Content":

    while char is not (whitespace ( ) [ ]  { } end-of-file):
        append char to string
        read char
    end while

    # Transition to state "Between content":

    if closer is end-of-file:
        # We do not have opener and closer yet. Decide.
        if char is ):
            set opener to (
            set closer to )
            read char
        else if char is ]:
            set opener to [
            set closer to ]
            read char
        else if char is }:
            set opener to {
            set closer to }
            read char
        else:
            # defaults:
            set opener to [
            set closer to ]
        end if
    else:
        # closer is known. Did we get it?
        if char is closer:
            # Yes, consume it.
            read char
        else
            # Special conflict resolution when char != closer?
        end if
    end if

    output opener
    output string
    output closer

end loop

Note that this loop does not read a new char at every iteration, because the state machine evolves inside the loop. We prime it with the first input character, and every iteration of the outer loop begins at the "between content" state.

In the "between content" -state, you output all whitespace characters as-is. This state is where you flush all the characters that will not be parenthesized or bracketed.

If you encounter an open parens or open bracket, you consume it, but set the opener and closer characters to match it. They will later on be used to surround the actual content.

If you don't see an open parens or an open bracket, set closer to an impossible sentinel value (that does not occur in the input) as a sign that you need to decide on them only afterwards.

Within the "content" state, you save all content characters to a buffer. Note that checking for close parens and close brackets is not enough: you need to check for open parens and open brackets too, if you wish to handle e.g. "(foo(bar" correctly.

If the closer is impossible after the loop in the "content" state, you need to check if char is a close parens or close bracket that defines the opener and closer. If so, you consume it, and must read a new char for the next iteration of the outermost loop. Otherwise, you need to check if char was the closer you expected, and if so, consume it and read next char for the next iteration of the outermost loop. Otherwise, you need to set opener and closer to some default values.

If closer is known, and char is a close parens or close brackets, you have a conflict. If you do nothing, then the conflict is resolved implicitly, as if an separate empty piece of content was added there. (For (foo] you get (foo)[].)

At this point, you are ready to transition back to "between content" state, with the correct opener and closer, and the content in the string buffer. So, output them, and your outer loop is complete.
_ _ _ _

Implementing the above state machine took me about 100 lines of clean C code, plus comment lines. In particular, input

Code:

{foo((bar}baz)

yields output

Code:

{foo}()(bar){}(baz)

The empty parens occur because it has no closing parens; the state machine implicitly adds an empty content there. The empty curly braces appear because bar begins with a parens, but ends with a curly brace: the opener and closer do not match. This state machine resolves that conflict by assuming there is an empty piece of content after bar, like I explained above.

When your state machines start becoming more complex, you can implement "sub-machines": either sectioning the code like I did above, or better yet, split it into separate functions. These sub-machines are almost always quite linear; they progress through a set of states in a specific order (possibly returning early).

When I personally do that, my functions tend to have the signature

Code:

int handle_some_state(FILE *const in, int c, additional variables related to state);

The c contains the first character to be handled in that state, already read from the input stream in, and returns the character that was read but not handled by that state. If it needs to modify some buffers or variables, specify them (their addresses as pointers; pass by reference, not by value) as additional parameters to the function.

Note that you could use ungetc() to push the one character back into the stream. It is internal to the C library, and does not affect the file/stream outside the process in any way. I'm just personally so lazy I've found it easier to use the "you have the character already in c" idiom, rather than use ungetc().

Originally Posted by Nominal Animal

You can simplify your logic by using the fact that you have delimiter pairs surrounding your content.

You essentially have just two states: within content, and between content. The identity of the delimiters is just a data point you keep in helper variable(s). (This is the laziness bit I mentioned in another thread, when designing state machines.)

Does that mean the lazier my state machine is, the better (when it comes to complexity) it will be?
in the another thread, could I have used a lazier approach? i.e. used the "within content/between content" approach?

Originally Posted by Nominal Animal

I'm just personally so lazy I've found it easier to use the "you have the character already in c" idiom.

please explain further what this idiom is.

Originally Posted by thames

Does that mean the lazier my state machine is

I meant the lazier you, the programmer is, the better the state machine should be.

It should be as simple as -- or shall we say, the least complex -- it can be, but still do its job.

Originally Posted by thames

in the another thread, could I have used a lazier approach? i.e. used the "within content/between content" approach?

Good question.

No, I don't think so, because the state machine diagram is not a straight line like here. You have various transitions that only occur in some cases. In this case, the state machine diagram is straight as an arrow (or more accurately, a one-way ring), just with state transitions that have many side effects the code needs to perform.

How to decide when to use more states and when to use more complicated transitions?

Beats me. I have to work it out the hard way, considering different code structures, basically writing the majority or at least the heart of the code in my head (at an abstract level; I may be an idiot, but I'm definitely not an idiot savant), and then pick the one that seems likely to yield best fruit. Usually I end up writing some skeleton code for two choices, then develop them in parallel until one seems better than the other.

Originally Posted by thames

please explain further what this idiom is.

The idea is that when your loop body starts, it will always have the current character already read into a variable, c, instead of for example having the loop start by reading the next character. You read the next character into c only after you have fully handled the current character.

If you think about walking on a beach looking for a nice black round pebble, the approach where you start each loop iteration by reading a new character maps to "Start by picking up a pebble. If it is nice and black, put it in your pocket and walk away. If it is wet, drop it and move up the beach, otherwise drop it and move down the beach". However, this approach starts by you already holding the pebble: "As long as the pebble you have is not (nice and black): if it is wet, drop it and move up the beach. Otherwise drop it and move down the beach. Pick up a new pebble."

Now, sometimes you may have to add weirder cases like "If the pebble has creepy crawlies on it, drop it fast." or perhaps better selection methods, like "Pick up the nicest pebble you can see." If you look at the sentences above, both of these conditions are simpler (require less code) to add to this approach, as compared to adding them to the traditional one where you start the loop iteration by picking up a new pebble.

Back to programming.

The nice thing about this approach is that you have c in your hands, and you can jump around your state machine, through several state transitions without reading a new character. This means you can avoid duplicating code by adding jumps or conditionals, since the cause of the transition is always c.

The side effects are very often exactly like in my pseudo-code above: "empty" input sequences, that match states that did not consume any input characters. When your state machine is simply a chain of states (even two states like here), such output often turns out to be the desirable one.

The downside is that this approach is often rather complicated to document fully, especially if your co-authors are of the lazy sort who tend to hack things without bothering to understand the logic, just sticking some if clause in a likely spot that seems to produce the desired results after minimal testing (.. if any).

If that happens, this approach will very rapidly degenerate into unreadable mess. You need to keep a strict hold on the structure and documentation to keep it maintainable; and, unfortunately, if you encounter a case that does not fit the existing code well enough, you may need to rewrite the function to keep it maintainable.

Fortunately, if your co-authors understand and agree with the logic, this approach is easy to maintain. Well, barring new functionality that may need a rewrite from a different approach.

Sometimes the nature of the state machine changes by "minor feature requests" or "just an itty bitty tweak".

@Nominal

Read and flush white-space as is.

How can I do this? I didn't get there yet.

actually, I misinterpreted the exercise:

from KnR 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.)"

I don't need to fix the syntax. However, I really want to write this SM since I've been understanding it from the last thread.

Originally Posted by thames

How can I do this?

Assume you have the current character already read in c.

If you are in a state where you wish to skip ASCII whitespace characters, you only need to do

Code:

    while (c == '\t' || c == '\n' || c == '\v' ||
           c == '\f' || c == '\r' || c == ' ') {
        c = getc(stdin);
    }

Note how even in the loop you always have the reason, c, for any state change in your hand?

If you are in a state where you wish to read and flush white-spaces, you do

Code:

    while (c == '\t' || c == '\n' || c == '\v' ||
           c == '\f' || c == '\r' || c == ' ') {
        putc(c, stdout);
        c = getc(stdin);
    }

Originally Posted by thames

actually, I misinterpreted the exercise:

from KnR 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.)"

Heh heh.. Consider the removing comments state machine.

What would happen if you wrote the output even when inside comments, too (you'd just have to remember to output the comment characters that are consumed by the intermediate states), and added checks to disallow newlines within quotes and doublequotes? And add a new state, ANGLE_BRACKETED, similar to double quotes?

I haven't tested it out in the code, but I suspect you'd only need to add maybe two dozen lines to get the complete functionality. Since all input is also output, the state machine could, in fact, be simplified.

Now that I think about it, the main reason that type of state machine is better for that case, is because the transitions require multiple input characters, and may branch after the first match. For example, // and /* are the start markers for two different states.

.. and that thought caused a yet another lightbulb moment. If you write a state machine that handles lexemes instead of characters -- basically newline, non-newline-white-space, ", ', (, [, ], ), //, /*, */, and (anything else), then you can do a very, very simple state machine. (Technically you'd have a mini-parser or miniature state machine reading the input into lexemes, and an outer state machine working on its output.)

I'll write some test code and report back whether that approach works.

Inspired by powernet, I wrote this for the KnR 1-24 exercise:

Code:

#include <stdio.h> 

#define MAXLINE 100

int getLine(char* s, int lim);

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;
} 

int main(void) 
{ 
  char s[MAXLINE];
  int t, num_dquotes, num_squotes, len, curly_brackets, 
         parens, square_brackets, s_quoted, d_quoted;
  
  num_dquotes = num_squotes = len = 0;
  s_quoted = d_quoted = curly_brackets = parens = square_brackets = 0;
  
  while( (len = getLine(s, MAXLINE)) > 0) 
  { 
     t = 0; 
     while(t < len) 
     { 
        switch(s[t]) 
        { 
          case '(': 
              parens++;
          break;
          
          case  ')': 
              parens--;
          break;
          
          case '[': 
              square_brackets++;
          break;
          
          case ']': 
             square_brackets--;
          break;
          
          case '{': 
             curly_brackets++;
          break;     
          
          case '}': 
             curly_brackets--;
          break;      
          
          case '\'': 
           s_quoted = -1;
           num_squotes++;
             if(num_squotes == 0 || num_squotes == 2) 
               s_quoted = 0;
          break;     
          
          case '\"':                  
           d_quoted = -1;
           num_dquotes++;
             if(num_dquotes == 0 || num_dquotes == 2) 
               d_quoted = 0;
          break;      
        }
        t++;     
     }
   }    
     
     if(parens != 0)
      printf("The parentheses weren\'t properly closed.\n");
     if(curly_brackets != 0)
      printf("The curly brackets weren\'t properly closed.\n");
     if(square_brackets != 0)
      printf("The square brackets weren\'t properly closed.\n");   
     if(d_quoted != 0)
      printf("The double quotes weren\'t properly closed.\n"); 
     if(s_quoted != 0) 
      printf("The single quotes weren\'t properly closed.\n"); 
     if(parens == 0 && curly_brackets == 0 && square_brackets == 0 && 
        d_quoted == 0 && s_quoted == 0)
      printf("It looks like the syntax is correct.\n");            
         
  return 0;    
}

of course, unfortunately, it doesn't use SM because I'm only counting the number of times the chars appeared.

Reporting on my findings after investigating (see my post #7 above):

Bah, it was a poor idea to read groups of characters with special meaning, then use that small set of entities as the feed to the state machine. It took 110 lines for the functions that read and write special entities (newlines, /*, */, //, (, ), braces, [, ]) as negative characters, plus almost 200 lines of sparsely commented code to implement the full state machine using the "separate code block for each state" approach, for a total of slightly over 300 lines. And it's messy, definitely not elegant.

Using the comment-removing state machine code (I had written earlier to make sure the approach works) as a basis, I added a 37-line wrapper around getc() to count line numbers and immediately output the input so I could report the line where any errors were encountered, and to output everything read immediately, so my state machine does not need to output anything but the errors it notices. I needed a 12-line function to tell me the other character matching a parens, brace, or a bracket. Then I modified 15 lines, and added 27 new lines to the state machine, and I was done. Length is 156 lines total, and the code reads quite clean. Half the size the other approach, and much cleaner, too.

For both programs, I checked that it does not report any errors in some random source files taken from a stable Linux kernel. Then grabbed a test file, and seeded some errors. It seems to catch all of them, but due to the mechanism I chose, much later than a normal compiler would. It essentially notices only when the pairs don't match, or if there are unmatched pairs at the end of the input. But, both programs were happily quiet about all the source files I fed them.

Ah what the hell, I look like an idiot talking about code no-one has seen.

Here's the 165-line (now that I added the final state checks), 7-state machine, that should be able to detect errors in quoting, parentheses, braces, brackets, and comments. I think it looks clean, and should be maintainable (although I should definitely add comments explaining the intent behind each code block), but make up your own mind:

Code:

#include <stdio.h>

#define MAX_ACTIVES 1024

enum comment_states {
    NORMAL_CODE = 0,
    SINGLE_QUOTED,
    DOUBLE_QUOTED,
    AFTER_SLASH,
    CPP_COMMENT,
    C_COMMENT,
    C_COMMENT_ASTERISK
};

static unsigned long line = 1UL;

static inline int next(void)
{
    int  c;

    c = getc(stdin);

    if (c == '\n') {
        line++;
        c = getc(stdin);
        if (c != '\r') {
            ungetc(c, stdin);
            fputc('\n', stdout);
        } else
            fputs("\n\r", stdout);
        return '\n';

    } else
    if (c == '\r') {
        line++;
        c = getc(stdin);
        if (c != '\n') {
            ungetc(c, stdin);
            fputc('\r', stdout);
        } else
            fputs("\r\n", stdout);
        return '\n';

    } else
    if (c != EOF) {
        fputc(c, stdout);
        return c;
    }

    return EOF;
}


static inline int pair(const int c)
{
    switch (c) {
    case '(': return ')';
    case ')': return '(';
    case '[': return ']';
    case ']': return '[';
    case '{': return '}';
    case '}': return '{';
    default:  return '\0';
    }
}


int main(void)
{
    enum comment_states  state = NORMAL_CODE;
    char                 active[MAX_ACTIVES];
    int                  actives = 0;
    int  c;

    while (EOF != (c = next()))
        switch (state) {

        case AFTER_SLASH:
            if (c == '/') {
                state = CPP_COMMENT;
                break;
            } else
            if (c == '*') {
                state = C_COMMENT;
                break;
            }
            state = NORMAL_CODE;

        case NORMAL_CODE:
            if (c == '/')
                state = AFTER_SLASH;
            else
            if (c == '"')
                state = DOUBLE_QUOTED;
            else
            if (c == '\'')
                state = SINGLE_QUOTED;
            else
            if (c == '(' || c == '[' || c == '{') {
                if (actives >= MAX_ACTIVES) {
                    fprintf(stderr, "Line %lu: Too deep nesting.\n", line);
                    return 1;
                }
                active[actives++] = c;
            } else
            if (c == ')' || c == ']' || c == '}') {
                if (actives < 1)
                    fprintf(stderr, "Line %lu: '%c' without a prior '%c'.\n", line, c, pair(c));
                else
                if (active[actives - 1] != pair(c))
                    fprintf(stderr, "Line %lu: '%c', but expected '%c'.\n", line, c, pair(active[actives - 1]));
                else
                    actives--;
            } else
            break;

        case SINGLE_QUOTED:
            if (c == '\\')
                next();
            else
            if (c == '\'')
                state = NORMAL_CODE;
            break;

        case DOUBLE_QUOTED:
            if (c == '\\')
                next();
            else
            if (c == '\"')
                state = NORMAL_CODE;
            break;                

        case CPP_COMMENT:
            if (c == '\n')
                state = NORMAL_CODE;
            break;

        case C_COMMENT:
            if (c == '*')
                state = C_COMMENT_ASTERISK;
            break;

        case C_COMMENT_ASTERISK:
            if (c == '/')
                state = NORMAL_CODE;
            else
            if (c != '*')
                state = C_COMMENT;
            break;
        }

    if (state == C_COMMENT || state == C_COMMENT_ASTERISK)
        fprintf(stderr, "Line %lu: Expected end of comment */ before end of input.\n", line);
    else
    if (state == DOUBLE_QUOTED)
        fprintf(stderr, "Line %lu: Expected '\"' before end of input.\n", line);
    else
    if (state == SINGLE_QUOTED)
        fprintf(stderr, "Line %lu: Expected '\'' before end of input.\n", line);

    while (actives > 0)
        fprintf(stderr, "Line %lu: Expected '%c' before end of input.\n", line, pair(active[--actives]));

    return 0;
}

Edited to add the nine if-else lines near the end. I forgot to verify that the state is sane at end of input.

Also, please remember I wrote the above for testing purposes only. I did not intend to show it at all to anyone, just decided to show it because I'm stupid.

Originally Posted by Nominal Animal

Also, please remember I wrote the above for testing purposes only. I did not intend to show it at all to anyone, just decided to show it because I'm stupid.

Thanks for not showing the program. That was wise not stupid. I will try to code it looking at the pseudo.

Ah what the hell, I look like an idiot talking about code no-one has seen.

O_o

I don't see why.

Talking out the ideas with him as you have been is a lot better than throwing code around.

Now, if you were asking for help finding a source error without posting code that would make you look like an idiot.

Edited to add the nine if-else lines near the end. I forgot to verify that the state is sane at end of input.

O_o

Is this the right code?

I only glanced at it, but I think your code transitions to account for `actives' when handling string or character literals.

Soma

Originally Posted by thames

I will try to code it looking at the pseudo.

A very commendable attitude; I respect that.

Just remember to have fun, especially the fun of discovering your own way to do stuff.

If you get stuck, and have to take a look at others' code, that's quite okay too, if you take the time to understand why you got stuck, and why some other approach works. It's still your way if you make your own choices based on your understanding, and not because someone else said it is better.

I personally have learned a lot just by reading both good code and bad code; good code to learn what works, especially what kinds of code patterns tend to work in the long term, and bad code to learn what to avoid. I, too, have a lot to learn still -- and I hope I never stop learning.

I do feel like a jackass for showing the code. Sorry about that.

Originally Posted by phantomotap

I only glanced at it, but I think your code transitions to account for `actives' when handling string or character literals.

What do you mean? The code is supposed to ignore parentheses, brackets, and braces within character constants and string literals. And since both string literals and character constants can occur within all three (parentheses, brackets, and braces), there should be no reason to account for active (open) ones wrt. character constants or string literals.

I could be wrong, though; I often am.

What do you mean?

Well, I may be wrong, but it looks like the code doesn't ignore parentheses, brackets, or braces within character constants and string literals.

I think conditions like "single quote" are not consumed/discarded properly with respect to updating the state because only the characters representing the start of such a sequence is consumed/discarded before transition back into a state where `actives' may be updated.

In other words, I think you are only consuming/discarding the first character in the sequence '(' when the entire sequence must be consumed else you parse the parentheses character normally.

Soma