10

I'm very new to the concept of writing an assembler and even after reading a great deal of material, I'm still having difficulties wrapping my head around a couple of concepts.

  1. What is the process to actually break up a source file into tokens? I believe this process is called lexing, and I've searched high and low for a real code examples that make sense, but I can't find a thing so simple code examples very welcome ;)

  2. When parsing, does information ever need to be passed up or down the tree? The reason I ask is as follows, take:

    LD BC, nn

It needs to be turned into the following parse tree once tokenized(???)

  ___ LD ___
  |        |
 BC        nn

Now, when this tree is traversed it needs to produce the following machine code:

01 n n

If the instruction had been:

LD DE,nn

Then the output would need to be:

11 n n

Meaning that it raises the question, does the LD node return something different based on the operand or is it the operand that returns something? And how is this achieved? More simple code examples would be excellent if time permits.

I'm most interested in learning some of the raw processes here rather than looking at advanced existing tools so please bear that in mind before sending me to Yacc or Flex.

3 Answers 3

10

Well, the structure of the tree you really want for an instruction that operates on a register and an memory addressing mode involing an offset displacement and an index register would look like this:

    INSTRUCTION-----+
    |      |        |
  OPCODE  REG     OPERAND
                  |     |
                OFFSET  INDEXREG

And yes, you want want to pass values up and down the tree. A method for formally specifying such value passing is called "attribute grammars", and you decorate the grammar for your langauge (in your case, your assembler syntax) with the value-passing and the computations over those values. For more background, see Wikipedia on attribute grammars.

In a related question you asked, I discussed a tool, DMS, which handles expression grammars and building trees. As language manipulation tool, DMS faces exactly these same up-and-down the tree information flows issues. It shouldn't surprise you, that as a high-end language manipulation tool, it can handle attribute grammar computations directly.

12
  • 1
    This was intended to be illustrative of the trees he needs to build, rather than matching a specific Z80 instrution. I coded a LOT of Z80 assembler back in the 1980s; I may know more about it than you think.
    – Ira Baxter
    Aug 23, 2009 at 20:36
  • Then demonstrate your knowledge. Have you written a Z80 assembler? I Haven't, but I have written 8080 and 6809 assemblers, and your advice seems to me to be dead wrong.
    – anon
    Aug 23, 2009 at 20:48
  • Your experience is probably different than mine. I've coded assemblers for the Collins 8311 (circa 1968), a 12 and 16 bit machines that didn't make it commercially so you havent heard of them, microcode assemblers, and the 6809 assembler you saw in the other message. I've also built a variety of compiler front ends(check out my bio information and website). My early assemblers were built by ad hoc means and worked. Stuff since the 80s I've built using lexers and parsers because it is far easier to specify, to maintain, to extend, you name it.
    – Ira Baxter
    Aug 23, 2009 at 21:07
  • 2
    When recursive descent works, it works great. But it only works well on modest sized grammars that don't change fast (when you build DSLs sometimes the grammar does change fast) and which don't require any lookahead or any type information to resolve the parse (your beloved C++ has a bad lookahead problem here). When you aren't in that window, more powerful (read "full context free") parsing engines are better, and explicit specifications of the full grammar make it a lot easier to revise and maintain. And once you have such machinery, its easy to kill gnats, too, and you should.
    – Ira Baxter
    Aug 23, 2009 at 22:34
  • 1
    Nested structures and trees are simply isomorphic representations. So, its take your choice. The good thing about the tree is that you can get it directly from the parser. If you want to convert it to nested structures you can do that, and it might make navigation of the nested structures seem simpler. But, to do the conversion, you have to walk the tree anyway, so you already have navigation. If you access the nested structures heavily, they will win out in performance... but surely when building an assembler you are only going to consult each "field" of the instruction once.
    – Ira Baxter
    Feb 1, 2019 at 22:03
7

It is not necessary to build a parse tree. Z80 op codes are very simple. They consist of the op code and 0, 1 or 2 operands, separated by commas. You just need to split the opcode up into the (maximum of 3) components with a very simple parser - no tree is needed.

6
  • What about relative memory addresses> surely some kind of symbolic tree is needed for this? perhaps even a table
    – Darknight
    Aug 20, 2009 at 10:21
  • The questioner was asking about parsing the OP codes. You certainly need a symbol table to assist in creating the assembler's actual machine code output, but that is a completely different issue.
    – anon
    Aug 20, 2009 at 10:23
  • @Darknight: Would there still not be a valid point to creating a parse tree. For example, other occurrences could play a part such as here are some ASM code strings that have variations in the syntax: Labels, Comments, Brackets, Global Variables, .DB, .DS, .DW Would these not also become more simplified if a parse tree was used? @Neil: Could you elaborate? Regards, GP
    – Gary Paluk
    Aug 20, 2009 at 12:59
  • 2
    @Gary You could do that if you want to complicate your life. I've written a couple of assemblers (though not one for the Z80) and they are normally easily implemented via a simple tokenising scheme (as I suggested in my answer) and an expression evaluator to evaluate address and other expressions. The expression evlauator may use a tree (though a stack based one is enough in my experience) but there is no need to make the parse tree your basic data structure.
    – anon
    Aug 20, 2009 at 13:14
  • @Neil Thanks for your feedback... You don't happen to have a code example do you? Would probably clarify alot! :)
    – Gary Paluk
    Aug 20, 2009 at 13:35
3

Actually, the opcodes do have not a byte base, but an octal base. The best description I know is DECODING Z80 OPCODES.

1
  • Ya, right on. Octal lets you translate directly, and a recursive call can deal with the offset registers. One does not need to build a syntax tree at all. Each instruction and be directly mapped.
    – EvilTeach
    Jul 29, 2011 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.