Hi,

I think the code I am attaching can correctly find errors in Boolean
expressions of the type:

a) (a+b).(c+d)
b) ((a+!d).(!c+e))
c) (!!!a+(!d)).(!!!!c+f)

It should also be able to use identifiers with more than one letter like:
a) _abc
b) _12b
c) abc2

The Algorithm:
After many hours of pulling my little left hair trying to make
recursive descent parsing to work without going into too many
complications, I decided to try an old parsing algorithm I created
some 20 years ago. This algorithm is straightforward and works by
verifying any token is preceded and succeeded by acceptable tokens. In
cases a token cannot follow another if a certain other token is not
present at a specified position, the algorithm makes deeper
comparisons to detect erroneous tokens.

I am attaching the source file for comments for all those who may want
to comment.

Edward
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

#define INVALID 0
#define VALID   1

typedef char* pchar;
pchar* tokens;             /* global variable to hold token list */
int token_count = 0;       /* global variable to keep track of token count */
int error_pos = 0;         /* global variable to hold error position */

#define token_delta 50

typedef struct {
  int start_bracket;
  int stop_bracket;
  int consecutive_brackets;
} t_bracket_values;

void tokenise(char* expression) {
  char ch;              /* character at iterator's position */
  char* atoken;         /* token to be added to token list  */
  char* start = NULL;   /* holds a char* to point to start of multicharacter token */
  char* string_token;   /* holds multicharacter token */
  int char_count = 0;   /* keeps track of number of characters in multicharacter token */
  
  int while_counter = 0;
  /* expr_len_and_null holds the total length of input string including null terminator */
  int expr_len_and_null = strlen(expression) + 1;
  while (while_counter++ <= expr_len_and_null) {
    ch = *expression++; 
    switch (ch) {
      case '(': 
      case ')':
      case '.':
      case '+':
      case '!':
      case '\0':
        if (start && char_count > 0) {
          string_token = malloc((char_count + 1)*sizeof(char));
          strncpy(string_token, start, char_count);
          tokens[token_count++] = string_token;
                  
          start = NULL;
          char_count = 0;
        }                
      
        if (ch == '\0') return;
        atoken = malloc(2*sizeof(char));
        atoken[0] = ch;
        atoken[1] = '\0';
        tokens[token_count++] = atoken;
        break;
        
      case '\n':
        break;  
        
      default:
        if (start == NULL)
          start = expression - 1;
        char_count++;  
    }
  }
}

void free_memory() {
  int k = token_count;
  
  while (--k >= 0) free(tokens[k]);
  free(tokens);
}

/****************PARSER*****************/

static char* getToken(pchar* tokens, int i) {
  if (i < token_count)
    return tokens[i];
    else return NULL;
}
#define alpha              "abcdefghijklmnopqrstuvwxyz"

/* succeeds ". + )" end */
#define alpha_cl_br        ")"alpha

/* succeeds "! alpha " */
#define oper_op_br         "!+.("

/* at the beginning of expression */
#define alpha_excl_op_br   "!("alpha

static int isOperand(pchar* tokens, int i) {
  char* atoken = getToken(tokens, i);
  
  if (atoken == NULL) 
    return 0;
  else {
    if (strlen(atoken) > 1)
      return 1;
      else return (strchr(alpha, atoken[0]) != NULL);
  }  
}

int getErrorPosn(pchar* tokens) {
  int i = -1;
  char prev_ch = '\0', ch;
  int error_pos1 = -1, error_pos2 = -1;
  char* atoken;
  
  if (token_count == 1) {
    if (!isOperand(tokens, 0))
      i = 0;
      
    error_pos = i;
    return error_pos;  
  }  
  
  while (++i < token_count) {
    atoken = getToken(tokens, i);
    ch = atoken[0];
    
    if (i > 0 && i < token_count - 1) {
      if ( (ch == '+' || ch == '.' || ch == ')') && 
           (prev_ch == ')' ||  isOperand(tokens, i - 1))  )
      {    
        prev_ch = ch;  
        continue;
      }
        
      if ( (ch == '!' || ch == '(' || isOperand(tokens, i)) &&
           strchr(oper_op_br, prev_ch) )
      {
        prev_ch = ch;
        continue;
      }
    }
    prev_ch = ch;
    
    /* at the end of token list */
    if ( (i == token_count - 1) && (ch == ')' || isOperand(tokens, i)) )
      continue;
    /* at the beginning of token list */  
    if ( (i == 0) && (ch == '!' || ch == '(' || isOperand(tokens, i)) )
      continue; 
      
    error_pos1 = i;
    break;   
  }
  
  int brackets = 0;
  for (i = 0; i < token_count; i++) {
    atoken = getToken(tokens, i);
    ch = atoken[0];
    
    if (ch == '(') brackets++;
      else if (ch == ')')
        brackets--;
        
    if (brackets < 0) {
      error_pos2 = i;
      break;
    }    
  }
  
  if (brackets > 0)
    error_pos2 = i;
  
  /* choose the earlier error for output */
  if (error_pos1 > error_pos2)
    error_pos = error_pos1;
    else error_pos = error_pos2;
    
  return error_pos;  
}


/***************************************/

int main() {
  extern int error_pos;

  char input[101];

  tokens = malloc(token_delta*sizeof(char*));
  fgets(input, 100, stdin);
  tokenise(input);
  
  int k = -1;
  /* print the tokens one per line */
  printf("token count is %d\n", token_count);
  while(++k < token_count)
    printf("%s\n", tokens[k]);
    
  getErrorPosn(tokens);
  if (error_pos > -1)
    printf("Error found at position %d\n", error_pos + 1);
    else printf("No error found.\n");

  free_memory();
  
  return 0;
}
_______________________________________________
Dng mailing list
Dng@lists.dyne.org
https://mailinglists.dyne.org/cgi-bin/mailman/listinfo/dng

Reply via email to