EchoBai Blog

项目介绍

1
2
3
4
5
6
7

          _     _                             _ _           
__      _| |__ (_)   ___ ___  _ __ ___  _ __ (_) | ___ _ __ 
\ \ /\ / / '_ \| |  / __/ _ \| '_ ` _ \| '_ \| | |/ _ \ '__|
 \ V  V /| | | | | | (_| (_) | | | | | | |_) | | |  __/ |   
  \_/\_/ |_| |_|_|  \___\___/|_| |_| |_| .__/|_|_|\___|_|   
                                       |_|     

本项目打算用C语言设计一个极简的WHI语言编译器。github上也有不少极其优秀的且完整的项目，那么我的目的就是只关注编译器最核心的原理部分，而不是力求一定要尽善尽美。

设计原则将采用kiss原则，即使其尽可能的简单。项目地址

在token识别上，打算采用正则表达式匹配的做法来达到更好的识别token的目的。

在目标语言上，将源程序翻译为简单栈式抽象机代码。同时与预设结果进行比较以验证编译器的正确性。

项目任务及完成情况见task.todo文件

正则表达式介绍

正则表达式（英语：Regular Expression，常简写为regex、regexp或RE），又称正则表示式、正则表示法、规则表达式、常规表示法，是计算机科学的一个概念。正则表达式使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串。在很多文本编辑器里，正则表达式通常被用来检索、替换那些匹配某个模式的文本。

正则表达式常见规则

构造正则表达式的方法：用多种元字符与运算符将小的表达式结合在一起来创建更大的表达式。正则表达式的组件可以是单个的字符、字符集合、字符范围、字符间的选择或者所有这些组件的任意组合。

正则表达式是由普通字符（例如字符 a 到 z）以及特殊字符（称为”元字符”）组成的文字模式。模式描述在搜索文本时要匹配的一个或多个字符串。正则表达式作为一个模板，将某个字符模式与所搜索的字符串进行匹配。

语法分析设计

设计概要

关于错误处理部分的设计

对于错误处理，我们主要将所有的错误类型定义在一个结构体中

1
2
3
4
5

struct grammer_error{
  int errorkind;
  const char* str;
  // void (*handler) (int errorkind,int row, int col);
} errors[];

之所以将其分离开来，而不是直接在有错误的地方用printf打印的主要原因在于，尽量减少模块之间的耦合性。而且这样设计的好处还在于，我们可以在结构体中加入更多的特性，比如后期可能为每一个错误处理增加一个出错处理函数（如注释部分所示），当我们识别到具体的错误时就对其进行一定的处理达到识别多个错误的目的，而不是简单的识别一个错误然后直接退出，这样可以减少用户因多个错误导致的多次编译。

代码生成

回填链表的设计

由于我们需要在一遍扫描中生成指令代码，但是遇到分支循环语句时，由于执行时间的限制，我们暂时看不到后续跳转的位置，因此我们就需要一种数据结构将需要跳转的位置保存下来，当我们执行到合适的位置的时候对其进行回填。而具体的数据结构设计如下：

1
2
3
4
5
6
7

struct backpatchlist
{
  int inst_remain;
  struct backpatchlist *tail;
  struct backpatchlist *next;
};

首先是一个用于存储待回填的指令标号字段，紧接着是链表的尾指针，最后是存储下一个链表结构的字段。尾指针的设计我认为是比较合理的，其避免了两个均持有一定元素的链表在合并时的遍历问题，即寻找合适的插入位置。而如果存储了尾指针，首先初始必为只持有一个元素的两个链表合并，我们对其执行以下操作，这样后续的合并操作我们就可以用O(1)的时间复杂度来完成。

1
2
3
4
5
6
7
8
9
10
11
12
13

struct backpatchlist *merge(struct backpatchlist *bpl1, struct backpatchlist *bpl2){
  if(!bpl1 && !bpl2){
    return nullptr;
  } else if(!bpl1 && bpl2){
    return bpl2;
  } else if(bpl1 && !bpl2){
    return bpl1;
  } else{
    bpl1->tail->next = bpl2;
    bpl1->tail = bpl2->tail;
    return bpl1;
  }
}

项目背景

随着互联网的日益发展，各类智能终端已遍布人们的日常生活。本项目致力于建立一个从嵌入式设备到互联网网页的实时控制链，旨在通过提供一系列可视化的用户接口以实现人们对各类嵌入式设备的控制。同时为建立一套更加贴合主流的智能家居打下一个基础。下面我将对本项目目前所具备的功能，运行的基本原理，开发工具的基本版本以及接口设计的基本原则等做一个简要的介绍。项目地址