---

前引

---

各位好 这篇是我开坑的第一篇编译原理的博客 也是第一篇关于我学习编译原理的博客 不得不说一下 在这段时间中 尤其是上一周 和 这一周 今天已经是大二上的第十周了 这段时间我的心情是比较的down的

至于为什么down 是因为 可能这段时间对于数据库 和 计网想要在重新反复看的抵触情绪比较强烈 再加上自己这段时间学习效率相对大一没有那么高了 我自己总结了一下大概是因为 学习的难度提升了 + 能够马上看到成果的那种 激励情绪已经消散很多了 可能是现在学到这里了 真的都是非常底层且非常不容易理解的东西了

前段时间看数据库底层 innode存储引擎就明显感觉到有点点吃力 或许是不是很愿意这段时间看 想换个时间看 强迫自己做一些事情终究是不好的 正好下学期也要学数据库原理了 我初步打算是 这学期在最后的这几周 把编译原理绝大部分看懂 并且实现一个属于自己的正则引擎 如果还有剩余时间的话 自己再学一下C++ 去重新看看c++ primer 最初学c++的时候不得不说是学的比较囫囵吞枣了 我比较力扣也刷了这么多题了 现在可以调侃一下自己说 已经是入门的c++ stl user + c语言 user了 哈哈

当然 我们言归正传 为什么我开了新坑 原因就是学编译原理 肯定是必须有两本书出现 一本是大名鼎鼎的龙书 一本书是还没有买的虎书 很恼人的说 最近这段时间看龙书 也是一个非常打击我的事情 因为确确实实看到20多页的时候 我发现自己真的看不下去而且看不懂了 以至于昨晚我找我的好朋友绕着校园到处转 一边吐苦水一边暗自给心里面灌鸡汤 告诉自己无论如何今天一定要坚持看下去 然后坚持又看了几页发现自己是真的消化不下去/(ㄒoㄒ)/~~

也就导致了 自我怀疑 和 自我的情绪消极了 但这可能是必经要走的路吧 于是我就打算先看网课 再看书 或许是不是会能够看懂了呢 那我们就先把中科大的网易云课堂里面的编译原理 一步步慢慢消化吧

---

第一章：编译器介绍

---

1、任务介绍

---

题目：（本题目是一个动手实践类题目，需要具备C语言和数据结构基础。）
在课程中，我们讨论一个小型的从表达式语言Sum到栈计算机Stack的编译器，在附件中，你能找到对该编译器的一个C语言实现，但这个实现是不完整的，请你把缺少的代码补充完整（不超过10行代码）。
加分题：实现常量折叠优化。

---

2、实现思路

---

其实这部分也就是 让我们从总览一下 一个编译器大致需要走过的路程是什么 我们的任务就是 通过一个已经在内存中实现出来的 抽象语法树 我们通过后序遍历就可以得到 我们的栈计算机的顺序执行命令

其实也就是这些 主要的还是理解 我们示例代码里面的结构体 还有各函数的用意是什么 最后的list_reverse_print就是一个常规的递归 没其他什么了

---

3、函数实现

---

1、list_reverse_print

---

// "printer"
void List_reverse_print (struct List_t *list)
{
    if(!list)   return;
    List_reverse_print(list->next);
    printf("stack instruction: %s",(list->instr->kind == STACK_ADD ? "Add" : "Push: "));
    if(list->instr->kind != STACK_ADD) printf("%d",((struct Stack_Push*)list->instr)->i);
    printf("\n");
}

---

2、compile

---

void compile (struct Exp_t *exp)
{
  switch (exp->kind){
  case EXP_INT:{
    struct Exp_Int *p = (struct Exp_Int *)exp;
    emit (Stack_Push_new (p->i));
    break;
  }
  case EXP_SUM:{
    struct Exp_Sum* p = (struct Exp_Sum *)exp;
    compile(p->left);
    compile(p->right);
    emit(Stack_Add_new());
    break;
  }
  default:
    break;
  }
}

---

4、代码实现

---

#include <stdio.h>
#include <stdlib.h>

#define TODO()                                  \
  do{                                                           \
    printf ("\nAdd your code here: file \"%s\", line %d\n",     \
            __FILE__, __LINE__);                                \
  }while(0)

///////////////////////////////////////////////

// Data structures for the Sum language.

enum Exp_Kind_t {EXP_INT, EXP_SUM};
struct Exp_t
{
  enum Exp_Kind_t kind;
};

struct Exp_Int
{
  enum Exp_Kind_t kind;
  int i;
};

struct Exp_Sum
{
  enum Exp_Kind_t kind;
  struct Exp_t *left;
  struct Exp_t *right;
};

// "constructors"
struct Exp_t *Exp_Int_new (int i)
{
  struct Exp_Int *p = malloc (sizeof(*p));
  p->kind = EXP_INT;
  p->i = i;
  return (struct Exp_t *)p;
}

struct Exp_t *Exp_Sum_new (struct Exp_t *left, struct Exp_t *right)
{
  struct Exp_Sum *p = malloc (sizeof(*p));
  p->kind = EXP_SUM;
  p->left = left;
  p->right = right;
  return (struct Exp_t *)p;
}

// "printer"
void Exp_print (struct Exp_t *exp)
{
  switch (exp->kind)
  {
  case EXP_INT:{
    struct Exp_Int *p = (struct Exp_Int *)exp;
    printf ("%d", p->i);
    break;
  }
  case EXP_SUM:{
    struct Exp_Sum *p = (struct Exp_Sum *)exp;
    Exp_print (p->left);
    printf ("+");
    Exp_print (p->right);
    break;
  }
  default:
    break;
  }
}

//////////////////////////////////////////////
// Data structures for the Stack language.
enum Stack_Kind_t {STACK_ADD, STACK_PUSH};

struct Stack_t
{
  enum Stack_Kind_t kind;
};

struct Stack_Add
{
  enum Stack_Kind_t kind;
};

struct Stack_Push
{
  enum Stack_Kind_t kind;
  int i;
};

// "constructors"

struct Stack_t *Stack_Add_new ()
{
  struct Stack_Add *p = malloc (sizeof(*p));
  p->kind = STACK_ADD;
  return (struct Stack_t *)p;
}



struct Stack_t *Stack_Push_new (int i)
{
  struct Stack_Push *p = malloc (sizeof(*p));
  p->kind = STACK_PUSH;
  p->i = i;
  return (struct Stack_t *)p;
}

/// instruction list
struct List_t
{
  struct Stack_t *instr;
  struct List_t *next;
};

struct List_t *List_new (struct Stack_t *instr, struct List_t *next)
{
  struct List_t *p = malloc (sizeof (*p));
  p->instr = instr;
  p->next = next;
  return p;
}

// "printer"
void List_reverse_print (struct List_t *list)
{
    if(!list)   return;
    List_reverse_print(list->next);
    printf("stack instruction: %s",(list->instr->kind == STACK_ADD ? "Add" : "Push: "));
    if(list->instr->kind != STACK_ADD) printf("%d",((struct Stack_Push*)list->instr)->i);
    printf("\n");
}

//////////////////////////////////////////////////
// a compiler from Sum to Stack
struct List_t *all = 0;

void emit (struct Stack_t *instr)
{
  all = List_new (instr, all);
}

void compile (struct Exp_t *exp)
{
  switch (exp->kind){
  case EXP_INT:{
    struct Exp_Int *p = (struct Exp_Int *)exp;
    emit (Stack_Push_new (p->i));
    break;
  }
  case EXP_SUM:{
    struct Exp_Sum* p = (struct Exp_Sum *)exp;
    compile(p->left);
    compile(p->right);
    emit(Stack_Add_new());
    break;
  }
  default:
    break;
  }
}

//////////////////////////////////////////////////
// program entry
int main()
{
  printf("Compile starting\n");
  // build an expression tree:

  //            +

  //           / \

  //          +   4

  //         / \

  //        2   3

  struct Exp_t *exp = Exp_Sum_new (Exp_Sum_new(Exp_Int_new (2),Exp_Int_new(3)), Exp_Int_new (4));
  // print out this tree:
  printf ("the expression is:\n");
  Exp_print (exp);
  printf("\n");
  // compile this tree to Stack machine instructions
  compile (exp);
  // print out the generated Stack instructons:
  List_reverse_print (all);
  printf("\nCompile finished\n");
  return 0;
}

---

5、实现效果

---

---

结束语

---

总体来说 我已经感觉很久没有思考并上手写过代码了 昨天看轮子哥写过一些话 真的感觉人与人的差距真的很大很大 轮子哥在我前面已经把我拉开了不知道有多远 前面很多年知识的铺垫 + 天生的聪明 学习本来就是一个抛物线 你感觉自己学的很多的时候 其实学的仅仅是一点点 当自己确实学的很多的时候 会感觉可能自己什么都没有学

或许真的是这样 希望自己这段时间能够 真的把编译原理不说全部看懂 至少最后希望自己能够真的实现一个属于自己的正则引擎吧 同时真的也很感谢轮子哥 让我明白在我前面的人 真的离我距离有多远 希望自己也能继续去完成自己原来想要完成的东西吧