looking for a math engine, an interpreter written in C++, similar to TIcalc's

[legacy]

hi guys
i am looking for a pretty piece of C++ code similar to the math engine of the TIcalc's pocked calculators (Texas Instruments, e.g. TI89, TI92)
i do not need any CAS, just an interpreter able to handle integer, float, in list and matrix, plus common expressions

it's for hobby purposes, i'd like to use it with a linux embedded board, text interface only.

[legacy]

how complex is to write an interpreter with AST ?

[Howardlong]

Do people still use Lex and Yacc or this stuff, or have things moved on in the 20+ years since I last wrote an interpreter?

[legacy]

yes, sometimes i use them, but i have also built a library with my lexer and tokenizer.
what i'd like to focus on is how to generate an AST, probably i have to read more about.

[alexanderbrevig]

I would make a bytecode interpreter and then a simple translator for the syntax you want i.e TIcalc to YourAwesomeByteLang.

[IanB]

yes, sometimes i use them, but i have also built a library with my lexer and tokenizer.
what i'd like to focus on is how to generate an AST, probably i have to read more about.

Mathematical expressions work quite well with a simple recursive descent parser, but more complex language expressions (like C++) are impractical to roll by hand and work much better with compiler generation tools like yacc.

[JacquesBBB]

hi guys
i am looking for a pretty piece of C++ code similar to the math engine of the TIcalc's pocked calculators (Texas Instruments, e.g. TI89, TI92)
i do not need any CAS, just an interpreter able to handle integer, float, in list and matrix, plus common expressions

it's for hobby purposes, i'd like to use it with a linux embedded board, text interface only.

Is an executable OK ?  Or you absolutely need the source code ?
What are the memory size requirements ?

[alexanderbrevig]

what about http://www.ticalc.org/programming/emulators/software.html maybe one of them is FOSS

[legacy]

Is an executable OK ?  Or you absolutely need the source code ?
What are the memory size requirements ?

the target board is a MIPS SoC/linux with 64Mbyte of ram, but i do not want to put an executable on, i want to design something, so i'd like sources as "something that can provide me a get-started"

[legacy]

Mathematical expressions work quite well with a simple recursive descent parser

what do you think about the RPN approach to evaluate "expressions" ?
i have already implemented a very simple RPN engine.

A lot of time ago i implemented this toy-interpreter, and since then a few interpreters (for my job, also using yacc to reduce the "time to market", while "Little-interpreter" was for hobby purposes, designed from scratches without any tool), but i still have a lot to learn

[daybyter]

yacc is a bit dated? Take a look at Antlr.

[JacquesBBB]

We have used extensively Bison/Lex in order to overcome some limitations of yacc/lex for big projects.

[paf]

Take a look at  Calc:

http://www.isthe.com/chongo/tech/comp/calc/
http://sourceforge.net/projects/calc/

[JacquesBBB]

Take a look at  Calc:

From what I look (rapidly I confess), it does not seem to use a tool like bison/lex (or yacc/lex) to define a grammar in an abstract way,
but  just parse the input with dedicated C code.
This will be very difficult to  understand and maintain.

[zapta]

From what I look (rapidly I confess), it does not seem to use a tool like bison/lex (or yacc/lex) to define a grammar in an abstract way,
but  just parse the input with dedicated C code.
This will be very difficult to  understand and maintain.

Recursive decent parsing can be very simple and intuitive.

[Dago]

I personally have used Ragel for parser generation, it generates a stand-alone finite state machine in C so it has no dependencies so it should also be easy to integrate to an embedded project: http://www.colm.net/open-source/ragel/

Writing a calculator with Ragel sounds actually kinda fun, might have to think about that.

[ivaylo]

If it's a calculator with a single data type you are after, it's fun and all of the above mentioned methods will work. If you allow variable assignments, function definitions, scope and such, you should be ready for a different level of fun.

[legacy]

If you allow variable assignments, function definitions, scope and such, you should be ready for a different level of fun.

that is 

[JacquesBBB]

Then you are probably left with bison/flex.
You can start easily a small calculator with it, but it can evolve to a full interpreted language.

just google search for "flex bison calculator" and you will find many examples on the web that
you can then expand to your needs.

[legacy]

thank you

umm, i'd also like to learn (just to learn, i mean read, for practical things i will use "building tools") the process to get a list of tokens into an abstract syntax tree, is there any paper that can teach me this ?

[FrankBuss]

I did such an interpreter some time ago: http://www.frank-buss.de/formula/ Sorry, webpage is in German, but the code and comments (not much) are in English. My idea was to create an object oriented and easy to extend interpreter, which can evaluate a formula with variables fast. First it parses the input with a recursive descent parser, written in C++ (Parser.cpp), which converts the infix input to a list of tokens in postfix format, and a list of variables. Then the variables can be set and the list can be evaluated very fast e.g. for drawing diagrams. The code comes with a Visual Studio project and CppUnit test case and a Windows example program for drawing diagrams to see how to use it. The parser and evaluator itself should be compilable without changes for any C++ target system.

The standard book for learning how parsers, compilers etc. work is the dragon book.

[JacquesBBB]

I have not done it for a while, but  apart from the quoted reference (dragon book), and its new edition,
you may just search on the web for  "bison/flex compilers". As an example, this  looks like a usable tutorial
http://epaperpress.com/lexandyacc/download/LexAndYaccTutorial.pdf

[legacy]

@FrankBuss
i have written a pretty RPN evaluator for expressions, it's pretty able to handle variable, built-in functions (sin, cos, tan …), user-defined function (def my_f(…..))

Code: [Select]

lex("a=b a==b a!=b abc=/=bcd0 logicalNot ! shiftLeft >> notEqual end");

 - token[0]: token=[a] TokenAlpha
 - token[1]: token=[=] TokenAssign
 - token[2]: token=[b] TokenAlpha
 - token[3]: token=[a] TokenAlpha
 - token[4]: token=[==] TokenEqual
 - token[5]: token=[b] TokenAlpha
 - token[6]: token=[a] TokenAlpha
 - token[7]: token=[!=] TokenNotEqual
 - token[8]: token=[b] TokenAlpha
 - token[9]: token=[abc] TokenAlpha
 - token[10]: token=[=/=] TokenNotEqual
 - token[11]: token=[bcd0] TokenAlphaNum
 - token[12]: token=[logicalNot] TokenUnaryNot
 - token[13]: token=[!] TokenUnaryNot
 - token[14]: token=[shiftLeft] TokenShiftLeft
 - token[15]: token=[>>] TokenShiftRight
 - token[16]: token=[notEqual] TokenNotEqual
 - token[17]: token=[end] TokenRightBrace

RPN engine, expression validator 

Code: [Select]

# calc "a=1+2+3*a*b*c"
output: a12+3a*b*c*+=
shunting_yard_analysis PASSED
stack_analysis PASSED
#########################
#    good expression    #
#########################


Code: [Select]

# calc "a++1"
output: a+1+
shunting_yard_analysis PASSED
stack_analysis FAILED
#########################
#    bad  expression    #
#########################


Code: [Select]

# calc "a+((1+2)"
Error: parentheses mismatched
shunting_yard_analysis FAILED
stack_analysis FAILED
#########################
#    bad  expression    #
#########################

i have a pretty tokenizer library, written to convert a script into a list of tokens, and i have already written an interpreter that look like pascal (see the Little project, it has conditional and loop statements, it does not have functions, yet)


my Little project

example script

Code: [Select]

Program factorial
Begin
    Input n
    factorial = 1
    While n > 1
    Begin
        factorial = factorial * n
        n = n - 1
    End
    Output factorial
End



i have studied on the first edition of the dragon book, but it misses the AST approach, i can't see any Abstract Syntax Tree, while Yacc &C are using CST !

[FrankBuss]

my Little project

Nice, looks like this is exactly what you were asking for, just add support for matrix operations etc.

[legacy]

yes, it's a very old project, done as homework in order to get my university degree, it's very simple so i can re-use it, but first i want to rewrite it in the AST way. Also i have written the RPN engine and the new talker engine, 3 different projects that could be merged up into 1 project.

i hope

[zapta]

.
written in C++ (Parser.cpp), which converts the infix input to a list of tokens in postfix format, and a list of variables. Then the variables can be set and the list can be evaluated very fast e.g.

For embedded calculators it may be more memory efficient the do the calculation as part of the recursive decent parsing, passing the resolved values up the tree.

BTW, with java I had good experience with JavaCC, you define the lexical, grammer and even the semantic if you want in a single file, everything is type safe, including custom abstract types, and you have the expression power of Java.

[ivaylo]

BTW, with java I had good experience with JavaCC...

I hear the latest versions of JavaCC can generate C++ code nowadays. I did http://fraid.sourceforge.net using JavaCC long time ago and IMO it is a much more modern tool than lex, yacc, bison, etc. Also instead of clunky syntaxes for the user entering and parsing matrices I stuck to systems of equations, but that fit my application may not fit yours...