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

Quote:

---

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?

Quote:

---

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.

Quote:

---

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.

Quote:

---

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.

Quote:

---

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

Quote:

---

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

Quote:

---

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

---

Quote:

---

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.

Quote:

---

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.

Quote:

---

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.

Quote:

---

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

Quote:

---

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.

Quote:

---

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

Quote:

---

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

Quote:

---

Originally Posted by phantomotap

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.

---

There is a bug on line 114, where there is an extra else, that caused NORMAL_CODE to fall through to SINGLE_QUOTED. Remove the extra else, and the code seems to work.

You see, the loop iteration always begins by reading the next character. The first ' in NORMAL_CODE state causes the state to change to SINGLE_QUOTED, but by the time you get to the relevant case statement, the c now refers to a new character because it was read in the loop condition. Since there is no transition to NORMAL_CODE unless there is an end of input (which ends the loop) or a ', single-quoted input is consumed witihin that state.

Note that this code is only intended to scan, not fix, any input.

O_o

I decided to confirm my assumption, but on reading your post again I guess you didn't aim in that direction?

You don't want to do nesting coherence for string and character literals at all?

I'm only confused because it does look like you put effort in that direction for the other bits.

[Edit]
To see what I'm talking about put a single '\'' character on line 151 (That would be before applying the `else' fix which I did for consistency.). The error you get is unrelated to the '\'' character because the code treats several lines as being part of the character literal.
[/Edit]

Soma

Quote:

---

Originally Posted by phantomotap

I decided to confirm my assumption, but on reading your post again I guess you didn't aim in that direction?

---

You're absolutely right, sorry!

I took off on the tangent thames stated in post #6, but neglected to mention it. Ouch.

Before post #6, the code and logic I've posted targets the problem thames stated in the original post in this thread.

After post #6, my code and logic targets the K&R problem thames mentioned: "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. "

Apologies for derailing the thread.

Quote:

---

Originally Posted by phantomotap

To see what I'm talking about put a single '\'' character on line 151 (That would be before applying the `else' fix which I did for consistency.). The error you get is unrelated to the '\'' character because the code treats several lines as being part of the character literal.

---

Yes. There are two reasons why that happens.

First, the state machine progresses through the code, and assumes the code thus far is correct. When it encounters a single quote, it must assume it is the start of a character literal.

Second, the state machine treats string literals and character literals exactly the same way; it does not make any assumptions about the length or contents of the character literal. This is truly a bug, because string literals are not allowed to contain unescaped newlines, whereas string literals are.

Fixing the bug does seem to make it yield correct output. Adding fflush(stdout); just before outputting any error messages will also help pinpoint the location of the error, since the error message should appear right after the character that made the machine to recognize the error was output.


Let me also say a big thank you. Not only just because you've pointed at least two bugs in my code already, but you have made me think about the state machine from different perspective, not just from the viewpoints that come to me naturally. I do my best work in a team where that happens and is encouraged; where discovering holes and bugs and weaknesses in ones implementation is genuinely appreciated. I definitely do, my code can always benefit from another pair of sharp eyes.

If you or anybody else have the time and interest to test it, here is the latest version of my code with both fixes and the enhancements included:

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) {
                    fflush(stdout);
                    fprintf(stderr, "Line %lu: Too deep nesting.\n", line);
                    return 1;
                }
                active[actives++] = c;
            } else
            if (c == ')' || c == ']' || c == '}') {
                if (actives < 1) {
                    fflush(stdout);
                    fprintf(stderr, "Line %lu: '%c' without a prior '%c'.\n", line, c, pair(c));
                } else
                if (active[actives - 1] != pair(c)) {
                    fflush(stdout);
                    fprintf(stderr, "Line %lu: '%c', but expected '%c'.\n", line, c, pair(active[actives - 1]));
                } else
                    actives--;
            }
            break;

        case SINGLE_QUOTED:
            if (c == '\\')
                next();
            else
            if (c == '\'')
                state = NORMAL_CODE;
            else
            if (c == '\n') {
                fflush(stdout);
                fprintf(stderr, "Line %lu: Missing terminating ' character.\n", line - 1UL);
                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;
        }

    fflush(stdout);

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

---

While the code is nowhere near a C lexer (scanner), to me it is surprisingly compact compared to what it achieves.

Considering the C syntax, I think that if you wanted to add new features like detecting missing semicolons, it would be easier to overhaul the state machine, and make it into a genuine C parser/scanner instead. The state map would become completely different, but the basic structure should not be that much different.

C syntax is complex enough that I'd actually turn to a parser generator. For example, GNU Bison can generate the C, C++, or Java code needed, and you can find syntax files for Bison to generate a C parser on the net.

Quote:

---

You're absolutely right, sorry!

---

Quote:

---

Apologies for derailing the thread.

---

*shrug*

No foul here.

I also rather doubt the original poster is much put off considering that he could have learned a bit from the discussion.

Quote:

---

Let me also say a big thank you.

---

Cheers.

Soma

Quote:

---

Originally Posted by phantomotap

I also rather doubt the original poster is much put off considering that he could have learned a bit from the discussion.

---

Indeed. Every bit of information is appreciated. :)
I was wondering about portability. Has the program to be ansi compliant to be portable? if yes, does inline make the program unportable?

Quote:

---

Originally Posted by thames

Has the program to be ansi compliant to be portable?

---

All the environments I personally care about have C99 support. In fact, I'm more concerned with C++98/C++08/C++11 compatibility nowadays.

ANSI C refers to ANSI X3.159-1989, also known as C89, also known as ISO/IEC 9899:1990, also known as C90. (Yes, C89 and C90 are the exact same version.)

C99 provides "static inline" with the exact same semantics as it is used in C++, and flexible array members (final member in a structure with length determined at compile time). I consider these features essential for C programming. I often use the __thread keyword (GNU extension for thread-local storage, _Thread_local in C11) and compiler-provided atomic and vector built-ins (provided by GCC, ICC, and Pathscale compilers at least).

Microsoft is the only vendor whose C compiler does not support C99, to my knowledge. I stopped using their products seven years ago, so I wouldn't really know for sure, though. However, their compiler is, I understand, a combined C/C++ compiler, which means it is likely to support at least static inline (since it is C++).

(Then there are also some ancient environments; you might one day need to program an existing factory robot or something, that only has an ANSI C compiler available.)

So, the answer depends entirely on the gamut of systems you consider. I limit myself to sane POSIX systems, so to me, the code is perfectly portable. Windows programmers might disagree.

Quote:

---

Originally Posted by thames

if yes, does inline make the program unportable?

---

As it is just an optimization feature, more used to indicate programmer intent than anything else, you can always drop it, and make the code plain C89.

Quote:

---

Originally Posted by Nominal Animal

Windows programmers might disagree. As it is just an optimization feature, more used to indicate programmer intent than anything else, you can always drop it, and make the code plain C89.

---

-_- I prefer to stick to C99. :p

Edit: I didn't know ANSI refers to C89.

Code:

---

active[actives]++;
.
.
.
if (active[actives - 1] != pair(c)) {
                    fflush(stdout);
                    fprintf(stderr, "Line %lu: '%c', but expected '%c'.\n", line, c, pair(active[actives - 1]));
                } else
                    actives--;

---

Nominal, I didn't understand this section. Let's say I put inside the array:

Code:

---

active[0] = '('
active[1] = '}'
active[2] = ...

---

how can

Code:

---

active[actives-1]

---

be parentheses if the array stopped at index 2? To me it would be curly brackets in consequence of

Code:

---

active[actives++] = c

---

is it because

Code:

---

actives--

---

? if it is, I still don't understand since the routine only decrements if the pairs coincide.

Quote:

---

Originally Posted by thames

Nominal, I didn't understand this section.

---

No, I think you got it correct.

Initially, actives = 0. When the code encounters an open parens, brace, or bracket, (c == '(' || c == '[' || c == brace), it does

Code:

---

    active[actives++] = c;

---

The post-increment occurs after the assignment; in other words, the above does the exact same thing as

Code:

---

    active[actives] = c;
    actives++;

---

Therefore, if actives > 0, there is at least one open parens/brace/bracket, and the innermost one (latest encountered) is active[actives - 1]. Due to the increment happening after the assignment.

If we look at the code you pointed out:

Code:

---

            if (c == ')' || c == ']' || c == '}') {
                if (actives < 1) {
                    fflush(stdout);
                    fprintf(stderr, "Line %lu: '%c' without a prior '%c'.\n", line, c, pair(c));
                } else
                if (active[actives - 1] != pair(c)) {
                    fflush(stdout);
                    fprintf(stderr, "Line %lu: '%c', but expected '%c'.\n", line, c, pair(active[actives - 1]));
                } else
                    actives--;
            }

---

The first inner if statement just verifies there is at least one open parens/brace/bracket, so we don't try to access a char before the actual array (that would be a buffer underrun bug).

The second inner if statement can be rewritten as

Code:

---

                if (active[actives - 1] == pair(c))
                    actives--;
                else /* error */

---

As I said above, because actives gets incremented after the open parens/brace/bracket is added to the array, active[actives - 1] is always the innermost open one.

Quote:

---

Originally Posted by thames

I still don't understand since the routine only decrements if the pairs coincide.

---

Exactly!

Remember, this code is the one that verifies C quotes, parentheses, brackets, and braces, the logic you mentioned in post #6. It does not implement the logic you specified in your initial post and what I described in post #3.

I'm sorry I confused everyone; I just got engrossed with the tangential, and lost the main thread here.

The code I tested my implementation of the logic in post #3 is below. It is very sparsely commented, since I did not intend to show it to anyone at any point, only quickly threw it together to test the logic I described. I haven't even checked it for any bugs, either. It is also limited to 1023 characters per content sequence.

Code:

---

#include <stdio.h>

int main(void)
{
    char        buffer[1024];
    char *const q = buffer - 1 + sizeof buffer;
    char      *p = buffer;
    int        head, tail, c;

    c = getc(stdin);

    while (1) {

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

        /* No more input? */
        if (c == EOF)
            break;

        /* Head delimiter? */
        if (c == '(') {
            head = '(';
            tail = ')';
            c = getc(stdin);

        } else
        if (c == '{') {
            head = '{';
            tail = '}';
            c = getc(stdin);

        } else
        if (c == '[') {
            head = '[';
            tail = ']';
            c = getc(stdin);

        } else
        if (c == '<') {
            head = '<';
            tail = '>';
            c = getc(stdin);

        } else {
            head = EOF;
            tail = EOF; /* Unknown -- must not match any real characters! */
            /* We have the first content char in c already,
            * so no c = getc(stdin) here. */
        }

        /* Clear buffer. */
        p = buffer;

        /* Content state. */
        while (c != EOF  && c != tail &&
              c != '('  && c != '{'  && c != '[' && c != '<' &&
              c != ')'  && c != '}'  && c != ']' && c != '>' &&
              c != '\t' && c != '\n' && c != '\v' &&
              c != '\f' && c != '\r' && c != ' ') {

            /* Add to buffer, if there is room. */
            if (p < q)
                *(p++) = c;

            c = getc(stdin);
        }

        /* Add terminating NUL byte to the buffer. */
        *p = '\0';

        /* Did we expect a specific tail delimiter? */
        if (tail != EOF) {
            /* Yes. If we got it, consume it. */
            if (c == tail)
                c = getc(stdin);

        } else {
            /* No, we don't know the delimiters yet.
            * See if the tail delimiter defines the pair. */
            if (c == ')') {
                head = '(';
                tail = ')';
                c = getc(stdin);
            } else
            if (c == ']') {
                head = '[';
                tail = ']';
                c = getc(stdin);
            } else
            if (c == '}') {
                head = '{';
                tail = '}';
                c = getc(stdin);
            } else
            if (c == '<') {
                head = '<';
                tail = '>';
                c = getc(stdin);
            } else {
                /* No delimiters. Use [ ] by default. */
                head = '[';
                tail = ']';
                /* Since c is not a delimeter, we do not
                * consume it here. */
            }
        }

        /* Return to whitespace state. */
        putc(head, stdout);
        fputs(buffer, stdout);
        putc(tail, stdout);
    }

    return 0;
}

---

In fact, if I knew I'd show it at some point, I would have written at least two helper functions: one to tell if a character is a non-content character, and another to return the paired delimiter (or none if not a paired delimiter); that should shorten the loop quite a bit, and make the code much easier to read.

This version of my program that implements the original logic described in this thread is probably easier to follow:

Code:

---

#include <stdio.h>

/* Return nonzero (true) if c is an ASCII whitespace character.
*/
static inline int is_whitespace(const int c)
{
    return (c == '\t' || c == '\n' || c == '\v' ||
            c == '\f' || c == '\r' || c == ' ');
}

/* Return nonzero (true) if c is an open parens/brace/whatever.
*/
static inline int is_opener(const int c)
{
    return (c == '(' || c == '<' || c == '[' || c == '{');
}

/* Return nonzero (true) if c is an close parens/brace/whatever.
*/
static inline int is_closer(const int c)
{
    return (c == ')' || c == '>' || c == ']' || c == '}');
}

/* Return zero (false) if c is EOF, whitespace, opener, or closer.
*/
static inline int is_content(const int c)
{
    return (c != EOF &&
            !is_whitespace(c) &&
            !is_opener(c) &&
            !is_closer(c));
}

/* Return the close parens/brace/whatever that corresponds to c.
*/
static inline int closer_of(const int c)
{
    switch (c) {
    case '(': return ')';
    case '<': return '>';
    case '[': return ']';
    case '{': return '}';
    default:  return '\0';
    }
}

/* Return the open parens/brace/whatever that corresponds to c.
*/
static inline int opener_of(const int c)
{
    switch (c) {
    case ')': return '(';
    case '>': return '<';
    case ']': return '[';
    case '}': return '{';
    default:  return '\0';
    }
}

int main(void)
{
    char        buffer[1024];
    char *const q = buffer - 1 + sizeof buffer;
    char      *p = buffer;
    int        head, tail, c;

    c = getc(stdin);

    while (1) {

        /*
        * State: Between content
        */

        while (is_whitespace(c)) {
            putc(c, stdout);
            c = getc(stdin);
        }

        /* No more input? */
        if (c == EOF)
            break;

        /*
        * Transition to state: Content
        */

        if (is_opener(c)) {
            /* Yes, save and consume. */
            head = c;
            tail = closer_of(c);
            c = getc(stdin);

        } else {
            /* We do not know the opener yet. */
            head = EOF;
            tail = EOF;
        }

        /* Clear buffer. */
        p = buffer;

        /*
        * State: Content
        */

        while (is_content(c)) {

            /* Add to buffer, if there is room. */
            if (p < q)
                *(p++) = c;

            c = getc(stdin);
        }

        /*
        * Transition to state: Between content
        */

        /* Add terminating NUL byte to the buffer. */
        *p = '\0';

        /* Did we expect a specific tail delimiter? */
        if (is_closer(tail)) {
            /* Yes. If we got it, consume it. */
            if (c == tail)
                c = getc(stdin);

        } else {
            /* No, we don't know the delimiters yet.
            * See if the tail delimiter defines the pair. */
            if (is_closer(c)) {
                /* It is a closer, so yes, it defines. */
                head = opener_of(c);
                tail = c;
                c = getc(stdin);
            } else {
                /* No, use [ ] by default. */
                head = '[';
                tail = ']';
                /* Since c is not a delimeter, we do not
                * consume it here. */
            }
        }

        /* Print the head delimiter, */
        putc(head, stdout);

        /* the content (if any; it may be empty), */
        fputs(buffer, stdout);

        /* and the tail delimiter. */
        putc(tail, stdout);
    }

    return 0;
}

---

If you read it side-by-side with the logic I described in post #3, it should match.

Quote:

---

Remember, this code is the one that verifies C quotes, parentheses, brackets, and braces, the logic you mentioned in post #6. It does not implement the logic you specified in your initial post and what I described in post #3.

I'm sorry I confused everyone; I just got engrossed with the tangential, and lost the main thread here.

---

You don't need to feel sorry; I knew what the code was doing because I tested it. :)
I will also analyse the easier program. Many thanks for your effort people.

Quote:

---

char *const q = buffer - 1 + sizeof buffer;

---

are you assigning to q the buffer minus the last index (\0') ?

Code:

---

p = buffer

---

cleaning buffer ... I thought you were assigning again the address of buffer to the p pointer.

Quote:

---

Originally Posted by thames

are you assigning to q the buffer minus the last index (\0') ?

---

Yes, q is a pointer to the last char in the buffer. I use it to avoid buffer overrun, while keeping one char reserved for the final '\0'.

Quote:

---

Originally Posted by thames

Code:

---

p = buffer

---

cleaning buffer ... I thought you were assigning again the address of buffer to the p pointer.

---

Exactly, but because p points to the end of the content in the buffer, it "clears" the buffer in the logical sense.

Remember, comments should state the intent behind the code. Anyone can read the code and see what it does, but comments should state why.

That assignment resets our buffer pointer (current end of content pointer) to the start of the buffer, thus "clearing" it, even though it does not modify the buffer contents. It does not have to modify anything, because there is an unconditional *p = '\0' before we use the buffer contents as a string.