본문으로 건너뛰기
黯羽轻扬매일 조금씩

the-super-tiny-compiler 소스 코드 해석

무료2018-09-03#JS#compiler in JavaScript#JS写编译器#编译原理JavaScript#抽象语法树

200 행 정도의 JS 로 쓴 "참새형"컴파일러

一.목표

컴파일러를 구현함으로써 간단한 식 변환을 서포트하고, Lisp 스타일의 함수 호출을 C 스타일로 변환합니다. 예를 들어:

              LISP-style              C-style
2 + 2         (add 2 2)               add(2, 2)
4 - 2         (subtract 4 2)          subtract(4, 2)
2 + (4 - 2)   (add 2 (subtract 4 2))  add(2, subtract(4, 2))

즉 (add 2 2) 를 입력하고, add(2, 2) 를 출력하는 것을 요구합니다

二.설계

컴파일 작업을 3 개의 부분으로 분할합니다:

  • 해석:코드 문자열을 추상 표현으로 변환

  • 변환:추상 표현을 원하는 형태로 수정

  • 코드 생성:변환済みの 추상 표현을 새로운 코드 문자열로 변환

여기서의 해석에는 어휘 해석과 구문 해석이 포함되며, 어휘 해석기가 코드 문자열을 일련의 어휘 유닛 (token) 으로 변환하고, 그 후 구문 해석기가 구문 구조 (구문 성분 및 그 관계를 포함) 를 기술할 수 있는 중간 표현 형식 (Intermediate Representation) 또는 추상 구문 나무 (Abstract Syntax Tree) 를 생성합니다

구조로 보면, 어휘 유닛은 독립된 구문 성분 (수치, 라벨, 구두점, 연산자 등) 을 기술하는 작은 오브젝트의 그룹이고, 추상 구문 나무 (약칭 AST) 는 깊은 네스트된 오브젝트로, 처리하기 쉽고 구문 구조 정보를 휴대하고 있습니다. 예를 들어:

// 代码字符串
(add 2 (subtract 4 2))
// 词法单元
[
  { type: 'paren',  value: '('        },
  { type: 'name',   value: 'add'      },
  { type: 'number', value: '2'        },
  { type: 'paren',  value: '('        },
  { type: 'name',   value: 'subtract' },
  { type: 'number', value: '4'        },
  { type: 'number', value: '2'        },
  { type: 'paren',  value: ')'        },
  { type: 'paren',  value: ')'        },
]
// AST
{
  type: 'Program',
  body: [{
    type: 'CallExpression',
    name: 'add',
    params: [{
      type: 'NumberLiteral',
      value: '2',
    }, {
      type: 'CallExpression',
      name: 'subtract',
      params: [{
        type: 'NumberLiteral',
        value: '4',
      }, {
        type: 'NumberLiteral',
        value: '2',
      }]
    }]
  }]
}

변환 단계에서는 AST 를 수정합니다. 즉 위에서 생성된 트리 구조를 traverse 하여, 노드 레벨의 조작 (노드의 추가/삭제/변경) 과 속성 레벨의 조작 (속성의 추가/삭제/변경) 을 수행합니다. 물론, 새로운 트리를 생성할 수도 있습니다

구현상은, 깊이 우선 traverse 로 잘, 특별한 것은 없습니다. 노드마다 처리하는 것은조금 재미있습니다:

var visitor = {
  NumberLiteral: {
    enter(node, parent) {},
    exit(node, parent) {}
  },
  CallExpression: {
    enter(node, parent) {},
    exit(node, parent) {}
  },
  //...
};

노드를 방문하는 조작을 visitor 층으로서 꺼내고, traverse 過程中에 어휘 유닛 타입에 대응하는 enter/exit 메서드를 호출하기만 하면 됩니다. 이것은 약간의 테크닉입니다

AST 를 수정한 후, 마지막 코드 생성環節로 진행하여, traverse 하여 수집하고, AST 를 코드 문자열로 되돌립니다

三.구현

어휘 해석

// 接受代码字符串 input
function tokenizer(input) {
  // 当前正在处理的字符索引
  let current = 0;
  // 输出结果集合，存放词法单元
  let tokens = [];

  // 遍历字符串，挑出词法单元
  while (current < input.length) {
    let char = input[current];

    // 匹配左括号、右括号
    if (char === '(') {
      tokens.push({
        type: 'paren',
        value: '(',
      });
      current++;

      continue;
    }
    if (char === ')') {
      tokens.push({
        type: 'paren',
        value: ')',
      });
      current++;

      continue;
    }

    // 跳过空白字符
    let WHITESPACE = /\s/;
    if (WHITESPACE.test(char)) {
      current++;
      continue;
    }

    // 匹配数值
    let NUMBERS = /[0-9]/;
    if (NUMBERS.test(char)) {
      let value = '';

      // 匹配连续数字，作为数值
      while (NUMBERS.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({ type: 'number', value });

      continue;
    }

    // 匹配形如"abc"的字符串
    if (char === '"') {
      let value = '';

      // 吃掉左双引号
      char = input[++current];
      // 收集两个双引号之间的所有内容，作为字符串值
      while (char !== '"') {
        value += char;
        char = input[++current];
      }
      // 吃掉右边双引号
      char = input[++current];
      tokens.push({ type: 'string', value });

      continue;
    }

    // 匹配函数名，要求只含大小写字母
    let LETTERS = /[a-z]/i;
    if (LETTERS.test(char)) {
      let value = '';

      // 收集连续字母
      while (LETTERS.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({ type: 'name', value });

      continue;
    }

    // 无法识别的字符，报错
    throw new TypeError('I dont know what this character is: ' + char);
  }

  return tokens;
}

코드 문자열을 traverse 하여, 각 어소를 분할하고, 어휘 유닛의 형식에 패키지합니다

구문 해석

function parser(tokens) {
  // 当前正在处理的 token 索引
  let current = 0;

  // 递归遍历（因为函数调用允许嵌套），把 token 转成 AST 节点
  function walk() {
    let token = tokens[current];

    // 数值
    if (token.type === 'number') {
      current++;

      // 生成一个 AST 节点，表示数值字面量
      return {
        type: 'NumberLiteral',
        value: token.value,
      };
    }

    // 字符串
    if (token.type === 'string') {
      current++;

      return {
        type: 'StringLiteral',
        value: token.value,
      };
    }

    // 函数调用
    if (
      token.type === 'paren' &&
      token.value === '('
    ) {
      // 丢掉左括号，取下一个 token 作为函数名
      token = tokens[++current];

      let node = {
        type: 'CallExpression',
        name: token.value,
        params: [],
      };

      // 看下一个 token
      token = tokens[++current];

      // 右括号之前的所有 token 解析完都是参数
      while (
        (token.type !== 'paren') ||
        (token.type === 'paren' && token.value !== ')')
      ) {
        node.params.push(walk());
        token = tokens[current];
      }
      // 吃掉右括号
      current++;

      return node;
    }

    // 无法识别的 token，报错
    throw new TypeError(token.type);
  }

  // AST 的根节点
  let ast = {
    type: 'Program',
    body: [],
  };
  // 填充 ast.body，允许多条语句，所以放循环里
  while (current < tokens.length) {
    ast.body.push(walk());
  }

  return ast;
}

함수 호출의 네스트에 대응하기 위해, 재귀를 사용하여 token 시퀀스를 traverse 합니다

traverse

function traverser(ast, visitor) {
  // 遍历 AST 节点数组
  function traverseArray(array, parent) {
    array.forEach(child => {
      traverseNode(child, parent);
    });
  }

  function traverseNode(node, parent) {
    // 从 visitor 取出对应的一组方法
    let methods = visitor[node.type];
    // 通知 visitor 我们正在访问 node
    if (methods && methods.enter) {
      methods.enter(node, parent);
    }

    switch (node.type) {
      // 根节点
      case 'Program':
        traverseArray(node.body, node);
        break;
      // 函数调用
      case 'CallExpression':
        traverseArray(node.params, node);
        break;
      // 数值和字符串，没孩子，不用处理
      case 'NumberLiteral':
      case 'StringLiteral':
        break;

      // 无法识别的 AST 节点，报错
      default:
        throw new TypeError(node.type);
    }

    // 通知 visitor 我们要离开 node 了
    if (methods && methods.exit) {
      methods.exit(node, parent);
    }
  }

  // 开始遍历
  traverseNode(ast, null);
}

AST 구조를 재귀 traverse 하고, traverse 過程中에 visitor 에게 통지합니다. 측면 과 같은 느낌입니다

변환

// 输入 Lisp AST，输出 C AST
function transformer(ast) {
  // 新 AST 的根节点
  let newAst = {
    type: 'Program',
    body: [],
  };

  // 偷懒以简单粗暴的方式维持新旧 AST 的联系，方便在遍历过程中操作新 AST
  ast._context = newAst.body;

  // 创建 vistor，开始遍历
  traverser(ast, {
    // 数值和字符串，直接原样插入新 AST
    NumberLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'NumberLiteral',
          value: node.value,
        });
      },
    },
    StringLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'StringLiteral',
          value: node.value,
        });
      },
    },

    // 函数调用
    CallExpression: {
      enter(node, parent) {
        // 创建不同的 AST 节点
        let expression = {
          type: 'CallExpression',
          callee: {
            type: 'Identifier',
            name: node.name,
          },
          arguments: [],
        };

        // 函数调用可以有孩子，建立节点对应关系，供子节点使用
        node._context = expression.arguments;

        // 顶层函数调用算是语句，包装成特殊的 AST 节点
        if (parent.type !== 'CallExpression') {
          expression = {
            type: 'ExpressionStatement',
            expression: expression,
          };
        }

        parent._context.push(expression);
      }
    }
  });

  return newAst;
}

traverse(traverser) 와 수정 (visitor) 조작이 2 층으로 분리되어 있기 때문에, 구 AST 노드를 traverse 하는 동시에, 대응하는 신 AST 부모 노드를 명확히 아는 것은 그다지 용이하지 않습니다. 여기서간단 포폭 인 방식을 채용하고, 직접 새로운 _context 속성을 추가함으로써 구 AST 노드의 부모 노드에 조작 대상의 신 AST 노드 참조를 갖게 합니다. 사용할 수 있지만, 구 AST 를 오염시킵니다

코드 생성

// 递归遍历新 AST，输出代码字符串
function codeGenerator(node) {
  switch (node.type) {
    // 根节点，把 body 里的所有内容都生成一遍，按行输出
    case 'Program':
      return node.body.map(codeGenerator).join('\n');

    // 表达式语句，处理其表达式内容，并添上分号
    case 'ExpressionStatement':
      return (
        codeGenerator(node.expression) + ';'
      );

    // 函数调用，添上括号，参数用逗号分隔
    case 'CallExpression':
      return (
        codeGenerator(node.callee) +
        '(' +
        node.arguments.map(codeGenerator).join(', ') +
        ')'
      );

    // 标识符，数值，原样输出
    case 'Identifier':
      return node.name;
    case 'NumberLiteral':
      return node.value;

    // 字符串，用双引号包起来再输出
    case 'StringLiteral':
      return '"' + node.value + '"';

    // 无法识别的新 AST 节点，报错
    default:
      throw new TypeError(node.type);
  }
}

AST 를 다시 코드 문자열로 되돌리고, 세미콜론을 추가해야 할 것은 세미콜론을 추가하고, 괄호를 추가해야 할 것은 괄호를 추가합니다……

플로 연결

function compiler(input) {
  let tokens = tokenizer(input);
  let ast    = parser(tokens);
  let newAst = transformer(ast);
  let output = codeGenerator(newAst);

  return output;
}

위의 모든環節을 연결하고, 간단한 컴파일러를 구성합니다. 확실히 200 행 정도의 모습입니다.试玩一下:

const input  = '(add 2 (subtract 4 2))';
let output = compiler(input);
// add(2, subtract(4, 2));
console.log(output);

四.최적화

2 개의 최적화 포인트:

  • 어휘 해석:문자마다 매치하는 것은 중복되고, 효율이 허용할 수 있는 경우, 정규 표현식이 더 명확

  • 변환:새로운 AST 를 생성하는 방식은 더럽고, 구 AST 를 오염시킵니다. 추가의 데이터 구조를 통해新旧 AST 의 연락을 기록하고, 구 AST 에 영향을 주는 것을 회피할 수 있습니다

보다 명확한 어휘 해석

예를 들어 각 어소에 대응하는 정규 표현:

const REGEX = {
  PAREN: /^\(|^\)/,
  WHITESPACE: /^\s+/,
  NUMBERS: /^\d+/,
  STRING: /^"([^"]+)?"/,
  NAME: /^[a-z]+/i
};

while (rest.length > 0) {
  let type, value;
  // 匹配结果，本次匹配消费掉的串长度
  let matched, span;

  // 匹配左括号、右括号
  if (matched = rest.match(REGEX.PAREN)) {
    type = 'paren';
  }
  //...匹配其它词素

  value = value || matched[0];
  tokens.push({type, value});
  rest = rest.slice(span || matched[0].length);
}

비교 명확해졌습니다. 확장성을 향상하고 싶은 경우, 어소 관련의 type, value, span 을 더욱구성화 할 수 있습니다:

// 词素相关配置
const lexemes = [
  {
    regex: /^\(|^\)/,
    type: 'paren',
    value: 0,
    span: 0
  }, {
    regex: /^\d+/,
    type: 'number',
    value: 0,
    span: 0
  }, {
    regex: /^"([^"]+)?"/,
    type: 'string',
    value: 1,
    span: 0
  }, {
    regex: /^[a-z]+/i,
    type: 'name',
    value: 0,
    span: 0
  }
];

然后以统一的方式处理这些词素:

while (rest.length > 0) {
  // 跳过空白字符
  if (matched = rest.match(/^\s+/)) {
    rest = rest.slice(matched[0].length);
    continue;
  }

  lexemes.forEach(({regex, type : t, value: v, span: s}) => {
    if (matched) return;
    if (matched = rest.match(regex)) {
      type = t;
      value = matched[v];
      span = matched[s].length;
    }
  });

  if (matched) {
    tokens.push({type, value});
    rest = rest.slice(span);
  }
  else {
    // 无法识别的字符，报错
    throw new TypeError('Unexpected character: ' + rest);
  }
}

보다 클린한 변환

새로운 트리를 생성하려면 2 가지 일을 수행해야 합니다:

  1. 노드 매핑

  2. 트리 구조의 작성

노드 매핑은 쉽지만, 새로운 노드를 어디에 걸어야 하는지가 문제 입니다. visitor 와 transformer 는 구현상은 독립한 2 층이므로,新旧 2 개의 트리의 연락을 수동으로 기록할 필요가 있습니다. 예를 들어 위 변환 부분 소스 코드 중의:

// 偷懒以简单粗暴的方式维持新旧 AST 的联系，方便在遍历过程中操作新 AST
ast._context = newAst.body;
// 函数调用可以有孩子，建立节点对应关系，供子节点使用
node._context = expression.arguments;

이로써 현재 방문 중인 구 노드에 대응하는 신 노드를 신 트리의 어느 위치에 걸어야 하는지가わかります. 예를 들어:

// 旧树中父节点身上挂着对应新树节点的孩子数组，把新节点填进去
parent._context.push({
  type: 'NumberLiteral',
  value: node.value,
});

그러나 이 구현은 더럽습��다 (传入된 구 트리 ast 를 오염시킵니다). 보다 합리적인做法은 비침입적인 방식으로 신 트리 중의 현재 액티브한 노드 컨테이너를 기록하는 것으로, 함수 호출은 네스트를 허가하므로, 스택 구조를 사용하여 기록할 필요가 있습니다:

// 用额外的数据结构维持新旧 AST 的联系
let stack = [newAst.body];
function peak() {
  return stack[stack.length - 1];
}

구 트리를 재귀 traverse 하는過程中에 이 연락을 유지합니다:

// 函数调用
CallExpression: {
  enter(node, parent) {
    // 取出活跃的新树节点容器
    let newASTHost = peak();

    // 创建新树节点
    let expression = {
      type: 'CallExpression',
      callee: {
        type: 'Identifier',
        name: node.name,
      },
      arguments: [],
    };

    // 函数调用可以有孩子，建立节点对应关系，供子节点使用
    stack.push(expression.arguments);

    // 填充新树结构
    newASTHost.push(expression);
  },
  leave(node, parent) {
    // 参数收集结束，回到上一层
    stack.pop();
  }
}

이로써 구 트리를 오염시키는 일은 없어지고, 비용도 그다지 높지 않습니다 (추가의 데이터 구조 stack 1 개)

五.소스 코드

Github 주소:https://github.com/ayqy/the-super-tiny-compiler

P.S.상세한 주석付き의原版 및 최적화 후의 구현을 포함합니다

참고 자료

댓글

아직 댓글이 없습니다

댓글 작성