chap9.lst

The Art of C++一书的配套源代码

listing 1
// Recursive descent parser for integer expressions. 
// 
#include <iostream> 
#include <cstring> 
#include <cstdlib> 
#include <cctype> 
#include "mccommon.h" 
 
using namespace std; 
 
// Keyword lookup table. 
// Keywords must be entered lowercase. 
struct commands { 
  char command[20]; 
  token_ireps tok; 
} com_table[] = { 
  "if", IF,  
  "else", ELSE, 
  "for", FOR, 
  "do", DO, 
  "while", WHILE, 
  "char", CHAR, 
  "int", INT, 
  "return", RETURN, 
  "switch", SWITCH, 
  "break", BREAK, 
  "case", CASE, 
  "cout", COUT, 
  "cin", CIN, 
  "", END  // mark end of table 
}; 
 
// This structure links a library function name 
// with a pointer to that function. 
struct intern_func_type { 
  char *f_name; // function name 
  int (*p)();   // pointer to the function 
} intern_func[] = { 
  "getchar", call_getchar, 
  "putchar", call_putchar, 
  "abs", call_abs, 
  "rand", call_rand, 
  "", 0  // null terminate the list 
}; 
 
// Entry point into parser. 
void eval_exp(int &value) 
{ 
  get_token(); 
 
  if(!*token) { 
    throw InterpExc(NO_EXP); 
  } 
 
  if(*token == ';') { 
    value = 0; // empty expression 
    return; 
  } 
 
  eval_exp0(value); 
 
  putback(); // return last token read to input stream 
} 
 
// Process an assignment expression. 
void eval_exp0(int &value) 
{ 
  // temp holds name of var receiving the assignment. 
  char temp[MAX_ID_LEN+1];  
 
  tok_types temp_tok; 
 
  if(token_type == IDENTIFIER) { 
    if(is_var(token)) { // if a var, see if assignment 
      strcpy(temp, token); 
      temp_tok = token_type; 
      get_token(); 
      if(*token == '=') { // is an assignment 
        get_token(); 
        eval_exp0(value); // get value to assign 
        assign_var(temp, value); // assign the value 
        return; 
      } 
      else { // not an assignment 
        putback(); // restore original token 
        strcpy(token, temp); 
        token_type = temp_tok; 
      } 
    } 
  } 
  eval_exp1(value); 
} 
 
// Process relational operators. 
void eval_exp1(int &value) 
{ 
  int partial_value; 
  char op; 
  char relops[] = { 
    LT, LE, GT, GE, EQ, NE, 0 
  }; 
 
  eval_exp2(value); 
 
  op = *token; 
  if(strchr(relops, op)) { 
    get_token(); 
    eval_exp2(partial_value); 
 
    switch(op) { // perform the relational operation 
      case LT: 
        value = value < partial_value; 
        break; 
      case LE: 
        value = value <= partial_value; 
        break; 
      case GT: 
        value = value > partial_value; 
        break; 
      case GE: 
        value = value >= partial_value; 
        break; 
      case EQ: 
        value = value == partial_value; 
        break; 
      case NE: 
        value = value != partial_value; 
        break; 
    } 
  } 
} 
 
// Add or subtract two terms. 
void eval_exp2(int &value) 
{ 
  char  op; 
  int partial_value; 
  char okops[] = { 
    '(', INC, DEC, '-', '+', 0 
  }; 
 
  eval_exp3(value); 
 
  while((op = *token) == '+' || op == '-') { 
    get_token(); 
 
    if(token_type == DELIMITER && 
       !strchr(okops, *token)) 
         throw InterpExc(SYNTAX); 
 
    eval_exp3(partial_value); 
 
    switch(op) { // add or subtract 
      case '-': 
        value = value - partial_value; 
        break; 
      case '+': 
        value = value + partial_value; 
        break; 
    } 
  } 
} 
 
// Multiply or divide two factors. 
void eval_exp3(int &value) 
{ 
  char  op; 
  int partial_value, t; 
  char okops[] = { 
    '(', INC, DEC, '-', '+', 0 
  }; 
 
  eval_exp4(value); 
 
  while((op = *token) == '*' || op == '/' 
         || op == '%') { 
    get_token(); 
 
    if(token_type == DELIMITER && 
       !strchr(okops, *token)) 
         throw InterpExc(SYNTAX); 
 
    eval_exp4(partial_value); 
 
    switch(op) { // mul, div, or modulus 
      case '*': 
        value = value * partial_value; 
        break; 
      case '/': 
        if(partial_value == 0) 
          throw InterpExc(DIV_BY_ZERO);        
        value = (value) / partial_value; 
        break; 
      case '%': 
        t = (value) / partial_value; 
        value = value - (t * partial_value); 
        break; 
    } 
  } 
} 
 
// Is a unary +, -, ++, or --. 
void eval_exp4(int &value) 
{ 
  char  op; 
  char temp; 
 
  op = '\0'; 
  if(*token == '+' || *token == '-' || 
     *token == INC || *token == DEC) 
  { 
    temp = *token; 
    op = *token; 
    get_token(); 
    if(temp == INC) 
      assign_var(token, find_var(token)+1); 
    if(temp == DEC) 
      assign_var(token, find_var(token)-1); 
  } 
 
  eval_exp5(value); 
  if(op == '-') value = -(value); 
} 
 
// Process parenthesized expression. 
void eval_exp5(int &value) 
{ 
 
  if((*token == '(')) { 
    get_token(); 
 
    eval_exp0(value); // get subexpression 
 
    if(*token != ')') 
      throw InterpExc(PAREN_EXPECTED); 
    get_token(); 
  } 
  else 
    atom(value); 
} 
 
// Find value of number, variable, or function. 
void atom(int &value) 
{ 
  int i; 
  char temp[MAX_ID_LEN+1]; 
 
  switch(token_type) { 
    case IDENTIFIER: 
      i = internal_func(token); 
      if(i != -1) { 
        // Call "standard library" function. 
        value = (*intern_func[i].p)(); 
      } 
      else if(find_func(token)) { 
        // Call programmer-created function. 
        call(); 
        value = ret_value; 
      } 
      else { 
        value = find_var(token); // get var's value 
        strcpy(temp, token); // save variable name 
 
        // Check for ++ or --. 
        get_token(); 
        if(*token == INC || *token == DEC) { 
          if(*token == INC) 
            assign_var(temp, find_var(temp)+1); 
          else 
            assign_var(temp, find_var(temp)-1); 
        } else putback();          
      } 
 
      get_token(); 
      return; 
    case NUMBER: // is numeric constant 
      value = atoi(token); 
      get_token(); 
 
      return; 
    case DELIMITER: // see if character constant 
      if(*token == '\'') { 
        value = *prog; 
        prog++; 
        if(*prog!='\'') 
          throw InterpExc(QUOTE_EXPECTED); 
 
        prog++; 
        get_token(); 
 
        return ; 
      } 
      if(*token==')') return; // process empty expression 
      else throw InterpExc(SYNTAX);  // otherwise, syntax error 
    default: 
      throw InterpExc(SYNTAX); // syntax error 
  } 
} 
 
// Display an error message. 
void sntx_err(error_msg error) 
{ 
  char *p, *temp; 
  int linecount = 0; 
 
  static char *e[]= { 
    "Syntax error", 
    "No expression present", 
    "Not a variable", 
    "Duplicate variable name", 
    "Duplicate function name", 
    "Semicolon expected", 
    "Unbalanced braces", 
    "Function undefined", 
    "Type specifier expected", 
    "Return without call", 
    "Parentheses expected", 
    "While expected", 
    "Closing quote expected", 
    "Division by zero", 
    "{ expected (control statements must use blocks)", 
    "Colon expected" 
  }; 
 
  // Display error and line number. 
  cout << "\n" << e[error]; 
  p = p_buf; 
  while(p != prog) { // find line number of error 
    p++; 
    if(*p == '\r') { 
      linecount++; 
    } 
  } 
  cout << " in line " << linecount << endl; 
 
  temp = p; 
  while(p > p_buf && *p != '\n') p--; 
 
  // Display offending line. 
  while(p <= temp) 
    cout << *p++; 
 
  cout << endl; 
} 
 
// Get a token. 
tok_types get_token() 
{ 
 
  char *temp; 
 
  token_type = UNDEFTT; tok = UNDEFTOK; 
 
  temp = token; 
  *temp = '\0'; 
 
  // Skip over white space. 
  while(isspace(*prog) && *prog) ++prog; 
 
  // Skip over newline. 
  while(*prog == '\r') { 
    ++prog; 
    ++prog; 
    // Again, skip over white space. 
    while(isspace(*prog) && *prog) ++prog; 
  } 
 
  // Check for end of program. 
  if(*prog == '\0') { 
    *token = '\0'; 
    tok = END; 
    return (token_type = DELIMITER); 
  } 
 
  // Check for block delimiters. 
  if(strchr("{}", *prog)) {  
    *temp = *prog; 
    temp++; 
    *temp = '\0'; 
    prog++; 
    return (token_type = BLOCK); 
  } 
 
  // Look for comments. 
  if(*prog == '/') 
    if(*(prog+1) == '*') { // is a /* comment 
      prog += 2; 
      do { // find end of comment 
        while(*prog != '*') prog++; 
        prog++; 
      } while (*prog != '/'); 
      prog++; 
      return (token_type = DELIMITER); 
    } else if(*(prog+1) == '/') { // is a // comment 
      prog += 2; 
      // Find end of comment. 
      while(*prog != '\r' && *prog != '\0') prog++; 
      if(*prog == '\r') prog +=2; 
      return (token_type = DELIMITER); 
    } 
 
  // Check for double-ops. 
  if(strchr("!<>=+-", *prog)) {  
    switch(*prog) { 
      case '=': 
        if(*(prog+1) == '=') { 
          prog++; prog++; 
          *temp = EQ; 
          temp++; *temp = EQ; temp++; 
          *temp = '\0'; 
        } 
        break; 
      case '!': 
        if(*(prog+1) == '=') { 
          prog++; prog++; 
          *temp = NE; 
          temp++; *temp = NE; temp++; 
          *temp = '\0'; 
        } 
        break; 
      case '<': 
        if(*(prog+1) == '=') { 
          prog++; prog++; 
          *temp = LE; temp++; *temp = LE; 
        } 
        else if(*(prog+1) == '<') { 
          prog++; prog++; 
          *temp = LS; temp++; *temp = LS; 
        } 
        else { 
          prog++; 
          *temp = LT; 
        } 
        temp++; 
        *temp = '\0'; 
        break; 
      case '>': 
        if(*(prog+1) == '=') { 
          prog++; prog++; 
          *temp = GE; temp++; *temp = GE; 
        } else if(*(prog+1) == '>') { 
          prog++; prog++; 
          *temp = RS; temp++; *temp = RS; 
        } 
        else { 
          prog++; 
          *temp = GT; 
        } 
        temp++; 
        *temp = '\0'; 
        break; 
      case '+': 
        if(*(prog+1) == '+') { 
          prog++; prog++; 
          *temp = INC; temp++; *temp = INC; 
          temp++; 
          *temp = '\0'; 
        } 
        break; 
      case '-': 
        if(*(prog+1) == '-') { 
          prog++; prog++; 
          *temp = DEC; temp++; *temp = DEC; 
          temp++; 
          *temp = '\0'; 
        } 
        break; 
    } 
 
    if(*token) return(token_type = DELIMITER); 
  } 
 
  // Check for other delimiters. 
  if(strchr("+-*^/%=;:(),'", *prog)) { 
    *temp = *prog; 
    prog++; 
    temp++; 
    *temp = '\0'; 
    return (token_type = DELIMITER); 
  } 
 
  // Read a quoted string. 
  if(*prog == '"') { 
    prog++; 
    while(*prog != '"' && *prog != '\r' && *prog) { 
      // Check for \n escape sequence. 
      if(*prog == '\\') { 
        if(*(prog+1) == 'n') { 
          prog++; 
          *temp++ = '\n'; 
        } 
      } 
      else if((temp - token) < MAX_T_LEN)  
        *temp++ = *prog; 
 
      prog++; 
    } 
    if(*prog == '\r' || *prog == 0) 
      throw InterpExc(SYNTAX); 
    prog++; *temp = '\0'; 
    return (token_type = STRING); 
  } 
 
  // Read an integer number. 
  if(isdigit(*prog)) { 
    while(!isdelim(*prog)) { 
      if((temp - token) < MAX_ID_LEN)  
        *temp++ = *prog; 
      prog++; 
    } 
    *temp = '\0'; 
    return (token_type = NUMBER); 
  } 
 
  // Read identifier or keyword. 
  if(isalpha(*prog)) { 
    while(!isdelim(*prog)) { 
      if((temp - token) < MAX_ID_LEN)  
        *temp++ = *prog; 
      prog++; 
    } 
    token_type = TEMP; 
  } 
 
  *temp = '\0'; 
 
  // Determine if token is a keyword or identifier. 
  if(token_type == TEMP) { 
    tok = look_up(token); // convert to internal form 
    if(tok) token_type = KEYWORD; // is a keyword 
    else token_type = IDENTIFIER; 
  } 
 
  // Check for unidentified character in file. 
  if(token_type == UNDEFTT) 
    throw InterpExc(SYNTAX); 
 
  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. 
token_ireps look_up(char *s) 
{ 
  int i; 
  char *p; 
 
  // Convert to lowercase. 
  p = s; 
  while(*p) { *p = tolower(*p); p++; } 
 
  // See if token is in table. 
  for(i=0; *com_table[i].command; i++) { 
    if(!strcmp(com_table[i].command, s)) 
      return com_table[i].tok; 
  } 
 
  return UNDEFTOK; // unknown command 
} 
 
// Return index of internal library function or -1 if 
// not found. 
int internal_func(char *s) 
{ 
  int i; 
 
  for(i=0; intern_func[i].f_name[0]; i++) { 
    if(!strcmp(intern_func[i].f_name, s))  return i; 
  } 
  return -1; 
} 
 
// Return true if c is a delimiter. 
bool isdelim(char c) 
{ 
  if(strchr(" !:;,+-<>'/*%^=()", c) || c == 9 || 
     c == '\r' || c == 0) return true; 
  return false; 
}

listing 2
// A Mini C++ interpreter. 
 
#include <iostream> 
#include <fstream> 
#include <new> 
#include <stack> 
#include <vector> 
#include <cstring> 
#include <cstdlib> 
#include <cctype> 
#include "mccommon.h" 
 
using namespace std; 
 
char *prog;  // current execution point in source code  
char *p_buf; // points to start of program buffer 
 
// This structure encapsulates the info 
// associated with variables. 
struct var_type { 
  char var_name[MAX_ID_LEN+1]; // name 
  token_ireps v_type; // data type 
  int value; // value  
}; 
 
// This vector holds info for global variables. 
vector<var_type> global_vars; 
 
// This vector holds info for local variables 
// and parameters. 
vector<var_type> local_var_stack; 
 
// This structure encapsulates function info. 
struct func_type { 
  char func_name[MAX_ID_LEN+1]; // name 
  token_ireps ret_type; // return type 
  char *loc; // location of entry point in program  
}; 
 
// This vector holds info about functions. 
vector<func_type> func_table; 
 
// Stack for managing function scope. 
stack<int> func_call_stack; 
 
// Stack for managing nested scopes. 
stack<int> nest_scope_stack; 
 
char token[MAX_T_LEN+1]; // current token 
tok_types token_type; // token type 
token_ireps tok; // internal representation 
 
int ret_value; // function return value 
 
bool breakfound = false; // true if break encountered 
 
int main(int argc, char *argv[]) 
{ 
  if(argc != 2) { 
    cout << "Usage: minicpp <filename>\n"; 
    return 1; 
  } 
 
  // Allocate memory for the program. 
  try { 
    p_buf = new char[PROG_SIZE]; 
  } catch (bad_alloc exc) { 
    cout << "Could Not Allocate Program Buffer\n"; 
    return 1; 
  }