LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 11-09-2016, 03:13 AM   #1
JJJCR
Senior Member
 
Registered: Apr 2010
Posts: 2,141

Rep: Reputation: 447Reputation: 447Reputation: 447Reputation: 447Reputation: 447
Lightbulb 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.

 
Old 11-10-2016, 01:10 AM   #2
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1}
Posts: 6,258
Blog Entries: 24

Rep: Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193
Quote:
Originally Posted by JJJCR View Post
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.
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.

Last edited by astrogeek; 11-10-2016 at 01:35 AM. Reason: typos
 
1 members found this post helpful.
Old 11-10-2016, 04:04 AM   #3
JJJCR
Senior Member
 
Registered: Apr 2010
Posts: 2,141

Original Poster
Rep: Reputation: 447Reputation: 447Reputation: 447Reputation: 447Reputation: 447
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.
 
Old 11-10-2016, 06:40 AM   #4
firstfire
Member
 
Registered: Mar 2006
Location: Ekaterinburg, Russia
Distribution: Debian, Ubuntu
Posts: 709

Rep: Reputation: 428Reputation: 428Reputation: 428Reputation: 428Reputation: 428
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!
 
Old 11-10-2016, 07:28 AM   #5
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,609
Blog Entries: 4

Rep: Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905
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.)
 
1 members found this post helpful.
Old 11-10-2016, 07:48 AM   #6
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,774

Rep: Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081
Quote:
Originally Posted by sundialsvcs View Post
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).
 
1 members found this post helpful.
Old 11-10-2016, 08:40 AM   #7
pan64
LQ Addict
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 21,685

Rep: Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274
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)
 
Old 11-11-2016, 12:25 AM   #8
JJJCR
Senior Member
 
Registered: Apr 2010
Posts: 2,141

Original Poster
Rep: Reputation: 447Reputation: 447Reputation: 447Reputation: 447Reputation: 447
Lightbulb

Quote:
Originally Posted by ntubski View Post
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).
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.
 
Old 11-11-2016, 12:27 AM   #9
JJJCR
Senior Member
 
Registered: Apr 2010
Posts: 2,141

Original Poster
Rep: Reputation: 447Reputation: 447Reputation: 447Reputation: 447Reputation: 447
Question

Quote:
Originally Posted by sundialsvcs View Post
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.)
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?
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Resource execution sequence within a service in cluster.conf srithi Linux - Newbie 0 07-11-2010 06:48 PM
Interpreter wee-face Programming 3 03-04-2007 05:48 PM
Linux Interpreter jazman Linux - General 7 06-05-2006 10:27 AM
rc.local execution sequence? carboncopy Slackware 5 01-05-2005 09:51 PM
interpreter gr33ndata Programming 5 04-23-2004 11:10 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 05:50 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration