Everything Else

salad of math

I've never understood the crazy demand for people collecting books which should teach about how to write a compiler and then they simply invoke lord Bison and mistress Lex during their laboratory activities.

  • Bison: YACC-compatible Parser Generator
  • Lex: Lexical Analyzer Generator
  • Yacc: Yet Another Compiler-Compiler
  • Flex: Fast scanner generator
  • Coco/R Compiler Generator

Sure there's enough software and hardware floating around now that you can mess about and possibly crank out something good with them on linux (which has the above tools), but ... I wonder how many knowledgeable people have really eaten a salad of math.

These yet another compiler - tools are good but … they tend to hide all the magic behind. While the math is rigorous and well defined, in computer science you can have cold drinks of various mixtures of raw or cooked fruits. That's the real fun.

See the following expression

Code: Select all

# eval 1+(2.2*3.0E9+ ( 0xdeadbeaf logicalAnd 0xffffffff ) )


eval has said …. it's a "good expression" ... ohhh my goodness, certainly a bug in my source code, but what a delicious salad, let me offer a shake of different kinds, floating points with hex, logical with arithmetic and evil code

Code: Select all

yards analysis: PASSED
stack analysis: PASSED

rpn_v[]={ 0 3 5 4 8 10 9 6 1 }

[1] 1 token_DecValue, type12
[2.2] 1 token_FloatinPointENGValue, type15
[3.0E9] 1 token_FloatinPointSCIValue, type16
[*] -1 token_Asterisk, type55
[0xdeadbeaf] 1 token_HexValue, type13
[0xffffffff] 1 token_HexValue, type13
[logicalAnd] -1 token_LogicalAnd, type41
[+] -1 token_Plus, type53
[+] -1 token_Plus, type53

#########################
#    good expression    #
#########################

(it's a lie, it's not a good expression, it's simply a bug)

Reading books like " dragon book " and " computer science algorithms for dummies " I was tempted to do my best to produce the worst code, so I have been playing with lexers , parsers , and RPN for weeks. The result is a black mass. The lexer is working good, but It was extremely difficult to make it to understand floating point notation, I was tempted to reinvent the wheel, then I grabbed the idea from SCI and ENG notations. It's used in CASIO pocket calculators . It was also more difficult to play with stack to make the engine to understand operators, their precedence and associativity

Code: Select all

/*
*  precedence   operators       associativity
* ---------------------------------------------
*  1            !               right to left
*  2            * / %           left to right
*  3            + -             left to right
*  4            =               right to left
*/


now it seems it's beginning to work

Code: Select all

# eval 1.1 + 2.2 * 3.0E9

yards analysis: PASSED
stack analysis: PASSED

rpn_v[]={ 0 2 4 3 1 }

[1.1] 1 token_FloatinPointENGValue, type15
[2.2] 1 token_FloatinPointENGValue, type15
[3.0E9] 1 token_FloatinPointSCIValue, type16
[*] -1 token_Asterisk, type55
[+] -1 token_Plus, type53

#########################
#    good expression    #
#########################


Code: Select all

# eval 1+2+

yards analysis: PASSED
stack analysis: FAILED

#########################
#    bad  expression    #
#########################


Code: Select all

# eval 1+2+(2+3

Error: parentheses mismatched/case1

yards analysis: FAILED
stack analysis: PASSED

#########################
#    bad  expression    #
#########################


but …. as you can see in the first eval above, the calculator has also learnt how to tell "lies"

this happens because in computer science you have to care about
  • data size (8bit, 16bit, 32bit, ...)
  • data type (integer, floating point, ...)
  • data sign (unsigned, signed, ...)

and certainly other things.



Today I have implemented a few mechanisms to handle functions. Probably I am too strong data type addicted because I used Pascal and ADA for too long.

Code: Select all

# eval Fa(Fb(1,2,3,4,5),Fc(6,7,8,9),0)

yards analysis: PASSED
stack analysis: PASSED

function_pool has 3 functions
+ function1 [Fa] { typeRet typeRet type12 } 3 args
+ function2 [Fb] { type12 type12 type12 type12 type12 } 5 args
+ function3 [Fc] { type12 type12 type12 type12 } 4 args

rpn_v[]={ 4 6 8 10 12 2 17 19 21 23 15 26 0 }

[1] 1 token_DecValue, type12
[2] 1 token_DecValue, type12
[3] 1 token_DecValue, type12
[4] 1 token_DecValue, type12
[5] 1 token_DecValue, type12
[Fb] -4 token_StrictAlphaNum, type19
[6] 1 token_DecValue, type12
[7] 1 token_DecValue, type12
[8] 1 token_DecValue, type12
[9] 1 token_DecValue, type12
[Fc] -3 token_StrictAlphaNum, type19
[0] 1 token_DecValue, type12
[Fa] -2 token_StrictAlphaNum, type19

#########################
#    good expression    #
#########################


I am considering the RPN method as the hypothetical way to transform a math expression into machine opcodes, crazy idea for AS. I do not like methods like Recursive Descent .




recipes of lexers, parsers, interpreters, compilers
anybody is cooking its own salad of math ?

let me know :D
Some prowling the streets, looking for sweets from their Candyman , I'm Looking for a new IP30/Octane2
My machine got the Xbow damaged, so I swapped for a second hand Rigol-DG1032Z WaveGen/DDS@30Mhz
IP30 purposes : linux (kernel development), Irix Scientific Apps { Ansys, Catia, Pro/E, FiberSIM, AutoDYNþ }
Other Projects : { Cerberus , Woody Box , 68K-board, SWI_DBG }, discontinued Console hacks { GB , PSX1 }
Wanted Equipments : { U1732C LCR meter by Keysight, alternatives are the welcome }
I have been developing a custom soft core for weeks, it's a mashup between M88K ( eight eight key , by Motorola, it's their first RISC) and MIPS R2K in its first release.

The result is a multi cycle reduced instruction set computer . It has no pipeline , it doesn't scale good with its clock, the ratio is something like 1:5 (10MIPS @ 50Mhz of clock). It does millions of instructions for seconds but you can't call it M.I.P.S. (1)

Its ISA is easy enough that you can assembly opcodes by your hands. It has no AS-compiler yet, I have to code it, so I am also working on a super simple compiler. At this stage I do not need to toy with a full C compiler, I just need something able to convert a math expression into assembly code

Considering the RPN as the hypothetical way to transform a math expression into machine opcodes, the paper in attachment says

- do not start from scratch!!! -

extremely daunting, inspiring great fear: I am looking for " mr motivator " :mrgreen:


(1) originally, M.I.P.S. was an acronym for ( M )icroprocessor without ( I )nterlocked ( P )ipeline ( S )tages
while in the context of CPU performance measurement , MIPS stands for 'Million Instructions Per Second' , probably the most useless benchmark ever invented
Some prowling the streets, looking for sweets from their Candyman , I'm Looking for a new IP30/Octane2
My machine got the Xbow damaged, so I swapped for a second hand Rigol-DG1032Z WaveGen/DDS@30Mhz
IP30 purposes : linux (kernel development), Irix Scientific Apps { Ansys, Catia, Pro/E, FiberSIM, AutoDYNþ }
Other Projects : { Cerberus , Woody Box , 68K-board, SWI_DBG }, discontinued Console hacks { GB , PSX1 }
Wanted Equipments : { U1732C LCR meter by Keysight, alternatives are the welcome }
Well, you could write a new backend for gcc, Open64 or Open Watcom, but the disadvantage is
that these compiler all have more than 1 million lines of code. You probably need one year full-time
only to understand how the compiler internally works. As mentionend in the paper that you attached, there is LCC which is a C89 C-Compiler that has much less lines of code. You need to borrow or buy
the LCC book if you want to retarget LCC because only in the book is the necessary information.
In my opinion LCC is less suited as a C-Compiler for a new processor. One reason is that the LCC source code is more complicated than necessary. Another reason is the lack of end user documentation and a third reason is, that if your processor has instructions that don't fit to the
IR of LCC your version of LCC will generate slow code.

I suggest to have a look at the almost forgotten Desmet C compiler 3.1h, which is a ANSI C compiler and is open source (see: http://www.desmet-c.com ). Desmet C was a commercial C-compiler in the MS-DOS era. Advantages are:
- It is a production quality C compiler with full end-user documentation.
- It is small enough that one man can understand the complete C-compiler source within some
weeks.
- It is not a resource hog (MS-DOS only had 640 kByte RAM).

P.S.
Some people use a Raspberry Pi to run an MS-DOS emulator.
:Fuel: 600 MHz, 2 GB RAM, 72 GB 15k RPM HD
:O2: 180 MHz
good idea, I will give an eye :D


About code generation from RPN, this paper provides a few examples. I could use my RPN-parser, just writing a simple (not optimized) code-gen for my Softcore. It will not be a full compiler, but it's enough ok for math expressions. I need them in order to verify the correctness of each math operation inside an infinity loop. I have designed and implemented a debug processor, it can inspect all the registers, step by step, so, I will be able to say if the ALU and other few parts of the CPU are really working or not.

Expected Value isEqualTo? Actual Value, if not ----> YoYo, hAllo mr.bug

Already tested a few part of them with test vectors in a vhdl simulator, but I have tested individually, it's time to have fun with real math expressions :D
Some prowling the streets, looking for sweets from their Candyman , I'm Looking for a new IP30/Octane2
My machine got the Xbow damaged, so I swapped for a second hand Rigol-DG1032Z WaveGen/DDS@30Mhz
IP30 purposes : linux (kernel development), Irix Scientific Apps { Ansys, Catia, Pro/E, FiberSIM, AutoDYNþ }
Other Projects : { Cerberus , Woody Box , 68K-board, SWI_DBG }, discontinued Console hacks { GB , PSX1 }
Wanted Equipments : { U1732C LCR meter by Keysight, alternatives are the welcome }
Just a hint:

Allen Holub's "Compiler design in C" [Prentice Hall 1990] is a classic: it shows you how to design the (functional) backbone of an ANSI C compiler from scratch, from lexical analysis to optimization strategies - and all with complete source code.
If man would have been created out of the rib of a woman - how different would the world be?
Image

it it this one ?

as written here it seems it's out of print
but you can obtain a digital copy with sources


see the comment about sources
Bear in mind, though, that this code hasn't been touched since dinosaurs ruled the earth,
and it's all in plain-old C. It will undoubtedly require some massaging for any contemporary compiler
to accept it and I can't really help you with this process


it sounds like ohhh!

may be I will buy a second hand from Amazon dot com (I like the paper)
thank you for the tips :D


Image

this is the 'Dragon book" I have here
it's good for the theory, not so good for the practice


btw, I hope I can recycle my lexer
Some prowling the streets, looking for sweets from their Candyman , I'm Looking for a new IP30/Octane2
My machine got the Xbow damaged, so I swapped for a second hand Rigol-DG1032Z WaveGen/DDS@30Mhz
IP30 purposes : linux (kernel development), Irix Scientific Apps { Ansys, Catia, Pro/E, FiberSIM, AutoDYNþ }
Other Projects : { Cerberus , Woody Box , 68K-board, SWI_DBG }, discontinued Console hacks { GB , PSX1 }
Wanted Equipments : { U1732C LCR meter by Keysight, alternatives are the welcome }
@Holub: yes, that's it [I've a hard cover copy from '91]. True, the provided C code from 25 years ago might be outdated by today's industrial strength compilers [whatever that means]. But that's not the point: he shows you how to *design* an C compiler from scratch, and not how to implement it most efficiently [actually, you're certainly free to tweak the provided source in any way you like - in fact, the source should still be floating around somewhere on the net, but I can't remember where I got my copy from]. I don't know of any better. So, even it's only a second-hand copy on Amazon, grab it - and enjoy.

@Dragon: right, theoretically fine but practically useless.
If man would have been created out of the rib of a woman - how different would the world be?
Oskar45 you are my personal mr motivator :mrgreen:

ebay UK and ebay US seem to have second hand copies, things like 50 euro shipped
I have already ordered a copy



have you written something evil in the past ? let me know
Some prowling the streets, looking for sweets from their Candyman , I'm Looking for a new IP30/Octane2
My machine got the Xbow damaged, so I swapped for a second hand Rigol-DG1032Z WaveGen/DDS@30Mhz
IP30 purposes : linux (kernel development), Irix Scientific Apps { Ansys, Catia, Pro/E, FiberSIM, AutoDYNþ }
Other Projects : { Cerberus , Woody Box , 68K-board, SWI_DBG }, discontinued Console hacks { GB , PSX1 }
Wanted Equipments : { U1732C LCR meter by Keysight, alternatives are the welcome }
ivelegacy wrote: have you written something evil in the past ? let me know
Yes. E.g., I 'd just hoaxed you in to get yourself a copy of Holub :P

PS: Out of curiosity - are you located in the UK?
If man would have been created out of the rib of a woman - how different would the world be?
Italy, but I am planning to go to the North of England for a while. May be I will change my trip to London. I am waiting for a few answers from a English Institute, and from a restaurant which has promised to pay the English course in exchange of a performance like dishwasher in their kitchen. So I have strongly protested , it's true I am trying to escape the computer science, but I also have a some skills as sommelier, so I want to suggest fresh wine to ladies during my working holidays. Ummm, they have said I am not so good (well, OK, OK, I have a few difficulties speaking on the phone), so ... they offer me their tall pile of dishes to be cleaned.

that's life, and it could have been worse. Imagine what could happen behind a chinese laundry X______X

btw, I will have the time to study that marvelous book :mrgreen:
Some prowling the streets, looking for sweets from their Candyman , I'm Looking for a new IP30/Octane2
My machine got the Xbow damaged, so I swapped for a second hand Rigol-DG1032Z WaveGen/DDS@30Mhz
IP30 purposes : linux (kernel development), Irix Scientific Apps { Ansys, Catia, Pro/E, FiberSIM, AutoDYNþ }
Other Projects : { Cerberus , Woody Box , 68K-board, SWI_DBG }, discontinued Console hacks { GB , PSX1 }
Wanted Equipments : { U1732C LCR meter by Keysight, alternatives are the welcome }
If you are coming to England Ivelagacy, forget dish washing, with your English you could get a job in any call center.

Heck, I'd even employ you, just so we looked like a normal company.
-----------------------------------------------------------------------
Hey Ho! Pip & Dandy!
:Octane2: :Octane2: :O2: :Indy: loft => :Indigo: :540: :Octane: :Octane: :Indy:
I had a phone call with Nicolle of Robosavvy (UK). It was interesting ... she called me on the cell phone because I did a really hot jam on ebay, we were out of 90 euro on an auction and they lost my parcel, but then she distracted me with her sexy voice so I was not able to claim hard.

I was out of money, parcel lost, and ... the phone call ended with a cup of coffee offered to her. There is certainly something wrong with my English.

Ohhh, and let me say I am not able to understand more than the 50% of Sex & the City (Gaga has the full DVD set), even if I am quite able to understand Samantha Jones (Kim Cattrall) . Her obscenity is not obscenity, it's fun.

Everyday English movies planned for a long time, I signed up for my free Blockbuster On Demand account. They have thousand and thousand of movies and English DVDs with Italian subtitles. Yesterday I watched " Only Lovers Left Alive (2013) ". it's a vampire movie, but it's not true blood, it's a complex drama, so complex I was tempted to bite my neighbors. Or the tulip plants (made of plastic) in the living room.





I have added a new feature: codegen
It tries to generate opcodes from an RPN expression

here it is a simple example

Code: Select all

# codegen 1+2+3

yards analysis: PASSED
stack analysis: PASSED

function_pool_show_all ... 0 functions

rpn_v[]={ 0 2 1 4 3 }

[1]  1 K3 cookie     token_DecValue, type12
[2]  1 K3 cookie     token_DecValue, type12
[+] -1 K5 operator   token_Plus, type53
[3]  1 K3 cookie     token_DecValue, type12
[+] -1 K5 operator   token_Plus, type53

#########################
#    good expression    #
#########################

##############[ code gen ]##############
load r1,1
load r2,2
uadd r1,r1,r2
load r2,3
uadd r1,r1,r2



Code: Select all

# codegen 1+Fa(2)+Fb(3+4)

yards analysis: PASSED
stack analysis: PASSED
function_pool_show_all ... 2 functions
+ function1 [Fa] { type12 } 1 args ticket_rpn=2
+ function2 [Fb] { type12 } 1 args ticket_rpn=7

rpn_v[]={ 0 4 2 1 9 11 10 7 6 }

[1]  1 K3 cookie     token_DecValue, type12
[2]  1 K4 f_cookie   token_DecValue, type12
[Fa]  0 K2 function   token_StrictAlphaNum, type19
[+] -1 K5 operator   token_Plus, type53
[3]  1 K4 f_cookie   token_DecValue, type12
[4]  1 K4 f_cookie   token_DecValue, type12
[+] -1 K6 f_operator token_Plus, type53
[Fb]  0 K2 function   token_StrictAlphaNum, type19
[+] -1 K5 operator   token_Plus, type53

#########################
#    good expression    #
#########################

##############[ code gen ]##############
load r1,1
load_and_push r2,2
uadd SP,SP,2 /* arg_n, return address */
call Fa
load r2,(SP) /* load function result */
uadd r1,r1,r2
load_and_push r2,3
load_and_push r3,4
uadd r2,r2,r3
usub SP,SP,2
push r2
uadd SP,SP,2 /* arg_n, return address */
call Fb
load r2,(SP) /* load function result */
uadd r1,r1,r2
Some prowling the streets, looking for sweets from their Candyman , I'm Looking for a new IP30/Octane2
My machine got the Xbow damaged, so I swapped for a second hand Rigol-DG1032Z WaveGen/DDS@30Mhz
IP30 purposes : linux (kernel development), Irix Scientific Apps { Ansys, Catia, Pro/E, FiberSIM, AutoDYNþ }
Other Projects : { Cerberus , Woody Box , 68K-board, SWI_DBG }, discontinued Console hacks { GB , PSX1 }
Wanted Equipments : { U1732C LCR meter by Keysight, alternatives are the welcome }