NO

Author Topic: Expression evaluators and interpreters  (Read 3196 times)

Freddy

  • Guest
Expression evaluators and interpreters
« on: August 23, 2007, 06:13:06 am »
Does anyone know where can I find good information about how to write expression evaluators and interpreters in C?

I want to see if I can write something like:
>> x=2
< x=2 >
>> y=3
< y=3 >
>> x+y
< 5 >
>> _

:D

Diddl

  • Guest
Re: Expression evaluators and interpreters
« Reply #1 on: August 23, 2007, 08:33:17 am »
normally yacc and lex is used for such things (parser).

but for me this tools are too complicated. I write my parsers with Coco/R: look here

Synfire

  • Guest
Re: Expression evaluators and interpreters
« Reply #2 on: August 24, 2007, 04:01:48 am »
I got bored a while back and coded an expression calculator in C++. You could use that as a starting point if you want, it handles precedence and basic floating point math. I actually developed it to give a friend of mine ideas on how to do quick expressions for his assembler (which he was coding in assembly but I wasn't wasting my time doing it in all out assembly). If I get a little bit of time I might be able to convert it over to C if you want, shouldn't be that hard. Just finding the time is the issue (work, school, life, etc).

http://www.codegurus.org/attachments/calc.zip

Regards,
Bryant Keller

Note: The expressions can be multiline expressions. Enter your expression followed by a semi-colon ';', the semi-colon tells the calculator you are finished with the expression and when you hit enter it should print the value on the screen. As you can see below, it's not perfect but at least it does the math right.

Code: [Select]
Press <CTRL-C> to quit.
calc: var = ( 7 * ( pi + 3 ) ) /
              2 ); var = ( var + 4 ) * 3;
21.4956
calc: calc: 76.4867
calc: var + 3;
79.4867
calc: var + 4;
80.4867
calc: var + 7;
83.4867
calc: var
;
77.4867
calc: ^C
« Last Edit: August 24, 2007, 04:03:25 am by Synfire »

Freddy

  • Guest
Re: Expression evaluators and interpreters
« Reply #3 on: August 24, 2007, 06:14:46 am »
Thanks!
I was reading Bjarne's C++ book.
There was an example with this same algo.
I could understand this. Also, your code is very well organized and works. :)

But I will still try to make this in pure C. :D
Would it be too much work? C++ has pretty handy thing like maps.

Synfire

  • Guest
Re: Expression evaluators and interpreters
« Reply #4 on: August 24, 2007, 10:25:13 am »
Thanks!

No problem mate

I was reading Bjarne's C++ book.
There was an example with this same algo.
I could understand this. Also, your code is very well organized and works. :)

Yea, it's a very simple method, I'm not really surprised. Basically you just create procedures to handle each layer of precedence then call through them as you grab each token until you reach the end of your input (in my case it's a CTRL-C).

But I will still try to make this in pure C. :D
Would it be too much work? C++ has pretty handy thing like maps.

Nah, I don't think it would be that much work. The most complex part, and the reason I used C++, will be the translation of the symbol table from use of maps. In C you would accomplish this simply by using a linked list, if you want to optimize you would add a hashing function to save your symbols as 32-bit hashes then compare the hash values. That usually speeds up things rather than having to do string comparisons. This is actually something assemblers and compilers will do because they need to be able to quickly search through the symbol table, and they also tend to store many symbols. Hashing the strings into smaller 32-bit values makes the searches faster and  the memory usage less.

One other thing you will have to do yourself is implement a put_back() system. If I was you I'd probably just make my own I/O wrapper that handled it for you. Two most important ones would be getnext() and undo(). The reason for this is because at times you will read a character and find out that you might need to put it back onto the stream to be "read" again once you finish processing. An example of this is where you have an expression like (2+pi) because there is no space between these tokens you will need to read some of them and undo() the one at the end of the token. Like in that expression we read p, then i, then ), upon seeing ) we know that we've reached the end of the identifier so we undo() the ) putting it back up to be read again later, and processes the pi identifier. The undo() function simply has to push values onto a custom stack (or linked list) and the getnext() checks that "stack" for NULL, if it's not NULL it pops the value off of the stack. If it is NULL then it just reads from the normal input (be it a file or stdin). C++ does this for me using cin.get() and cin.putback(). Check out lines 135 and 136 to see it in action.

But like I said, if I can get some time away from school I'll throw something together for you (or look and see if I can't find something from back when I was still doing a lot of C programming). But for now, I'm going to bed (I've got classes tomorrow). :)

Offline jcfuller

  • Member
  • *
  • Posts: 35
Re: Expression evaluators and interpreters
« Reply #5 on: December 02, 2007, 01:15:53 am »
Is it possible to get lex/yacc (flex/bison) output to compile with Pelles C?
I am a real novice on both fronts.
I am going through a lex/yacc book and the examples compile and run fine on linux but I'd like to try them on windows without having to install gcc.

James