Interpreter Sequence execution
 

Hello guys, can anyone give an idea on how to do the algorithm to execute the sequence of action for an Interpreter.

I'm using Java to Interpret.
Example:
I have a file that I will load with an extension of ".txt".

I can read each line and able to tokenize, but i'm stuck on how to execute the code line by line.

Let's say I have this file: addFile.txt

It contains:

ADD 1 2
MUL 2 5
ADD 1 SUB 7 6

The output of course is just the basic math:
3
10
0

3rd line will be zero since it will equate to (1 + (7 - 6)

My question is, how to process line by line, store the result move on to the next line until all lines are executed.

Can anyone give me an idea on how to do it? I really need help on this.
Links to free compiler ebooks, tutorials or any materials is of great help.

Thank you.

:confused::banghead::doh:

What you are looking for is not an algorithm, but a parser.

As you are working with java, ANTLR would be a very good place to start.

You might also find javaCC to be of interest.

In general, the sequence of action will be determined by the grammer for your language as it is processed by your parser, producing an abstract syntax tree, or AST.

Ordinarily your parser will call your lexer (tokenizer or scanner) repeatedly to read tokens until it has recognized a valid sentence for your grammar, constructing the AST in the process. Your action handlers will then produce the desired end product from the AST.

A compiler will produce executable code as its output. An interpreter will execute the sentences immediately. Both depend on the same grammar, lexer, parser and AST, so a search of those terms should lead you to many good online resources.

Thanks Astrogeek, I got this link: https://en.wikipedia.org/wiki/Interpreter_pattern I will start from here.

Do you got links to free compiler ebooks?

I know I can search, but I just can't get any good links.

Hi.

I hope this is not a homework.

Good news is that you use so called prefix notation, aka Polish notation. The evaluation of such expressions is trivial and only requires a stack. The pseudocode is given in the first link. Basically you read expression from right to left, every number is pushed onto the stack and every operator is evaluated with operands taken from the top of the stack and result is pushed back onto the stack. I personally prefer Reverse Polish notation, which is evaluated left-to-right.

Note that this evaluation procedure is not limited to numerical expressions if the stack can hold other data types. You can even implement first-class functions this way (see PostScript).

If your syntax will be more involved then you really need a parser, as suggested by @astrogeek. But even in this case it may be useful to convert to PN or RPN intermediate representation first (with the help of parser).

As for parsers, I really recommend you to implement at least one recursive descent parser yourself for educational purposes. For production it is of course better to use some parser generator, like ANTLR. These tools use some domain specific language, usually EBNF, to describe the syntax. Besides EBNF I recommend you to look up another notation -- Parsing Expression Grammar (PEG), since it is well suited for describing programming languages and is often used nowadays.

Good luck!

Actually, the third line will be 2 because "1 + (7 - 6)" = "1 + 1." :)

It appears to me that this is more-or-less a parsing problem. The main program reads the input file a line at a time, then calls some subroutine to evaluate each line.

That subroutine would then split the line by blank spaces, e.g. using a regular-expression, to produce a stack of entries which may consist either of numeric constants or operands.

You can now use an algorithm similar to that of a parser's internal ("shift/reduce") engine to do the work. The only interesting bit is operator precedence, where a line such as "ADD 1 MUL 3 5" needs to be sure to multiply 3*5 before adding it to 1. (An incorrect implementation might wind up multiplying 4*5.)

I disagree, Polish notation doesn't have operator precedence, that's what makes it so simple. "MUL 3 ADD 5 1" should give 18 (3 * (5 + 1)), not 16 ((3 * 5) + 1).

my god, everything was already explained, nothing to add. I have only one question/comment:
you told you have already implemented a tokenizer. Would be nice to see that probably to give you some hints on how to continue. But probably you want to start over (I have no idea)

Hi ntubski, I agree with you Polish notation don't have operator precedence. I'm actually working on this one also.

But I think right to left scanning will solve the operator precedence.

Hi Sundialsvcs, yes you're right it will be 2, unless it will be 6 - 7 then it will be zero.

The main program reads the input file a line at a time, then calls some subroutine to evaluate each line.

Do you think switch case in Java, is suitable for this?