【笔记】从零开始手搓编程语言（二）

2025-11-18

字数统计: 3.7k字 | 阅读时长≈ 15分

来自瑞典Linköping University的Filip Strömbäck老师来我们组访问，进行的一个名为Bootstrapping a Programming Language from Nothing的Seminar。本文的内容为基于此材料的个人理解。

在上一篇中我们手撸了一个十六进制编码器，可以支持解析文本文件，自动小端序输出，支持写注释。现在，至少我们不用一个个数的敲机器码了。

接下来要解决的是另一个反人类的事情：手动链接。在写上次的程序时，我们需要把每个跳转指令的目标地址一个个的掰手指数出来，这很麻烦。更麻烦的是，当你想修改程序导致字节数变化之后，这些地址都会变，完了要重新数重新填。于是，这次我们来解决这个问题，摆脱手动链接。

Week 2: Labels & Strings

为了实现这一点，我们在上次的HEX语言的基础上进行改进，可以支持代码中的地址用符号表示，并可以以绝对/相对地址模式引用它们。

设计

首先要注意不管怎么说，我们现在手上的工具还很有限，我们的语言设计要尽可能易于实现。

这次我们的语言对应一个状态机，它会记录当前的虚拟地址和文件偏移量，每读到一个十六进制数都会更新它们。

首先我们需要支持定义label，为了简化实现我们以冒号后面跟label名为格式：例如定义looplabel就写成:loop，这样读到:我们就可以进入对应的逻辑了。读到label时，我们只需要把当前状态中的虚拟地址和文件偏移量存起来以供后续引用即可。
然后是引用的方法。我们用=loop表示引用loop的绝对地址，而-loop表示引用相对地址，也就是loop的地址减掉这个引用的地方的地址。
我们还提供$loop来引用loop位置的文件偏移量。
为了提供灵活性我们设计000010000@来表示将当前状态的虚拟地址设置成@前面的数，也就是0x10000。同样，这个顺序也是为了简化实现。

有了这些功能可以简化很多我们之前数字节的工作。首先是跳转语句可以写成：

1
2
3

:loop
...
E9 -loop                ;; jmp loop

其次，在访问全局变量的内存地址时：

1 2	0001000c@ :curn ; define a variable curn at 0x1000c C7 05 =curn 00000000 ; mov [curn], 0

最后，在填写ELF头时，文件大小我们可以通过在文件末尾插入一个label然后引用它的文件偏移量来自动得出：

1
2
3

$EOF	;; the file size
...
:EOF	;; put this line at the end of the file

看起来很不错！那怎么实现呢？

实现

首先这个状态机要记录当前读到的数字curnum，当前的文件偏移量fileoffset，当前的虚拟地址viraddr。

首先我们会发现，正如上面的EOF例子，label是可以先使用后定义的（所有的向后跳转也是一样），这意味着我们没办法单pass从头到尾扫一遍解决这个问题。于是，我们第一遍先把所有的十六进制数都输出到一个buffer，所有的需要填label的地方先空出来，并且第一遍我们把所有的label所在地的地址信息都收集起来。全部读完之后，再根据每个需要填label的地方，填上对应的地址，就大功告成了。也就是说，在内存里我们需要一个输出buffer，一个label表负责记录所有程序中的label和地址，以及一个fixup表负责记录每个需要填写的地方供第二遍填写的时候使用。

基于上次的代码逻辑，主循环是不变的，只是对于数字我们先输出到buffer而不是标准输出。主循环的其它情况：

当读到@时，此时curnum应该已经有一个数字了，将viraddr置为curnum，并且不输出数字。
当读到:时，读取后面的label，随后把当前的viraddr和fileoffset记入label表。
当读到=时，读取后面的label，在输出buffer留4字节的空位，并在fixup表注册当前的buffer指针、这个label需要写入绝对地址。
当读到-时，读取后面的label，在输出buffer留4字节的空位，并在fixup表注册当前的buffer指针、这个label需要写入相对地址。
当读到$时，读取后面的label，在输出buffer留4字节的空位，并在fixup表注册当前的buffer指针、这个label需要写入文件偏移量。

大概思路就是这样了。

实现细节

因为实现起来很麻烦，所以我们能简化就简化。

首先要解决的是label的表示问题，因为字符串实在太麻烦了。反正是给自己用的，首先限制label最多4个字符，然后只能使用大小写字母。然后我们就观察到，字母们的ASCII分布在0x40到0x70之间，他们的高字节为0100, 0101，0110，0111，前面的01是相同的，我们直接抹掉。这样我们就可以用6bit表示一个字母，4个字符的label就是一个24bit的数。这是一个完美哈希，我们直接用这个数做label表的下标，label表每个entry记录虚拟地址和文件偏移量两个32位数共8字节，整个哈希表开64MiB就够了。更好的是，因为是哈希表，所以我们可以很方便的根据label找到对应存放它虚拟地址或是文件偏移量的地方，这是确定的！

有了label表，fixup表就很方便了，每个entry记录两个指针：要输出到的buffer地址，和引用的label表中对应的地址，这个是确定的。

最后一个小细节：在fixup的时候，填绝对地址的时候很简单，而填相对地址的时候我们还要减去那个引用处的地址。既然如此我们为什么不在一开始就减去呢？在遇到=时，在buffer处填0；在-时，则填写当前地址取负。这样在fixup时，在目标buffer地址处加上对应的地址就好啦。

于是我们可以耐心写出汇编程序：

global _start

section .data
fileoffset:    dd 0        ; fileoffset, the next empty byte of out
viraddr:       dd 0        ; 
curnum:        dd 0        ; 
fixupidx:      dd 0        ; index of the fixup table

section .bss
out:  resb 0x20000   
label:  resb 0x20000   
fixup:  resb 0x8000000  

section .text

_start:
    ;; edi: bytes rea
    mov edi, 0
    jmp loop

clearcomment:
    call readbyte
    cmp eax, 0x0A       ;; if ch != '\n' goto clear
    jne clearcomment

loop:
    mov ebp, 0          ;; loop variable: read number twice
    
startread:
    call readbyte

    cmp eax, 0x3B       ;; if ch == ';' goto clear
    je clearcomment

    cmp eax, 0x40       ;; if ch != '@' goto notat
    jne notat
    mov eax, [curnum]   ;; viraddr <- curnum
    mov [viraddr], eax
    mov dword [curnum], 0
    mov edi, 0          ;; size of curnum = 0 !!
    jmp loop

notat:
    cmp eax, 0x3A           ;; if ch != ':' goto notcolon
    jne notcolon

    call readlabel          ;; the result hash is in esi
    shl esi, 3              ;; an entry has 8 bytes
    mov eax, [fileoffset]   ;; label[hash].file <- fileoffset 
    mov [esi+label], eax    
    mov eax, [viraddr]      ;; label[hash].vir <- viraddr
        
    mov [esi+label+4], eax  
    jmp loop

notcolon:
    mov ecx, eax            ;; here we handle '=' and '-'
    push eax                ;; save eax == ch
    xor ecx, 0x2D
    and ecx, 0xFFFFFFEF
    cmp ecx, 0
    jne not2D3D             ;; if ch != 2D or 3D

    call readlabel
    mov eax, [fixupidx]     ;; fixup[fixupidx].out <- fileoffset
    mov ebx, [fileoffset]
    mov [eax+fixup], ebx

    shl esi, 3              ;; vaddridx of hash 
    add esi, label+4        
    add eax, 4              ;; fixup[fixupidx].label <- vaddridx
    add [eax+fixup], esi
    
    add dword [fixupidx], 8 ;; point to the next entry

    ;; if ch == 0x2D, relative substract from output in advance
    pop eax
    xor eax, 0x2D           ;; now eax is either 3D or 2D
    shr eax, 4              ;; 0 or 1
    sub eax, 1              ;; mask
    mov ebx, [viraddr]      ;; ebx <- viraddr + 4
    add ebx, 4
    and ebx, eax            ;; assign only when eax == 2D
    mov eax, [fileoffset]
    sub [eax+out], ebx

    add dword [fileoffset], 4       ;; point to the next number
    add dword [viraddr], 4          ;; update viraddr!!
    jmp loop

not2D3D:
    cmp eax, 0x24           ;; if ch != '$' goto notdollar
    jne notdollar

    call readlabel
    mov eax, [fixupidx]     ;; fixup[fixupidx].out <- fileoffset
    mov ebx, [fileoffset]
    mov [eax+fixup], ebx

    shl esi, 3              ;; fileaddridx of hash 
    add esi, label
    add eax, 4              ;; fixup[fixupidx].label <- fileidx
    add [eax+fixup], esi
    
    add dword [fixupidx], 8          ;; point to the next entry
    add dword [fileoffset], 4       ;; point to the next number
    add dword [viraddr], 4          ;; update viraddr!!
    jmp loop

notdollar:
    ;; the origin logic of stage 1
    cmp eax, 0x20           ;; if ch <= 0x20(white) goto emit
    jbe emit

    cmp eax, 0x40           ;; if ch < 0x40 (digits) goto mask
    jb mask

    sub eax, 0x7            ;; ch -= 7

mask:
    and eax, 0xF
    shl dword [curnum], 4         ;; esi = (esi << 4) | eax
    or [curnum], eax
    add ebp, 1
    cmp ebp, 2
    jb startread            ;; 2 digits = 1 byte
    add edi, 1              ;; byte read + 1
    jmp loop

emit:
    cmp edi, 0              ;; if it reads nothing
    je loop

    mov eax, [fileoffset]   ;; write 1 byte
    mov ebx, [curnum]
    mov [eax+out], bl       ;; out[fileoffset] = curnum
    shr dword [curnum], 8

    add dword [fileoffset], 1     ;; point to next byte
    add dword [viraddr], 1        ;; update viraddr

    sub edi, 1              ;; count byte to emit
    cmp edi, 0
    ja emit
    jmp loop

readbyte:   ; read a byte, return in eax
    push 0
    mov eax, 3
    mov ebx, 0
    mov ecx, esp
    mov edx, 1
    int 0x80

    ; HACK: if read EOF, do fixup
    cmp eax, 0
    je done

    ;; get char
    pop eax
    ret

readlabel:          ;; read a label, get the hash value
                    ;; return in esi
                    ;; a label is up to 4 bytes
    mov esi, 0
inner:
    call readbyte

    cmp eax, 0x20   ;; if ch == is white goto iswhite
    jbe iswhite

    and eax, 0x3F
    shl esi, 6      ;; esi = (esi << 6) | eax
    or esi, eax
    
    jmp inner

iswhite:
    ret
    
done:                   ;; after reading fill fixup
    mov edi, fixup      ;; edi: index, base
    mov ecx, [fixupidx] ;; ecx: boundary
    add ecx, fixup

fixuploop:
    mov eax, [edi]      ;; eax <- output pointer
    mov ebx, [edi+4]    ;; ebx <- label pointer

    mov ebx, [ebx]
    add [eax+out], ebx  ;; [outputptr] += [labelptr]

    add edi, 8          ;; point to the next entry
    cmp edi, ecx        ;; if edi < fixupidx goto fixuploop
    jb fixuploop

output:                 ;; then output
    mov eax, 4          ;; use one write call to output everything
    mov ebx, 1
    mov ecx, out
    mov edx, [fileoffset]
    int 0x80

    ;; exit(0)
    mov eax, 1
    mov ebx, 0
    int 0x80

里面还有一个小细节：

在=和-的逻辑中唯一的区别是-需要在buffer处写当前地址的负，而=什么都不做。而注意到=和-的ASCII分别是0x3D和0x2D，二进制只差1位。所以我们可以很方便的利用它做一个掩码，就可以实现只在-的时候写入负数了。这样可以省掉一个跳转指令，因为填起来很麻烦！

流程：正攻vs.邪道

和上次一样，我们依然没有汇编器。正攻的流程是，我们还是要把上面的汇编代码给手敲成机器码，我们可以用上次的工具，省掉直接敲二进制的工作了。不过链接数字节这一步是省不了的。这样得到了二进制，再慢慢调试吧……其中的每一步都可能出错！

于是，我还是先用现成的汇编器得到了二进制，然后调试得到了至少保证正确的汇编代码。然后下一步仍然是要手敲机器码。不过因为这次我们开发了新语言，我们可以先用我们的新语言的语法来写，也就是指令是十六进制，而地址是带符号的版本，得到stage2.hex。

此时，这个文件仍然没办法使用，因为我们理论上还没有它的第一个解析器！不过既然我们已经用邪道得到了一个汇编写的解析器了，我们为什么不先利用一下它呢？于是我用它输入stage2.hex来测试一下，得到了对应的二进制，然后反汇编出来做参考来检查这个手敲机器码的过程有没有出错。事实证明还是错了挺多地方的，主要是寻址指令的地方。

好了，现在我们用了一些小手段确保这个源码也没错之后，最后一步就是手动链接了。这个代码太长了，要掰手指数字节还是摇了我吧！于是我仍然参考反汇编的结果，把要填地址的地方一个个填了进去，过程中同样可以用那个“黄金版本”来检查有没有填错。

总之不管怎么说，总算得到了一个纯手写的纯手链接的十六进制文件stage2-linked.hex。至此，就可以用上次的工具转成二进制了。我们可以验证一下结果：

先用stage1把源码stage2-linked.hex转成二进制stage2，然后这个程序应该能编译我们带符号版本的源码stage2.hex。最后得到的东西应该是一样的。

1
2
3

stage1 < stage2-linked.hex > stage2
stage2 < stage2.hex > stage2_
diff stage2 stage2_

应用：字符串

现在我们的“开发体验”已经大大提升了：我们可以放心修改源码、大胆使用跳转指令不用怕重新填写了！现在我们在此基础上可以稍微再改进一下这个源码，增加支持字符串的功能：

"xxx"双引号代表字符串，字符串里的内容作为ASCII直接输出到buffer即可
\为转义符，这样可以输出引号本身"\""，反斜杠本身也同理"\\"，为了简化实现，这是唯二支持转移的符号

实现起来也非常简单：

while (true) {
    int char = read_char();
    if (char == '"') return;
    if (char == '\\') char = read_char();
    output(char);
}

开发体验很好了，我们可以直接修改源码，修改得到stage3.hex：

;; after reading a byte
:ntdl
81 F8 00000022          ;; cmp eax, 0x22           ;; if ch == "\"" goto readstring
0F 84 -rdst             ;; je readstring

...
:rdst                   ;; read a string
E8 -rdby                ;; call rdby
    
81 F8 00000022          ;; cmp eax, 0x22           ;; if ch == "\"" goto loop
0F 84 -loop             ;; je loop

81 F8 0000005C          ;; cmp eax, 0x5C           ;; if ch == "\\" read another
0F 85 -ptcr             ;; jne ptcr
E8 -rdby                ;; call rdby

:ptcr
8B 1D =foff             ;; mov ebx, [foff]   ;; out[foff] <- ch
88 83 =outp             ;; mov [ebx+outp], eax
81 05 =foff 00000001    ;; add dword [foff], 1     ;; foff++; vadr++
81 05 =vadr 00000001    ;; add dword [vadr], 1
E9 -rdst                ;; jmp rdst
...

最后测试一下：

首先我们可以利用新的字符串功能重写这个代码得到stage3-str.hex：

;; after reading a byte
:ntdl
81 F8 "\"" 000000          ;; cmp eax, 0x22           ;; if ch == "\"" goto readstring
0F 84 -rdst             ;; je readstring
...

首先我们用刚刚的stage2程序来编译stage3.hex，得到的二进制应该可以支持新的语法stage3-str.hex。这两个得到的程序应该是一样的：

1
2
3

stage2 < stage3.hex > stage3
stage3 < stage3-str.hex > stage3_
diff stage3 stage3_

差不多完成了，现在我们可以写比较体面的代码了。（？）

Bonus

我们有一个还算体面的语言了。为了进一步提高开发体验，还可以再简简单单加个高亮。vscode安装highlight插件，然后在settings.json中配置：

{
  "highlight.regexFlags": "gm",
  "highlight.regexes": {
    // 双分号 ;; 注释 → 粗体绿色
    "(;;.*)": {
      "filterFileRegex": ".*\\.hex$",
      "decorations": [
        {
          "color": "#008000",
          "fontWeight": "bold"
        }
      ]
    },
    // 注释 ; 到行尾
    "(;.*)": {
      "filterFileRegex": ".*\\.hex$",
      "decorations": [
        {
          "color": "#008000",
          "fontStyle": "italic"
        }
      ]
    },
    // 字符串 "..."，单行，处理转义
    "(\"([^\"\\\\]|\\\\.)*\")": {
      "filterFileRegex": ".*\\.hex$",
      "decorations": [
        {
          "backgroundColor": "#FFFF99",
          "color": "#0000FF"
        }
      ]
    },
    // 定义 label :label
    "(:[A-Za-z]+)": {
      "filterFileRegex": ".*\\.hex$",
      "decorations": [
        {
          "color": "#00bba6",
          "fontWeight": "bold"
        }
      ]
    },
    // 使用 label $,=,-
    "([$=-][A-Za-z]+)": {
      "filterFileRegex": ".*\\.hex$",
      "decorations": [
        {
          "color": "#FF4500",
          "fontWeight": "bold"
        }
      ]
    }
  }
}

本文作者： Frankenstein
本文链接： https://salty-frankenstein.github.io/blog/2025/11/18/【笔记】从零开始手搓编程语言（二）/
版权声明： 本博客文章采用 CC BY-SA 4.0 协议进行许可。转载请注明作者与原文链接。