interpreter.cpp

// This code made available to his students by 
// Prof. Ronald Moore  
//     https://fbi.h-da.de/personen/ronald-moore/  
//     mailto:ronald.moore@h-da.de
// with no warranties whatsoever!


#include <cassert>
#include <cctype> // for isspace
#include <cstdlib> // for strtod
#include <iostream>
#include <fstream>
#include <string>
// include <vector>

// ===================
// LEXICAL ANALYSIS
// The following are taken to be tokens:
// left and right parenthesis, the plus and minus characters,
// as well as asterisk and forward slash -- and numbers.
// In the script, substraction and division are not supported,
// but it seems like time to add them.

// Preliminaries and Utilities
// ============================

// Utility Types
typedef double numberType; // feel fee to change this to something else like int or float or bigint....
typedef enum Token { 
	tok_number = 'n',
	tok_lparen = '(',
	tok_rparen = ')',
	tok_plus   = '+',
	tok_minus  = '-',
	tok_times  = '*',
	tok_div    = '/',
	tok_eof    = 'E',
	bad_tok    = 'X'
} Token;

// global variables -- sue me if you don't like that!
static std::istream *input = &(std::cin); // until proven otherwise
static std::string	currentLine( "" );
static int	currentLineNumber = -1;
static int	currentColumnNumber = 0;
static int	currentTokenLength = 0;

static Token next_token; // again with the global variables... 
static numberType currentNumber; // = zero....

static void printErrorMsg( const std::string Error )
{
	std::cout << "ERROR on line " << currentLineNumber
	          << ", column " << currentColumnNumber << " : " 
	          << Error << std::endl;
	std::cout << currentLine;
	for ( int col = 0; col < currentColumnNumber-1; col++ )
		std::cout << '-';
	std::cout << '^' << std::endl;
} // end printErrorMsg

// The Lexer
// ==========
static bool skippedWhiteSpace( ) { // return true if not at EOF, i.e. if skipped
	while ( true ) {
		int currentLineLength = currentLine.length();
		while ( currentColumnNumber < currentLineLength )
			if ( isspace( currentLine[ currentColumnNumber ] ) ) 
				currentColumnNumber++;
			else // if NOT isspace() 
				return true;
				
		// if we're here, we're at the end of a line.
		std::getline( *input, currentLine ); 
		currentLineNumber++;
		currentColumnNumber = 0;
		if ( ! *input ) // EOF!!
			return false;
		// else, repeat! 
		// Which is the same as 
		// return skippedWhiteSpace()  -- i.e. tail recursion.
	};
};		

static Token gettok( ) {
	assert( input ); // we assume nullptr != input
	if ( ! *input ) return bad_tok;
	// else, we can read from input
	
	// Skip white space, going to next line as necessary
	if ( ! skippedWhiteSpace( ) ) return tok_eof;
	        
	// We're have visible text in front of us.
	char currentChar = currentLine[ currentColumnNumber ];
	currentColumnNumber++; // usually, but see num...
	switch (  currentChar ) {
		case '(' : return tok_lparen;
		case ')' : return tok_rparen;
		case '+' : return tok_plus;
		case '-' : return tok_minus;
		case '*' : return tok_times;
		case '/' : return tok_div;
		default : 
			// either we have a number in front of us, or we don't
			assert( 0 < currentColumnNumber );
			char *alpha = &(currentLine[ currentColumnNumber-1 ]);
			// minus one because we incremented it before the switch
			char *omega = nullptr; // until we call strtod...
			double tmpValue = strtod( alpha, &omega );
			if ( alpha == omega ) {
				return bad_tok; // !!!
			};
			// else if strtod found a real number (or at least a double)
			currentNumber = tmpValue; // let C++ do the converison
			currentColumnNumber += (omega - alpha) -1;
			// minus one because we incremented it before the switch
			return tok_number;
	
	}; // end switch
	assert( false ); // we should never get here!
	return bad_tok;
} // end gettok
	
// PARSING!!!
// ===========
// 
// The grammar we are going to parse here is:
// Grammar:
// 	E	→ T E´
// 	E´	→ + T E´  | - T E´ | ε
// 	T	→ F T´
// 	T´	→ * F T´  |  / F T´  |  ε
// 	F	→ ( E ) | num
// Note that the recursive descent function for (e.g.) E´ 
// is nameded "E2ndHalf"-

// Forward Declarations
static numberType E();
static numberType E2ndHalf();
static numberType T();
static numberType T2ndHalf();
static numberType F();

// 	E	→ T E´
numberType E() { return T() + E2ndHalf(); }

// 	T	→ F T´
numberType T() { return F() * T2ndHalf(); }

// 	E´	→ + T E´  | - T E´ | ε
numberType E2ndHalf() {
    switch ( next_token ) {
		case tok_plus : 
			next_token = gettok(); // eat +
            return T() + E2ndHalf();

		case tok_minus : 
			next_token = gettok(); // eat -
			return (-1.0 * T()) + E2ndHalf();

		default : 
			return 0.0;
    }; 
} // end E2ndHalf

// 	T´	→ * F T´  |  / F T´  |  ε
numberType  T2ndHalf() { 
	numberType tmp, rhs, acc;
    switch ( next_token ) {
		case tok_times : 
			next_token = gettok(); // eat *
			return F() * T2ndHalf();
    case tok_div : 
		next_token = gettok(); // eat /
		tmp = F();
		if ( 0.0 != tmp ) 
			return (1.0/tmp) * T2ndHalf();
		// else if T() returned zero
		printErrorMsg( "Division by zero!" );
		// fall through to default return one
        
    default : 
		return 1.0;
    }; 
} // end T2ndHalf

// 	F	→ ( E ) | num
numberType  F() {
	numberType result = 0; 
    switch ( next_token ) {
		case tok_lparen : 
			next_token = gettok(); // eat lparen
            result = E();
            if ( tok_rparen == next_token ) {
				next_token = gettok(); // eat rparen
                return result;
			}; 
			// else if rparen not found
            printErrorMsg( "Expected Right Parenthesis" );
            return 0.0;

		case tok_number : 
			result = currentNumber; // side-effect of last gettok() 
            next_token = gettok(); // eat id
            return result;

		default : 
			printErrorMsg( "Expected Left Parenthesis or number" );
            return 0.0;
    }; 
}


// main (!)
// =========

int main( int argc, char **argv ) {

	if (2 != argc) {
		std::cerr << "Usage: " << argv[0] << " <fileName>.\n" 
		          << "You provided " << argc-1 << " arguments, we take exactly one (only).\n";
		return( -1 );
	};
	// else if 1 == argc ....
	std::string	fileName( argv[1] );
	if ( "-" != fileName ) {
		static std::ifstream ifs( fileName );
		input = &ifs;
	}

	// Prime the pump!
	next_token = gettok( );
	
	// get tokens and dump them... 
	while ( tok_eof != next_token ) {
		std::cout << currentLineNumber << ":" 
		          << currentLine << std::endl;
		numberType value = E( );
		std::cout << "INTERPRETER: " << value << std::endl;
	};
	std::cout << "End Of File!" << std::endl;
	
	return 0; // Alles klar!!!
}