node实现简易编译器-六虎

介绍

本文用node完结了一个简略的编译器mccompiler，主要用于学习，该文章是比较久之前写的了，有关准确性和时效性和当时写文章的情景和心态相关，笔者能力和精力有限，如有不当，还请指出，极力修正。

项目地址：github.com/mingmingjia… 大伙能够试试，有bug能够找我，尽管我也不一定修复，麻烦走过路过的巨佬帮忙star下，感恩的心❤️❤️

本文触及：编译器的词法剖析，笼统语义树生成，语法剖析，代码生成

本文要点内容：

完结正则表达式剖析器
完结简易版 Flex
完结 LR0和SLR 语法，并简略介绍其他语法(LL, LR1 LSPR) 4
完结生成汇编代码
完结简易编译器功能，供给编译时期类型检查和揣度，支撑加减乘除支撑函数的递归调用等功能

会包括的：

完结 nfa，以及联合 nfa => dfa，进行词法剖析
完结 dfa，进行语法剖析，并基于此构建笼统语法树(AST)
基于 ast 进行言语义剖析(类型检查以及是否契合言语规范)
基于 ast 生成汇编代码，尽管本文没有显示的终中间代码生成进程，可是也有相似的思想

不会包括的：本言语比较简略，不包括复杂数据结构的支撑，如数组对象等其他功能；不会触及复杂的编译器后端知识：如垃圾收回，寄存器染色，数据流剖析等等

minic 语法：

运算符：支撑+-*/运算，支撑运算优先级和常规的结合性
类型：支撑自然数(int 类型)，布尔值以及void
句子：支撑函数调用及递归调用，if-else 句子
和 C 一样，有必要要有 main 函数
变量有必要声明的时分一起赋值
答应注释，注释风格同C

int sum(int x, int y) {
 return x + y;
}
int feb(x: int) {
 if (x == 0) {
 return x;
  }
 return x + feb(x-1);
}

接下来从以下几个方面介绍：

lexier：包括正则表达式生成和词法token生成
parser：文法推导式解析和笼统语义树生成
checker：语法和类型校验
gener：汇编代码生成

Parser

在词法剖析阶段，输入是字符串，输出是 token 流，一开始规划输出是枚举值的数组，相似这样: [TYPE, ID, BRACE, ...]，可是这样会有问题，因为词素值没办法保留下来，所以后边改成了如下输出: [(line_num, TYPE, int), (line_num, ID, feb)]，(行号，类型, 词素值)三元组学在构建自动机进程中，自动机把输入流转成 token流，比方当词法剖析器读完 int 的时分，这时分就会回来一个 TYPE token，可是假如是 int1，就应该回来一个 ID token，所以这儿触及到贪婪读取，别的关于像 if 这种关键字，假如一起满足多种完结状况，应该触及到优先级，这儿的优先级比较简略，直接遍历终态节点数组endStates(能够理解为叶子节点)，遇到第一个契合的即回来，所以正则的优先级和前后次序有关；那么怎么构建自动机？咱们的方针是构建一系列单个正则表达式单元nfa，然后联组成一个大的nfa单元，这个nfa能够解析咱们的之前正则单元，再得到联合nfa的邻接矩阵edges，最后依据edges转成dfa，具体步骤如下：首先，需求名清晰的是，咱们的词法剖析器支撑以下几个单元： +: a+, : a, 衔接: ab，逻辑或: a|b，字符集: [a-z] 支撑少部分字符转义，如：\s,\ t, \n

怎么把正则表达式构建为 nfa：关于每一个单元正则表达式，能够直接生成对应的节点，可是有些问题咱们需求留意：咱们的输入是一个个正则表达式，正则表达式本身能够理解为是一个个单元，而这些单元又可能是字符或许其他单元和成的，如： a|b 便是一个单元，可是其组成便是 2 个字符 [a-z]|a 便是一个元外加一个一般字符别的关于中括号这种还需求特别处理，思路如下：即使是单个字符也会笼统成节点的概念，别的在生成自动机的进程中，因为存在[]，+，*等等这样的润饰符号，考虑运用 stack 进行存储，类比括号匹配算法。(lib => parser => nfa => flex函数)

构建根本正则单元：

export function connect(from: VertexNode, to: VertexNode): VertexNode {
  // from的尾和to的头相互衔接,留意circle
  let cur = graph.getVertex(from.index); // 获取邻接表
  const memo: number[] = [];
  while (cur.firstEdge && !memo.includes(cur.index)) {
    memo.push(cur.index);
    cur = graph.getVertex(cur.firstEdge.index);
  }
  graph.getVertex(cur.index).firstEdge = new Node(
    to.index,
    graph.getVertex(cur.index).firstEdge
  );
  return from;
}
```
2. 或
```js
export function or(a: VertexNode, b: VertexNode): VertexNode {
  const nodeStart = new VertexNode(Graph.node_id, null);
  graph.addVertexNode(nodeStart, nodeStart.index);
  nodeStart.firstEdge = new Node(a.index, null, a.edgeVal || null);
  nodeStart.firstEdge.next = new Node(b.index, null, b.edgeVal || null);
  const nodeEnd = new VertexNode(Graph.node_id, null);
  graph.addVertexNode(nodeEnd, nodeEnd.index);
  connect(a, nodeEnd);
  connect(b, nodeEnd);
  return nodeStart;
}
```
3. 字符集
```js
export function characters(chars: string[]) {
  const nodeStart = new VertexNode(Graph.node_id, null);
  graph.addVertexNode(nodeStart, nodeStart.index);
  const nodeEnd = new Node(Graph.node_id, null, chars);
  const tmp = new VertexNode(nodeEnd.index, chars);
  graph.addVertexNode(tmp, tmp.index);
  const pre = nodeStart.firstEdge;
  nodeStart.firstEdge = nodeEnd;
  nodeEnd.next = pre;
  return nodeStart;
}
```
4. *润饰符
```js
export function mutipliy(wrapped: VertexNode): VertexNode {
  const nodeStart = new VertexNode(Graph.node_id, null);
  graph.addVertexNode(nodeStart, nodeStart.index);
  const tmp = new Node(wrapped.index, null, null);
  nodeStart.firstEdge = tmp;
  let cur = graph.getVertex(wrapped.index); // 获取邻接表
  while (cur.firstEdge) {
    cur = graph.getVertex(cur.firstEdge.index);
  }
  connect(cur, nodeStart);
  return nodeStart;
}
```
5. +润饰符
```js
export function plus(base: VertexNode) {
  // 基于old新建节点
  let nodeStart = new VertexNode(Graph.node_id, base.edgeVal);
  nodeStart.firstEdge = base.firstEdge;
  const res = nodeStart;
  graph.addVertexNode(nodeStart, nodeStart.index);
  let cur = base?.firstEdge;
  while (cur) {
    const vertexNode = graph.getVertex(cur?.index);
    const tmp = new VertexNode(Graph.node_id, vertexNode.edgeVal);
    nodeStart.firstEdge = new Node(tmp.index, null, vertexNode.edgeVal);
    nodeStart = tmp;
    tmp.firstEdge = base.firstEdge;
    graph.addVertexNode(tmp, tmp.index);
    cur = vertexNode.firstEdge;
  }
  return mutipliy(res);
}

不过比较困扰的是这些节点的数据结构怎么存储是一件要考虑周到的事：需求节点 id，因为自动机是有向图，而且可能带环，而且节点和节点之间可能存在不止一条边，考虑了下，还是用邻接表存储(主要是第一版的代码是这样的，再加上假如感觉节点之间的衔接可能在某些情况下比较少，临界矩阵比较浪费内存)，firstEdge 指向其所有的临界边，edgeVal 是边上的值，关于该图的查找，运用 bfs+dfs+检测环。

如下：

if对应的nfa:

if对应的nfa

[a-z][a-z0-9]* 的nfa为:

[a-z][a-z0-9]* 的nfa

联合后就变成了一个大的nfa，并在终态节点上放置一些动作：

联合nfa

构建邻接矩阵：

const edges = new Array(200).fill(0).map((_item) => {
    return new Array(200).fill(0);
});
edges[起始点][停止点] = [边调集]，假如是epsilon，这儿运用null表示$\epsilon$
build_edges() dfs + bfs + 调集去重
```
```js
[  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],   ======> 0
  [0, 0, i, 0, null, 0, 0, 0, 0, 0],======> 1
  [0, 0, 0, f, 0, 0, 0, 0, 0, 0],======> 2
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]======> 3
  [0, 0, 0, 0, 0,	======> 4    [       a,  b,  c, 100, 101, 102,      103, 104, 105, 106, 107, 108,      109, 110, 111, 112, 113, 114,      115, 116, 117, 118, 119, 120,      121, z    ],
    0, 0, 0, 0
  ],
  [0, 0, 0, 0, 0, 0, 0, 0, null, 0],======> 5
  [0, 0, 0, 0, 0, 0, 0, 0,======> 6    [       a,  b,  c, d, 101, 102, 103, 104,      105, 106, 107, 108, 109, 110, 111, 112,      113, 114, 115, 116, 117, 118, 119, 120,      121, z,  0,  1,  2,  3,  4,  5,       6,  7,  8,  9    ],
    0,0
  ],
  [0, 0, 0, 0, 0, 0, 0, 0, null, 0],======> 7
  [0, 0, 0, 0, 0, 0, null, 0, 0, 0],======> 8
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]======> 9
]

能够验证下上面的邻接矩阵便是如下节点边值对(行索引对应source节点，列索引对应target节点，矩阵值便是边调集)：

1 => 2: i 1 => 4: null 2 => 3: f 4=>5: [a-z] 5=>8: null 6=>7: [a-z] [0-9] 7=>8: null 8=>6: null

依据邻接矩阵构建dfa

有了Closure和DFAedge算法单元，这样从NFA的起点动身，不断的更新DFAedge(S, c)，每次新生成的DFAedge(S, c)，即得到DFA里的状况节点，据此得到dfa状况搬运表

states[0] <- []
states[1] <- Closure([S])
p <- 1, j <- 0 
while j <= p 
	for c in 字母集 
		e <- DFAedge(states[j], c) 
		if e == states[i] for some i <= p 
			then trans[j][c] <- i
		else 
			p <- p + 1
			states[p] <- e
			trans[j][c] <- p
	j <- j + 1

构建完正则表达式之后就能够对咱们的输入处理成token流了。(lib => scan函数)

构建笼统语法树

这儿我用的是SLR文法，理论上上下无关文法所代表的文法规模： LR(1) > LAPR > SLR > LR(0) LR(0): 没有提早猜测的符号，容易呈现 shift-reduce 抵触以及 reduce-reduce 抵触，所以需求规划适合的文法； SLR: 有简略的猜测，能够用follow集处理部分shift-reduce 抵触，可是在有些情况下还是 shift-reduce抵触 LR(1): 能够处理部分shift-reduce 抵触，也处理部分reduce-reduce 抵触 LAPR: 因为 LR(1)的表特别大，在此基础上做了优化看如下文法1的 LR(0)生成进程：

E-> Program $
Program -> Assign == Assign
Assign -> Assign + Token
Assign -> Token
Token -> id

文法1 LR(0)对应的dfa

文法1对应的LR(0)状况搬运表

能够看到在状况 9 是存在移位-规约抵触的，这是因为 LR(0)默认在所有的完结符号处做规约。

slr 语法是比 LR(0),更为广泛的一种语法，它只在特定的地方放置规约动作。具体来说，在上面的例子里，在状况 9 处，只要规约式 1 的移位指针到达里末尾，所以能够看下规约式 1 后边可能会紧接着什么符号，也便是 followSet(Program) = {$}，所以只在$处放置规约动作。下面是 slr 剖析表：

文法1对应的SLR(0)状况搬运表

AST生成

生成好剖析表之后，就能够依据剖析表进行语法剖析了，如下所示，在提早界说好的文法发生式做对应的规约动作，如下case 0便是Formals -> int, TOKEN.ID，在这儿运用栈内的元素生成Formal_Class；就这样每次在对应的文法发生式上对对应的做规约动作，从而完结自底向上的ast的构建

[Formals -> int, TOKEN.ID]: 0,
[Formals -> Formals, ',', int, TOKEN.ID]: 1
case 0:
  res = new Formal_Class(yyvalsp[0][2], yyvalsp[1][2]);
  break;
case 1:
  res = new Formal_Class(yyvalsp[0][2], yyvalsp[1][2], yyvalsp[3]);
  break;

下图简略模拟了int ID (int ID)的token流处理进程：

增加图片注释，不超越 140 字（可选）

在没有规约动作的时分token一直push进栈，直到有对应的规约动作，这个时分按照指定的规约动作，生成非完结符，再把该非完结符放入栈内，重复进行，直到栈内为空或许遇到了$，当然，假如在这进程中遇到了不合法的字符，直接抛出反常。

以及进程中生成的简略ast如下：

Program_Class {
  expr: Function_Class {
    formal_list: [ 'x' ],
    name: 'total',
    expressions: Branch_Class {
      ifCond: Cond_Class {
        lExpr: Indentifier_Class { token: 'x' },
        rExpr: Int_Contant_Class { token: '0' },
        op: '=='
      },
      statementTrue: Return_Class { expr: Indentifier_Class { token: 'x' } },
      statementFalse: Assign_Class {
        name: 'm',
        ltype: 'int',
        r: Caller_Class {
          params_list: [ undefined ],
          id: 'total',
          params: Sub_Class {
            lvalue: Indentifier_Class { token: 'x' },
            rvalue: Int_Contant_Class { token: '1' }
          },
          next: undefined
        },
        next: Return_Class {
          expr: Add_Class {
            lvalue: Indentifier_Class { token: 'x' },
            rvalue: Indentifier_Class { token: 'm' }
          }
        }
      }
    },
    formals: Formal_Class { name: 'x', type: 'int', next: undefined },
    next: Function_Class {
      formal_list: [ 'x', 'y' ],
      name: 'sum',
      expressions: Return_Class {
        expr: Add_Class {
          lvalue: Indentifier_Class { token: 'x' },
          rvalue: Indentifier_Class { token: 'y' }
        }
      },
      formals: Formal_Class {
        name: 'y',
        type: 'int',
        next: Formal_Class { name: 'x', type: 'int', next: undefined }
      },
      next: Function_Class {
        formal_list: [],
        name: 'main',
        expressions: Assign_Class {
          name: 'x',
          ltype: 'int',
          r: Caller_Class {
            params_list: [ '10' ],
            id: 'total',
            params: Int_Contant_Class { token: '10' },
            next: undefined
          },
          next: Caller_Class {
            params_list: [ 'x' ],
            id: 'print',
            params: Indentifier_Class { token: 'x' },
            next: undefined
          }
        },
        formals: undefined,
        next: undefined,
        return_type: 'int'
      },
      return_type: 'int'
    },
    return_type: 'int'
  }
}

汇编代码生成思路：遍历ast自上向下进行运用仓库机代码生成，因为本言语比较简略，仅运用了3个寄存器，a0，v0，t0，其中v0是辅助寄存器协助函数回来值存储以及系统调用的退出和打印；

cgenForSub(e1, e2) {
	cgen(e1)
	sw $a0, 0($29)
	addiu $29, $29, -4
	cgen(e2)
	add $a0, $t0, $a0
}

这儿最重要的点是对声明变量的内存分配以及取变量的时分，要知道对应的效果域链，该从哪个效果域获取变量，只要咱们对根本的一些单元表达式做好了代码生成的作业，后边便是搭积木的作业了；下面是该言语的函数栈示意图：

函数仓库示意图

这儿怎么取参数？因为函数栈在扩增的时分，不太便利通过sp指针获取参数和变量的存储位置，所以这儿运用fp指针去作为基地址，寻觅参数和局部变量关于效果域问题是采用的树结构存储(双向链表)，每次从当时所在效果域内寻觅变量，再持续依次向上寻觅，直到找到函数级效果域；

八、编写代码高亮语法插件：我这儿是速成版，比较简略，只触及简略的语法部分需求安装： $ npm install -g vsce $ npm install -g yo 假如是需求编写全新的插件，则运转yo code 挑选 new Language Support，提示一些问题，按需填写即可，插件名称尽可能仅有，否则在插件市场里不好搜，运转完指令之后会有一个生成目录，编写高亮语法的文件在 xxx.tmLanguage.json 文件里，假如你只是装备一个 VS Code 中已有言语的语法，记住删掉生成的 package.json 中的 languages 装备。 www.bookstack.cn/read/VS-Cod…

这儿看下我的规则：

  "editor.tokenColorCustomizations":{
    "[Default Dark+]": { // 这儿是自己所挑选的主题色彩，我的是vscode默认的色彩
      "textMateRules": [
        {
          "scope": "identifier.name", // 自界说或许契合标准规范的命名，对应插件里的xxx.tmLanguage.json文件里的name选项
          "settings": {
              "foreground": "#33ba8f"
          }
      },
      {
        "scope": "id.name.mc",
        "settings": {
            "foreground": "#eb8328"
        }
      }
      ]
    }
  }
```
xxx.tmLanguage.json里的装备：
``` json
{
	"$schema": "https://raw.githubusercontent.com/martinring/tmlanguage/master/tmlanguage.json",
	"name": "minic",
	"patterns": [
		{
			"include": "#keywords"
		},
    {
      "include": "#type"
    },
    {
      "include": "#number"
    },
    {
      "include": "#id"
    },
    {
      "include": "#comment"
    }
	],
	"repository": {
    "type": {
			"patterns": [{
				"name": "support.type.primitive.mc",
				"match": "\b(void|int|bool)\b" // 类型
			}]
		},
    "keywords": {
			"patterns": [{
				"name": "keyword.control.mc",
				"match": "\b(if|while|for|return|else)\b" // 关键字
			}]
		},
    "number": {
			"patterns": [{
				"name": "constant.numeric.mc",
				"match": "\b[0-9]+\b" 
			}]
		},
    "id": {
			"patterns": [{
				"name": "id.name.mc",
				"match": "\b[a-z][a-z0-9]*\b"
			}]
		},
    "comment": {
			"patterns": [{
				"name": "comment.line.double-dash",
				"match": "^//.*" //注释
			}]
		}
	},
	"scopeName": "source.mc"
}

参阅文章

LL1文法、LR(0)文法、SLR文法、LR(1)文法、LALR文法 [栈和栈帧)

LL(1),LR(0),SLR(1),LALR(1),LR(1)对比与剖析

语法剖析——自底向上语法剖析中的规范LR和LALR

node实现简易编译器

介绍

Parser

构建笼统语法树

AST生成

参阅文章

作者信息

推广

node实现简易编译器

介绍

Parser

构建笼统语法树

AST生成

参阅文章

相关文章

Git之使用GitHub搭建远程仓库

Compose之主题

【技术管理】我该如何和表现差的员工谈绩效呢？

关于 DataLeap 中的 Notebook你想知道的都在这

作者信息

推广