I think this is now somewhere useful. Pointed at text in memory, it will correctly evaluate an infix expression, properly ignoring leading and trailing spaces. I've included the usual arithmetic operators and also, given its eventual use, bitwise logical operators. Precedence is logic, then multiplication/division, then finally addition/subtraction. This can be overridden using brackets as required - though this requires all routines to hold their own data on the stack because it's recursive. There are no unary operators at the moment though I may add them later, and the only radix is decimal.
Suitable for a tiny basic, it also accepts 26 variables A-Z (not case sensitive). I preload them with values from 0-25 for testing but in the real world that would be unnecessary of course. There is as yet no assignment operator; that will be further in the process.
When an error is found, an error variable is set and further evaluation halted; the returned value is undefined. This differs from Dr Crenshaw's original as he just drops straight down to the OS; I need to complete the operation to unwind the stack and then stop.
This is all very simple C to make it easy to convert to assembly - see earlier posts in this thread for examples. I've not included all the routines for brevity but they should be obvious.
Look is a global char which holds the last character read by GetChar(); mem_ptr is a global pointer to char.
SkipSpaces does what you expect but because it uses GetChar, it also loads Look with the next character to process.
This is called before everything else; it sets up the start of the expression to be evaluated, and (temporarily) preloads the variables.
Code:
void Init (char * mem)
{
mem_ptr = mem;
err = ERR_NONE;
for (int q = 0; q < 26; q++)
{
vars[q] = q;
}
SkipWhite();
GetChar();
SkipWhite();
}
Expression reads either a term, or adds/subtracts further terms as long as there are any - evaluation is left to right.
Code:
int16_t Expression (void)
{
int16_t value;
if (IsAddOp(Look))
{
value = 0;
}
else
{
value = Term();
}
if (ERR_NONE == err)
{
while (IsAddOp(Look))
{
// there are only two possibilities
if ('+' == Look)
{
Match ('+');
value += Term();
}
else
{
Match ('-');
value -= Term();
}
}
}
return value;
}
Term() is similar, but rather than looking for * or / it's expecting logic operators from Alu();
Code:
int16_t Term (void)
{
int16_t term = Alu();
if (ERR_NONE == err)
{
while (IsMulOp(Look))
{
// there are only two possibilities
if ('*' == Look)
{
Match ('*');
term *= Alu();
}
else
{
Match ('/');
term /= Alu();
}
}
}
return term;
}
It's all looking very similar; if we don't find anything interesting, we look for factors...
Code:
int16_t Alu (void)
{
// bitwise logical operations
int16_t alu = Factor();
if (ERR_NONE == err)
{
while (IsLogOp(Look))
{
if ('&' == Look)
{
Match ('&');
alu &= Factor();
}
else if ('|' == Look)
{
Match ('|');
alu |= Factor();
}
else
{
Match ('^');
alu ^= Factor();
}
}
}
return alu;
}
Finally we get to Factor(), where we both handle brackets by recursive calls to Expression(), and actual numbers of variables.
Code:
int16_t Factor (void)
{
int16_t factor;
if (Look == '(')
{
Match ('(');
factor = Expression ();
Match (')');
}
else if (isalpha(Look))
{
factor = vars[GetName() - 'A'];
}
else
{
factor = GetNum();
}
return factor;
}
Match() is interesting. It checks that it is already looking at the desired character and if it is, advances the pointer and reloads Look with the next character. This can throw an error if the character doesn't match.
Code:
void Match (char x)
{
// match a specific input character, get the next character
// and skip over any following white space
if (x == Look)
{
GetChar();
SkipWhite();
}
else
{
char buf[4]; // Expected needs a string
sprintf(buf, "%c", x);
Expected(buf);
}
}
GetNum() and GetName() return either a multi-numeral integer, or a single letter.
Code:
char GetName (void)
{
// validate and return a single character variable name
// get an identifier
char ret = ' ';
if (!isalpha(Look))
{
Expected("Name");
}
ret = toupper(Look);
GetChar();
SkipWhite();
return ret;
}
int16_t GetNum (void)
{
// get a number
int16_t ret = 0;
if (!isdigit(Look))
{
Expected("Integer");
}
while (isdigit(Look))
{
ret *= 10;
ret += Look - '0';
GetChar();
}
SkipWhite();
return ret;
}
Neil