debugging finite state machine spell checker code

Question

I need someone to debug the lines of c++ code I wrote below so it can run. It is intended to spell check the word "and" using state to state transition.

#include<iostream>
#include<string>

using namespace std;

string in_str;
int n;
void spell_check()
{
     int i;
     FILE *in_file;

     while (!EOF(in_file))
     {
           fscanf(in_str);
           n = strlen(in_str);
           start(in_str,n);
     }
}

void start()
{
     char next_char;

     int i = 0;
     if (n == 0)
     {
           cout<<"This is an empty string";
           exit();//do something here to terminate the program
     }
     else{
          next_char = in_str[i];

          if(next_char == 'a')
          {
                       i++;
                       if(i >= n) error();
                       else state_A(i);
          }
          else error();
     }
}

void state_A(int i)
{
     if(in_str[i] == 'n')
     {
                  i++;
                  if(i<n) state_AN(i);
                  else error();
     }
     else error();
}

void state_AN(int i)
{
     if(in_str[i] == 'd')
     {
                  if(i == n-1)
                       cout<<" Your keyword spelling is correct";
                  else
                      cout<<"Wrong keyword spelling";
     }
}

int main()
{
    spell_check();
    return 0;
}

Answer 1

Few comments:

• Defining the FILE object is not enough. You need to call fopen to actually open a file and only then can you read from it using fscanf or some such.

• strlen() returns a size_t -- an unsigned type. They work with C-style null-terminated strings. std::string is a C++ string class. To use strlen get a C-style string first:

E.g:

  strlen(in_str.c_str());

• Typically, fstream objects are used for file handling.

• Instead of using global objects, try to pass around the information as arguments.

• The error function is not defined.

Answer 2

1. You have to define your functions before you use them
2. There is no function named error
3. exit, fscanf, and strlen are defined in libraries that are not included.
4. fscanf has a few more parameters
5. the test on EOF is wrong, look into fscanf for this one

you might want to add -Wall to your compilation instruction to find all defects yourself in the future. Also good reference material can be easily found on the internet, for instance cplusplus.com.

And because I'm feeling generous today:
A switch combined with recursion is a far more elegant solution for your state machine...

Answer 3

Here's a C program that you could use to test your code:

// -*- coding: utf-8 -*-
#include <stdio.h>
#include <stdlib.h> // EXIT_*

#define log(msg) do { \
  puts(msg); \
  } while(0)

/** $ graph-easy --input=fsm.dot --as=boxart

         ┌─────────────────────────────────────────┐
         │                                         │
         │               [^a]                      │
         │       ┌───────────────────┐             │
         │       ▼                   │             │
         │     ╔═══════╗   [^a]    ╔════╗          │
         │     ║       ║ ───────┐  ║    ║          │
         │     ║ START ║        │  ║ O  ║          │ a
         └──── ║       ║ ◀──────┘  ║    ║ ─┐       │
               ╚═══════╝           ╚════╝  │       │
                 │                   │     │       │
                 │                   │ a   │       │
                 │                   ▼     │       │
                 │                 ╔════╗  │       │
                 │        ┌─────── ║ A  ║ ◀┼───────┘
                 │        │        ╚════╝  │
                 │        │          │     │
                 │        │          │ n   │
                 │        │          ▼     │
                 │        │        ╔════╗  │
                 │        │        ║ N  ║ ─┼───────┐
                 │        │        ╚════╝  │       │
                 │        │          │     │       │
                 │        │          │ d   │       │
                 │        │          ▼     │       │
╔═════╗  EOS     │        │        ╔════╗  │       │
║ END ║ ◀────────┼────────┼─────── ║ D  ║  │       │
╚═════╝          │        │        ╚════╝  │       │
                 │        │          │     │       │
                 │        │ [^n]?    │ .   │ EOS   │ [^d]?
                 │        │          ▼     ▼       ▼
                 │        │        ╔══════════════════════╗
                 │        └──────▶ ║                      ║
                 │                 ║        ERROR         ║
                 │       EOS       ║                      ║
                 └───────────────▶ ║                      ║
                                   ╚══════════════════════╝
*/
typedef enum State {
  O, START, A, N, D, ERROR
} State;

static int next_token(void) {
  int ch = getchar();
  if (ch == '\n') // consider newline as EOS
    return EOF;
  return ch;
}

static int spell_check(void) {
  State state = O;
  int token = -1;
  while ((token = next_token()) != EOF) {
    switch(state) {
    case START:
      log("I am comming");
      // fall through
    case O:
      state = token == 'a' ? A : START; break;
    case A:
      state = token == 'n' ? N : ERROR; break;
    case N:
      state = token == 'd' ? D : ERROR; break;
    case D:
      state = ERROR; break;
    case ERROR:
      return EXIT_FAILURE;
    default:
      log("can't happen");
      return EXIT_FAILURE;
    }
  }
  if (state == O)
    log("This is an empty string");
  return state == D ? EXIT_SUCCESS : EXIT_FAILURE;
}

int main(void) {
  int rc = spell_check();
  if (rc == EXIT_SUCCESS)
    log(" Your keyword spelling is correct");
  else
    log("Wrong keyword spelling");
  return rc;
}

Usage:

$ gcc *.c && (echo and | ./a.out; echo $?)

Output:

 Your keyword spelling is correct
0