Парсер

#include <iostream>
#include <cctype>
#include <cstdlib>
#include <cstring>
using namespace std;
 
// The Small Basic token types.
enum typesT { UNDEFTOK, OPERATOR, NUMBER, VARIABLE, COMMAND,
              STRING, QUOTE };
 
// The Small Basic command tokens.
enum SBtokensT { UNKNCOM, PRINT, INPUT, IF, THEN, FOR, NEXT, TO,
                 GOTO, GOSUB, RETURN, EOL, FINISHED, END };
 
/* These are the constants used to call serror() when
   a syntax error occurs.  Add more if you like.
   NOTE: SERROR is a generic error message used when
   nothing else seems appropriate. */
enum errorsT 
    { SERROR, PARENS, NOEXP, DIVZERO, EQUAL_EXP,
      NOT_VAR, LAB_TAB_FULL, DUP_LAB, UNDEF_LAB,
      THEN_EXP, TO_EXP, TOO_MNY_FOR, NEXT_WO_FOR,
      TOO_MNY_GOSUB, RET_WO_GOSUB, MISS_QUOTE };
 
enum double_ops { LE=1, GE, NE };
 
extern char *prog;  // points into the program 
extern char *p_buf; // points to start of program
 
extern int variables[26]; // variables 
 
extern struct commands { 
  char command[20];
  SBtokensT tok;
} table[];
 
extern char token[80]; // holds string representation of token 
extern typesT token_type; // contains type of token 
extern SBtokensT tok; // holds the internal representation of token 
 
void eval_exp(int &result);
void eval_exp1(int &result);
void eval_exp2(int &result);
void eval_exp3(int &result);
void eval_exp4(int &result);
void eval_exp5(int &result);
void eval_exp6(int &result);
void atom(int &result);
void putback();
void serror(errorsT error);
typesT get_token();
SBtokensT look_up(char *s);
bool isdelim(char c);
bool is_sp_tab(char c);
int find_var(char *s);
 
// Entry point into parser. 
void eval_exp(int &result)
{
  get_token(); 
  if(!*token) {
    serror(NOEXP); 
    return; 
  }
  eval_exp1(result); 
  putback(); // return last token read to input stream 
}
 
// Process relational operators. 
void eval_exp1(int &result)
{
  // Relational operators.
  char relops[] = {
    GE, NE, LE, '<', '>', '=', 0
  };
 
  int temp;
  register char op;
 
  eval_exp2(result);
  op = *token;
  if(strchr(relops, op)) {
    get_token();
    eval_exp1(temp);
    switch(op) { // perform the relational operation 
      case '<':
        result = result < temp;
        break;
      case LE:
        result = result <= temp;
        break;
      case '>':
        result = result > temp;
        break;
      case GE:
        result = result >= temp;
        break;
      case '=':
        result = result == temp;
        break;
      case NE:
        result = result != temp;
        break;
    }
  }
}
 
//  Add or subtract two terms. 
void eval_exp2(int &result)
{
  register char op; 
  int temp; 
 
  eval_exp3(result); 
  while((op = *token) == '+' || op == '-') {
    get_token(); 
    eval_exp3(temp); 
    switch(op) {
      case '-' :
        result = result - temp;
        break;
      case '+':
        result = result + temp;
        break;
    }
  }
}
 
// Multiply or divide two factors. 
void eval_exp3(int &result)
{
  register char op; 
  int temp; 
 
  eval_exp4(result); 
  while((op = *token) == '*' || op == '/') {
    get_token(); 
    eval_exp4(temp); 
    switch(op) {
      case '*' :
        result = result * temp;
        break;
      case '/':
        if(!temp) serror(DIVZERO); // division by zero attempted
        result = result / temp;
        break;
    }
  }
}
 
// Process integer exponent.
void eval_exp4(int &result)
{
  int temp, ex; 
  register int t;
 
  eval_exp5(result); 
  if(*token== '^') {
    get_token(); 
    eval_exp4(temp); 
    if(!temp) {
      result = 1;
      return;
    }
    ex = result;
    for(t=temp-1; t>0;  t--) result = result * ex;
  }
}
 
// Is a unary + or -. 
void eval_exp5(int &result)
{
  register char op; 
 
  op = 0; 
  if((token_type==OPERATOR) &&
      *token=='+' || *token=='-')
  {
    op = *token; 
    get_token(); 
  }
  eval_exp6(result); 
  if(op=='-') result = -result;
}
 
// Process parenthesized expression. 
void eval_exp6(int &result)
{
  if(*token == '(') {
    get_token(); 
    eval_exp2(result); 
    if(*token != ')')
      serror(PARENS); 
    get_token(); 
  }
  else
    atom(result); 
}
 
// Find value of number or variable. 
void atom(int &result)
{
  switch(token_type) {
    case VARIABLE:
      result = find_var(token); 
      get_token(); 
      return; 
    case NUMBER:
      result = atoi(token); 
      get_token();   
      return; 
    default:
      serror(SERROR); 
    }
}
 
// Find the value of a variable. 
int find_var(char *s)
{
  if(!isalpha(*s)){
    serror(NOT_VAR); // not a variable
    return 0; 
  }
  return variables[toupper(*token)-'A']; 
}
 
// Display an error message.
void serror(errorsT error)
{
  char *p, *temp;
  int linecount = 0;
  register int i;
 
  static const char *e[]= {   
    "Syntax error", 
    "Unbalanced parentheses", 
    "No expression present",
    "Division by zero",
    "Equal sign expected",
    "Not a variable",
    "Label table full",
    "Duplicate label",
    "Undefined label",
    "THEN expected",
    "TO expected",
    "Too many nested FOR loops",
    "NEXT without FOR",
    "Too many nested GOSUBs",
    "RETURN without GOSUB",
    "Double qoutes needed"
  }; 
  cout << e[error]; 
 
  p = p_buf;
  while(p != prog) {  // find line number of error 
    p++;
    if(*p == '\r') {
      linecount++;
    }
  }
  cout << " in line " << linecount << ".\n";
 
  temp = p;  // display line with error
  for(i=0; i<20 && p>p_buf && *p!='\n'; i++, p--);
  for(; p<=temp; p++) cout << *p;
    
  throw(1); // throw an exception
}
 
// Get a token. 
typesT get_token()
{
  register char *temp;
 
  token_type = UNDEFTOK; 
  tok = UNKNCOM;
  temp = token;
 
  if(*prog=='\0') { // end of file 
    *token = '\0';
    tok = FINISHED;
    return(token_type=OPERATOR);
  }
 
  while(is_sp_tab(*prog)) ++prog;  // skip over white space 
 
  if(*prog=='\r') { // crlf 
    ++prog; ++prog;
    tok = EOL; *token='\r';
    token[1]='\n'; token[2]=0;
    return (token_type = OPERATOR);
  }
 
  if(strchr("<>", *prog)) { // check for double op
    switch(*prog) {
      case '<':
        if(*(prog+1)=='>') {
          prog++; prog++;
          *temp = NE;
        }
        else if(*(prog+1)=='=') {
          prog++; prog++;
          *temp = LE;
        }
        else {
          prog++;
          *temp = '<';
        }
        temp++;
        *temp = '\0';
        break;
      case '>':
        if(*(prog+1)=='=') {
          prog++; prog++;
          *temp = GE;
        }
        else {
          prog++;
          *temp = '>';
        }
        temp++;
        *temp = '\0';
        break;
    }
    return(token_type = OPERATOR);
  }
 
  if(strchr("+-*^/=;(),", *prog)){ // operator
    *temp = *prog;
    prog++; // advance to next position 
    temp++;
    *temp = '\0'; 
    return (token_type=OPERATOR);
  }
    
  if(*prog=='"') { // quoted string 
    prog++;
    while(*prog!='"'&& *prog!='\r') *temp++ = *prog++;
    if(*prog=='\r') serror(MISS_QUOTE);
    prog++; *temp = '\0';
    return(token_type=QUOTE);
  }
  
  if(isdigit(*prog)) { // number 
    while(!isdelim(*prog)) *temp++ = *prog++;
    *temp = '\0';
    return(token_type = NUMBER);
  }
 
  if(isalpha(*prog)) { // var or command 
    while(!isdelim(*prog)) *temp++ = *prog++;
    token_type = STRING;
  }
  
  *temp = '\0';
 
  // see if a string is a command or a variable 
  if(token_type==STRING) {
    tok = look_up(token); // convert to internal rep 
    if(!tok) token_type = VARIABLE;
    else token_type = COMMAND; // is a command 
  }
  return token_type;
}
 
// Return a token to input stream. 
void putback() 
{
 
  char *t; 
 
  t = token; 
  for(; *t; t++) prog--; 
}
 
/* Look up a token's internal representation in the
   token table.
*/
SBtokensT look_up(char *s)
{
  register int i;
  char *p;
 
  // convert to lowercase 
  p = s;
  while(*p){ 
    *p = tolower(*p);
    p++;
  }
 
  // see if token is in table 
  for(i=0; *table[i].command; i++)
    if(!strcmp(table[i].command, s))
      return table[i].tok;
  return UNKNCOM; // unknown command
}
 
// Return true if c is a delimiter. 
bool isdelim(char c)
{
  if(strchr(" ;,+-<>/*%^=()", c) || c==9 || c=='\r' || c==0) 
    return true;  
  return false; 
}
 
// Return true if c is space or tab. 
bool is_sp_tab(char c)
{
  if(c==' ' || c=='\t') return true;
  else return false;
}

#include <iostream>
#include <fstream>
#include <cctype>
#include <cstdlib>
#include <cstring>
using namespace std;
 
const int NUM_LAB = 100;
const int LAB_LEN = 10; 
const int FOR_NEST = 25;
const int SUB_NEST = 25;
const int PROG_SIZE = 10000;
 
// The Small Basic token types.
enum typesT { UNDEFTOK, OPERATOR, NUMBER, VARIABLE, COMMAND,
              STRING, QUOTE };
 
// The Small Basic command tokens.
enum SBtokensT { UNKNCOM, PRINT, INPUT, IF, THEN, FOR, NEXT, TO,
                 GOTO, GOSUB, RETURN, EOL, FINISHED, END };
 
/* These are the constants used to call serror() when
   a syntax error occurs.  Add more if you like.
   NOTE: SERROR is a generic error message used when
   nothing else seems appropriate. */
enum errorsT
      { SERROR, PARENS, NOEXP, DIV_ZERO, EQUAL_EXP,
      NOT_VAR, LAB_TAB_FULL, DUP_LAB, UNDEF_LAB,
      THEN_EXP, TO_EXP, TOO_MNY_FOR, NEXT_WO_FOR,
      TOO_MNY_GOSUB, RET_WO_GOSUB, MISS_QUOTE };
 
char *prog; // points into the program 
char *p_buf; // points to start of program
 
int variables[26]= { // 26 user variables,  A-Z
  0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0
};
 
// keyword lookup table
struct commands { 
  char command[20]; // string form 
  SBtokensT tok; // internal representation 
} table[] = { // commands must be entered lowercase 
  "print", PRINT, // in this table. 
  "input", INPUT,
  "if", IF,
  "then", THEN,
  "goto", GOTO,
  "for", FOR,
  "next", NEXT,
  "to", TO,
  "gosub", GOSUB,
  "return", RETURN,
  "end", END,
  "", END  // mark end of table 
};
 
char token[80];
typesT token_type;
SBtokensT tok;
 
// label lookup table 
struct label {
  char name[LAB_LEN]; // label 
  char *p; // points to label's location in source file 
} label_table[NUM_LAB];
 
// support for FOR loops 
struct for_stack {
  int var; // counter variable 
  int target; // target value 
  char *loc; // place in source code to loop to 
} fstack[FOR_NEST]; // stack for FOR/NEXT loop
 
char *gstack[SUB_NEST]; // stack for gosub 
 
int ftos;  // index to top of FOR stack
int gtos;  // index to top of GOSUB stack
 
void print();
void scan_labels();
void find_eol();
void exec_goto();
void exec_if();
void exec_for();
void next();
void fpush(struct for_stack i);
void input();
void gosub();
void greturn();
void gpush(char *s);
void label_init();
void assignment();
char *find_label(char *s);
char *gpop();
struct for_stack fpop();
bool load_program(char *p, char *fname);
int get_next_label(char *s);
 
// prototypes for functions in the parser file 
void eval_exp(int &result);
typesT get_token();
void serror(errorsT error), putback();
 
int main(int argc, char *argv[])
{
  if(argc!=2) {
    cout << "Usage: sbasic <filename>\n";
    return 1;
  }
 
  // allocate memory for the program 
  try {
    prog = new char [PROG_SIZE];
  } catch(bad_alloc xa) {
    cout << "Allocation Failure\n";
    return 1;
  }
 
  p_buf = prog;
  
  // load the program to execute 
  if(!load_program(prog, argv[1])) return 1;
 
  // begin main interpreter try block
  try {
    scan_labels(); // find the labels in the program 
    ftos = 0; // initialize the FOR stack index 
    gtos = 0; // initialize the GOSUB stack index
    do {
      token_type = get_token();
      // check for assignment statement 
      if(token_type==VARIABLE) {
        putback(); // return the var to the input stream 
        assignment(); // must be assignment statement 
      }
      else // is command
        switch(tok) {
          case PRINT:
            print();
            break;
          case GOTO:
            exec_goto();
            break;
          case IF:
            exec_if();
            break;
          case FOR:
            exec_for();
            break;
          case NEXT:
            next();
            break;
          case INPUT:
            input();
            break;
          case GOSUB:
            gosub();
            break;
          case RETURN:
            greturn();
             break;
          case END:
            return 0;
        }
    } while (tok != FINISHED);
  } // end of try block
 
  /* catch throws here.  As implemented, only
     serror() throws an exception.  However, 
     when creating your own languages, you can
     throw a variety of different exceptions.
  */
  catch(int) {
    return 1; // fatal error 
  }
 
  return 0;
}
 
// Load a program.
bool load_program(char *p, char *fname)
{
  ifstream in(fname, ios::in | ios::binary);
  int i=0;
 
  if(!in) {
    cout << "File not found ";
    cout << "-- be sure to specify .BAS extension.\n";
    return false;
  }
  
  i = 0;
  do {
    *p = in.get();
    p++; i++;
  } while(!in.eof() && i<PROG_SIZE);
 
  // null terminate the program
  if(*(p-2)==0x1a) *(p-2) = '\0'; // discard eof marker
  else *(p-1) = '\0';
 
  in.close();
  return true;
}
 
// Find all labels. 
void scan_labels()
{
  int addr;
  char *temp;
 
  label_init(); // zero all labels 
  temp = prog;  // save pointer to top of program 
 
  // if the first token in the file is a label 
  get_token();
  if(token_type==NUMBER) {
    strcpy(label_table[0].name, token);
    label_table[0].p = prog;
  }
 
  find_eol();
  do {     
    get_token();
    if(token_type==NUMBER) {
      addr = get_next_label(token);
      if(addr == -1 || addr == -2) {
        (addr == -1) ? serror(LAB_TAB_FULL) : serror(DUP_LAB);
      }
      strcpy(label_table[addr].name, token);
     
      // save current location in program 
      label_table[addr].p = prog;
    }
 
    // if not on a blank line, find next line 
    if(tok!=EOL) find_eol();
  } while(tok!=FINISHED);
  prog = temp; // restore original location
}
 
// Find the start of the next line.
void find_eol()
{
  while(*prog!='\n'  && *prog!='\0') ++prog;
  if(*prog) prog++;
}
 
/* Return index of next free position in label array. 
   -1 is returned if the array is full.
   -2 is returned when duplicate label is found.
*/
int get_next_label(char *s)
{
  register int i;
 
  for(i=0; i<NUM_LAB; ++i) {
    if(label_table[i].name[0]==0) return i;
    if(!strcmp(label_table[i].name, s)) return -2;
  }
 
  return -1;
}
 
/* Find location of given label.  A null is returned
   if label is not found; otherwise a pointer to the
   position of the label is returned.
*/
char *find_label(char *s)
{
  register int i;
 
  for(i=0; i<NUM_LAB; ++i) 
    if(!strcmp(label_table[i].name, s)) 
      return label_table[i].p;
  return 0; // error condition 
}
 
/* Initialize the array that holds the labels. 
   By convention, a null label name indicates that
   the array position is unused.
*/
void label_init()
{
  register int i;
 
  for(i=0; i<NUM_LAB; ++i) 
    label_table[i].name[0] = 0;
}
 
// Assign a variable a value.
void assignment()
{
  int var, value;
 
  // get the variable name
  get_token();
  if(!isalpha(*token)) {
    serror(NOT_VAR);
    return;
  }
 
  // convert to index into variable table
  var = toupper(*token)-'A';
 
  // get the equal sign
  get_token();
  if(*token != '=') {
    serror(EQUAL_EXP);
    return;
  }
 
  // get the value to assign 
  eval_exp(value);
 
  // assign the value
  variables[var] = value;
}
 
// Execute a simple version of the BASIC PRINT statement.
void print()
{
  int result;
  int len=0, spaces;
  char last_delim, str[80];
 
  do {
    get_token(); // get next list item 
    if(tok==EOL || tok==FINISHED) break;
    if(token_type==QUOTE) { // is string
      cout << token;
      len += strlen(token);
      get_token();
    }
    else { // is expression
      putback();
      eval_exp(result);
      get_token();
      cout << result;
      itoa(result, str, 10);
      len += strlen(str); // save length
    }
    last_delim = *token; 
 
    // if comma, move to next tab stop 
    if(*token == ',') {
      // compute number of spaces to move to next tab
      spaces = 8 - (len % 8); 
      len += spaces; // add in the tabbing position
      while(spaces) { 
        cout << " ";
        spaces--;
      }
    }
    else if(*token==';') {
      cout << " ";
      len++;
    }
    else if(tok!=EOL && tok!=FINISHED) serror(SERROR); 
  } while (*token==';' || *token==',');
 
  if(tok==EOL || tok==FINISHED) {
    if(last_delim != ';' && last_delim != ',')
      cout << endl;
  }
  else serror(SERROR); 
 
}
 
// Execute a GOTO statement. 
void exec_goto()
{
  char *loc;
 
  get_token(); // get label to go to 
 
  // find the location of the label 
  loc = find_label(token);
  if(loc==NULL)
    serror(UNDEF_LAB); // label not defined 
 
  else prog = loc;  // start program running at that loc
}
 
// Execute an IF statement.
void exec_if()
{
  int result;
 
  eval_exp(result); // get value of expression
 
  if(result) { // is true so process target of IF 
    get_token();
    if(tok!=THEN) {
      serror(THEN_EXP);
      return;
    } // else, target statement will be executed 
  }
  else find_eol(); // find start of next line 
}
 
// Execute a FOR loop. 
void exec_for()
{
  struct for_stack stckvar;
  int value;
 
  get_token(); // read the control variable 
  if(!isalpha(*token)) {
    serror(NOT_VAR);
    return;
  }
  // save index of control var
  stckvar.var = toupper(*token)-'A';
 
  get_token(); // read the equal sign
  if(*token != '=') {
    serror(EQUAL_EXP);
    return;
  }
 
  eval_exp(value); // get initial value 
 
  variables[stckvar.var] = value;
 
  get_token();
  if(tok!=TO) serror(TO_EXP); // read and discard the TO
 
  eval_exp(stckvar.target); // get target value
 
  /* if loop can execute at least once,
     push info on stack */
  if(value >= variables[stckvar.var]) { 
    stckvar.loc = prog;
    fpush(stckvar);
  }
  else // otherwise, skip loop code altogether
    while(tok!=NEXT) get_token();
}
 
// Execute a NEXT statement. 
void next()
{
  struct for_stack stckvar;
 
  stckvar = fpop(); // read the loop info
 
  variables[stckvar.var]++; // increment control var
 
  // if done, return
  if(variables[stckvar.var] > stckvar.target) return; 
 
  fpush(stckvar);  // otherwise, restore the info
  prog = stckvar.loc;  // loop 
}
 
// Push the FOR stack.
void fpush(struct for_stack stckvar)
{
  if(ftos==FOR_NEST)
    serror(TOO_MNY_FOR);
 
  fstack[ftos] = stckvar;
  ftos++;
}
 
// Pop the FOR stack.
struct for_stack fpop()
{
  if(ftos==0) 
    serror(NEXT_WO_FOR);
 
  ftos--;
  return(fstack[ftos]);
}
 
// Execute a simple form of the BASIC INPUT command. 
void input()
{
  char var;
  int i;
 
  get_token(); // see if prompt string is present 
  if(token_type==QUOTE) {
    cout << token; // if so, print it and check for comma 
    get_token();
    if(*token != ',') serror(SERROR);
    get_token();
  }
  else cout << "? "; // otherwise, prompt with ?
  var = toupper(*token)-'A'; // get the input var 
 
  cin >> i; // read input 
 
  variables[var] = i; // store it 
}
 
// Execute a GOSUB command. 
void gosub()
{
  char *loc;
 
  get_token();
 
  // find the label to call
  loc = find_label(token);
  if(loc==NULL)
    serror(UNDEF_LAB); // label not defined 
  else {
    gpush(prog); // save place to return to 
    prog = loc;  // start program running at that loc
  }
}
 
// Return from GOSUB.
void greturn()
{
   prog = gpop();
}
 
// Push GOSUB stack. 
void gpush(char *s)
{
  if(gtos==SUB_NEST)
    serror(TOO_MNY_GOSUB);
 
  gstack[gtos] = s;
  gtos++;
}
 
// Pop GOSUB stack. 
char *gpop()
{
  if(gtos==0)
    serror(RET_WO_GOSUB);
 
  gtos--;
  return(gstack[gtos]);
}