chlang 初版

by chainhelen

关于chlang

这是个玩具解释器，通过完成它学习了许多关于编译器前端的知识点

github地址

本来这是个c语言项目，由于c语言实现实在过于繁琐，遂弃坑转为java，采用maven的项目管理结构

本语言主要参考了《自制编程语言》、c4的源代码

本文更新于2017.06.21

词法分析

词法分析器所在代码

主要有三个java文件构成，不讲一些自动机相关知识，默认已知

TOKEN_TYPE.java

  1. 主要描述符号类型，带有RW开头的表示Reserved Word，也就是保留关键词
  2. 最早期的开发比较简单，并没有 '>=' 这类的关系运算符，不会跟'='冲突产生太多的lookhead，这一部分是之后才加上的
  3. 语言中只支持两种基础数据类型，整型(int)和字符串(string)，当然为了实现闭包，还有函数这个数据类型，但不在这里体现

TOKEN.java

  1. 每一个符号都对应一个TOKEN对象，用来保存该符号信息
  2. 一开始我不知道JAVA一切皆对象这种神设定,所以内部有两个成员变量int String的类型。其实直接用Object保存万物即可。
  3. 还有一些"助攻类"的函数比如priToken

LEXER.java

  1. 词法分析源代码的主要逻辑
  2. line 代表当前解析到源代码的行数
  3. curLineFirstCharPosInSrcCode 主要用来辅助求 当发生解析错误情况 当前行的具体列数
  4. srcCurPos 当前解析源码字符在源码中索引
  5. src 保存传入的源码
  6. reservedWords 这个跟TOKEN_TYPE.java中RW保持一致，因为把保留词提出来，也可以利用词法分析的手段，具体看public LEXER(String src)的实现
  7. getNextToken() 返回下一个符号，并且解析继续下去，主要识别TOKEN_TYPE里面定义的类型，本质上是个自动机（正则表达式）
  8. lookHead() 返回下一个符号，但是解析不往下走，也就是说，如果再次调用lookHead()还是这个符号;

语法分析

语法分析器所在代码

ASTNODE_TYPE.java

  1. 主要表示抽象语法树上的节点类型，注意这时候就已经不需要括号这样类似的符号类型
  2. 注释中都有bnf范式，早期的实现是不支持关系运算符，所以之前代码中构成expression中元素中含有additive_expression，而不含equllity_expression
  3. bnf 范式中右式代表更原子(primitive)，比如equality_expression的右式含有relation_expression，那么可知程序中 ">=" 比 "==" 优先计算
  4. 函数声明中子节点参数parameterList，即便该没有参数，也应该保留这个节点
  5. 通常类c、java语言，函数（方法）的声明中不可以再次声明函数（方法），故而它们的 bnf 产生式 中block是不会出现函数声明的，例如 the bnf of java , 左式 method_declaration，而右式包含statement_block，statement_block的右式及其子式不含有method_declaration；但是要实现函数也可以 return 函数，就得允许这种语法存在，例如 the bnf of js ，找到这样一条路径Statement -> VariableStatement -> VariableDeclarationList -> VariableDeclaration -> Initialiser -> AssignmentExpression -> LeftHandSideExpression -> CallExpression -> MemberExpression -> FunctionExpression；所以在后期代码中 修改了产生式 StatementList 包含了 definition_statement 而不是 statement

ASTNODE

  1. 抽象语法树上的每一个节点都对应一个ASTNODE，这里的节点value我采用了Object类型，囊括比较麻烦的类型分装
  2. 后来为了加入控制流程，需要维护子节点的关系，所以引入了parentNode，nextNode，prevNode（后被证实无需引入亦可实现）
  3. 还有一些辅助函数

PARSER

  1. 语法分析核心流程，根节点一定是definitionOrStatement()，几乎对每种节点都对应写了一个函数（方法），并且返回对应该种节点类型的ASTNODE实例，由每个函数自己去构建父子关系，并且进行校验
  2. 比较注意的是设计BNF避免左递归，我从《自制编程语言》的BNF范式中感觉有左递归问题（但这一点我并没有进行实际考察）
  3. 由于我没有想好如何把抽象语法树画出来，所以添加了一个能导出xml格式AST的方法（函数）

虚拟机

这里我写废了，虚拟指令没有构建好，所以这里的代码是未完成的

解释部分

这种方式较虚拟机而言要粗暴点，代码在这里

SCOPE.java

  1. 这个地方比较复杂，开始没设计好，弄成了单向链表，上下文保存的信息都在 scope 其实应该也是棵树，这么说为了能够实现闭包
  2. SYMBOL_TYPE 就是identifier符号表类型，跟立即数（或者数字字面量、字符串字面量）不同，每一个identifier需要存储一些信息以供后面程序使用
  3. 除了基本数据类型，还有函数和INT（系统函数、中断，主要用来跟外界设备连接的）；每个函数对象能够对应一个 scope上的一棵节点，这样能够顺其树干查找 identifier 信息
  4. 符号的查找都是通过name找的

EVAL.java

  1. 最核心的解释过程，recursionEvalAstNode递归解释，每次传入一棵节点，比较麻烦的是上下文问题(看这里）；所以引入了CtrFlowFlag，当然这种引入是不友好的；比如导致很难实现setTimeout等类似的函数
  2. 解释过程，包含一些校验、和隐身强制，例如int + string 返回的结果是 string，但是 int - string 会报错
  3. expression的计算结果，是保存在栈上面的，上层节点可以从栈上取出结果然后重新封装进行压栈，以供上层节点使用；funtionDeclaration 和 functionCall 参数就很不同，一个是parameter(元素是identifier)，一个是argument(元素是expression)
  4. 当前执行上下文并不是单向链式的，例如突然执行了一个闭包函数，那么上下文节点是需要切换到树上非邻近的节点，但是总有某个时刻需要重新恢复，所以这里也采用了scopeNodeStack形式实现

测试

  1. 本来我想这是用callback的形式，将结果弄出来做assert，但是java实现回调这样搞，这样场景有点过度设计了
  2. 比较粗暴，把print 和 println 两个系统中断输入的数据除了输出以外还保存返回，用来test
  3. 主要看EVAL_Test.java的测试即可