chlang 初版

关于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_blockstatement_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. 后来为了加入控制流程,需要维护子节点的关系,所以引入了parentNodenextNodeprevNode(后被证实无需引入亦可实现)
  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的计算结果,是保存在栈上面的,上层节点可以从栈上取出结果然后重新封装进行压栈,以供上层节点使用;funtionDeclarationfunctionCall 参数就很不同,一个是parameter(元素是identifier),一个是argument(元素是expression)
  4. 当前执行上下文并不是单向链式的,例如突然执行了一个闭包函数,那么上下文节点是需要切换到树上非邻近的节点,但是总有某个时刻需要重新恢复,所以这里也采用了scopeNodeStack形式实现

测试

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