🔒 Locked

Building a compiler (Script)

Started by Nice Coder Jul 9, 2004 at 6:49 AM 24 replies 3.5k views

Original Post

101

Jul 9, 2004 at 6:49 AM

Currently my VM is looking pretty good: It has a stack(for calls/returnes) 8 registeres (doubles) Subroutines A seperate type for code (to make compilation easier) Math (+-*/ bitshifts) Bitwise operations (xor or and not) Memory operations (sto, ret, memory copy and memory set) RAM (actually an array, but it is used by sto and ret as a temperary storage place for registers) And an extra functions class which it can call, which has 1. A displaying function which finds a null terminated string (found by argument) and displayes it 2. An Asking function, which takes a string from an inputbox and turns it into a null terminated string. 3. A memory resiser sub which resises the array 4. a memory clear sub which sets the contents of the array to 0 Currently, i need to make a compiler. An asm compiler is not that difficult, ie. xor eax, ebx turns into 6:0 1 6-Functions index on the jumptable (which i use to call it) 0-Eax register's location 1-Ebx register's location The result would be in edx But a script-asm compiler would, How do i go from print "Hello world" to


1:103 0  'load value 103 to eax register
14:0 1 'load eax register to location 1 in RAM
1:101 0 'and so on
14:0 2
1:101 0
14:0 3
1:108 0
14:0 4
1:108 0
14:0 5
1:111 0
14:0 6
1:32 0
14:0 7
1:119 0
14:0 8
1:111 0
14:0 9
1:114 0
14:0 10
1:108 0
14:0 11
1:100 0
14:0 12
19:0 0 0  'display null-terminated string starting at 0

^^^^ is an actual working program. My problem is how do i get it? With variables, i have a few ideas, like allocating where they all are, then replacing them inside the source file (ie. a turns into 102) arrays- no clue a + b / 2 i have got about 0.5 of a clue convert into two operands Mset 0 2 Div b 0 Add a b Then replace a and b with their values Mset 0 2 div 2 0 Add 1 2 Then compile into opticode values 0:0 2 4:2 0 2:1 4 I am currently googling and reading all i can about compiling, but everything seems to use flex and bison! Any help would be appriciated Please comment on how to compile/how bad my vm is/if you want the source code/to test that the forums "Post" feature works DENC

Author

101

Jul 9, 2004 at 7:21 AM

Finished asm compiler
Works like a charm
Does anybody have any pointers to those who are writing their own script/asm compilers.

And for the asc { } tags (invaluable if your compiler is buggy).
Does any idea on how to make the asm tags?

29

Jul 9, 2004 at 7:21 AM

Use flex and bison! Why don't? They're nice and do the work for you. I'm currently trying to learn them using this tutorial:http://www.epaperpress.com/lexandyacc/index.html.

40

Jul 9, 2004 at 7:26 AM

I think 99% of compilers are made using other tools, like lex, yacc, flex, bison, etc. You're reinventing the wheel if you do everything from scratch.

Unless you have a really weird language, there are two steps to compilation: lexical analysis, where you break the code up into "tokens", and syntactical/semantical analysis, where you figure out the meaning of a sequence of tokens, usually using a grammar for your language, and generate code. There are tools for both of these, and they're designed to work well with each other.

When using a lexer tool, you usually define a few token types and provide a regular expression for each one. The lexer also attaches the actual string matched with each token (for example, the variable name for an IDENTIFIER token). For example, say you're making a simple calculator that supports decimal numbers, parantheses, '+' and '*'. You'd have five token types: NUMBER (which is a sequence of digits, defined by the regular expression "[0-9]+"), PLUS ("+"), TIMES, LBRACKET and RBRACKET. The lexer tool would produce C code which defines these token types as constants and, given an input, returns an array of token structs (int type, char* value).

When using a syntactical/semantical analysis tool, you provide a context-free grammar for your language, and code to execute upon reaching each one. In the example above, the grammar might look as follows (note that several types of "terms" are defined in order to make order of operations work correctly):

<Expression> ::= <SumTerm> PLUS <Expression> | <SumTerm>  // note that "|" means "or"<SumTerm> ::= <ProdTerm> TIMES <SumTerm> | <ProdTerm><ProdTerm> ::= NUMBER | LPAREN <Expression> RPAREN

Generating code form this is harder. But basically, you provide C code to be executed for each rule (within the same file where you define your grammar, usually). For example, if you encounter the rule ::= NUMBER, you take the NUMBER's string value, parse it into an int, and generate some code that pushes that onto the stack. If you encounter ::= PLUS , you evaluate the SumTerm and Expression first, then take the code string generated for the SumTerm, append to it the code string generated by the Expression, and append your 'add top 2 elements of stack' opcode. From the code snippets you provide for each rule, the syntactical analysis tool will generate a C function which, given a sequence of tokens, generates the equivalent "assembly code". Then, using your compiler is as simple as reading a file, tokenizing it, and calling the function.

If you're not using a stack for arithmetic in your program, but rather registers, code generation is a bit harder, but basically you have to keep track of which ones are used at each point and put your result into the next one, essentially emulating a stack. (This is why Java, for example, just uses a stack for local calculations instead of bothering with registers, although if you were compiling to real ASM you'd need to work with registers).

Mod

395

Jul 9, 2004 at 7:49 AM

You'd benefit from reading Game Scripting Mastery by Alex Varanese. I bought this book, mainly because I wanted to write my *own* compiler instead of using things like Lex/Yacc. Yes, I know it's reinventing the wheel, but it's all part of the fun, right?

This book takes you up from knowing nothing, to teaching you how to build a VM, a lexer and then a Paser for a C-like language.

Don't get me wrong, it can be basic at times, but there's a good read in it if you're good at thinking how you can improve upon what the author is showing you.

Author

101

Jul 9, 2004 at 8:00 AM

Flex and bison are... nice but i do not want to have flex and bison difficulties now... this is just a scripting language!

For the For loops, something like
for a = 0 to b step c

next a

could be converted into
0 Mset a, 0
1 add c, 0
2 add a, edx
3 cmp a,b
jgth 100
'code inbetween for and next
99 jmp 0
100 'do stuff after loop

That could be converted into something like
ret ecx, 2 'Get the max variable
ret eax, 0 'reset the counting register
ret ebx, 1 'get the count from RAM
Mcpy eax, edx 'Set it back to edx for calculation
add edx, ebx 'this part counts
cmp eax, ecx 'compare the values to the maximum value
jgth 100 'if greater then, get out of the loop

jmp 4 'Jump back to the add

So basically to implement a for loop,
I would just tack that bit of code in, replacing 2, 0 and 1 with the location of the max variable, the count variable and the initial count respectively.

I would also replace the 100 with the line number of the jmp + 1
and i would set the 4 to the line number of the add.

Bit complex, but it works! (this is quite fun!)

A do loop would be a bif different
It would be like

cmp eax,ebx
jgth 100
..
..
..
..
jmp 0
where 0 is where the cmp is
and 100 is where the jmp is.

I've been reading too many tutorials now, haven't i?
I should be able to get the for loop and the do loop pretty soon. its just the memory allocation/deallocations going to be a nightmare!

[Edit]
Evolutional-Thats a nice book, but the chances of me laying my hands on a book that isn't in the library are very slim.

Matei-How would you define all of those terms?
The language i would be compiling from would be like basic and C,
It would use the same conditional structure, ++, --, *=, ect.
But it would also use DIM's, public sub's and all the rest to make it very easy to write for.

Please post replies,
And hopefully this compiler will get finished soon,
and does ANYBODY have -->*ANY*<-- help reguarding putting in asm tags?
DENC

Author

101

Jul 9, 2004 at 8:57 AM

Sorry to post more then once in a row, but my above post was huge as it is.

My basic idea is now to get a recursive design, ie.
in this bit of code:

dim zdim xdim yz = 100dofor x = 0 to 100 step 2print xnext xy++loop until y = z

It would first be cut into 3 parts
the first part (the dims) would go to the decleration subroutine, and would provide all the valiables an adress.
it has no other parts to it so it returns back
The second part (the =) would go to the assignment subroutine,
and would create the source of "sto 100, 0" or the like. it also has no other parts to it and so returns back.

current output sto 100, 0

the last third third has a for loop and as such the third is split into 2 parts
the first part is the for loop and goes into the for sub
the second part is the inc and goes into the math sub where it is changed into code.

Then they all return back and finally it is left with all the code.

my function would go something like

public function Assemble(Inp as string)for each line of inp (stored in I)if it is the start of a part then    out += the starting code of that part    do    increment the current line (stored in j)    loop until it reaches the end of the part    out += output from assemble with inp being the text between lines i and j)    out += the ending code of that partend ifnext lineassemble = outend function

My hope is to split it into a tree, and then find the correct output for bits of the tree, then use those to fill in the rest.
each bit would have to 1. get all of its registers when needed and 2. store all needed registers after use.

Has anybody seen a recursive compiler like this?
DENC

5

Jul 9, 2004 at 9:06 AM

There is a tutorial that would probably be perfect for you. I was in the same situation with my VM/compiler. It was just a simple language so I didn't want to go through the trouble of learning lexx and bison.

Check out Jack Crenshaw's "Let's Build a Compiler."
http://compilers.iecc.com/crenshaw/

The article shows you in a very non-technical way, how to build a simple compiler. The only problem is that his example code is in Pascal and his compiler generates code for the 68k, but the concepts are still easy to pick up on.

26

Jul 9, 2004 at 9:11 AM

I highlly recommend the above tutorial series (Lets make a compiler). My scripting language, NerveBreak, wouldn't be reality without this document :-).

138

Jul 9, 2004 at 4:32 PM

Quote:
Original post by Matei
Unless you have a really weird language, there are two steps to compilation: lexical analysis, where you break the code up into "tokens", and syntactical/semantical analysis, where you figure out the meaning of a sequence of tokens, usually using a grammar for your language, and generate code. There are tools for both of these, and they're designed to work well with each other.

Syntactical analysis(parsing) is considered a separate task from semantic analysis. And while the former is often handled by Yacc-like tools, there are no tools for generating semantic analyzers that have gained any significant amount of popularity. Most existing compilers use a hand written semantic analyzer.

You also forgot two steps: Optimization and code generation.

Author

101

Jul 9, 2004 at 6:19 PM

I'm reading that tutorial now... it has no end-of-line (charter 13 and chr 10) markers... the other versions are a bit jumbled... but i'm sure i can manage.

I would still like to know howe good a recursive parser would be...

something like

public function assemble(li as string)inp = split(li,  " ")for x = 0 to ubound(inp)if inp(x) is the start off a piece then    out += startpieceasm(typeofpiece)    y = x        do    ++y    loop until inp(y) is the end of the piece    take the string from inp(x) to inp(y),    if it contains only one piece, then        out += end of piece code    else        out += assemble(string from inp(x) to inp(y)        out += end of piece code    end ifend ifnext xassemble = outend function

Am i going in the right direction?
DENC

234

Jul 9, 2004 at 7:28 PM

If you're serious about building a compiler (as opposed to wanting to spend 10 minutes to build a toy language that you'll never use for anything), I suggest you buy the dragon book ("Compilers: Principles, Techniques and Tools", make sure to use the gamedev refferer links =-)

I've just started reading it, but so far it covers the same stuff as other tutorials/books I've read in a much, much better way. Since it is actually a textbook meant for introductory classes, it is somewhat expensive, but you can get a used copy for $30 or so on any of a number of sites.

You might also want to look over some of the links in my thread Parsing & Obfuscation?

Author

101

Jul 9, 2004 at 9:07 PM

i'm going to try to get that book as soon as i can..... (its not a 10 minute project, its the scripting engine for every program and game that needs one (modded to suit) for a Long time-until i make a better one)

My compiler is still not working as well as it should, as i expected, my main problem is the variables! i'm having a hard time getting it to work!

Author

101

Jul 10, 2004 at 12:34 AM

Ok, i've got variables working...
I'm going to have to clean up the code quite a bit .. :(

Currently the variables are post-processed, so i get the output asm code like
xor a,b
add b,d

...

Heres my plan to implement loops,

When i reach a do, or a for i store its location in a variable, (as well as adding the needed code).

So then once i stumble upon a next, or a loop i place a
jmp [location]
Where location is the location i found the last for/do

For maths, i would surmise that something like
a + b / c
would be
add a, b
div edx, c

edx-Register where the results of maths ops go.

And as such, maybe take the first two, and generate the code for it, and then for each other one, do the operation with edx as the argument?

Please post away,
DENC

Author

101

Jul 10, 2004 at 2:45 AM

Asm tags now work
You can now use things like
DIM x
x = 200
asm {Mcpy eax, ebx;Mset eax 20}

[edit]
How should i work out how to do DO maths, the closest i can come is something like,
expression = "b = a * 2 + c *3"
take the hrs of it (a * 2 + c * 3) and split it where it meats a mathamatical symbol (The *, the +).
First off i would need to set the int registers with the constants,
Mset ax, 2
Mset bx, 3
Then for the first two, i do something like
Mult eax, ax
THen for each other one, i would do something like
add edx, ebx
And
mult edx, bx

And then copy it back to b
Mcpy edx, eax

It there a simpler way?

[Edited by - Nice Coder on July 10, 2004 3:45:24 AM]

Author

101

Jul 10, 2004 at 4:21 AM

I was going to read the tutorials at
http://alphafern.com/BrianCBecker/CompilerTutorial/
But TechTeaM has hacked the site.....
.
.
.
Any other good tutorials on compiler building? (i've googled, yet there seem to be few hits)

234

Jul 10, 2004 at 10:55 AM

General compiler creation is much more difficult than can be covered in a short tutorial. I've looked for a LONG time and I've found hundreds of tutorials that cover maybe 1% of the subject if you sum them all together. My main problem with most of them was they say "ok now that you don't know anything about compiler making at all, just type this code into lex and yacc and you'll have our compiler!" when really I want to know what I'm doing and then do it. That is why I finally gave in and bought 'the dragon book'. There is an 'ok' free book in the topic I linked to earlier. It can get you started while you're waiting to get 'the dragon book'

28

Jul 10, 2004 at 12:46 PM

This page is great. Took that class last semester.

http://w3.msi.vxu.se/multimedia/datalogi/compiler/index.htm

Author

101

Jul 10, 2004 at 9:58 PM

Thanks ekas,

I've got a good version of:
Agamemnon (The VM)
Hexagon (The Asm compiler)
And:
Mirkwood (The asm optimizer)

I've got a question about the VM,
Should i add in a memory stack?
So instead of going on the memory-go-round if you have more things the registers.
Because you could just keep things in a stack.

Is it worth building onto Agamemnon v1.0.1?

Also,
I'm probabily going to compile everything onto one/many active x DLL's, can you use active x DLL's from C++?

Please post away,
DENC

14

Jul 11, 2004 at 2:46 AM

Here is some stuff you might be interested in if you agree to my conditions.

Compiler/VM example

David

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.