Compiler help

The usual strategy consists of lexing, parsing, code generation.

Lexing is fairly simple. It turns a string ("z = x * y ; z = 3 * x + 2") into a list of symbols:

[(name, "z"), (assign), (name, "x"), (operator, mul), (name, "y"), (sequence, ";"), (name, "z"), (assign, "="), (int, 3) ]

You can use tools (like Lex or Flex) to generate a lexer from a grammar, or you can do everything yourself.

Parsing is more complex. It turns the list of symbols into a forest (list of trees):

          (assign)------------------------------------>(assign)          |      |                                     |      |(name, "z")      (operator, mul)             (name, "z")      (operator, add)                 |             |                              |             |       (name, "x")             (name, "y")      (operator, mul)             (int, 2)                                                |             |                                         (int, 3)             (name, x)

Again, you can use tools (like YACC, bison or others) to generate a parser from a grammar, or you can do everything yourself (usually a Recursive descent parser).

Code generation is turns this tree into assembly (or directly into machine code). You usually have to do this yourself, but simple variants are not that difficult. You visit every tree and recursively translate the nodes.

[ignore] Now that I have typed this out, I notice you probably already know most of that.

I was thinking of doing this myself.. i can convert from expression to a tree by myself, and then from the tree to asm by hand, the problem is that i don't understand how to do it properly.

For example, could you explain recursive decent parsing? i've read through it, but i'm not sure if i'm just being thick, but i don't understand how to put it into practice...

As an alternative to lexical scanning / semantic parsing pair, you should really look toward PEGs (parsing expression grammars.) They basically reflect, with a clean syntax, recursive descent parsers (the easiest to implement.) Lexing and Parsing are merged into a single step.

Where it all begun.
Interesting template implementation.

If you have already built the tree, one simple approach is to make the virtual engine that will run the assembly stack based. I don't know if you are trying to output to your own assembler format or not.

The idea is that your vm has an internally managed stack and the math operations work on the values on the stack. So the "add" instruction, for example, would pop the top two values off the stack, add them together, then push the result back on the stack.

1+(2*3) then becomes:

push 1
push 2
push 3
mul (so stack now contains 6 then 1)
add
pop (to clear the stack and put the result back in a "register")

Whereas (1+2)*3 becomes

push 1
push 2
add
push 3
mul
pop

Your tree nodes just then need a virtual emit method. For the nodes representing the literal numbers, this just emits "push value". For the math operators, it is just:

psuedo:
left_node->emit();
right_node->emit();

switch(type)
{
case add: cout << "add\n"; // etc
}

This way, whether the left node of a math node is a literal value or another math node (and so on to any depth of complexity), the values will be processed in the correct order based on the way the tree is constructed.

HTH

Recursive descent parsing:

First, think up a grammar, e.g.:

StatementSeq ::= (empty) | Statement StatementSeqStatement ::= Var '=' ExprExpr ::= Literal | Literal '+' ExprLiteral ::= Name | Int

Then, translate each rule into a simple procedure, e.g.:

ListOfNodes StatementSeq () {  if(TokenStreamIsEmpty()) return new ListOfNodes();  Node first = Statement();  ListOfNodes rest = StatementSeq();  return (s ++ rest);}Node Statement() {  Node left = Var();  Eat('=');  Node right = Expr();  return new Node(left, right);}Node Expr() {  Node l = Literal();  if(NextTokenIs('+')) {    Eat('+');    Node r = Expr();    return new Node('+', l, r);  }  else return l;}Node Literal() {  if(NextTokenIs(INT)) return new Node(INT, PopNextToken());  if(NextTokenIs(NAME)) return new Node(NAME, PopNextToken());}

where TokenStreamIsEmpty, NextTokenIs and PopNextToken manipulate the currently remaining list of tokens; Eat pops a token and throws an exception if it is not equal to the given argument; Node is a data structure that stores at least left and right child Nodes and a node type; ListOfNodes is a list of such nodes; "node ++ list" puts the node in front of the list.

Note how the rules of the grammar are in an almost one-to-one relationship with the code.

X -> Y Z | Walways becomes more or less:TypeOfX X() {  if(canDetectY) {    return Combine(Y(), Z());  }  if(canDetectW) {    return W();  }}

This also means you are a bit restricted in the form of grammar you can use for this, like LL(k). This more or less means looking at the k leftmost tokens is enough to find out the correct derivation.

[Edited by - samv on August 7, 2006 5:03:13 AM]

Quote:

StatementSeq ::= (empty) | Statement StatementSeqStatement ::= Var '=' ExprExpr ::= Var | Int | Expr '+' Expr (...) Note how the rules of the grammar are in an almost one-to-one relationship with the code. (...)

Make it a PEG :

Statements <- Statement Statement*Statement <- Var '=' ExprExpr <- Expr OP Expr / Var / Int

And you've got a 1 on 1 description of your parser.

No proselytism intended :)

Thanks for all the help, its really appreciated :D

From what i understand, we take the expression, and we grab a token and then we get what other pieces we need from the token stream and we emit them.

now, say for

x = y * 2 + 3

we start off and the first token we find is the equals.

This then causes us to go into a function, that looks at the current buffer of stuff we've seen (in this case x), as well as looking ahead until the end of the buffer, before adding it into the tree?

So we have

    setx     y * 2 + 3

We then scan y * 2 + 3, for the next token, which is the *

and in that function, we scan for the next token, which is 2

so then we have

setx   mul    y    2 + 3

We then continue scanning 2 + 3, until we find the token +, and then we grab until the end of token stream, which is now 3.

So we have a tree

setx  mul     y  add         2  3

I then start from the righthand side and move up, and i start emiiting code. i think i'm starting to get it....

still a problem with operator precedence, but i think i have an idea...

if i assign each operator a certain precidence value, so say adds are 1, muls 2, brackets 3, ect.

I then move down the list from left to right, looking for a child who has a lower precedence value then the greatest one seen, when that happens, You swap the current nodes righthand child's node type to the current node's type, and then you swap the lefthand child of the current node with the righthand child of the nodes rigthand child.

So, basically

setx  mul     y  add         2  3

setx  add     y  mul         2  3

setx  add     3  mul         2  y

Which seems to be right. Would this sort of algorithm work well for a C like language? (and i can't change the processor it runs on, because, well, its a prototype processor....)

how would i deal with brackets?

x = (y + 2) * 3

setx   mul   3  add       y  2

so, we lower the value of anything in the brackets, so that it moves back to the top of the pile...?

What i was thinking of doing, is first off seperating the code into individual expressions first, which i then lex, parse, then emit asm for it, before moving on to the next expression....

This should mean that i
#1, don't have a big tree in memory
#2, can easily find declerations

(this is my first compiler, i just want to make sure that i've got it all down)

[Edited by - Nice Coder on August 7, 2006 7:21:11 AM]

Quote:

Original post by Nice Coder now, say for x = y * 2 + 3 we start off and the first token we find is the equals. ... We then scan y * 2 + 3, for the next token, which is the *

Not exactly. A recursive descent parser looks at the tokens strictly from left to right, while deriving the parts that make up larger parts from top down.

Another example:

Statement ::= Var "=" Expr
Expr ::= MulExpr | MulExpr "+" Expr
Factor ::= Var | Int | "(" Expr ")"

This grammar allows statements like: x = y*3 + (z + w)*4

Let's look at how we parse a Statement:

Statement ::= Var "=" Expr
MulExpr ::= Factor | Factor "*" MulExpr

So if we know we have a statement, the first thing from left to right is a variable, so we parse it; this creates a Var-Node. The next thing is a "=", so we eat it. The next thing is an expression so we parse it; this creates an Expr-Node. Finally, we create an Assign-Node that contains the Var-Node and the Expr-Node.

Parsing a Variable is simple. Just create a Var-Node that contains the Var-Token.

Result so far:

         (Assign)         |      |(Var, "x")      (...)

Parsing an Expr-Node is the interesting part:

Expr ::= MulExpr | MulExpr "+" Expr

First we have a MulExpr, so we parse it. Then we might have a "+"; if so we eat it and know that an Expr must follow, so we parse it (Recursively!). Finally we either just return the single MulExpr-Node, or we create a Add-Node that contains both MulExpr-Node.

         (Assign)         |      |(Var, "x")      (Expr, "+")                |         |            (...)         (...)

MulExpr ::= Factor | Factor "*" MulExpr

Parsing a MulExpr is very similar. Just replace MulExpr, "+" and Expr with Factor, "*" and MulExpr respectively.

           (Assign)           |      |  (Var, "x")      (Expr, "+")                  |         |     (MulExpr, "*")         (MulExpr, "*")     |            |         |            | (...)            (...) (...)            (...)

Factor ::= Var | Int | "(" Expr ")"

Parsing a Factor is also simple: If the next token is a Var, parse a Var. If its an Int parse an Int-Node. If its a "(", we eat it and know that an Expr and a ")" will follow, so we parse the Expr (again, recursively!), eat the ")" and just return the Expr-Node.

               (Assign)               |      |      (Var, "x")      (Expr, "+" )_______                      |                  |         (MulExpr, "*")                  (MulExpr, "*")         |            |                  |            |(Var, "y")            (Int, 3) (Expr, "+")            (Int, 4)                                |         |                      (Var, "z")         (Var, "w")

Done! [SMILE]

If you copy paste the explanations of "Parsing a ..." every time i said "so we parse a ...", you will see that we actually look at the tokens in exactly left to right order. Note that even though the way I drew the trees implies that they grow from top to bottom, they acutually don't!

The operator precedence will be correct automatically, because of the way the grammar was created!

What I mean by ...-Node is something like:

struct Node
{
enum { Assign, Var, Int, Add, Mul } type;
Node *left;
Node *right;
};

[Edited by - samv on August 7, 2006 7:30:56 AM]

Quote:

Original post by Nice Coder What i was thinking of doing, is first off seperating the code into individual expressions first, which i then lex, parse, then emit asm for it, before moving on to the next expression.... This should mean that i #1, don't have a big tree in memory #2, can easily find declerations

I wouldn't worry about wasting memory in the beginning. You really need to understand the principles first. But (assuming you have no control flow statements) you can easily have something like

while(!Done) {  Node *s = Statement();  EmitCodeForStatement(s);  DeleteRecursively(s);}

If you really want to have the most memory-efficient, simplest possible compiler you can even not generate the tree at all and just emit code whenever I said "create A node". But it will be very inflexible (optimizations are almost impossible) and mix up the parser and the code generator.

Quote:

Original post by Nice Coder now, say for x = y * 2 + 3 we start off and the first token we find is the equals.

Just to clarify things a bit : tokens are the smallest semantic values in a grammar much like words and punctuation in non formal languages (read "common languages" like esperanto). In C, for example, while anIdentifier = ( are tokens.

u+v*w^x-y/z

Setep one, make two lists, the operators and the variables:

u v w x y z
+ * ^ - /

Next we need to insert the operations in the right order. We'll start by searching backwards for the ^ operator.

We need to know the operators distance from the last element in the operator list. In this case, '^' is 2. We'll call this offset.

Now start at the end of the variable list. While offset isn't 0, we move backwards one element. If this element is a variable, we decrease offset by 1. If it's an operator, leave it alone. If you support functions, add one less than the number of arguments it takes.

u v w x y z            ^

Offset isn't 0, so we move back 1.

u v w x y z          ^

This is a variable, so we decrease offset. Offset is now 1. Offset isn't 0, so we move back 1.

u v w x y z        ^

This is a variable so we decrease offset. Offset is now 0, we're done! Insert our operator here, and remove it from the operator list.

u v w x ^ y z+ * - /

Now, repeat this with the other operators, going forward for * and /, and again after that for + and -. When you're done, you end up with this:

u v w x ^ * + y z / -

This is the original formula in reverse polish notation. Doing math with this is really easy. You just go from left to right, pushing any variables onto the stack, and the operators pop the top two variables off the stack and push their result. When you reach the end, the value at the top of the stack is the result.

If you want to allow paranthisis, then when you reach '(', you can call your function recursively (they should all be using the same variables list, but have their own operator list) and when you reach ')' you can apply the operators you collected at this level and return.

You can also work backwords to create your syntax tree. Pop the element at the end of the list. If it's a variable, you've reached the end of the branch. If it's an operator, pop the next element (the second argument) off the list, and repeat recurively. Then do this again with the next element (the first argument).

Got it, thanks :D