I'm not beyond asking for help especially when my professor is a real tool.

this is my homework assignment

( 20 points ) We discussed in class converting an infix expression to a postfix expression. In the implementation of in2post.cpp, we have used an operator stack to hold the operators and both the inputs and outputs are strings; it can only handle integers. You may generalize it by passing in the infix expression in a stack and output the postfix expression in a queue. You may define a TOKEN which can be an operator or a number as follows:

enum WhatKind { oper, number };
typedef struct {
WhatKind kind;
double num;
char op;
} TOKEN;

Your conversion function may have the form,
void in2post( stack <TOKEN> &infix, queue <TOKEN> &postqueue );

Before calling this function, you have to parse the infix expression into TOKENs and put them in the infix stack. The output is the postfix tokens saved in postqueue.

Next, write a function to evaluate the postfix expression. You may first convert the postfix queue to the post stack. Your function may look like:

double evaluate ( stack <TOKEN> &post )
{
stack eval;
double first, second, ans;
char bin_op;
TOKEN tp, te;
while ( !post.empty() ){
tp = post.top();
post.pop();
if ( tp.kind == number )
eval.push( tp );
else {
...
}
}
....
}

What's a TOKEN?

...

typedef struct {
WhatKind kind;
double num;
char op;
} TOKEN;

See here

aah... i still don't get it... what are "lexemes"?

Eris on a freaking pogo stick, just use the damn wikipedia. Just try it.

ok

You suck relay01!

Given the lack of code tags, I would have to agree with that statement.

Sheesh, I had to do that in MIPS assembler, and here you get to use a nice high level language. What are you complaining about?

Yeah, because he did half the work for you....

relay01,

I don't know if your question was answered or not.

I believe your professor means that TOKEN should be one of the math functions.
A * B - C / (D + E)

Each of the MULTIPLY, DIVIDE, ADD, SUBTRACT are the "TOKENS" to which your professor is referring.

You should probably have two strings: infixString and postfixString.

Basically:

1) You are given an INFIX problem (like above)
2) Parse the INFIX expression, and print out the resulting POSTFIX expression
- i) For each character that is read in from the infixString, perform the following:
- ii) If the input character is a letter, append that letter to the end of postfixString
- iii) If the input character is a TOKEN, put that TOKEN onto a stack which you will retrieve later
- iv) If the next input character is another letter, get (read: POP) the TOP element from your stack and insert it onto the end of your postfixString.
- v) You have to make sure to check the preference of the TOKENS when you remove them: *, / and % have higher precedence than + or -, so be sure to remove the correct one.
3) Output, at the very end, the POSTFIX string

The only exception to the above is if your professor's code includes parentheses (like in my example INFIX expression). If he does, once you encounter a ), you have to loop though all the items in your stack until you find the ( and push everything you find into your postfixString.

This way, the above will do this:
A * B - C / (D + E)

infixString          postfixString                  myStack
-----------          -------------                  -------
A                    A                              (empty)
*                                                   *
B                    AB*                            (empty) -- (because we removed the "*")
-                    AB*                            -
C                    AB*C                           - (not removed because the NEXT character is higher-precedence: "/")
/                    AB*C                           -/
(                    AB*C                           -/(
D                    AB*CD                          -/(
+                    AB*CD                          -/(+
E                    AB*CDE+                        -/( (removed the "+")
)                    AB*CDE+                        -/ (removed the "(")
                     AB*CDE+/                       - (still inside the FOR..LOOP for the ")" TOKEN)
                     AB*CDE+/-                      (empty)

I hope that helps somewhat with your assignment.

Well if you are learning compiler theory then I would argue that it's better to stay high level. You'll get more done faster and learn more about the stuff you are supposed to study (compiler theory, not assembler).

Not if he also had to actually compile to machine code Knowing the assembler would go a long way to understanding the workings of the chip/system, and what to compile the code to

Yeah but technically that's not compiler theory.

Um, compiling code isn't compiler theory? Whod'a thunk it!

Assembler isn't compiler theory. If it was then you could say that any format is compiler theory, as it's necessary knowledge if you want to compile something into said format (PostScript, PDF, SVG, XML, HTML and so on). Compiler theory in itself are the generic methods used to turn one format into another.

I think you need to read what I said again

That last message I was pulling your chain

Yeah he needs to know assembler in that case. Can't really get why he head to implement his compiler in assembler though, but I guess it could be a good exercise if you study assembler.

Maybe hes just old? IIRC his day job involves a lot of COBOL. (at least I think its him..)

Writing an assembler is obviously a compiler theory thing. A compiler is a compiler no matter what it compiles.

I think hes saying writing it IN assembler isn't so much compiler theory, and may get in the way of teaching pure compiler theory.

Well, compiler theory is just that, theory: It's got nothing to do with whatever language you're using should you want to actually write a compiler.

Yes, that's what I'm saying Thomas. I haven't said that writing an assembler isn't a compiler theory thing, at least I don't think so? I've said that learning assembler isn't a compiler theory thing and that you would probably want to use a high level language if you want to create a compiler. As you will get more stuff done and have a greater freedom to experiment.

When I started with assembler, I was the assembler. I wrote the assembler code with pencil on paper. Then, using a table, I looked up the hexcodes and wrote them down on the same paper next to the assembler mnemonics. Then I had to count the bytes to get all absolute and relative jumps right. Then I typed in the hexcode.

I couldn't stand the thought of having to do that for my two VM projects, so I ended up writing some nice assemblers for both of them first one was two pass, so you could actually reference labels that are declared after you use them

That's some crazy stuff Johan. When was that?

Sounds cool Thomas. Tell us more about them? Perhaps show some of that assembler code?

I must tell you, the first VM i did was one of my first real projects, back almost 6 years ago. The code has been worked on at various times over the years, so its kinda messy and not well thought out.

casminfo.txt:

The actual code for the assembler is attached (comp.c), I assume it won't fi tin a code box, even with much of the unnesesary bits pulled out.

Also attached (parse.c) is the assembler for my newer script vm.

edit:

Heres an example asm file for the parse.c assembler:

This one utilized the allegro binding I made for it. screen is allegro's screen, and "thing" is an object that the program used to draw a box or pixle on screen.

And heres an example for he comp.c assembler:

edit2, and here's the lib.inc you see from that last example:

Yup, a mini libc omg.

Yeah OMG is a good expression. I briefly checked out the source code, but around 2100 lines is a bit to much for a casual viewing. Impressive work.

Needs a CRZ opcode.

Thanks I was always a little proud of my little CHIP project. Even though its pretty dead now. I ended up writing two styles of execution loop for it, one with a while+switch, and a "threaded" aka "computed goto" "loop". The computed goto code ran around 10x faster than the plain while+switch, back in the day, on my Athlon 900, or it could have been my 450 p3 (I cant recall now), I got upwards of 10 MIPS out of this VM. It could be much better if I didn't have all that "smart" register and fancy arg handling, and make 60x more actual instructions, but I didn't want to go there without making some "generator" for all the extra instruction types, which I never finished.

The second vm I made is pretty cool. It has psuedo OO support. you can set a "foo.bar" to a function: set "foo.bar" "somefunction" call it using the "extended" function calling support, as: foo.bar; and the assembler will do call "somefunction" "foo". And the "second pass" will attempt to turn all string references (which are looked up in a symtab hash at runtime normally), into direct symbol references (pointers to the stuff stored in the symtab, instead of a string which may need to be parsed, ie: "foo.bar.baz" requires the engine to split it at the dots, and then do a look up for baz in bar, and bar in foo, and foo in the global symtab...), which speeds up the engine by N times. (gotta be more than 10 but I can't recall). Oh yeah, the "foo.bar" syntax means look up the "bar" property in the "foo" object, and "foo.bar.baz" means, look up the baz property in the (possibly anon) object referenced in bar, and lookup the bar property in the foo object. I don't think i could have made it more complex >:)

edit: X-G, excuse my ignorance, but what is a CRZ opcode? I've not heard of that one. A couple google searches didn't seem to help either.

So it has first-class functions?

The newer of the two does yes.

function doit
   set doit system.stack.pop
   print doit.value
ret

Nice work Moose. CRZ op rules.

I don't think the OP was posting about a compilation oriented assignment. From what I've seen here in the states, infix to postix is a standard exercise students do when studying stacks etc... You certainly wouldn't use that method in a real compiler, you'd generate assembler from the AST.

And you don't have to generate code at all. For my little Basic thingy I'm executing from the tree.

How much compilers would assembler compile, if assembler would compile compilers? :-P

(Ducks)

You're probably right about the goal of the assignment. I didn't check out the code he posted. Infix to postfix is a common excercise here as well when studying stacks.

Yeah. How is it going with that?

IMO, compiling to some slim bytecode will always be more efficient runtime wise than traversing a tree. Not that its necessarily needed in all cases, but I like to brag about irrelevant things like MIPS, FLOPS and MHZ.

It sounds sensible to me at least. Perhaps there is also a bit more flexibility in there. As you can layer things so that you can write a new backend for some other type of format (like Java Byte Code or something).

On the other hand executing an interpreter directly from the tree is probably easier to implement.

I always had this mental block with doing a direct execute interpreter. Wasn't ever able to fully grasp how to make one when I was still learning about VMs and such.

It's coming along slowly. The method I'm using is pretty simple when your just passing ints around, but when you starting adding ints OR floats, it doesn't work:

As you can see the exec function just returns an int. Now I'm looking into using a runtime store of some sort to pass values around.

But it's two different issues; compiling and then what you do with it. This is a question of the execution environment. And I'm beginning to see why emitting bytecode for a virtual machines is such a good idea.