ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
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
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.
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.)
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)
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.
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?
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.