第一个例子是实现扫描器，扫描代码字符流把代码切割成一个个token对象。
第二个例子基于第一个的扫描器实现转换器，把扫描的token转换得到抽象语法树(AST)，这时候还没考虑代码优先级。
第三个例子引入pratt算法按得到按优先级的AST。
到第三个例子时候都还是遍历AST树。按对应操作符用代码计算结果，和编译的机器码相差甚远。到这个例子就有那么点编译器的意思了。这个例子把AST树遍历的节点操作转换得到X86汇编代码。
编译和测试效果
[root@zlzlinux 04_Assembly]#
[root@zlzlinux 04_Assembly]# ls
cg.c comp1 data.h decl.h defs.h expr.c gen.c input01 input02 interp.c main.c Makefile out.s Readme.md scan.c tree.c
[root@zlzlinux 04_Assembly]# rm comp1
rm：是否删除普通文件 'comp1'？y
[root@zlzlinux 04_Assembly]# make
cc -o comp1 -g cg.c expr.c gen.c interp.c main.c scan.c tree.c
[root@zlzlinux 04_Assembly]# ls
cg.c comp1 data.h decl.h defs.h expr.c gen.c input01 input02 interp.c main.c Makefile out.s Readme.md scan.c tree.c
[root@zlzlinux 04_Assembly]# cat input01
2 + 3 * 5 - 8 / 3
[root@zlzlinux 04_Assembly]# ./comp1 input01
############################AST Tree#########################################
-
/ \
/ \
/ \
/ \
/ \
/ \
/ \
+ /
/ \ / \
/ \ / \
/ \ / \
2 * 8 3
/ \
3 5
############################AST Tree#########################################
ExeResult:15
############################out.s#########################################
.text
.LC0:
.string "%d\n"
printint:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl %edi, -4(%rbp)
movl -4(%rbp), %eax
movl %eax, %esi
leaq .LC0(%rip), %rdi
movl $0, %eax
call printf@PLT
nop
leave
ret
.globl main
.type main, @function
main:
pushq %rbp
movq %rsp, %rbp
movq $2, %r8
movq $3, %r9
movq $5, %r10
imulq %r9, %r10
addq %r8, %r10
movq $8, %r8
movq $3, %r9
movq %r8,%rax
cqo
idivq %r9
movq %rax,%r8
subq %r8, %r10
movq %r10, %rdi
call printint
movl $0, %eax
popq %rbp
ret
############################out.s#########################################
[root@zlzlinux 04_Assembly]#
AST树对应汇编部分解释，前后的是固定部分，这个汇编就是按下面树组装的,采用左-右-中遍历
############################AST Tree#########################################
-
/ \
/ \
/ \
/ \
/ \
/ \
/ \
+ /
/ \ / \
/ \ / \
/ \ / \
2 * 8 3
/ \
3 5
############################AST Tree#########################################
//遍历2加载数字2到空闲寄存器r8
movq $2, %r8
//然后遍历2右树，发现有子树就遍历3，加载3到空闲寄存器r9
movq $3, %r9
//然后遍历到5，加载数字5到空闲寄存器r10
movq $5, %r10
//然后遍历到乘号，组装乘法汇编，这时候r9释放了
imulq %r9, %r10
//然后遍历到加号组装加法汇编，把r8结果加入r10,r8释放了
addq %r8, %r10
//然后扫描到数字8，申请可用寄存器就是被释放的r8了
movq $8, %r8
//然后扫描到数字3，申请可用寄存器就是被释放的r9了
movq $3, %r9
//然后遍历到除号，组装除法汇编
movq %r8,%rax
cqo
idivq %r9
//除的结果放到r8，r9释放了
movq %rax,%r8
//然后遍历到根的减号，组装减法汇编，r8释放了
subq %r8, %r10
通过上面的AST树遍历理解汇编就很自然了。什么时候用什么寄存器都不是刻意做的。而是cg.c里有数组标识了几个cpu寄存器可用性。放数组就从可用的里面返回个，指令操作完成后就把不需要的寄存器可用性释放。如此就得到一个看着挺玄的汇编寄存器使用。我以前一直奇怪生成汇编怎么知道什么时候用什么寄存器，怎么使用寄存器不发生冲突的。对这些的疑惑都可以从cg.c逻辑得到解答。不把树打印出来理解普拉特算法和遍历AST树生成汇编还挺难理解的。
gen.c用来实现和平台无关的编译逻辑，传入AST根到generatecode方法，该方法调用对应平台的cgpreamble方法组装汇编程序前面固定部分。调用genAST递归遍历AST树，然后针对每个节点调用对应平台的汇编生成代码方法。调用cgprintint拼接调用打印输出的汇编代码，然后调用cgprintint拼接汇编尾部代码。
#include "defs.h"
#include "data.h"
#include "decl.h"
// Generic code generator
// Copyright (c) 2019 Warren Toomey, GPL3
/*
这里面放编译AST树的逻辑。借助递归遍历整棵AST树，调用每个操作符的汇编本地化代码得到AST树对应的汇编，每个操作都是返回的结果寄存器的索引。
通过用generatecode整合了汇编前后固定部分和打印输出调用部分。
*/
// 编译AST树，返回结构寄存器索引
// Given an AST, generate
// assembly code recursively
static int genAST(struct ASTnode* n) {
int leftreg, rightreg;
// Get the left and right sub-tree values
//递归编译左子树
if (n->left)
leftreg = genAST(n->left);
//递归编译右子树
if (n->right)
rightreg = genAST(n->right);
//根据操作符组装对应汇编
switch (n->op) {
//组织加法汇编，返回结果寄存器
case A_ADD:
return (cgadd(leftreg, rightreg));
//组织减法汇编，返回结果寄存器
case A_SUBTRACT:
return (cgsub(leftreg, rightreg));
//组织乘法汇编，返回结果寄存器
case A_MULTIPLY:
return (cgmul(leftreg, rightreg));
//组织除法汇编，返回结果寄存器
case A_DIVIDE:
return (cgdiv(leftreg, rightreg));
//组织加载整数汇编，返回结果寄存器
case A_INTLIT:
return (cgload(n->intvalue));
default:
fprintf(stderr, "Unknown AST operator %d\n", n->op);
exit(1);
}
}
//遍历编译AST树得到汇编代码
void generatecode(struct ASTnode* n) {
//结果寄存器所有
int reg;
//组装汇编前面固定部分
cgpreamble();
//组装AST语法树的汇编
reg = genAST(n);
//组装打印的汇编
cgprintint(reg);
//组装汇编的结尾
cgpostamble();
}
cg.c实现特定平台的汇编生成逻辑，这里给程序生成汇编一共用了四个可用寄存器r8,r9,r10,r11，用freereg数组记录每个寄存器使用状态，对应值是1即可用，0就是不可用。对具体加、减、乘、除操作用到寄存器就调用alloc_register方法得到一个空闲寄存器。用完的不需要的寄存器就调用free_register释放可用性。通过这样防止生成汇编代码使用寄存器出现冲突。然后实现各操作的汇编生成片段即可。cgload就对应AST上的数字，对应汇编就是tmovq $数字 寄存器，这时候就调用申请空闲寄存器方法，从可用寄存器返回个可以位置，对应就是寄存器名称。cgadd对应AST的操作“加”，对应汇编就是addq 寄存器1 寄存器2，把1加到2上，加完了释放1寄存器使用，后续业务申请可以用1寄存器了。
#include "defs.h"
#include "data.h"
#include "decl.h"
// Code generator for x86-64
// Copyright (c) 2019 Warren Toomey, GPL3
/*
这里面实现编译本地化逻辑，针对特定CPU架构组装汇编指令片段，实现了组装X86汇编固定前面和结尾的逻辑。
然后实现了加、建、乘、除、打印调用的汇编片段逻辑。编译AST树时候遍历AST就按AST操作调用把AST树转换为汇编代码
*/
// List of available registers
// and their names
// 自由寄存器，该数组标识对应的reglist哪个寄存器可用
static int freereg[4];
//对应汇编寄存器名称。每次通过freereg判断可用性申请一个可用的寄存器名称组装汇编
static char *reglist[4]= { "%r8", "%r9", "%r10", "%r11" };
// Set all registers as available
// 设置所有寄存器为可用状态
void freeall_registers(void)
{
freereg[0]= freereg[1]= freereg[2]= freereg[3]= 1;
}
//申请一个可用寄存器，返回可用的位置所有
// Allocate a free register. Return the number of
// the register. Die if no available registers.
static int alloc_register(void)
{
for (int i=0; i<4; i++) {
if (freereg[i]) {
freereg[i]= 0;
return(i);
}
}
fprintf(stderr, "Out of registers!\n");
exit(1);
}
//释放一个寄存器所有
// Return a register to the list of available registers.
// Check to see if it's not already there.
static void free_register(int reg)
{
if (freereg[reg] != 0) {
fprintf(stderr, "Error trying to free register %d\n", reg);
exit(1);
}
freereg[reg]= 1;
}
// 编译前面部分，先输出固定的汇编
// Print out the assembly preamble
void cgpreamble()
{
//释放所有寄存器
freeall_registers();
fputs(
"\t.text\n"
".LC0:\n"
"\t.string\t\"%d\\n\"\n"
"printint:\n"
"\tpushq\t%rbp\n"
"\tmovq\t%rsp, %rbp\n"
"\tsubq\t$16, %rsp\n"
"\tmovl\t%edi, -4(%rbp)\n"
"\tmovl\t-4(%rbp), %eax\n"
"\tmovl\t%eax, %esi\n"
"\tleaq .LC0(%rip), %rdi\n"
"\tmovl $0, %eax\n"
"\tcall printf@PLT\n"
"\tnop\n"
"\tleave\n"
"\tret\n"
"\n"
"\t.globl\tmain\n"
"\t.type\tmain, @function\n"
"main:\n"
"\tpushq\t%rbp\n"
"\tmovq %rsp, %rbp\n",
Outfile);
}
//编译的结尾部分，输出固定的尾部汇编
// Print out the assembly postamble
void cgpostamble()
{
fputs(
"\tmovl $0, %eax\n"
"\tpopq %rbp\n"
"\tret\n",
Outfile);
}
//加载一个整数到寄存器返回寄存器索引
// Load an integer literal value into a register.
// Return the number of the register
int cgload(int value) {
//申请一个可用的寄存器
// Get a new register
int r= alloc_register();
//组装加载整数的汇编。把数字放入申请的可用寄存器
//如果0位可用那么就是放入%r8
// Print out the code to initialise it
fprintf(Outfile, "\tmovq\t$%d, %s\n", value, reglist[r]);
return(r);
}
//组装加法汇编代码，按传入两个可用寄存器位置组装对应寄存器汇编代码
// Add two registers together and return
// the number of the register with the result
int cgadd(int r1, int r2) {
fprintf(Outfile, "\taddq\t%s, %s\n", reglist[r1], reglist[r2]);
//释放寄存器可用性
free_register(r1);
return(r2);
}
//组装减法汇编代码，按传入两个可用寄存器位置组装对应寄存器汇编代码
// Subtract the second register from the first and
// return the number of the register with the result
int cgsub(int r1, int r2) {
fprintf(Outfile, "\tsubq\t%s, %s\n", reglist[r2], reglist[r1]);
//释放寄存器可用性
free_register(r2);
return(r1);
}
//组装乘法汇编代码，按传入两个可用寄存器位置组装对应寄存器汇编代码
// Multiply two registers together and return
// the number of the register with the result
int cgmul(int r1, int r2) {
fprintf(Outfile, "\timulq\t%s, %s\n", reglist[r1], reglist[r2]);
//释放寄存器可用性
free_register(r1);
return(r2);
}
//组装除法汇编代码，按传入两个可用寄存器位置组装对应寄存器汇编代码
// Divide the first register by the second and
// return the number of the register with the result
int cgdiv(int r1, int r2) {
fprintf(Outfile, "\tmovq\t%s,%%rax\n", reglist[r1]);
fprintf(Outfile, "\tcqo\n");
fprintf(Outfile, "\tidivq\t%s\n", reglist[r2]);
fprintf(Outfile, "\tmovq\t%%rax,%s\n", reglist[r1]);
//释放寄存器可用性
free_register(r2);
return(r1);
}
//组装打印调用的汇编代码
// Call printint() with the given register
void cgprintint(int r) {
fprintf(Outfile, "\tmovq\t%s, %%rdi\n", reglist[r]);
fprintf(Outfile, "\tcall\tprintint\n");
//释放寄存器可用性
free_register(r);
}
由于生成的AST树不直观，所以我自己实现了打印AST树的逻辑，把AST树形象的在屏幕打印出来。
//得到AST树的深度
int DeepTree(struct ASTnode* T)
{
if (!T)
{
return 0;
}
//左子树深度大于右子树则将左子树的深度加一返回, 这个返回值便是以该节点做根节点的树的深度, 右子树深度大时则相反
return DeepTree(T->left) > DeepTree(T->right) ? DeepTree(T->left) + 1 : DeepTree(T->right) + 1;
}
//T为二叉树的根节点,a是数组的起始地址,i,j是当前节点在数组中的位置
//如果节点有孩子,其孩子的j坐标为 j±(height-i+1)/2
void fillPrintArray(struct ASTnode* T, char* a, int i, int j)
{
int ti, tj;
if (T) //如果该位置有节点
{
char printc[5] = { ' ' };
switch (T->op) {
case A_ADD:
printc[0] = '+';
break;
case A_SUBTRACT:
printc[0] = '-';
break;
case A_MULTIPLY:
printc[0] = '*';
break;
case A_DIVIDE:
printc[0] = '/';
break;
case A_INTLIT:
sprintf(printc, "%d", T->intvalue);
break;
default:
printc[0] = ' ';
}
*(a + (i * printWidth) + j) = printc[0];
if (T->op == A_INTLIT)
{
for (int k = 0; k < 5; k++)
{
if (printc[k] != ' ')
{
*(a + (i * printWidth) + j + k) = printc[k];
}
}
}
if (T->left) //有左右孩子给对应的连接线,左右孩子的值在下一层递归赋
{
//将该点与其左孩子之间的连线全部填上'/'
for (ti = i + 1, tj = j - 1; tj > j - (printHeight - i + 1) / 2; tj--)
{
*(a + ((ti)*printWidth) + tj) = -1;
ti++;
}
}
if (T->right)
{
for (ti = i + 1, tj = j + 1; tj < j + (printHeight - i + 1) / 2; tj++)
{
*(a + ((ti)*printWidth) + tj) = 1;
ti++;
}
}
//经过循环,ti恰好指到其孩子所在的层
fillPrintArray(T->left, a, ti, j - (printHeight - i + 1) / 2);
fillPrintArray(T->right, a, ti, j + (printHeight - i + 1) / 2);
}
}
//打印AST树
void printAstTree(struct ASTnode* T)
{
int i, j;
int n = DeepTree(T); //计算出深度n
//在计算机中数据以二进制形式存储,所以一个数据左移1位就相当于乘以2的1次方
printWidth = (2 << n) - 3; // 2^(n+1)-3
printHeight = (2 << (n - 1)) - 1; // 2^n-1
char* a = (char*)malloc(sizeof(char) * (printWidth * printHeight)); // 申请空间
// 空间初始化为0
for (i = 0; i < printHeight; i++)
{
for (j = 0; j < printWidth; j++)
{
*(a + (i * printWidth) + j) = 0;
}
}
//调用之前定义好的函数,填充打印数组
fillPrintArray(T, a, 0, (printWidth - 1) / 2);
//根据打印数组的内容来实现打印
for (i = 0; i < printHeight; i++)
{
for (j = 0; j < printWidth; j++)
{
if (*(a + (i * printWidth) + j) == -1)
{
printf("/");
}
else if (*(a + (i * printWidth) + j) == 1)
{
printf("\\");
}
else if (*(a + (i * printWidth) + j) == 0)
{
printf(" ");
}
else
{
printf("%c", *(a + (i * printWidth) + j));
}
}
printf("\n");
}
}
同时把生成的汇编也打印出来
// Main program: check arguments and print a usage
// if we don't have an argument. Open up the input
// file and call scanfile() to scan the tokens in it.
void main(int argc, char *argv[]) {
//AST树根节点
struct ASTnode *n;
//打印调用示例
if (argc != 2)
{
usage(argv[0]);
}
//初始化
init();
//打开代码文件
if ((Infile = fopen(argv[1], "r")) == NULL) {
fprintf(stderr, "Unable to open %s: %s\n", argv[1], strerror(errno));
exit(1);
}
//打开输出汇编文件
if ((Outfile = fopen("out.s", "w")) == NULL) {
fprintf(stderr, "Unable to create out.s: %s\n", strerror(errno));
exit(1);
}
//扫描一个token
scan(&Token); // Get the first token from the input
//得到AST树，用pratt算法构造优先级AST树
n = binexpr(0); // Parse the expression in the file
//打印树
printf("############################AST Tree#########################################\n");
//打印AST树
printAstTree(n);
printf("############################AST Tree#########################################\n");
printf("ExeResult:%d\n", interpretAST(n)); // Calculate the final result
//编译得到汇编代码
generatecode(n);
//关闭输出文件
fclose(Outfile);
printf("############################out.s#########################################\n");
PrintFile("out.s");
printf("############################out.s#########################################\n");
exit(0);
}
//打印文件
//fileName:文件名
void PrintFile(char * fileName)
{
int fd = -1;
int wr = -1;
//打开文件
if ((fd = open(fileName, O_RDONLY, 0666)) < 0)
{
printf("创建或打开文件%s失败: %s\n", fileName, strerror(errno));
return;
}
//读数据
char buf[1024];
memset(buf, 0, sizeof(buf));
lseek(fd, 0, SEEK_SET);
//循环读取数据
while (wr = read(fd, buf, sizeof(buf)) > 0)
{
//输出
printf("%s", buf);
memset(buf, 0, sizeof(buf));
}
//关闭文件
close(fd);
printf("\n");
}
其他测试
[root@zlzlinux 04_Assembly]#
[root@zlzlinux 04_Assembly]#
[root@zlzlinux 04_Assembly]#
[root@zlzlinux 04_Assembly]# touch zlzcode
[root@zlzlinux 04_Assembly]# vim zlzcode
[root@zlzlinux 04_Assembly]# ./comp1 zlzcode
############################AST Tree#########################################
-
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
- /
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
+ * 9 3
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
1 * * 8
/ \ / \
/ \ / \
/ \ / \
2 3 / 2
/ \
4 5
############################AST Tree#########################################
ExeResult:4
############################out.s#########################################
.text
.LC0:
.string "%d\n"
printint:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl %edi, -4(%rbp)
movl -4(%rbp), %eax
movl %eax, %esi
leaq .LC0(%rip), %rdi
movl $0, %eax
call printf@PLT
nop
leave
ret
.globl main
.type main, @function
main:
pushq %rbp
movq %rsp, %rbp
movq $1, %r8
movq $2, %r9
movq $3, %r10
imulq %r9, %r10
addq %r8, %r10
movq $4, %r8
movq $5, %r9
movq %r8,%rax
cqo
idivq %r9
movq %rax,%r8
movq $2, %r9
imulq %r8, %r9
movq $8, %r8
imulq %r9, %r8
subq %r8, %r10
movq $9, %r8
movq $3, %r9
movq %r8,%rax
cqo
idivq %r9
movq %rax,%r8
subq %r8, %r10
movq %r10, %rdi
call printint
movl $0, %eax
popq %rbp
ret
############################out.s#########################################
[root@zlzlinux 04_Assembly]#
[root@zlzlinux 04_Assembly]# cat zlzcode
1+2*3-4/5*2*8-9/3
[root@zlzlinux 04_Assembly]#
哈哈，把树打印出来展示，机智的我啊，对编译的理解又提升了，慢慢学习吧，争取能达到c自举。