Writing a simple assembler
Alex
(since asm conf. is dead, i post it here, maybe someone can help)
In my current project , i have to create i simple assembler for an 8-bit
processor.
Since i am a novice at language writing, I would like to ask if somebody
can direct to some articles
on this topic, or where to start looking at.
Thank for help.
--
Alex
Jim Granville
Alfred Arnold's AS is here
http://john.ccac.rwth-aachen.de:8000/as/download.html
This covers many microcontrollers.
and more complex, is Randall Hyde's HLA
http://webster.cs.ucr.edu/AsmTools/HLA/index.html
latticeSemi's downloads for the small Mico8 SoftCPU include
an assembler source, but it is simpler than AS, which now
supports Mico8.
-jg
samIam
Language Translators: Assemblers, Compilers, and Interpreters
by John Zarrella
ISBN: 0935230068
used on amazon is around ~$4 and change.
I bought it to give me a heads up for a project I was working on at
home ... I needed to write an assembler for a 8bit micro as well and
needed to brush up on the different modules comprising such a task.
Its rich in theory and practical!!!
(versus the "dragon book" which is all theory and no practical
examples )
toby
My favoured tools are lex/yacc (flex/bison). Source code to my
assembler for simple architectures is here (non-macro though):
http://www.telegraphics.com.au/svn/dpa/trunk/
Notes here http://www.telegraphics.com.au/sw/info/dpa.html
>
>
> --
> Alex
Isaac Bosompem
VHDL.
I have a general idea of how I am going to attack this (I dont have any
theoretical books).
I will outline my plans to you a bit later. Hopefully, people will
offer some critique and we can learn together :).
Isaac Bosompem
OK here is my general idea:
What I have decided to do was to split the assembler into classes. I
figured this would be a good time to do something useful and advance my
C++ knowledge and methodologies.
1. Preprocessor
Basically takes equates and macros and replaces them with their
equivalent. This alone will require a pass across the entire file.
1. File Tokenizer
Once the preprocessor has finished, the assembly will start to take
place. This respective class will take the file and divide it into
tokens (with selected delimiters). Its sole purpose is to maintain the
position in the file, memory associated with it etc.
2. Global Hash Table
This portion was added to make my life easier. I decided that instead
of parsing the data through text, which will make my job a living hell,
I decided to use a global hash table to keep track of strings. This way
I can just do a table lookup of the hashed token, look up type flags
and determine what to do from there (assemble an opcode, report error,
incompatible types, etc.)
3. Opcode hash list
This portion really is the portion of the program which contains hash
values for each of the opcode words (minus size suffixes), of course
everything will be put in uppercase before its hash value is taken.
4. Opcode assembler.
Takes an opcode from the hash list, parses parameters and assembles the
respective opcode, based on the size of the variable (if operated), the
register operands, etc.
This is my general idea, of course I havent started to code it yet as I
am still planning it.
I do need an efficient hashing function, with a low probability of
collisions (ideally). I will need to code to handle collisions.
Anyways I am open to new ideas hopefully you have some of your own to
add.
-Isaac
--------------------------------------------------------------------------------------------------------------
I am an EE student looking for summer employment in Toronto, Canada
area
If you have any openings please contact me at isaacb[AT]rogers[DOT]com.
David R Brooks
language in BNF, then augment the BNF by appending to each rule the name
of a function to be called when that rule is matched (ie fires). Let's
call this augmented syntax BNF+.
Once you have the core BNF engine running, it can build the assembler
for you (usually called a compiler-compiler, but this is assembler).
You write the syntax of BNF itself, in BNF+. Feed this as input to the
engine, and get out a set of control tables. Drive the engine with
these, and it will read anything in BNF+ (eg your assembly language).
Besides the BNF engine, you need a symbol table (indexing method of your
choice), and the back-end code generation functions.
You can do this without a tokeniser, by defining a token on BNF, &
letting the main engine do the work. This is simple, but slow.
The following examples are not fully functional, but should give the
flavour of the thing:
Fragment of a BNF+ syntax file:
* rule elements semantic function
file = {oneline} [eof] .
oneline = line ending . NextLine
*-----------------------------------------------
* Basic elements
eof = #26 .
eol = {ws} [comment] #10 .
ws = wsc {wsc} .
wsc = " " |
#9 .
digit = ("0".."9") .
uphex = ("A".."F") .
lowhex = ("a".."f") .
upper = ("A".."Z") .
lower = ("a".."z") .
hexchar = digit | HexValueDigit
uphex | HexValueUpper
lowhex . HexValueLower
letter = upper |
lower .
symch = letter |
digit |
"_" .
Top-level function of the BNF+ engine:
// Syntax "engine": the core of the system
#define SP current.syntab[current.synptr]
#define GETCHR {currch = getchr(¤t);}
#define NEXTCH {lastch = currch; current.fileptr++; \
GETCHR; if(currch=='\n') current.linum++;}
#define GOTOCH(x) {current.fileptr = x; GETCHR}
#define EXIT {if(init.filename) fclose(init.input); \
return(current);}
state engine(state init)
{
state current; // Local copy (we may want to back-up)
state temp; // Workspace for recursive calls
WORD rule;
char error[100];
char currch;
init.depth++;
if(init.filename) // Open new file...
{
if(!(init.input = fopen(init.filename, "rb")))
{
sprintf(error,"Fatal: cannot open file %s\n", init.filename);
fatal(error);
}
init.fileptr = 0; // Start at BOF
init.linum = 1;
getchr(NULL); // Force a re-read
}
current = init;
current.filename = NULL; // File dealt with
GETCHR;
do
{
rule = SP;
currstate = ¤t; // Expose it for logging
#if LOGSTATE
{
static int ctr = 0;
char zz[8];
if((currch >= 0x20) && (currch <= 0x7e))
sprintf(zz,"<%c> ",currch);
else
sprintf(zz,"0x%02x", currch);
fprintf(logfile,"%5d %3d%6d [%4d] %s [%4d] %c\n",ctr++,
init.depth, rule,current.synptr, zz, current.fileptr, (current.match) ?
'T' : 'F');
fflush(logfile);
}
#endif
if(rule < 0) // SUB RULE
{
if(current.match)
{
temp = current;
temp.synptr = -rule; // Rule address
temp = engine(temp);
current.match &= temp.match;
if(temp.match)
GOTOCH(temp.fileptr);
}
}
else
{
if(rule < 200) // LITERAL CHAR
{
current.match &= ((char)rule == currch);
if(current.match)
NEXTCH
}
else
switch(rule)
{
case 202: // '|' ALTERNATE RULE
if(!current.match)
{ // Last test failed:
back-up & try next
current.match = init.match;
current.fileptr = init.fileptr;
current.synptr++; // To start of new rule
break;
}
// Else, fall through (rule succeeded)
case 201: // '.' END OF RULE
current.synptr++; // Point at semantic
if(current.match)
{
#if LOGSEMANTIC
char zz[8];
if((lastch >= 0x20) && (lastch <= 0x7e))
sprintf(zz,"<%c> ",lastch);
else
sprintf(zz,"0x%02x", lastch);
if(SP)
fprintf(logfile," Semantic[%4d] %s\n",SP,zz);
fflush(logfile);
#endif
semantics[SP](); // Semantic function (zero
is valid)
}
EXIT;
case 203: // '{'
case 204: // '['
temp = current;
temp.synptr++;
temp = engine(temp);
if(temp.match) // If it worked, swallow
the chars.
GOTOCH(temp.fileptr);
if(current.syntab[temp.synptr] != 2+SP)
{
sprintf(error,"Fatal: bracket imbalance at
%d:%d\n", temp.synptr, current.synptr);
fatal(error);
}
if(temp.match && (current.syntab[temp.synptr] == 205))
continue; // {...} repeats indefinitely
else
current.synptr = temp.synptr;
break;
case 205: // '}'
case 206: // ']'
EXIT;
case 207: // RANGE
current.match &= ((currch >=
(char)current.syntab[current.synptr+1]) && (currch <=
(char)current.syntab[current.synptr+2]));
current.synptr += 2;
if(current.match)
NEXTCH;
break;
case 208: // '@' - include file
temp = current;
temp.filename = Identifier;
temp.fileptr = 0; // Start at BOF of inner file
current.synptr++; // Point to nested rule
temp.synptr = -SP;
temp = engine(temp); // Run the nested file
current.match &= temp.match;
default:
{
sprintf(error,"Fatal: unrecognised syntax code at
[%d] = %d\n", current.synptr, rule);
fatal(error);
}
}
}
if(!current.match) // If this rule failed, back-up
GOTOCH(init.fileptr)
do
{
current.synptr++; // Next syntax item (skip if tests
have failed)
} while(!(current.match || (SP > 200)));
} while(1); // End the DO loop
}
Artenz
> (since asm conf. is dead, i post it here, maybe someone can help)
>
> In my current project , i have to create i simple assembler for an 8-bit
> processor.
If you know scripting languages like Perl or python, you can make
something fairly quickly. I've made a simple Perl assembler script for
my small FPGA-based CPU in about 200 lines of code.
For simple projects, a line by line translation works fine. Match each
line against a set of patterns, translate mnemonic to opcode through a
hash, and call subroutine to fill in operand bits. Use two passes. In
the first pass, you build the symbol table (a hash), and in the second
pass, you can generate the code. Or store all code in array, and dump
it after second pass.
If you need more advanced features like macros, things become a bit
more complicated, and then a properly written assembler, using lex/yacc
maybe a better choice.
CBFalconer
>
... snip ...
>
> I do need an efficient hashing function, with a low probability of
> collisions (ideally). I will need to code to handle collisions.
>
> Anyways I am open to new ideas hopefully you have some of your own
> to add.
You are welcome to use hashlib, which is under GPL licensing, and
was designed to fill just this sort of need. It is written in pure
ISO C.
You could open one table and stuff it with the opcodes. Another
could hold the macros, and yet another the symbols. The tables
will all use the same re-entrant hash code, yet can have widely
different content.
<http://cbfalconer.home.att.net/download/hashlib.zip>
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
Alex
Well, that what i thought initially. I know Tcl and used it for parsing
hdl code, so this seems to be an easy and fast solution for the given
problem.
I just want to clarify few things - do I really need two passes (omit
preprocessor for)
in case I don't have conditional branches and jumps.
At the same time I was thinking about implementing such a feature as
merging few sequential instructions
provided they can be accomplished simultaneously. Obviously it is possible
to declare just a new
instructions, but this will not look that tidy.
Anyway, thank you for help.
Alex
--
Alex
Artenz
> I just want to clarify few things - do I really need two passes (omit
> preprocessor for) in case I don't have conditional branches and jumps.
The only reason I have two passes is to resolve forward branches/jumps.
If you don't have those, you can use one pass. In my case, implementing
two passes is nothing more than putting a 'foreach $pass (1..2)' loop
around the main loop. I first read the entire source file in a array of
lines, and dump generated code in an array of instructions. The first
and second pass are identical, but during the first pass, unknown
symbols will generate bad code. This gets fixed automatically on the
second pass. After the 2nd pass, the array of generated code is written
to the output file.
Alex
I think that in any case the main problem is to write an efficient hash
function.
To make my life easier I was initially thinking about writing my asm in a
scripting language,
since it make string processing rather simple. For now that would work (in
the other case in will be necessary to
describe the syntax via BNF).
Can you explain why it is so necessary for you to use hash table in step 2
(apart from speed gain).
Alex
On Tue, 07 Mar 2006 03:30:00 -0000, Isaac Bosompem <x86...@gmail.com>
wrote:
--
Alex
Alex
By way how the translation of mnemonic to opcode through a hash works when
i have variation on instruction parameters. Is it interpreted just as a
differents
instruction, or some sort of subset of the original instruction?
On Tue, 07 Mar 2006 12:37:32 -0000, Artenz <usen...@ladybug.xs4all.nl>
wrote:
--
Alex
Alex
Dragon book would be really usefull in case I would like to create serious
C compiler,
otherwise it is too theoretical as you've said.
--
Alex
Artenz
> By way how the translation of mnemonic to opcode through a hash works when
> i have variation on instruction parameters. Is it interpreted just as a
> differents instruction, or some sort of subset of the original instruction?
What I did was make small subroutines for each of the different types
of instructions. So, I have one for branches, one for arithmetical,
etc.. Usually there are a few instructions in each type, and the hash
translates the instruction into a base opcode value. The subroutine
then takes that base value, and adds specific bits for the operands and
such.
For instance, a pattern match in the main loop finds two words
separated by whitespace, where the first word is in the %cond hash. If
found, it calls the branch subroutine:
branch( $1, $2 ), next if m/^(\w+)\s+(\w+)$/ and $cond{$1};
The %cond hash looks like this:
my %cond = (
"beq" => 0x100,
"bne" => 0x108,
...
);
And the branch subroutine builds the opcode:
sub branch
{
my ($cond, $dest) = @_;
my $addr = $labels{$dest};
my $base = $cond{$cond};
if( defined($addr) ) {
my $rel = $addr - $loc;
if( $rel >= -6 && $rel <= -2 ) {
$code[$loc++] = $base + $rel + 6;
...
} else {
$loc++;
}
}
toby
Alex wrote:
> Thank you for your comment, you gave me a lot of food for thought.
> I think that in any case the main problem is to write an efficient hash
> function.
It certainly isn't the main problem. In fact it isn't a problem at all,
such things are readily available.
Jonathan Kirwan
>In my current project , i have to create i simple assembler for an 8-bit
>processor. Since i am a novice at language writing, I would like to ask if
>somebody can direct to some articles on this topic, or where to start looking at.
What do you already have experience with? Have you written a
tokenizer before? Have you written recursive descent parsers (the
easiest general form) before? Are you familiar with the syntax and
semantics of 'productions'? Can you convert a left-recursive form to
a right-recursive?
The basics of writing an assembler by hand (not through the use of,
say, lexers and compiler-compiler tools) are first somehow first
proceeding beyond just simple character scanning. A tokenizer is a
very simple step to take and is almost natural in concept. For
example, a tokenizer for this paragraph might simply break out words,
periods, parentheses, and other special characters. With the central
idea being the word which you might then use to parse sentences at a
still higher level. But it also includes the idea of parsing larger
concepts, such as a pseudo-op or a complete instruction.
A useful assembler may need to be able to handle forward label
references, too. That may suggest to you a second pass through the
source. If you support symbols, you'll need a table to hold those
you've seen. That can involve hashing functions for fast lookup, or
just simple linear scanning. Etc.
My first assembler was written in BASIC, supported symbols (a symbolic
assembler), did not support macros, and took me from a Friday night
through to the following Sunday afternoon to finish and get working.
On Monday, I used it to assembly my first actual assembly program and
run it on an HP 2116 CPU. To load the program and run it, I wrote
more BASIC code using a BASIC interpreter to read the data file and
load a memory array with it and then to jump into it.
At the time, I knew only a little about parsing and tokenizing but my
instincts worked well. So it's not hard. Best thing is to just get
started by looking at a few lines of example source code and thinking
about what you would need to do by hand if you were to mentally
assemble them. Work it out on paper.
Probably, what had helped me was something that was called CARDIAC. It
was a paper computer (cheap) where you could write data and
instructions on little erasable areas in numbered cells and there was
a little paper ladybug you moved around by hand. Having had to act
like a computer running code probably had put me in the right frame of
mind earlier in my life. CARDIAC was late 1972 for me. My first
assembler was in 1975.
I have a lot of possible references for you to read, but I'd need to
know more about you to recommend any particular one. None of them are
perfect for everyone and some can be very bad for some, even though
they are excellent for others.
Jon
samIam
SO WHAT they provide O(1) search/insert times ... but they are FIXED in
size ... and you often have to implement collision detection to get
around soem problems.
A red-and-black tree is a better compromise ... a data structure that
"grows" with the program run, and offers reasonable search and insert
times (Olog(n)?)
There is no way to know how many labels/symbols exist in your asm source
file ... and JUST choosing a hash table size and then reallocating twice
that size whenever it fills up ... isnt a sound method of implementing a
symbol table in my honest opinion.
For an opcode table (which is fixed in size as in you know the number
of opcodes in the micro) a hash table makes more sense.
Grant Edwards
> I have never understood the obsession with hash tables.
>
> SO WHAT they provide O(1) search/insert times ... but they are FIXED in
> size ... and you often have to implement collision detection to get
> around soem problems.
>
> A red-and-black tree is a better compromise ... a data structure that
> "grows" with the program run, and offers reasonable search and insert
> times (Olog(n)?)
If it's just "simple assembler" why not just use a list with
O(n) access time.
Better yet, use a real programming language with a dictionary
type (Python, Smalltalk, whatever).
--
Grant Edwards grante Yow! ... or were you
at driving the PONTIAC that
visi.com HONKED at me in MIAMI last
Tuesday?
samIam
> O(n) access time.
Most 8bit micros have anywhere from 40 - 60 instructions (opcodes
NOT opcodes+addressing formats)
O(n) searches on that set looks like a waste of cpu cyles
> Better yet, use a real programming language with a dictionary
> type (Python, Smalltalk, whatever).
There are somethings you can ONLY do in assembly ... and on an 8 bit
micro (with 64k address space) every byte counts
Bu
Hi,
About 30 years ago i wrote a (cross) assembler for the Intel 8080
processor (8 bit) in Basic (from Hewlett Packard).
I believe i have somewhere still the listing of this program.
If you are very interested i will look what i still have and try to
scan it (i do not have it in electronic format, maybe as punch paper
tape (:-)
As far as i remember it is a two pass assembler with simple macro's.
Bu.
Hans-Bernhard Broeker
> Better yet, use a real programming language with a dictionary
> type (Python, Smalltalk, whatever).
Why such overkill? I held back this long, but now there's no longer
any way of avoiding it. It has to be mentioned now, to put an end to
this discussion
Henry Spencer's "Amazing Awk Assembler"
And yes, you can still find that beast out there, if you want to.
--
Hans-Bernhard Broeker (bro...@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
dke...@hotmail.com
HI Alex
You might look at the example of an assembler for the 8080, written
by John Cassidy, in the language Forth. Although, it is only a single
pass assembler, it includes control structures. The part that really
makes
it worth while is that the entire source code fits easily on a single
8.5X11 sheet of paper. This makes it easy to understand and
easy to modify.
With a little more modifications, it can still be a single pass
assembler
with forward referencing. Still, it is possible to handle all of ones
referencing
problems in a simple fast single pass assembler. The other thing to
remember
is that the order you assemble into the address space does not need
to be sequencial.
The simple control structures like 'if-then-else' help to make your
assembly
source code more readable and reduce the number of simple entry point
labels that tend to clutter most assembly source.
Last is that you have the Forth language in the background to create
macro
functions to any complexity that you like.
Dwight
Artenz
> > If it's just "simple assembler" why not just use a list with
> > O(n) access time.
>
> Most 8bit micros have anywhere from 40 - 60 instructions (opcodes
> NOT opcodes+addressing formats)
>
> O(n) searches on that set looks like a waste of cpu cyles
Not necessarily. For example, my old Athlon XP 1800 does a strcmp()
between two matching 4-char strings in 17 nanoseconds. On average, a 4
char opcode can be found in 0.5 microseconds by linear search in array
of 60 entries.
In order to compensate for 10 minutes of time spent implementing a
better search, you'll need to run 1.2 billion lines of code through the
assembler.
toby
> I have never understood the obsession with hash tables.
>
> SO WHAT they provide O(1) search/insert times ... but they are FIXED in
> size ... and you often have to implement collision detection to get
> around soem problems.
Chaining is a well studied and simple idea, see, for instance Knuth.
>
> A red-and-black tree is a better compromise ... a data structure that
> "grows" with the program run, and offers reasonable search and insert
> times (Olog(n)?)
>
> There is no way to know how many labels/symbols exist in your asm source
> file ... and JUST choosing a hash table size and then reallocating twice
> that size whenever it fills up ... isnt a sound method of implementing a
> symbol table in my honest opinion.
There is an informed discussion of symbol table implementations at
http://groups.google.com/group/comp.compilers/browse_thread/thread/d44b7c420ab50e28?tvc=2
Hash tables are more efficient. See Anton Ertl's post:
Resizing is an O(n) operation (where n is the no. of entries in the
hash table at the time of resizing), but you resize only once every
O(n) elements, so the amortized cost of resizing per insertion is
O(n/n)=O(1); of course, there is no resizing cost when you are only
doing lookups.
Grant Edwards
>> O(n) access time.
>
> Most 8bit micros have anywhere from 40 - 60 instructions (opcodes
> NOT opcodes+addressing formats)
>
> O(n) searches on that set looks like a waste of cpu cyles
Who cares? It's an _assembler_. It'll be run at most a few
dozen times a day. It's not the kernel's scheduler.
>> Better yet, use a real programming language with a dictionary
>> type (Python, Smalltalk, whatever).
>
> There are somethings you can ONLY do in assembly ... and on an 8 bit
> micro (with 64k address space) every byte counts
Ah, the assembler is running on an 8-bit processor. I guess I
missed that. I assumed the assembler would be running on a
Linux or Windows host.
--
Grant Edwards grante Yow! Kids, don't gross me
at off... "Adventures with
visi.com MENTAL HYGIENE" can be
carried too FAR!
Isaac Bosompem
Hi CBFalconer,
WOW, your package will again make my life a lot easier. Thanks! I will
definitely make use of it!
Also I am writing for the PC, I was not aware that the OP was writing
for the CPU itself (well that is what I have gotten from the replies
posted).
Also guys, I didnt know of any other methods to implement it, I am
definitely going to stay away from parsing the text directly because it
would be fairly difficult to code.
What is a red - green tree? I know of a binary tree used in Huffman
Compression and the like, is this data structure similar?
Isaac Bosompem
Hi Alex,
I decided to use a hash table for step 2 to make life easy. I
originally thought of using a lookup table based on the first letter
within the string but I found it to be too complicated.
With a hash value, I can read the asm source, grab a token, run a hash
on it and look it up. It was done for simplicity, I didn't initially
believe there would be any speed improvements because you will have to
do a lookup of the hash value in the table to check if it is a valid
symbol and decide from there.
I don't know any scripting languages. I guess that is a weakness (and I
am also not that great with analog electronics as well) I do know VB
though haha. I dont know Python or TCL for that matter. I will pick
them up eventually, but the way I learn best is if I use the tool to
make something useful with it.
If you do decide to write the assembler in Python, please let me know.
samIam
> better search, you'll need to run 1.2 billion lines of code through the
> assembler.
This attitude is why there isnt much thought given to softare
development nowadays
and
its clearly reflected in the output and the drive for faster processors
and huge amounts of memory/resources
samIam
> hash table at the time of resizing), but you resize only once every
> O(n) elements, so the amortized cost of resizing per insertion is
> O(n/n)=O(1); of course, there is no resizing cost when you are only
> doing lookups.
Biggest assumption you are making here is that THERE IS SPACE TO
ALLOCATE/RESIZE.
Your assembler would not run on the target processor with that
mentality. It would exist only as a cross development tool on a system
with the resources to house it.
Software should be designed much better than that. But hey, what do I
know? Nothing apparently!
Artenz
On the contrary. I'm all for optimization, but only if it makes sense.
If, for any reasonable input size, the assembler takes no noticable
time to process the entire source, what point is there in further
improvements ? Instead, I prefer to optimize scarcer resources, such as
my own time. If making the assembler is just a step towards the goal
of having a binary program ready for a product, and not a goal in
itself, then spending more time on the assembler than you will ever
gain back by the optimizations simply makes no sense.
Gigahertz processors, and gigabyte memories are here. It would be waste
of resources not to use them whenever it saves us time.
CBFalconer
>
> I have never understood the obsession with hash tables.
>
> SO WHAT they provide O(1) search/insert times ... but they are
> FIXED in size ... and you often have to implement collision
> detection to get around soem problems.
Please do not top-post. It loses all context, and makes no sense.
Your answer belongs after, or intermixed with, the material you
quote, after snipping non-relevant portions.
You obviously did not look at hashlib (reference lost by the
toppost). It is not fixed in size. It can handle from 2 to about
8,000,000 entries as it stands, and the upper limit can be extended
with one line of code, and the method is detailed in the source.
You don't have to implement any collision detection, it is all done
for you.
The only case in which it is less than optimum if you need to
maintain the content in sorted order continuously. There are
provisions in hashlib that make it easy to sort the content on
demand, but that sort will be destroyed by the next entry or
deletion from the table.
Note that O(1) is considerably faster than O(logN). It tends to
relieve you of any need to think about the penalties of expansion.
CBFalconer
You said it, not I. If there is no room to house the symbol table,
there is probably no room to house the symbol table.
BTW how many embedded system assemblers and compilers are expected
to run on the destination system?
CBFalconer
> CBFalconer wrote:
>> Isaac Bosompem wrote:
>>>
>> ... snip ...
>>>
>>> I do need an efficient hashing function, with a low probability of
>>> collisions (ideally). I will need to code to handle collisions.
>>>
>>> Anyways I am open to new ideas hopefully you have some of your own
>>> to add.
>>
>> You are welcome to use hashlib, which is under GPL licensing, and
>> was designed to fill just this sort of need. It is written in pure
>> ISO C.
>>
>> You could open one table and stuff it with the opcodes. Another
>> could hold the macros, and yet another the symbols. The tables
>> will all use the same re-entrant hash code, yet can have widely
>> different content.
>>
>> <http://cbfalconer.home.att.net/download/hashlib.zip>
>
> will definitely make use of it!
You are welcome. This is exactly one of the sort of applications
it was designed for. Remember, it is GPL licensed, not GLPL, so
you are free to use it, but you are obliged to publish your code
under GPL if you ever promulgate your end program. If you only use
it for your own benefit, there are no restrictions.
Look at the usage in id2id-20, which may also be useful for any
mass identifier changes in a suite of source files.
Paul Keinanen
In the 1970's I wrote several cross-assemblers in Fortran running on
PDP-11s (which have 64 KiB address space) for various processors such
as 8080 and 1802. I never bothered to use anything more fancier than
linear search for opcode or symbol table search, since the total time
was dominated by the program load time, the source file read time (two
passes) and the binary output file writing (or even punching to paper
tape for downloading to the target :-).
It would be very hard to write so huge modules for any small target
processor that would require such a huge number of labels, that the
inefficient symbol table search time would have been of any
significance relative to the I/O times.
Paul
David Brown
> Isaac Bosompem wrote:
> ... snip ...
>> I do need an efficient hashing function, with a low probability of
>> collisions (ideally). I will need to code to handle collisions.
>>
>> Anyways I am open to new ideas hopefully you have some of your own
>> to add.
>
> You are welcome to use hashlib, which is under GPL licensing, and
> was designed to fill just this sort of need. It is written in pure
> ISO C.
>
> You could open one table and stuff it with the opcodes. Another
> could hold the macros, and yet another the symbols. The tables
> will all use the same re-entrant hash code, yet can have widely
> different content.
>
> <http://cbfalconer.home.att.net/download/hashlib.zip>
>
It's for this sort of reason that such programs should be written in
languages like Perl or Python (or even PHP). Just as C++ is a poor
choice of language for an 8051, so C/C++ is a poor choice of language
for an assembler running on a PC.
Both Perl and Python will give you much simpler regular expression
engines than any C library, vastly easier (and more flexible, and
probably faster) hash dictionaries, and a host of ready-to-use libraries.
42Bastian Schick
wrote:
>> There are somethings you can ONLY do in assembly ... and on an 8 bit
>> micro (with 64k address space) every byte counts
>
>Ah, the assembler is running on an 8-bit processor. I guess I
>missed that. I assumed the assembler would be running on a
>Linux or Windows host.
The OP wrote "for an 8 bit" not "on an 8 bit" CPU.
--
42Bastian
Do not email to bast...@yahoo.com, it's a spam-only account :-)
Use <same-name>@monlynx.de instead !
Grant Edwards
>>> If it's just "simple assembler" why not just use a list with
>>> O(n) access time.
>>
>>Most 8bit micros have anywhere from 40 - 60 instructions (opcodes
>>NOT opcodes+addressing formats)
>>
>>O(n) searches on that set looks like a waste of cpu cyles
>>
>>> Better yet, use a real programming language with a dictionary
>>> type (Python, Smalltalk, whatever).
>>
>>There are somethings you can ONLY do in assembly ... and on an
>>8 bit micro (with 64k address space) every byte counts
>
> In the 1970's I wrote several cross-assemblers in Fortran running on
> PDP-11s (which have 64 KiB address space) for various processors such
> as 8080 and 1802. I never bothered to use anything more fancier than
> linear search for opcode or symbol table search, since the total time
> was dominated by the program load time, the source file read time (two
> passes) and the binary output file writing (or even punching to paper
> tape for downloading to the target :-).
My point exactly. Worrying about hash tables for symbol lookup
reeks of premature optimization for "a simple assembler".
> It would be very hard to write so huge modules for any small
> target processor that would require such a huge number of
> labels, that the inefficient symbol table search time would
> have been of any significance relative to the I/O times.
I'm also surprised that somebody thinks they're going to use
C++ and generic hashing libraries on an 8-bit target with a 64K
address space.
--
Grant Edwards grante Yow! .. someone in DAYTON,
at Ohio is selling USED
visi.com CARPETS to a SERBO-CROATIAN
Grant Edwards
> CBFalconer wrote:
>> Isaac Bosompem wrote:
>> ... snip ...
>>> I do need an efficient hashing function, with a low probability of
>>> collisions (ideally). I will need to code to handle collisions.
>>>
>>> Anyways I am open to new ideas hopefully you have some of your own
>>> to add.
>>
>> You are welcome to use hashlib, which is under GPL licensing, and
>> was designed to fill just this sort of need. It is written in pure
>> ISO C.
>>
>> You could open one table and stuff it with the opcodes. Another
>> could hold the macros, and yet another the symbols. The tables
>> will all use the same re-entrant hash code, yet can have widely
>> different content.
>>
>> <http://cbfalconer.home.att.net/download/hashlib.zip>
>>
>
> It's for this sort of reason that such programs should be written in
> languages like Perl or Python (or even PHP). Just as C++ is a poor
> choice of language for an 8051, so C/C++ is a poor choice of language
> for an assembler running on a PC.
That's what I said, but apparently the assembler is running on
an 8-bit target with a 64K address space. So Python is out of
the question. But C++ and generic libraries are going to fit?
> Both Perl and Python will give you much simpler regular
> expression engines than any C library, vastly easier (and more
> flexible, and probably faster) hash dictionaries, and a host
> of ready-to-use libraries.
Yup.
--
Grant Edwards grante Yow! Darling, my ELBOW
at is FLYING over FRANKFURT,
visi.com Germany...
Grant Edwards
> On Tue, 07 Mar 2006 20:24:47 -0000, Grant Edwards <gra...@visi.com>
> wrote:
>
>>> There are somethings you can ONLY do in assembly ... and on an 8 bit
>>> micro (with 64k address space) every byte counts
>>
>>Ah, the assembler is running on an 8-bit processor. I guess I
>>missed that. I assumed the assembler would be running on a
>>Linux or Windows host.
>
> The OP wrote "for an 8 bit" not "on an 8 bit" CPU.
Then why does the target's 64K byte address space preclude the
use of a high-level programming language?
--
Grant Edwards grante Yow! You must be a CUB
at SCOUT!! Have you made your
visi.com MONEY-DROP today??
David Brown
No one is writing an assembler to run *on* the target. Someone jumped
into this thread with a discussion about running on an 8-bit target (as
far as I've noticed, the OP has not mentioned the type of target), and
how we should program efficiently in assembler rather than using high
level languages and hash tables. As far as I can figure out, he is
assumed that the thread was about writing in assembly language rather
than writing an assembler, and his confusion has spread.
Grant Edwards
Ah.
If that's the case, then I stand by my original suggestion of
using a high-level language like Python to write the assembler.
--
Grant Edwards grante Yow! Did you find a
at DIGITAL WATCH in YOUR box
visi.com of VELVEETA??
toby
> ... I stand by my original suggestion of
> using a high-level language like Python to write the assembler.
Yes, or Perl, and perhaps using a lexer/parser library. Even C++ with a
decent parser generator.
The fact that a thread headed "Writing a simple assembler" is dominated
by the topic of hashing indicates that something is seriously off the
rails somewhere.
>
> --
> Grant Edwards
samIam
the "thought police"!
> Please do not top-post. It loses all context, and makes no sense.
> You don't have to implement any collision detection, it is all done
> for you.
completely missing the point.
the problem is the NEED for collision detection ... and having to
re-allocate twice the memory when the table is filled.
having it "hidden" or "done for you" doesnt resolve the issues above
Alex
Second - the purpose was to write a simple assembler in order to generate
an op code on a PC
and then run it on my IC (fpga is used as a host controller).
I understand that the task is trivial for gurus, but being a novice in
this thing first thing that came to
my mind was simply to make two passes: first - preprocessor, detects all
the variables etc., second actual
translation - recognising mnemonics and generate an opcode . Obviously it
is not a "proper" way to do it
(grammar descriptions and so on..). That's why I was asking about some
examples and articles about this issue.
--
Alex
rand...@earthlink.net
Grant Edwards wrote:
>
> My point exactly. Worrying about hash tables for symbol lookup
> reeks of premature optimization for "a simple assembler".
>
Speaking from exprience ... :-)
First, choosing a good algorithm up front is not "premature
optimization." It's simply good design.
Second, despite the best intentions (encapsulation and other good
software engineering methods), it's often not so simple to just replace
one symbol table search routine with another.
Third, "a simple assembler" today may be a complex assembler tomorrow.
Better to do it right the first time around, especially as using a hash
table lookup isn't a whole lot more complex than a linear search.
I regret the day I said to myself "heck, this is just a prototype, I'll
use a simple linear search right now and fix it in the final version."
82 versions later and over 100,000 lines of code, I can attest that
this was the second worst design decision I made for my "prototype
assembler" (the #1 bad design decision was using Flex and Bison).
Cheers,
Randy Hyde
CBFalconer
And why do you assume an assembler needs the complication of a
regular expression engine? It can classify items very quickly. If
it starts in the lhcolumn it is either a name or a label. A label
terminates with a colon. A name should be followed by a pseudo op
such as macro or equ. A field starting after the lh column is an
op or a pseudo op. All else (unless the line has been terminated
by a comment marker) is an expression of some form.
Names, ops, etc. start with an alpha. Numeric constants start with
a digit, unless they come out of a symbol table. Nothing spreads
over multiple lines except a macro. We don't need macros for a
simple assembler.
What an assembler needs is a quick and consistent way to form and
maintain symbol tables. The complications appear in the object
format, if it is to generate relocatable linkable code.
Hans-Bernhard Broeker
> Second, despite the best intentions (encapsulation and other good
> software engineering methods), it's often not so simple to just replace
> one symbol table search routine with another.
In all fairness, a "symbol table search routine" that fails to be
easily replacable by another, should immediately be reported to the
nearest Committee on Abusive Nomenclature and Fraudulent Assumption of
Titles. If it can't be replaced, it's clearly not a search routine,
but a hack.
--
Hans-Bernhard Broeker (bro...@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
rand...@earthlink.net
Hans-Bernhard Broeker wrote:
> > one symbol table search routine with another.
>
> In all fairness, a "symbol table search routine" that fails to be
> easily replacable by another, should immediately be reported to the
> nearest Committee on Abusive Nomenclature and Fraudulent Assumption of
> Titles. If it can't be replaced, it's clearly not a search routine,
> but a hack.
I couldn't agree more. But more often than not, guess what happens.
Better to plan ahead, and be realistic.
Cheers,
Randy Hyde
Grant Edwards
>> My point exactly. Worrying about hash tables for symbol lookup
>> reeks of premature optimization for "a simple assembler".
>
> Speaking from exprience ... :-)
>
> First, choosing a good algorithm up front is not "premature
> optimization." It's simply good design.
>
> Second, despite the best intentions (encapsulation and other good
> software engineering methods), it's often not so simple to just replace
> one symbol table search routine with another.
Then you did it wrong. The API for a symbol lookup should be
dead simple.
--
Grant Edwards grante Yow! I feel like I'm
at in a Toilet Bowl with a
visi.com thumbtack in my forehead!!
samIam
> optimization." It's simply good design.
>
> Second, despite the best intentions (encapsulation and other good
> software engineering methods), it's often not so simple to just replace
> one symbol table search routine with another.
>
> Third, "a simple assembler" today may be a complex assembler tomorrow.
> Better to do it right the first time around, especially as using a hash
> table lookup isn't a whole lot more complex than a linear search.
>
> I regret the day I said to myself "heck, this is just a prototype, I'll
> use a simple linear search right now and fix it in the final version."
> 82 versions later and over 100,000 lines of code, I can attest that
> this was the second worst design decision I made for my "prototype
> assembler" (the #1 bad design decision was using Flex and Bison).
Randy, I tip my hat to you sir.
It seems many here have forgotten the tenet of Software Engineering.
I said it before and Ill say it now ..
it SHOWS in the sort of software currently developed.
Another thing that irks me is the "its done in this library so just use
it" argument. No one stops to question WHETHER that library is doing it
right/efficiently.
Anyway I am getting off the point ...
Isaac Bosompem
Grant Edwards wrote:
> On 2006-03-08, Paul Keinanen <kein...@sci.fi> wrote:
>
> >>> If it's just "simple assembler" why not just use a list with
> >>> O(n) access time.
> >>
> >>Most 8bit micros have anywhere from 40 - 60 instructions (opcodes
> >>NOT opcodes+addressing formats)
> >>
> >>O(n) searches on that set looks like a waste of cpu cyles
> >>
> >>> Better yet, use a real programming language with a dictionary
> >>> type (Python, Smalltalk, whatever).
> >>
> >>There are somethings you can ONLY do in assembly ... and on an
> >>8 bit micro (with 64k address space) every byte counts
> >
> > In the 1970's I wrote several cross-assemblers in Fortran running on
> > PDP-11s (which have 64 KiB address space) for various processors such
> > as 8080 and 1802. I never bothered to use anything more fancier than
> > linear search for opcode or symbol table search, since the total time
> > was dominated by the program load time, the source file read time (two
> > passes) and the binary output file writing (or even punching to paper
> > tape for downloading to the target :-).
>
> My point exactly. Worrying about hash tables for symbol lookup
> reeks of premature optimization for "a simple assembler".
Well the hash lookups were not for premature optimization. I first
decided on doing simple string parsing but I quickly realized it would
be a nightmare to code. I am simply looking for a solution that is easy
to code.
> > It would be very hard to write so huge modules for any small
> > target processor that would require such a huge number of
> > labels, that the inefficient symbol table search time would
> > have been of any significance relative to the I/O times.
>
> I'm also surprised that somebody thinks they're going to use
> C++ and generic hashing libraries on an 8-bit target with a 64K
> address space.
That choice might have been overambitious, but I do feel I need to get
a grasp of OOP programming.
I must ask though why you guys are so adamant about using TCL or
Python?! I have not started to code it yet, I am still in the planning
phase.
toby
> WOAH
> the "thought police"!
There is no need to overreact to somebody pointing out a breach of
Usenet etiquette. Doing so does, however, give us a clue to the
personality we're dealing with.
>
> > Please do not top-post. It loses all context, and makes no sense.
>
>
> > You don't have to implement any collision detection, it is all done
> > for you.
>
> completely missing the point.
> the problem is the NEED for collision detection ... and having to
> re-allocate twice the memory when the table is filled.
It's not "collision detection", it's chaining; it's not a "problem";
and if you want an O(1) lookup, hashes are for you. If not: there are a
million other data structures you can use. Buy this book:
http://dogbert.abebooks.com/servlet/SearchResults?an=knuth&tn=sorting
Plonk. (And I *never* plonk.)
toby
It can be argued that since you are in learning mode there is no
'wrong' way to go about it. Go forth and build your prototype; doing so
is a great way to learn about languages and tools that might be related
or make the task easier. :)
>
>
>
> --
> Alex
Grant Edwards
> I must ask though why you guys are so adamant about using TCL
> or Python?! I have not started to code it yet, I am still in
> the planning phase.
Because the sort of stuff you're planning wouldn't need
planning in a high level language. Things like symbol lookups
are just basic built-in operations.
--
Grant Edwards
gra...@visi.com
msg
>
> About 30 years ago i wrote a (cross) assembler for the Intel 8080
> processor (8 bit) in Basic (from Hewlett Packard).
> I believe i have somewhere still the listing of this program.
> If you are very interested i will look what i still have and try to
> scan it (i do not have it in electronic format, maybe as punch paper
> tape (:-)
>
Hi,
I am interested in seeing your BASIC assembler; if it is on paper
tape, I can read it (and return the tape with conversion of your
choice). I imagine this predates RMB (Rocky Mountain Basic)?
Regards,
Michael Grigoni
Cybertheque Museum
Jim Stewart
Total agreement. In the total time spent
posting on this thread, a simple assembler
could have been written and debugged :)
Myself, I'd just define some macros for
MASM, the old Microsoft DOS assembler.
Paul Keinanen
A two pass assembler is definitely a practical way of doing a
cross-assembler. The first pass must generate the correct amount of
code for each instruction, in order to "detect" the locations of all
branch target labels in the program. In the second pass do the same
thing again and using the label addresses stored in the symbol table,
generate the correct code (especially the branch/jump instructions).
When running the assembler on a system with a huge memory (such as PC)
just generate the code into memory with any forward jump/branch set to
0 and saving this location into a fix-up record. When the assembly is
ready to calculate the address of the label, you have to make a fix-up
patch at all those locations that referenced that label. Finally,
write the patched code into a file or target.
I would consider implementing a two pass cross assembler to be the
simplest thing, just use brute force :-).
If you are comfortable with a single pass assembler with fix-ups, you
could write as well a linker or a linking loader.
Paul
CBFalconer
>
... snip ...
>
> Another thing that irks me is the "its done in this library so
> just use it" argument. No one stops to question WHETHER that
> library is doing it right/efficiently.
If you are talking about my recommendation of hashlib, you are
perfectly free to comment on the correctness and efficiency of that
library. I claim it is both, although it may give up some slight
efficiencies for ease of use. It is out there in source form,
totally exposed to the winds of criticism.
toby
Hi Jim,
Now that is a technique I have heard of before! A gentleman Tom Evans
clued me into this, and I hope he will allow me the liberty of quoting:
There's two ways to "write an assembler in Macro 11".
The IMP/PACE one I mentioned was "the classic version". It had
the parser, symbol table management and everything, all lovingly
coded in individual machine instructions. Lots of them. How
redundant...
The SC/MP cross assembler (and other ones I've worked on ...
that generated microcode) consisted of MACROS.
This is cheating big-time. The Macro-11 assembler is being abused
to assemble and emit code for a different CPU, or sometimes not
even for a CPU but for a ROM Sequencer or worse. The macros have
the same names as the target CPU's op-codes and they simply
generate the appropriate code, (ab)using the symbol table
management built into Macro-11.
As a huge benefit you can also use all of the powerful macro
facilities in Macro-11. Try emulating all of that in lex/yacc.
Of course if the targeted CPU uses opcodes with the same names as
the ones the PDP-11 uses there's a bit of strife, ...
Macro-11 isn't exactly fast when abused like this. It took about
5 minutes to make [a] 1023-byte ROM ...
Kids these days have it easy! Lex! Yacc! Puts me in mind of:
http://www.phespirit.info/montypython/four_yorkshiremen.htm
"SECOND YORKSHIREMAN:
Luxury. We used to have to get out of the lake at six o'clock in
the morning, clean the lake, eat a handful of 'ot gravel, work twenty
hour day at mill for tuppence a month, come home, and Dad would thrash
us to sleep with a broken bottle, if we were lucky!"
--Toby
Jonathan Kirwan
Macro-11 is pretty good and I've read exactly these cases, back in the
1970's when I was using Macro-11. I never wrote Macro-11 code for a
cross-assembler, though. Just heard about it.
I've actually used MASM/ML from Microsoft for such things, though.
From my vague recollection of Macro-11 macros, MASM/ML's macro
facilities aren't nearly as general and can be confusing to figure
out, at times. But the linker will actually punch out a .COM file,
which is a clean, exact, binary image. MASM/ML will allow you to
place things in separate segments so that you can, on the fly, place
things into nicely organized sections which will later be fused
together as you see fit. (You can generate a .EXE, but you will need
another tool to 'fix' it up.)
Jon
Roger Ivie
> The SC/MP cross assembler (and other ones I've worked on ...
> that generated microcode) consisted of MACROS.
>
> This is cheating big-time. The Macro-11 assembler is being abused
> to assemble and emit code for a different CPU, or sometimes not
> even for a CPU but for a ROM Sequencer or worse. The macros have
> the same names as the target CPU's op-codes and they simply
> generate the appropriate code, (ab)using the symbol table
> management built into Macro-11.
I haven't done this with either MACRO-11 or MASM, but I have done it a
few times with MACRO-32.
First time was for FQAM, the QBus adapter for the VAXstation 3520/3540.
It was built around a simple state machine implemented with registered
EPROMs.
Currently, I'm using a set of MACRO-32 macros that let me migrate
microcode assembly for a 2910/29116 based system off an old META29R
setup that required a VAX onto an Alpha using MACRO-32. I've managed to
retain all the original mnemonics used in the META29R code and quite a
bit of the syntax. This let me do automated source code conversion
between the two assemblers, which was nice.
The result is a .PSECT containing an initialized array that I link
against a FORTRAN program to extract the binary in a variety of formats.
> Macro-11 isn't exactly fast when abused like this. It took about
> 5 minutes to make [a] 1023-byte ROM ...
Neither is MACRO-32. It took a MicroVAX 2000 half an hour to assemble
the microcode for the FQAM.
--
roger ivie
ri...@ridgenet.net
rand...@earthlink.net
toby wrote:
> >
> > Myself, I'd just define some macros for
> > MASM, the old Microsoft DOS assembler.
>
> Hi Jim,
>
> Now that is a technique I have heard of before! A gentleman Tom Evans
> clued me into this, and I hope he will allow me the liberty of quoting:
>
Having a good compile-time language (macro processor plus other
goodies) in an assembler is useful for creating all kinds of different
languages, not just assemblers. Interested individuals might want to
take a look at my chapter on "Domain Specific Languages" in "The Art of
Assembly Language" where it discusses how to use HLA's macros and
compile-time language to create "mini-languages". Certainly, an
assembler would be fairly trivial to write. Indeed, I'm using this
technique to create a small assembler for a virtual machine I've
created to help with some object code obfuscation.
Cheers,
Randy Hyde
Jonathan Kirwan
<rand...@earthlink.net> wrote:
I was hoping you'd pop in on this.
Jon
Jim Granville
Is your HLA v2.0 stable enough yet, that it can be used as a macro
assembler ? - I see it had recent update.
-jg
CBFalconer
> toby wrote:
>>>
>>> Myself, I'd just define some macros for
>>> MASM, the old Microsoft DOS assembler.
>>
>> Evans clued me into this, and I hope he will allow me the liberty
>> of quoting:
>
> Having a good compile-time language (macro processor plus other
> goodies) in an assembler is useful for creating all kinds of
> different languages, not just assemblers. Interested individuals
> might want to take a look at my chapter on "Domain Specific
> Languages" in "The Art of Assembly Language" where it discusses
> how to use HLA's macros and compile-time language to create
> "mini-languages". Certainly, an assembler would be fairly trivial
> to write. Indeed, I'm using this technique to create a small
> assembler for a virtual machine I've created to help with some
> object code obfuscation.
This, with different assemblers, linkers, etc. was precisely the
path I took for the first version of machine code generation (as
opposed to pcode generation) from PascalP. The result worked,
generated excessively bloated code, but verified the ideas. I then
wrote a proper code generator, which greatly improved speed,
register assignments, bloat, etc.
David Brown
That would be why people are recommending languages like Python - so
that such basic blocks like string parsing and hash tables are as easy
as possible.
>>> It would be very hard to write so huge modules for any small
>>> target processor that would require such a huge number of
>>> labels, that the inefficient symbol table search time would
>>> have been of any significance relative to the I/O times.
>> I'm also surprised that somebody thinks they're going to use
>> C++ and generic hashing libraries on an 8-bit target with a 64K
>> address space.
>
> That choice might have been overambitious, but I do feel I need to get
> a grasp of OOP programming.
>
OOP would be a good idea for such a task. May I recommend a good OOP
language, such as ... Python ? There are actually a fair number of
good OOP programming languages that could be used for such a task - C++
isn't really one of them (multiple inheritance, friends, and templates
are some of the "features" of C++ OOP that quickly lead to horrible
ugly, unreadable and unmaintainable code).
> I must ask though why you guys are so adamant about using TCL or
> Python?! I have not started to code it yet, I am still in the planning
> phase.
>
I don't think anyone has recommended TCL, nor are they likely to. TCL
has its place, and can be a useful language - but not for a task such as
this. I'm a Python fan, and I have no doubts in recommending Python as
a suitable language for writing an assembler. I'm not a Perl expert,
but I know enough about it to know it is also up to the job, but I don't
think it would be as good a fit. There are plenty of other options that
may or may not be good fits - I don't know them well enough (such as
Java, Smalltalk, OCAML, Ruby). And I know several languages that could
be used, such as C, C++ and Pascal, but which force you to start much
nearer the bottom instead of providing the basic building blocks.
Choosing your language is a much more important step than the choosing
the implementation for a particular data structure, and is definitely
part of the planning phase (do you want to choose languages *after*
starting coding?).
Paul Keinanen
>
> This is cheating big-time. The Macro-11 assembler is being abused
> to assemble and emit code for a different CPU, or sometimes not
> even for a CPU but for a ROM Sequencer or worse. The macros have
> the same names as the target CPU's op-codes and they simply
> generate the appropriate code, (ab)using the symbol table
> management built into Macro-11.
>
> As a huge benefit you can also use all of the powerful macro
> facilities in Macro-11. Try emulating all of that in lex/yacc.
At least RSX-11 also contained a nice table driven parser (TPARS) in
the run time library. Macros were used to define the state tables with
all the various transitions.
This parser was initially intended for command line parsing, but it
was so versatile that I wrote a cross assembler (for a strange 20 bit
test instrument processor). This cross assembler was then used to
write a Basic interpreter for that 20 bit processor. The parsing
tables became quite complex, due to the oddities of the target
processor.
The TPARS was also useable for parsing simple high level languages:-).
Paul
Everett M. Greene
And then there are meta-assemblers that can generate code
for any processor...
ArarghMai...@not.at.arargh.com
<jki...@easystreet.com> wrote:
<snip>
>> This is cheating big-time. The Macro-11 assembler is being abused
>> to assemble and emit code for a different CPU, or sometimes not
>> even for a CPU but for a ROM Sequencer or worse. The macros have
>> the same names as the target CPU's op-codes and they simply
>> generate the appropriate code, (ab)using the symbol table
>> management built into Macro-11.
>>
<snip>
>
>Macro-11 is pretty good and I've read exactly these cases, back in the
>1970's when I was using Macro-11. I never wrote Macro-11 code for a
>cross-assembler, though. Just heard about it.
>
>I've actually used MASM/ML from Microsoft for such things, though.
>From my vague recollection of Macro-11 macros, MASM/ML's macro
>facilities aren't nearly as general and can be confusing to figure
>out, at times. But the linker will actually punch out a .COM file,
>which is a clean, exact, binary image. MASM/ML will allow you to
>place things in separate segments so that you can, on the fly, place
>things into nicely organized sections which will later be fused
>together as you see fit. (You can generate a .EXE, but you will need
>another tool to 'fix' it up.)
Way back in the 70's I wrote a series of macros for 360 ASM F to cross
compile object for a IBM 705. The cute part is the the 705 was a
character machine, some what like a 14xx. Which meant that the binary
addresses from the symbol table had to be converted to 4? 5? character
leading zero strings. I have forgotten most of the details by now.
--
ArarghMail603 at [drop the 'http://www.' from ->] http://www.arargh.com
BCET Basic Compiler Page: http://www.arargh.com/basic/index.html
To reply by email, remove the garbage from the reply address.
Walter Banks
in PDP11 macro's. It didn't set any speed records. I think about 45
minutes to assemble 12K of code. It was enough to implement a
Daisy Wheel printer controller. The prototype is still around the office
in case someone needs a typewriter that actually hits the paper with a
hammer.
Macro 11 was a nice piece of software
w..
toby wrote:
> Hi Jim,
>
> Now that is a technique I have heard of before! A gentleman Tom Evans
> clued me into this, and I hope he will allow me the liberty of quoting:
>
> There's two ways to "write an assembler in Macro 11".
>
>
rand...@earthlink.net
CBFalconer wrote:
>
> This, with different assemblers, linkers, etc. was precisely the
> path I took for the first version of machine code generation (as
> opposed to pcode generation) from PascalP. The result worked,
> generated excessively bloated code, but verified the ideas. I then
> wrote a proper code generator, which greatly improved speed,
> register assignments, bloat, etc.
I don't know if "bloated" is the correct word to use here. To me,
"bloated" usually means "big". I can't imagine that either the set of
macros that did this, nor the code the macros generated, was
excessively big. OTOH, because macros are interpreted, and you've
effectively written a code generator with an interpreter, I can
certainly believe it was quite slow. Then again, I've seen assemblers
written in interpreted BASIC that weren't speed demons, either.
As for the 45 minute compile times I've seen mentioned elsewhere in
this thread, I'm not seeing that with my little "assembler written with
macros". Then again, it helps having a machine that's about 1,000 to
10,000 times faster than typical machines that MACRO-11 ran on :-)
(i.e., I'm sure HLA's performance would be worse if run on comparable
hardware).
Cheers,
Randy Hyde
Jim Stewart
These days, it's hard to imagine an assembler
that would be too slow. After all, the whole
symbol table can fit in the L1 cache with lots
of room left over (:
rand...@earthlink.net
Jim Stewart wrote:
>
> These days, it's hard to imagine an assembler
> that would be too slow. After all, the whole
> symbol table can fit in the L1 cache with lots
> of room left over (:
Until, of course, you include all the Win32 equates (all 20,000, or so,
of them).
And if your symbol table entries are a bit more complex than just a
name and a value (as is certainly true for HLA, for example) and you
tend to use long names (i.e., Win32 equates), you can use up the cache
fairly rapidly.
Oh, and don't forget, you want all the code to fit in the cache, too.
While the size of the executable code isn't a terribly great metric
(working set size, and all), fairly complex assemblers like HLA tend to
be fairly large.
While on the subject, I would also like to point out "yet another
reason not to use Flex and Bison" for assemblers-- the parsing and
lexer tables these assemblers produce are quite large. They blow away
the data cache, without even considering the effects of the symbol
table on the cache. HLA probably takes a 10x performance hit for this
very reason.
Cheers,
Randy Hyde
Jim Stewart
rand...@earthlink.net
Jim Stewart wrote:
>
> I defer to you knowledge of Win32 bloatage...
This has nothing to do with Win32 code. The problem exists under Linux
and every other OS on which Flex and Bison run. Bottom line is that
Flex and Bison generate a *lot* of table data and that obliterates the
cache compared to hand-generated parsers and lexers (at least,
well-written ones).
Cheers,
Randy Hyde
cs_po...@hotmail.com
> A two pass assembler is definitely a practical way of doing a
> cross-assembler. The first pass must generate the correct amount of
> code for each instruction, in order to "detect" the locations of all
> branch target labels in the program. In the second pass do the same
> thing again and using the label addresses stored in the symbol table,
> generate the correct code (especially the branch/jump instructions).
I would imagine things get more complicated when you have both a short
relative and a long call/jump addressing scheme - you don't know before
you emit the intervening code how far away your target will be, so you
don't know how long an instruction word you need to emit, so you don't
know how far away your target will be...
Of course if the two modes have different mnemonics, then it's up to
the user to pick the right one, and the assembler only to error if the
short one is used where it won't work.
Tauno Voipio
There is an algorithm, published in Datamation (1968-1970), which
enables the translation of variable-length addresses so that the
task of address length selection is left to the assembler.
It needs a third pass to resolve the addressing lengths.
IIRC, the Borland Macro Assembler for i86 family can also
resolve the addresses to long or short, depending on what
is needed.
--
Tauno Voipio
tauno voipio (at) iki fi
toby
rand...@earthlink.net wrote:
> Jim Stewart wrote:
> >
> > These days, it's hard to imagine an assembler
> > that would be too slow. After all, the whole
> > symbol table can fit in the L1 cache with lots
> > of room left over (:
> While on the subject, I would also like to point out "yet another
> reason not to use Flex and Bison" for assemblers--
Are you going to go into the reasons why one *would* want to use them?
Or will we leave that to others?
les.hild...@gmail.com
although it was a long time ago. The hardest part was parsing each
line (order of precedence, infix to outfix, multiple radix's, math,
exponents, etc..) The actual building of the symbol table (first
pass), and assigning the opcodes to mnemonics (second pass) was pretty
easy. The just write the output files, bin, hex, symbol, list etc..
My same basic assembler worked for PIC16c5x and 8748. I fould
universal cross assemblers table driven assembler, which would work for
any processor, and gave up on my own.
Les
Paul Keinanen
>Paul Keinanen wrote:
>
>> A two pass assembler is definitely a practical way of doing a
>> cross-assembler. The first pass must generate the correct amount of
>> code for each instruction, in order to "detect" the locations of all
>> branch target labels in the program. In the second pass do the same
>> thing again and using the label addresses stored in the symbol table,
>> generate the correct code (especially the branch/jump instructions).
>
>I would imagine things get more complicated when you have both a short
>relative and a long call/jump addressing scheme - you don't know before
>you emit the intervening code how far away your target will be, so you
>don't know how long an instruction word you need to emit, so you don't
>know how far away your target will be...
Backward references are easy to solve, the forward references are a
bit trickier :-). Anyway, you could speculatively generate the long
forward reference in the first pass and when the forward definition of
a label is encountered, check if the forward branch is within short
distance. If it is, in the symbol table, decrement any labels after
the branch instruction by the number of bytes saved. If an optimum
result is not needed, leave it this way.
However, when moving the labels upwards after the optimised
instruction may reduce the distance from some other prior long branch
instruction, which can also be optimised.
Thus, also the location of the speculative long branch instruction and
a pointer to the symbol table entry of the target label needs also to
be stored into a temporary symbol table. Those speculative long
branch instructions have been converted to short branches can be
removed from the symbol table.
When the symbol table shuffling is done, a normal second pass can be
performed and since the locations of all labels are now fixed, it is
easy to emit either a long or short branch instruction.
Paul
rand...@earthlink.net
toby wrote:
> > ...
> > While on the subject, I would also like to point out "yet another
> > reason not to use Flex and Bison" for assemblers--
>
> Are you going to go into the reasons why one *would* want to use them?
> Or will we leave that to others?
Flex and Bison are great for small prototype languages.
They might be okay for languages where you use Flex and/or Bison for
one small part of the compiler (e.g., they way they're used in GCC,
which is huge anyway). Trying to implement a compile-time language
inside a compiler written with Flex/Bison is a major pain in the butt
and it leads to all kinds of problems and restrictions on the grammar.
Let me give a classic example of a problem in HLA. HLA allows a data
declaration like the following:
static someVarName:int32;
or, it can allow a declaration like this:
static someVarName:int32; @external;
(with the obvious [I hope] effect.)
The problem is that if you follow a declaration of this sort by a
command that must be immediately executed at compile-time, you run into
some problems with Bison's one-symbol lookahead. In particular, the
compile-time statement may execute *before* the parser finishes the
declaration. This can create problems if the operation of that
compile-time statement depends upon the declaration, e.g., something
like
static someVarName:int32;
#if (@defined( someVarName)) ... #endif
Because the declaration has not finished yet, the symbol may not be
declared at the point the @defined compile-time function executes, and
@defined incorrectly returns false.
Unfortunately, you cannot (easily, anyway) merge the grammars of the
compile-time and run-time languages together. They are truly two
separate languages that the compiler must process concurrently (and the
other solution, using a preprocessor rather than a compile-time
language has an even bigger set of problems, such as lack of access to
objects declared or used in the run-time language).
Note that if you create a hand-written parser, it's easy enough to work
around problems like this. Of course, this has nothing to do with
working sets and blowing the cache away, but it is an example of some
problems I've encountered with using Flex and Bison to write a
full-blown macro assembler.
In general, assemblers have such simple grammars that using Bison for
anything other than processing arithmetic expressions is probably a
waste of time anyway. Flex can be useful, though. Nevertheless, a
Flex-generated scanner is going to be *way* bigger than most
hand-generated scanners (though the hand-generated scanner I wrote for
HLA v2.0 is far from tiny, as it was written to be fast and uses
in-line coding to implement a hash search for assembler keywords; and
that's many thousands of lines of code; fortunately, it doesn't all
execute all the time, and most of the memory it's sitting in doesn't
get touched, so you don't have the cache pollution problems you get
with Flex and Bison's tables).
Cheers,
Randy Hyde
Jim Granville
<snip>
> In general, assemblers have such simple grammars that using Bison for
> anything other than processing arithmetic expressions is probably a
> waste of time anyway. Flex can be useful, though. Nevertheless, a
> Flex-generated scanner is going to be *way* bigger than most
> hand-generated scanners (though the hand-generated scanner I wrote for
> HLA v2.0 is far from tiny, as it was written to be fast and uses
> in-line coding to implement a hash search for assembler keywords; and
> that's many thousands of lines of code; fortunately, it doesn't all
> execute all the time, and most of the memory it's sitting in doesn't
> get touched, so you don't have the cache pollution problems you get
> with Flex and Bison's tables).
Is HLA 2.0 ready enough the OP (in: writing a simple assemler)
could use its MACRO features, to create a desired cross-assembler ?
I'd imagine a HEX output would be needed - not sure if HLA 2.0 does that ?
-jg
toby
> toby wrote:
> > > ...
> > > While on the subject, I would also like to point out "yet another
> > > reason not to use Flex and Bison" for assemblers--
> >
> > Are you going to go into the reasons why one *would* want to use them?
> > Or will we leave that to others?
>
> Flex and Bison are great for small prototype languages.
> They might be okay for languages where you use Flex and/or Bison for
> one small part of the compiler (e.g., they way they're used in GCC,
> which is huge anyway). Trying to implement a compile-time language
> inside a compiler written with Flex/Bison is a major pain in the butt
> In general, assemblers have such simple grammars that using Bison for
> anything other than processing arithmetic expressions is probably a
> waste of time anyway. Flex can be useful, though. Nevertheless, a
> Flex-generated scanner is going to be *way* bigger than most
The fact that its specification is clearer and simpler, leading to a
more reliable and maintainable program, may matter more.
> hand-generated scanners (though the hand-generated scanner I wrote for
> HLA v2.0 is far from tiny, ...; fortunately, it doesn't all
> execute all the time, and most of the memory it's sitting in doesn't
> get touched, so you don't have the cache pollution problems you get
> with Flex and Bison's tables).
Cache pollution is not an issue that 999 out of 1000 HLL programmers
should concern themselves with. (Let's not confuse the assembler itself
with issues that might arise in assembly programming...)
The OP was, iirc, asking about "writing a simple assembler". A handmade
lexer/parser is likely outside the 'simple' zone: I argue that it's
easier and quicker to internalise 'info flex' and 'info bison' than to
internalise the Dragon Book, a bunch of more recent references *and*
fret oneself silly over cache pollution, pipeline stalls, etc.
In short, not every assembler is HLA.
> Cheers,
> Randy Hyde
Rod Pemberton
<rand...@earthlink.net> wrote in message
news:1142036486....@i40g2000cwc.googlegroups.com...
>
> toby wrote:
> > > ...
> > > While on the subject, I would also like to point out "yet another
> > > reason not to use Flex and Bison" for assemblers--
> >
> > Are you going to go into the reasons why one *would* want to use them?
> > Or will we leave that to others?
>
> Flex and Bison are great for small prototype languages.
> They might be okay for languages where you use Flex and/or Bison for
> one small part of the compiler (e.g., they way they're used in GCC,
> which is huge anyway). Trying to implement a compile-time language
> inside a compiler written with Flex/Bison is a major pain in the butt
> and it leads to all kinds of problems and restrictions on the grammar.
>
I'm interested in those statements.
(Sorry upfront to those who feel this is going off-topic since this thread
is heavily cross-posted).
I've run into this exact issue with a C99 grammar. The C language of course
is LALR(1) when stripped of typedef's and preprocessor directives. I can
deal with those issues, but I'm having a problem with flex. It matches
tokens by longest length, first. This is a problem with trigraphs,digraphs,
escape sequences, universal character constants, line continuation, etc.
All these small rules that must be processed first (C99 phase 1-4,5-7) and
are messing up the grammar: interfering with string tokenization,
preprocessor tokenization etc. At this point I'm thinking about writing a
pre-pre-processor and post-pre-processor just to deal with these situations
unless someone knows of a more elegant alternative.
Rod Pemberton
PS. Replies need to make it to alt.lang.asm for me to read.
Everett M. Greene
Just what is so complicated about parsing and lexical analysis
for a simple ASM (or even a complex ASM)? Do the obvious and
get on with the job.
toby
Well, we have differing definitions of 'the job'. I don't consider
reinventing the lexer/parser wheels (which can get arbitrarily complex
and tedious to get right/read/maintain) as *necessarily* part of this
'job' of writing an assembler. Ymmv.
Clearly HLA falls outside my parameters, or far outside the 'simple'
parameter, because it has strict performance requirements -- e.g. it
has to process very large symbol tables and a complex macro syntax, and
because it's among other things (forgive me) a competitor in a pissing
contest, if you've ever frequented alt.lang.asm. It's also written by
an assembly language programmer with an assembly language programmer's
preoccupations - cache, etc.
I am simply defending an alternative approach: Don't microdesign and
micromanage, but exploit tools like flex and bison to handle the
tedious and move on to focus on 'the real job'.
At one point I compared[1] two implementations of a PAL-III (PDP-8)
assembler, one with hand-coded lexer/parser, and one using flex/bison
(mine). In the hand-coded case, the code concerned with lexing/parsing
was 692 lines, or 58% of the program. In the flex/bison case, it was a
mere 179 lines, or 11% of the program (including token definitions,
grammar, support code). It seems reasonable to infer that there is
correspondingly less to write and debug in the latter case, by a factor
of nearly four. And it ends up in a clearer, more maintainable form.
But of course this reasoning applies most strongly to "simple"
projects.
[1] http://www.telegraphics.com.au/sw/info/dpa.html
Bu
>
>>
>> About 30 years ago i wrote a (cross) assembler for the Intel 8080
>> processor (8 bit) in Basic (from Hewlett Packard).
>> I believe i have somewhere still the listing of this program.
>> If you are very interested i will look what i still have and try to
>> scan it (i do not have it in electronic format, maybe as punch paper
>> tape (:-)
>>
>Hi,
>
>I am interested in seeing your BASIC assembler; if it is on paper
>tape, I can read it (and return the tape with conversion of your
>choice). I imagine this predates RMB (Rocky Mountain Basic)?
>
>Regards,
>
>Michael Grigoni
>Cybertheque Museum
Hi Michael,
I looked up what i still have on this 30-year old project (old
sentiment from my education).
I could not find the papertape. I only found the listing (with all
rem-statements removed to speed up the process).
This listing is not really 'structured' basic so it is not realy clear
for somebody else. I do have a detailed description on the cross
assembler program (that even has a simulator and reverse assembler!)
but this is in Dutch.
So thanks for the interest but i can not make it available without a
lot of extra work (scanning etc).
Bu
Isaac Bosompem
Do you know a good Python IDE? Which one do you use yourself?
toby
Isaac Bosompem wrote:
> Hi Grant, sorry for the cross posting.
>
> Do you know a good Python IDE? Which one do you use yourself?
Eclipse will integrate nicely with Python - though I am not a Pythonist
myself (I use Eclipse for C, C++, Perl, etc).
http://wiki.python.org/moin/EclipsePythonIntegration
Grant Edwards
> Hi Grant, sorry for the cross posting.
Um, you didnt. Cross-post, that is.
> Do you know a good Python IDE? Which one do you use yourself?
Bash and an editor with a good python mode. I use Jed.
--
Grant Edwards grante Yow! Nice decor!
at
visi.com
toby
> Jim Stewart wrote:
> > toby wrote:
> >
> > > Alex wrote:
> > >
> > >>First, I would like to thank everyone for a response and advice.
> > >>...
> > Myself, I'd just define some macros for
> > MASM, the old Microsoft DOS assembler.
>
> Hi Jim,
>
> Now that is a technique I have heard of before! A gentleman Tom Evans
> clued me into this, and I hope he will allow me the liberty of quoting:
>
> There's two ways to "write an assembler in Macro 11".
I don't know why I didn't think of this before, since I've been looking
at it recently, but Mauro Persano's wicked-clever abuse of templates to
create a mock-assembler syntax for GNU Lightning is also in this vein.
I'm wishing for an excuse to try out his froofyjit:
http://freshmeat.net/projects/froofyjit/?branch_id=62508&release_id=218685
http://fzort.org/bi/sw/froofy/index.html#froofyjit
>
> --Toby
toby
> toby wrote:
> > Jim Stewart wrote:
> > > toby wrote:
> > >
> > > > Alex wrote:
> > > >
> > > >>First, I would like to thank everyone for a response and advice.
> > > >>...
> > > Myself, I'd just define some macros for
> > > MASM, the old Microsoft DOS assembler.
> >
> > Hi Jim,
> >
> > Now that is a technique I have heard of before! A gentleman Tom Evans
> > clued me into this, and I hope he will allow me the liberty of quoting:
> >
> > There's two ways to "write an assembler in Macro 11".
> > ...
>
> I don't know why I didn't think of this before, since I've been looking
> at it recently, but Mauro Persano's wicked-clever abuse of templates to
Not Mauro Persano's, but actually belonging to mncw, a.k.a. bi:
http://freshmeat.net/~mncw/
http://www.advogato.org/person/bi/
Apologies for the misattribution. And I only use the word 'abuse'
jokingly :-)
Walter Banks
to work on many instruction sets for example the National COP8 family
which has some instructions that have a pc offset, offset in the current
page and absolute addressing modes.
The algorithm essentially says start with the longest instruction form and
reduce to a shorter version of the instruction until no more instructions
in the generated code have an "in range" workable form.
The COP8 case and many others with page oriented instructions start
to reduce code using the Datamation algorithm a secondary problem
starts to show as one of the source or destination addresses slides
over a page boundary.
The freescale 6812 has an interesting similar problem where one
of the call types has a different return instruction. Then this call is
used all calls to the subroutine needs to be the same type. In
automatically generated code we always want to generate the
shortest form but if any call cannot reach, all the calls need to be
changed and all the returns for the function must be changed as
well.
w..
Tauno Voipio
> The Datamation algorithm (Sorry I don't have the exact reference) fails
> to work on many instruction sets for example the National COP8 family
> which has some instructions that have a pc offset, offset in the current
> page and absolute addressing modes.
>
> The algorithm essentially says start with the longest instruction form and
> reduce to a shorter version of the instruction until no more instructions
> in the generated code have an "in range" workable form.
>
> The COP8 case and many others with page oriented instructions start
> to reduce code using the Datamation algorithm a secondary problem
> starts to show as one of the source or destination addresses slides
> over a page boundary.
>
> The freescale 6812 has an interesting similar problem where one
> of the call types has a different return instruction. Then this call is
> used all calls to the subroutine needs to be the same type. In
> automatically generated code we always want to generate the
> shortest form but if any call cannot reach, all the calls need to be
> changed and all the returns for the function must be changed as
> well.
I left out the paged architectures (PDP-8 & co from the years gone),
they belong to the same place as dinosaurs and Fortran - history.
The algorithm is extensible to the paged case, but as long as
there are several separately translated modules, the code produced
is sub-optimal.
In any case, the paged architectures are prone to page-zero overflow.
David Brown
> Hi Grant, sorry for the cross posting.
>
> Do you know a good Python IDE? Which one do you use yourself?
>
Idle is a simple one that is part of most Python installations. For
starting out, or for quick work, it's probably the fastest and easiest.
SPE and Eric are Python-specific IDEs.
Boa Constructor is a Python IDE and wxPython designer.
Most "big" editors are also IDEs, and can work with Python - Eclipse,
jedit, (x)emacs, vim, etc.
toby
> The Datamation algorithm (Sorry I don't have the exact reference) fails
> to work on many instruction sets for example the National COP8 family
> which has some instructions that have a pc offset, offset in the current
> page and absolute addressing modes.
>
> The algorithm essentially says start with the longest instruction form and
> reduce to a shorter version of the instruction until no more instructions
> in the generated code have an "in range" workable form.
"Relaxation" method comes to mind. The Transputer was an interesting
case, since you could build offsets of arbitrary magnitude with its
general prefix mechanism. (i.e. There were an arbitrary number of jump
instruction lengths, not just short and long.)
rand...@earthlink.net
toby wrote:
>
> Clearly HLA falls outside my parameters, or far outside the 'simple'
> parameter, because it has strict performance requirements
Hmm... That's the first time I've heard anyone claim HLA has "strict"
performance requirements. :-)
In matter of fact, HLA is one of the slower assemblers because
performance was never a design criterion for HLA v1.x (which is a
prototype used to develop the language).
> -- e.g. it
> has to process very large symbol tables and a complex macro syntax, and
> because it's among other things (forgive me) a competitor in a pissing
> contest, if you've ever frequented alt.lang.asm.
Performance has nothing to do with the "pissing contest" over in ALA.
On the performance side, only a few assemblers (e.g., NASM) are slower
than HLA.
> It's also written by
> an assembly language programmer with an assembly language programmer's
> preoccupations - cache, etc.
It's written in Flex, Bison, and C. As I've pointed out a couple of
times in this thread. Anyone concerned about "assembly language
preoccupations", especially the cache, would steer clear of Flex and
Bison. For reasons I've pointed out in this thread.
Boy, you seem to be a bit confused about what HLA is.
>
> I am simply defending an alternative approach: Don't microdesign and
> micromanage, but exploit tools like flex and bison to handle the
> tedious and move on to focus on 'the real job'.
That was exactly the approach I chose to use when developing the
prototype for the HLA language. I lived to regret that choice. Granted,
HLA has some sophisticated features that make it a bit more complex
than a "simple assembler", but is exactly those types of features for
which Flex and Bison are supposed to be ideal. Alas, the moment you
want to do something like macros, Flex and Bison (well, especially
Bison) become anchors, holding back the project.
>
> At one point I compared[1] two implementations of a PAL-III (PDP-8)
> assembler, one with hand-coded lexer/parser, and one using flex/bison
> (mine). In the hand-coded case, the code concerned with lexing/parsing
> was 692 lines, or 58% of the program. In the flex/bison case, it was a
> mere 179 lines, or 11% of the program (including token definitions,
> grammar, support code).
> It seems reasonable to infer that there is
> correspondingly less to write and debug in the latter case, by a factor
> of nearly four.
That is an incredible generalization that you cannot make on the basis
of such a small project.
> And it ends up in a clearer, more maintainable form.
> But of course this reasoning applies most strongly to "simple"
> projects.
Which, alas, have a habit of growing. And Bison parsers don't scale up
well.
Cheers,
Randy Hyde
toby
> toby wrote:
>
> >
> > Clearly HLA falls outside my parameters, or far outside the 'simple'
> > parameter, because it has strict performance requirements
>
> Hmm... That's the first time I've heard anyone claim HLA has "strict"
> performance requirements. :-)
>
> In matter of fact, HLA is one of the slower assemblers because
> performance was never a design criterion for HLA v1.x (which is a
> prototype used to develop the language).
>
> > -- e.g. it
> > has to process very large symbol tables and a complex macro syntax, and
> > because it's among other things (forgive me) a competitor in a pissing
> > contest, if you've ever frequented alt.lang.asm.
>
> Performance has nothing to do with the "pissing contest" over in ALA.
> On the performance side, only a few assemblers (e.g., NASM) are slower
> than HLA.
>
>
> > It's also written by
> > an assembly language programmer with an assembly language programmer's
> > preoccupations - cache, etc.
>
> It's written in Flex, Bison, and C. As I've pointed out a couple of
> times in this thread. Anyone concerned about "assembly language
> preoccupations", especially the cache, would steer clear of Flex and
> Bison. For reasons I've pointed out in this thread.
>
> Boy, you seem to be a bit confused about what HLA is.
Yes, I apologise for my ignorance of its implementation. I had gathered
from your earlier posts that you had rejected Flex/Bison early on. I
gather you will not use them in future rewrites?
>
>
> >
> > I am simply defending an alternative approach: Don't microdesign and
> > micromanage, but exploit tools like flex and bison to handle the
> > tedious and move on to focus on 'the real job'.
>
> That was exactly the approach I chose to use when developing the
> prototype for the HLA language. I lived to regret that choice. Granted,
> HLA has some sophisticated features that make it a bit more complex
> than a "simple assembler", but is exactly those types of features for
> which Flex and Bison are supposed to be ideal. Alas, the moment you
> want to do something like macros, Flex and Bison (well, especially
> Bison) become anchors, holding back the project.
I would agree with that. But again, maybe a macro assembler (especially
one with HLA's design goals) is outside the ambit of 'simple'.
>
> >
> > At one point I compared[1] two implementations of a PAL-III (PDP-8)
> > assembler, one with hand-coded lexer/parser, and one using flex/bison
> > (mine). In the hand-coded case, the code concerned with lexing/parsing
> > was 692 lines, or 58% of the program. In the flex/bison case, it was a
> > mere 179 lines, or 11% of the program (including token definitions,
> > grammar, support code).
> > It seems reasonable to infer that there is
> > correspondingly less to write and debug in the latter case, by a factor
> > of nearly four.
>
> That is an incredible generalization that you cannot make on the basis
> of such a small project.
I'm only talking about small projects, here. PAL-III is a strictly
defined syntax: It can't grow, and it doesn't have macros. This is only
a case study.
rand...@earthlink.net
Branch displacement optimization is provably NP-Complete. And this is
true whether there are only two branch sizes or an arbitrary number of
them. This means that the best known solution requires, worst case,
O(2**n) passes over the program (where n is the number of branches in
the program) to produce the optimally sized program.
Some assemblers, such as MASM, Gas, and FASM on the x86 start with long
branches and successively reduce their sizes on each pass (as legal)
until they make a pass during which no branch sizes change. This does
*not* produce, guaranteed, the minimal sized program. Indeed, it's
better in most cases to start off assuming the branches are short and
extend them as necessary. Even so, this scheme is not guaranteed to
produce the minimum sized program.
In fact, a "greedy" algorithm (make all the branches that can be made
short, short) is not guaranteed to produce the smallest program. You
can come up with some (synthetic) examples where making one particular
branch longer, that could be shorter, and the resulting program,
overall, consumes less bytes (think about other objects in the program,
besides branches, whose size depends upon the span of two labels).
Nevertheless, a "relaxation" or refinement approach, while not
guaranteed to be optimal, still produces very good results. It may
take an arbitrary number of passes, though. Two or three is rarely
enough for a complex program. I once generated a synthetic test file
and FASM made nearly 2,000 passes over the source file during
optimization.
Cheers,
Randy Hyde