The Theory Behind A SNES C Compiler

[undisbeliever]

Since there is a lack of WORKING 65816 (non-asm) Compilers (LordTech's SNESC doesn't count because it screws up if there is over 32KB of code + data (if so then it overwrite the SNES Header.)) I have decided to create my own SNES C Compiler (hensforth known as SCC).

I have just finished a 458 page 'crash-course' of the basic theory of compiler prac in pascal (which I had no knowledge of until now). IT IS REALLY EASY TO WRITE A WORKING COMPILER.

Anyway, I've discovered that writing a compiler is much easier if you break it down into 70 different parts (as defined in my BNF statements) and instead of writing a whole compiler it is even easier if you write a program to convert one language (in my case C) into assembly (to be processed by WLA - which takes care of all the memory addressing and SNES Headers (that really confuse me)).

SCC will rely entirely on static variables. This means that there can be over 256 bytes of variables, but functions cannot be called within itself (or any other linked function). (See the BNF for more reasons why I'm taking the static approach to SCC).

So far I've written a mathematical parser, that will convert almost any mathematical assignment to 65186 asm (ie. run it and type a=a+1 and see what comes out). I know that the code is not tight, but I will be able to fix most of it up with a peephole optimizer.

I have posted my current work (theory and prac) below. I would like my BNF statements checked by someone else (even though they're 5 pages long).

Here is a short description of a BNF statement, for those who don't understand what they are. Here is a short description.


This example BNF shows the how simple expressions are parsed:

Code: Select all

      <expression> ~~ <term> (<addop> <term>)*
            <term> ~~ <factor> (<mulop> <factor>)*

          <factor> ~~ <number> | '(' <expression> ')' | <ident>
     
           <addop> ~~ '+' | '-'
           <mulop> ~~ '*' | '/'

An expression is made up of one or more terms separated by '+' or '-' signs.
A term is made up of one or more factors separated by '*'or '/' signs.
A factor is either a number or another expression in brackets or an identifier(variable, function or pointer).

Here is a diagram if your still confused:

Code: Select all

                ----->   expressions
              /        /      |      \
             /     '+'        v        '-'
            |               terms
            |          /      |      \
            |      '*'        v        '\'
            |              factors
            |          /      |       \
            |       |_        v         _|
       (expression)        numbers         identity

So looking at the diagram brackets take place after factors(*,\) and they take place after terms(+,-).

In the expression a + b * (b + c), the parser will load a and add it to b multiplied by the sum of b + c. Because addition is less important then multiplication (ect).

Can any suggestions or comments be made that affect the initial design and planning (modifications to BNF statements, parsing to assembly conversions, necessary tables (like variable/function tables) including what they contain and any optimization ideas)

Thanks:

MarcTheMER
(The un-ordained, un-sacrid scribe and un-disbeliever of the Church Of The SubGenius)[/code]

[undisbeliever]

This is the BNF of my SNES C Compiler

Code: Select all

SCC - The SNES C Compiler
  Copyright (C) 2005, Marc Rowe (marcthemer@gmail.com)

  This program documentation with guidance from
         'LET'S BUILD A COMPILER!'
                    By Jack W. Crenshaw, Ph.D.
                            (http://compilers.iecc.com/crenshaw/)

     FILE: bnf
      USE: The entire list of BNF statements (syntax) for SCC
  CREATED: Tuesday September 13, 2005
INFLUENCE: Mike Oldfield - The Complete


NOTES (before starting):
 1) Everything in  ''  is case sensitive and everything in
    "" is case insensitive, but for speed purposes it must
    be in upper case.

 2) Some weird things can happen in this language that may
    not normally happen in C.
    These include:
      a++ = b + c;            a is the sum of b and c and
               then increased by one

      while(0) a:             This loop  would  do nothing
               but slow down the program.  If there
               was  "goto a;"  in  the program,  it
               would jump into the loop and out the
               other side.

      a;                      This just loads  the value a
               into the  accumulator.  It was setup
               this  way   because   functions  are
               treated like  variables.   Therefore
               if a function  is  called without an
               assignment  then  a  variable can be
               accessed without  an assignment too.

      (char)*(0x2100) = 15;   All numberetic pointers MUST
               have  a  type  statement  BEFORE the
               pointer  itself.   Otherwise it will
               store the value as a int.

 3) I'm not entirely  sure  if  I'm  going to have all the
    variables  in  the  program  static  or  not.   Having
    non-static variables  will  only  leave  256  bytes of
    variables in one  function.   Although  having  static
    variables  means  that  a  function  cannot  be called
    within itself (or any other linked function).

    Personally I'm opting  for  the  static approach.  (It
    will make the parsing and the 65816 assembly easier to
    code and  (let me emphasize again!)  you can have over
    256 bytes of code in each function). I've also noticed
    that there are  many  SNES  games that take the static
    approach in their coding.
    
 4) I  have  decided  to  leave  out  the  --a;  and  ++a;
    expressions from the compiler,  I don't know what they
    do  (the  "Teach  yourself  C"  tutorials  are  a  bit
    ambiguous about that)  so the only king of increase by
    one I'm allowing is a++; and a--;


                     THE ORDER OF OPERATIONS
                    -------------------------
      Level    Syntax Element     Operator

        0       unary operators    ++, --
        1       factor             literal, variable, function
        2       signed factor      unary minus
        3       term               *, /
        4       expression         +, -
        5       relation           <, <=, ==, !=
        6       not-factor         !
        7       bool-term          ^
        8       bool-expr          |, ^
        9       assignment         =, +=, -=, *=, = ,/=, %=
                                   &=, ^=, |=, <<=, >=,

 STARTING PROGRAM
------------------
         <program> ~~ (<top level decl>)*

  <top level decl> ~~ ['#' <preprocessor>]* | <global decl>




 PREPROCESSOR
--------------

    <preprocessor> ~~ <define> | <include> | <romname> |
                      <version> | <romsize> | <sramsize> |
                      <country>
                      

          <define> ~~ "DEFINE" <name> (<single def>|<multi def>)

      <single def> ~~ <replacement>

       <multi def> ~~ '('[<d-para>[','<d-para>]*]')'<replacement>

         <include> ~~ "INCLUDE" <filename>

        <filename> ~~ ('<' <file> '>') | ('"' <file> '"')

         <romname> ~~ "NAME" <header-name>

         <version> ~~ "VERSION" <header-version-number>

         <romsize> ~~ "SIZE" <header-romsize>

        <sramsize> ~~ "SRAM" <header-sram-size>

         <country> ~~ "COUNTRY" <header-country-name>



 DECLARATIONS
--------------

     <global decl> ~~ [<style>] [<class>]* <type> <decl>
      
            <decl> ~~ <function proto>          |
                      <function>                |
                      <data decl>

  <function proto> ~~ <function decl> ';'

        <function> ~~ <function decl> <code>


   <function decl> ~~ <name>'(' [<f-argu> [',' <fargu>]*] ')''

          <f-argu> ~~ <type> [*]<name>['['<size>']']


       <data decl> ~~ ['*']<name> [ '[' <size> ']' ]
                          ['=' <bool-expr>]
                              [',' ['*']<name> [ '[' <size> ']' ]
                                  ['=' <bool-expr>]]* ';'


           <style> ~~ "CONST" | "VOLATILE"
           <class> ~~ "AUTO" | "UNSIGNED" | "SIGNED"

            <type> ~~ "VOID" | "CHAR" | "INT"




 CODE
------

            <code> ~~ <single> | <block>

          <single> ~~ <control>                 |
                      <label>                   |
                      <var decl>                |
                      <assignment> ';'

           <block> ~~ '{' (<code>)* '}'

         <var dec> ~~ [<style>] [<class>] <type>
                         ['*']<name> [ '[' <size> ']' ]
                           ['=' <bool-expr>]
                              [',' ['*']<name> [ '[' <size> ']' ]
                                 ['=' <bool-expr>]]* ';'

           <label> ~~ <name> ':'




 CONTROL STRUCTURES
--------------------

         <control> ~~ <asm> | <break> | <case> | <continue>
                          <default> | <do> | <for>  |<goto> |
                          <if> | <switch> |  <while>

             <asm> ~~ "ASM" '{' (<asm-code> ';')* '}'

           <break> ~~ "BREAK" ';'

            <case> ~~ "CASE" <integer> ':'

       <continue> ~~ "CONTINUE" ';'

         <default> ~~ "DEFAULT" ':'

              <do> ~~ "DO" <code> "WHILE" '('<bool-exp>')'

             <for> ~~ "FOR" '('<assignment> ';' <bool-expr>
                          ';' <assignment>')' <code>

            <goto> ~~ "GOTO" <label> ';'
  
              <if> ~~ "IF" '('<bool-epxr>')' <code>
                          ["ELSE" <command>]

          <switch> ~~ "SWITCH" '('<bool-expr>')' <block>

          <return> ~~ "RETURN" <bool-expr> ';'

           <while> ~~ "WHILE" '('<bool-expr>')' <code>




 ASSIGNMENT STATEMENT
----------------------

      <assignment> ~~ <ident> [<var-assignment>]


           <ident> ~~ [<i-type>] <var> | <function>
             <var> ~~ <addr> ['['<bool-expr>']'] [<inc/dec-type>]
        <function> ~~ <name>([<expression> [',' <expression>]*])

          <i-type> ~~ ( '(' "CHAR" ')' ) | ( '(' "INT" ')' )
            <addr> ~~ <byte> | <int> | <pointer>

         <pointer> ~~ (<p-normal> | <p-sum>))
        <p-normal> ~~ <byte> | <int> | ( '*('<numberetic>')' )
           <p-sum> ~~ '*(' (<p-type> <addop> <bool-expr> ')'
          <p-type> ~~ <byte> | <int> | <numberetic>


   <var-assignment> ~~ <assignment type> <bool-expr>

 <assignment type> ~~ '=' | '+=' | '-=' | '*=' | '/='|
                           '%=' | '&=' | '^=' | '|='



       <bool-expr> ~~ <bool-term> [<orop> <bool-term>]*
       <bool-term> ~~ <not-factor> [<andop> <not-factor>]*
      <not-factor> ~~ [<notop>] <relation>
        <relation> ~~ <expression> [ <relop> <expression>]
      
            <orop> ~~ '|' | '^'
           <andop> ~~ '&'
           <notop> ~~ '!'
           <relop> ~~ '<' | '<=' | '==' | '!=' | '>' | '>='



      <expression> ~~ <first term> (<addop> <term>)*
      <first term> ~~ <first factor> <rest>
            <term> ~~ <factor> <rest>
            <rest> ~~ (<mulop> <factor>)*
    <first factor> ~~ [<addop>] <factor>
          <factor> ~~ <number> | '(' <bool-expr> ')' | <ident>
     
           <addop> ~~ '+' | '-'
           <mulop> ~~ '*' | '/' | '%'

[undisbeliever]

This is some information about how mathematical operators are handled

Code: Select all

SCC - The SNES C Compiler
  Copyright (C) 2005, Marc Rowe (marcthemer@gmail.com)

  This program documentation with guidance from
         'LET'S BUILD A COMPILER!'
                    By Jack W. Crenshaw, Ph.D.
                            (http://compilers.iecc.com/crenshaw/)

     FILE: mathematics
      USE: An introduction to how SCC
             calculates mathematical expressions.
  CREATED: Tuesday September 13, 2005
INFLUENCE: Led Zeppelin - Remasters
           Status Quo - Whatever You Want



 UNARY OPERATORS
------------------
	I  haven't  put  much   thought   into  this  expression.
	According to the BNF an  unary operator is activated ONLY
	if a ++ or -- directly follows a variable name.
	
	Therefore when the parser tries to load a factor, it must
	first  check  if  there  is a  ++  or  --  directly after
	the variable name.

	If there is the parse must increase/decrease the value by 
	one and then load the factor:
	
			[SEP #$20] ; only if it's a 8 bit value
			INC <address used in loading the factor>
			[REP #$30] ; only if it's a 8 bit value



 LOADING A FACTOR
------------------
	In the BNF there are two major types of factors;  numbers
	and identities.

	Numbers are loaded simply with the LDA #n op-code:
			LDA #number.

	An identity is not  as  simple  to  load  as I originally
	thought, there are  two  different  types  of identities;
	functions and variables.
	To  call  and  return  the   value  of  a  function,  the
	parameters  (which  will  first  be  calculated  with the
	bool-expr  function)  must  first  be  stored  in  memory
	(Either in the stack if  I  take the non-static approach,
	or in the WRAM if I don't (which again would be faster)).

	For example, with the static approach:
			<CALC: A + b>
			<STORE: foo::num>
			<CALC: 1>
			<STORE: foo::value>
			JSR foo

	Will  call  the  function  "square(char num,  int value)"
	after storing  the  value  (a + b)  in  the  variable num
	and storing 1 in the variable value.

	The approach used  in  storing  the  parameters into WRAM
	will be exactly  the  same  as  the  approach used in the
	function var-assignment.

	Anyway, variables fall  under  two categories; normal and
	pointers.
	
	To Load A Normal Variables:
			LDA var


	Again Pointers fall under two distinct categories; normal
	and numberetic pointers.  (NOTE: The size of a numberetic
	pointer  is  determined  by the  size  block  before  the
	pointer itself.

	To Load A Normal Pointer: (=p-type)
			LDA [p-type]

	To Load A Normal Calculated Pointer: (=*(p-type + p))
			<CALC: p>
			TAY
			[ASL]     ; only if the pointer is an int
			LDA [p-type], Y

	To Load A Numberetic Pointer: (=*(0x2100))
			LDA 8448

	To Load A Calculated Numberetic Pointer: (=*(0x2100 + p))
			<CALC: p>
			[ASL]     ; only if the pointer is an int
			TAX
			LDA 8448, X

	addr[value]s are parsed EXACTLY like calculated pointers.

	FINALLY when the variable is loaded into the accumulator,
	it must be properly sized.  The ident function will check
	the size of the variable by  either a lookup table or/and
	the i-type flag (for want of a better name).

	If the size is a char then:
			<LOAD: whatever>
			AND #$00FF

	Otherwise, the value is un-modified. I chose this because
	ALL calculations  are  done  in  16  bit  mode (Just like
	Lordtech's C compiler did all his calculations in 32 bit)
	(Yes, I am taking the COWARD'S WAY OUT - (whimpering) but
	Lordtech did it first)



 UNARY MINUS
-------------
	If the first term  (and  thus  the  first  factor)  in an
	expression has  a  '-'  behind  it  then  the parser will
	subtract or add 0 to the next factor to insure that it is
	becomes a negative value.

		LDA #$0000
		PHA
		<subtract next term>

	I know that if the parse  came across a  "-a*b"  it would
	actually translate it  to  "-(a*b)",  which luckally this
	will still return the same value.



 PROCESSING DIVISION/MULTIPLICATION
------------------------------------
	I've found this section of the initial parser a tough nut
	to crack.  I've given up on just writing code and decided
	to use the co-processor  to  calculate  the values to the
	multiplication, division and modulus expressions.

	When the parser comes  across a multiplication / division
	operator.  The  parser  will  store  the accumulator  (as
	derived from the last digit / expression)  into the stack
	(since the 65816 has only one calculatable register)  and
	then load and process the next factor.

	Then the parser will  activate the COP.  Depending on the 
	signature byte of the COP instruction determines the type 
	of operation done.

		Signature        Operation
		   $01              Multiply acc by the stack
		   $02              Divide the stack by acc 
		   $03              Modulus the stack by acc

	The resultant of this operator will be left on the stack.
	(if we didn't there would  still  be leftover data on the
	stack  (and the waste of  CPU  time removing some useless
	from the stack).

 PROCESSING EXPRESSIONS
------------------------
	As like processing multiplication / division,  we need to
	push the previous value onto the stack.   The parser will
	then load the next term (multiplied  expression) and then
	add or subtract the Stack with the accumulator.
	
	ADDITION:
		PHA                ; load prev value into stack
		<load next term>
		CLC
  ADC $01,S          ; add current by prev
  PLY                ; empty the stack
  
 SUBTRACTION:
  PHA                ; load prev value into stack
  <load next term>
  STA $00
  PLA                ; swap prev and current values
  SEC
  SBC $00            ; subtract prev by current

 The reason I used the '$00' address in the subtraction is
 because I need to swap  the  current  and previous vales.
 Otherwise, it would return "current - prev" (the negative
 of our desired answer).

Annoyingly while reformatting my computer, I accidentally corrupted my backups, so I must redo the theory of boolean expressions and control statements. Luckally I have hard copies

Anyhow, I had managed to get a program that could parse and translate mathematical and boolean instructions, but that too is lost to my backup corruption . I should only take me an hour to retype all that code. oh well

[whicker]

I wish I had the time to work on learning how a compiler works by writing one

Anyhow, your project looks promising.

One suggestion is that what really makes or breaks a compiler is how well it integrates with the intended hardware. It would be neat if after you're done writing the core functionality, that you could put in some optimizations to use the internal multiplier and divider, the ability to be able to define variables at a specific memory address, strong interrupt and HDMA control, standard library support (except printf, that's a nightmare plus it's almost completely worthless on a videogame machine), and a strong memory copy library that uses DMA.

Compression tools and decompression libraries would be a plus, but kind of unnecessary due to how much memory copiers and flash carts have.

For now, have fun and learn a lot.

[Nightcrawler]

I didn't get the chance to look at things in depth, but here are two things.

1.) Your implementation of add and subtract assumes you'll only ever add or subtract a max of 16-bit numbers.

It would also be a nice feature to be able to work with larger numbers. Often times 24 or 32-bit manipulations are done for exp points etc.. These can done simply by using the carry from the previous operation. You're implentiation always clears or sets the carry for addition and subtration making that impossible, unless I missed something?

In actual SNES programming, you may want 8-bit OR 16-bit operations as well. Do you support 8 and 16-bit mode?


2.) If you're going to use the internal multiplication or division SNES hardware in the future, please note you'll need to wait for 3 NOP's(I THINK.. can't remember off the top of my head) before you can check the register for the correct results.

[undisbeliever]

Well, I might think about that.


I was thinking that all calculation was done in 16 bit acc mode (like Lordtech's C Compiler) and that 32 bit calculations can be done by use of functions (also like LordTech's C Compiler).

The other way this could be done is look at the ENTIRE expression in advance (which, would make the compiler compltely difficult to work with) and then decide which type of calculation (8 bit, 16 bit, 32 bit) to be done for the expression.

OR as as a short-cut, if we're dealing with an assignment (a=???) we just process the following expression with the same size as the variable to be assigned.


Anyway, I was going to write the multiplication/division calculations using the internal SNES calculaton registers. And the libaries can also be written later.

[Bobbias2.0]

You would be my god if you actually made a nice C compiler for the SNES... I've been hoping that I could find one (that hopefully supports assembly blocks, as well) considering assembly is gonna take me forever to learn. And I've worked in C++ before (mostly DOS stuff, very little actual windows C++, lol)

[mozz]

The other way this could be done is look at the ENTIRE expression in advance (which, would make the compiler compltely difficult to work with) and then decide which type of calculation (8 bit, 16 bit, 32 bit) to be done for the expression.

What compilers typically do is parse the source code into a tree representation. Expressions in particular are easily represented as trees. Then recursively assign types to the nodes of the tree using whatever rules the language has for types. In C for example, integer promotion rules dictate that if you add a "short" expression to an "int" expression, the side that was a "short" would get promoted to an "int" and then the "int + int" operation would be used. A good way to represent this is to explicitly insert nodes into the tree anywhere you decide that a promotion or type conversion should apply. Your code generator can then emit the proper code for these promotion nodes just like it would for any other node.

To learn more about building real compilers, I would recommend this book:
http://www.amazon.com/gp/product/080532 ... 5&v=glance

There's also a bunch of information here (don't know how useful it is):
http://www.softpanorama.org/Algorithms/compilers.shtml

You can probably find lots of other useful info with Google.

[Nightcrawler]

This C compiler is going to be subject to some of the same limitations Lordtech's was. You're not going to be able to DO anything with it without the SNES hardware knowledge unless he writes a bunch of prewritten libraries for it.

C simplifies the coding, but the same knowledge is still required unless the is a wealth of prewritten routines.

[Bobbias2.0]

well, thtat would be helpful for people like me. I am beginning to learn a lot, quickly, about the SNES hardware and such, but I'm struggling mustly with the Assembly, so having C capabilities would help me. not just that, I could teach myself the assembly representations for some code that I could write in C but not in assembly...

[Nightcrawler]

Could be. I think though, by the time you really understand and learn what the hardware registers are and do, assembly won't be much of a problem for you anymore.

Guess only time will tell, right?

[grinvader]

Could be. I think though, by the time you really understand and learn what the hardware registers are and do, assembly won't be much of a problem for you anymore.

Guess only time will tell, right? ;)

My time told me: 104% TOTAL TRUTH

[Bobbias2.0]

lol, well, the faster I can teach myself to look at assembly and not go looking for mnemonics.txt, the easier things will be, and the less I'll need a C compiler for the snes.

[undisbeliever]

Well this compiler was written with the SNES harware registers in mind.

Hence my two new features:

resource (as defined in SNESC)
and a $2100 statement. (which would expand the c code

Code: Select all

$2100 = 15

into this

Code: Select all

LDA #15;
SEP #$20;
STA $002100;
REP #$20;

)

[Nightcrawler]

Also, keep in mind, some of the hardware registers can/SHOULD be written 8-bits or 16-bits at a time depending on how the system is set up. The VRAM registers are a good example.

[undisbeliever]

Done and done!

I have created 3 types of hex addresses.

$2100 - Byte address
$$2100 - Word address
$w2100 - Double byte address

And when I get the trees working properly, It should be even more grand.

[Nightcrawler]

Nice work! I commend your efforts to take the time to make this C compiler more useful than anything that has come before it.