一步步实现QBASIC编译器
本帖最后由 蔡万钊 于 2012-11-20 09:02 编辑为了学习编译原理, 找了个简单的语言编写编译器. 我选择了 QBASIC 这个人人都会的语言.
QBASIC 曾经有编译器, 在 16位时代的时候. 到了 32位时代, BASIC 语言就进入脚本行列, 解释执行
了. 到64位时代嘛 .. ... 恩恩, 没有编译器了. 解释器还算是有开源的几个.
QBASIC 语言漂亮,优雅别致. 简单易学. 大家不用它的原因无外忽无法和C 和谐共存. 而无法和C和谐
的原因很简单: 不是编译为本机代码.
所以, 我决定开始写一个QBASIC编译器, 能利用现代硬件, 利用上现代意义的优化能力的编译技术来
为 QBASIC 加速!
QBASIC 比 Go 语言简单多了, 如果能用编译解决效率问题, 自然打败Go不在话下.
幸运的是我们有 LLVM . 我只需要写个前端就可以了. 生成平台汇编的事情全权交给 llvm 打理了.
So, 这就是我的想法, 经过5 天紧张的开发, 已经实现基本功能了.
有人说我又写一个编译器, 是个国际笑话, so , 主题就如此了.
在这里宣布这样的事情是因为觉得可能找到共同兴趣的人能一起研究开发编译器.
我设定了3个目标:
1 实现完整的 QBASIC 语言. 至少是除了不建议使用的功能, 其他都要实现.
2 实现和C的无缝集成. 我将 BASIC 的函数调用约定设定为和C语言一致来解决这个问题. 因为是本
机码, 所以使用外部库的任务和C语言一样,交给链接器完成. 使用动态链接库不需要语言和运行时本
身的任何支持.
3 进行未来方向的语言扩展.
最后, 最重要的, show me the code
请移步访问 https://github.com/microcai/llvm-qbasic
实现方面的细节考虑:
1) QBASIC 支持数组, 数组的下标可以在定义的时候设定起始点. 第二, 数组自动扩展
实现办法: 数组实现为一个 STL 容器. 对下标的访问由编译器自动转化为对 operator [] 的调用.
operator 函数由编译器自动生成. 内置类型的operator则由运行时实现. 以便进行快速实现更好
的算法 变量离开作用域后要自动调用构析函数释放资源. 这样数组才不会导致内存泄漏.
2) 字符串. QBASIC 的字符串是内置类型. 字符串可以进行很多操作. 内存自动管理. 字符串可以做 +
法和比较运算.
实现办法: 字符串实际上为一个结构体, 由运行时库实现. 编译器自动插入对运行时的调用来完成
字符串操作. 字符串离开作用域要自动调用释放函数释放内存
3) PRINT/INPUT 语句. 和C不一样, BASIC 把 IO 操作内置为语言的一部分.
到目前为止我的编译器已经实现了部分的 PRINT 指令. 对打印到屏幕的PRINT语句直接转化为对
printf的调用. 这样一个不使用字符串,不输出到文件的QBASIC程序, 编译后将只依赖 C 运行时.
PRINT 有个可选的参数 #(数字) , 表示打印到数字指示的文件中. 这个必须由运行时来完成了.
4) 所有的运行时我都放到了libbrt - the qBasic RunTime library-里了. 目前为止没有任何实现. 运
行时默认将采取静态链接的方式. 对于生成脱离运行时的程序非常有用.
下面开始放出语言的实现教程- 请留意
本帖最后由 蔡万钊 于 2012-11-18 20:26 编辑
第一步: 词法分析
和所有语言其他语言一样, BASIC 语言由语句构成. 关键字和操作符号一起组成了语句的基本单位. 和 C 语言不一样的是 , QBASIC 的关键字特别多, 很多看起来像函数的操作其实是运算符. strlen() 都是运算符哦 ~
所有语言都需要把源文件分割为一个一个的 "token" , 每个 token 都有一定的类型, 比如"helloworld" 是一个 token , 类型是 字符串常量.IF是一个 token , 类型是 IF 关键字. 100 是一个 token , 类型是整数常量. 等等诸如此类.
将源码分割为正确的 token 并得出 token 类型, 这个过程就叫词法分析.
token一般采用正则表达式去匹配.使用* 这样的一个正则表达式就能匹配到一个正整数 ,\-* 则是负整数 [+\-]++.* 则是匹配到一个小数.
我们可以自己编写程序实现正则表达式, 将源码正确的隔离成 token 列表. 不过, 因为每个语言的第一步都是词法分析, 所以也就有了专门的工具自动生成词法解析器.
这样的一个工具就叫 LEX . GNU 出品的和 LEX 兼容的程序则是 flex (终于有了个不是g打头的gnu程序啊)
编写完成 lex 的规则后调用 lex 生成一个 C 源码的文件,其中包括了 yylex() 函数, 在自己的程序中调用此函数即可实现词法分析.
lex 的规则很简单一个正则表达式和一个 C语言的操作语句
ifprinrf("this is if\n");
elseprinrf("this is else\n");
\".*\"prinrf("this is a string\n");
上面的这个代码对输入执行三种匹配, 分别对匹配到的表达式执行执行3条 C 语句.
lex 遇到无法匹配的字符串将出现 词法错误, 所以要正确的编写 lex 规则, 将源码中能出现的所有合法 token 都编写对应的规则.
如果规则有多条 C 语句, 使用 {} 即可. 非常简单.
但是我们的匹配程序会一直执行, 直到
[*]出现词法错误
[*]遇到文件结束
这个时候我们只需要在 规则中加入 return 语句, 则词法分析函数 yylex() 就会返回.并且返回值就是在规则中指定的返回值. yylex() 可以再次调用,对源码的剩余部分继续执行匹配
好了, 有了这个行为我们的词法分析程序就是这样的
[*]打开源码, 将打开的文件赋值给 yyin
[*]调用 yylex() 获得一个 token 和一个 token 的类型( 规则里的 return 指定)
[*]继续调用直到完成词法分析
这样我们就获得了一个 token 连同其类型 (我们为每个关键字设定一个数字代表其类型) 的列表. 为了下一步的 语法分析奠定了基础.
本帖最后由 蔡万钊 于 2012-11-19 16:46 编辑
第二步,语法分析
语法分析是编译过程的第二步骤.
就和语言有 "主谓宾" 一样, QBASIC (连同世界上的其他计算机语言) 语言也是有一定的语法的.人类语言的语法要解析, 首先是确定单词的词性
, 名词还是动词 , 等. 计算机语言也是一样, 第一步词法分析就是确定了每个 token 的类型. 接下来就是根据类型确定这是什么语式.
要确定语式, 需要一定的语法规则, 这个语法的规则可以用BNF 范式进行描述.下面是一个数学四则运算表达式的 BNF 声明<expression> ::= <expression> + <expression>
| <expression> - <expression>
| <expression> * <expression>
| <expression> / <expression>
|( <expression> )
|<number>
表达式是一个递归定义:一个表达式可以是 两个表达式和一个运算符进行运算的结果, 也可以是一个括号中的表达式 (表示优先级了) , 最后才是简单的一个 number . 这个 number 是一个 token 由词法分析程序给出.
QBASIC 的语言也有 BNF 形式的描述。不过我更乐意自己从头写一个。
有了语法的 BNF 形式声明做什么呢？ 答案是写一个语法解析器。
语法解析器的任务是从词法分析程序接受token列表，然后依据BNF定义的语法规范生成一棵树结构，该结构代表了源程序的语义
这个树形数据结构就是 “抽象语法树”。语法分析的目的就是构筑 语法树。
本帖最后由 蔡万钊 于 2012-11-20 09:06 编辑
第二步：语法树定义 (2)：
语法树设计。
语法树是链接 语法分析和后端的桥梁。 良好的语法树能大大帮助简化汇编代码的生成。
语法树之所以称为 “抽象语法树” 因为它是抽象的 （废话）
语法树不一定是为某个语言设计， 事实上是， 一个良好设计的语法树能用服务于多个语言中。因为语言的基本控制流程都是一致的。 语法树有多个类型，分别对应到不同的语言操作上。但是都派生自同一个祖先。利用 C++ 的继承机制可以很轻松的实现。
QBASIC 是行语言， 每行一个或多个语句。一行有多个语句则用 ':' 冒好分隔。那么就定义一个 结构表示一个语句。 语句为一个语言的基本单位。
一个函数可以表示多个语句， 故而函数是“多个语句的集合体” 。 定义一个结构体收容 “多个语句” 。
这个结构体就是 “代码块” 。 代码块在 BNF 声明中采用的是递归定义：<codeblock> ::= <statement> | <codeblock> <seperator> <statement>
一个语句是一个代码块，多个用分隔符给出的语句集合体也是代码块。
一个语句有两种形式 ：声明和表达式。 声明就即变量声明， 函数原型声明，表达式则为数学运算。 注意一点： 函数调用也是表达式。 函数的返回值就是表达式的值。
表达式+ 回车就是一个语句。 或者是多个表达式用 “:” 隔开。 ':' 和 回车在分隔表达式的作用中语义是一样的。 也就是说， 用 BNF 语义就是这个描述形式<statement> ::= <expression> <seperator> |<statement> <expression> <seperator>
因为 expression 是递归定义的, 所以我们首先定义一个 expression 节点, 然后让所有其他类型的 expression 继承自expression 基类.
expression 要提供 代码生成 getval() 虚函数, 返回值应当是一个寄存器的引用.
说老实话，超级感兴趣。支持楼主。先认真学习你的代码和帖子。 第二步: 语法分析(3)
语法分析既然有个规范的 BNF 描述, 有没有一个自动化的程序, 拿一个 BNF 声明就能自动生成语法解析程序呢 ?
答案当然是有的 !
这样的程序就叫 yacc ( Yet Another Compiler Compiler) , GNU 出品的就是 bison , 兼容yacc.
yacc 的规则很简单 : 一个类 BNF 的声明和一个对应的 C 代码块.
和 lex 一样, yacc 处理 规则文件 (通常使用.y 扩展名) 后, 生成 一个C 文件,该文件实现了 yyparser() 函数. 这个函数就是语法解析程序了. yyparser 需要一个外部函数yylex() , 通过它调用词法分析程序.
等等, 你刚刚说yylex() ? 那不就是 lex 生成的么?
没错, lex & yacc 天生就是一对搭档. :)
语法分析(4)
yacc/bison 使用的语法和 BNF 非常接近, 看的懂 BNF 就看的懂 yacc/bison.
bison 匹配一条规则后, 就转而执行该规则定义的 C 代码块,expression: call_function
| '(' expression ')' { $ = $2 ;}
| expression '+' expression { $ = new CalcExprAST( $1, OPERATOR_ADD , $3 );}
| expression '-' expression { $ = new CalcExprAST( $1, OPERATOR_SUB , $3 );}
| expression '*' expression { $ = new CalcExprAST( $1, OPERATOR_MUL , $3 );}
| expression '/' expression { $ = new CalcExprAST( $1, OPERATOR_DIV , $3 );}
| expression tLTN expression { $ = new CalcExprAST( $1, OPERATOR_LESS , $3 );}
| expression tLEQ expression { $ = new CalcExprAST( $1, OPERATOR_LESSEQU , $3 );}
| expression tGTN expression { $ = new CalcExprAST( $1, OPERATOR_GREATER , $3 );}
| expression tGEQ expression { $ = new CalcExprAST( $1, OPERATOR_GREATEREQUL , $3 );}
| varref {
$ = new VariableExprAST( $1 ); // 变量引用也是一个表达式
}
| tInteger{
//常量
$ = new ConstNumberExprAST( $1 );
}
| tNUMBER //浮点数
| tSTRING { //字符串
$ = new ConstStringExprAST($1);
}
;
这里我为 表达式构造. CalcExprAST 是一个表达式基类的派生类, 它接受2个表达式和一个操作符作为构造函数, 生成含有2个子节点的表达式树. 表达式还可以继续包含子表达式, 这样就构成了一颗庞大的表达式树. 在后端, 我们会遍历这棵树,递归调用每一个节点生成汇编代码.
表达式处理是 AST 最重要也是最简单的部分 :)
chinaunix 的排版还真是不好做啊 .... 本帖最后由 蔡万钊 于 2012-11-20 09:48 编辑
语法解析(5) - 控制和代码块
程序可以说, 就是表达式和控制表达式的执行的控制流程组成的. 不同的语言其实只是不同在支持的表达式的"表意形式"和支持的控制流程语法形式不一样而已.
QB 语言和所有其他语言一样, 有 for 循环, while 循环, 有 if 条件判断, 有 switch 条件判断. 当然, 最简单的控制流程谁都支持的 : 顺序执行.
一个顺序执行的多行代码是 "代码块" . 代码快可以保护子代码块. 子又有子, 子又有孙. 这是个递归定义. 代码块是 AST 的一个非常重要的部分 . 所有其他的控制流程都基于代码块构建.
一个代码块包含一条进入语句, 多行顺序执行语句, 和多个退出语句. 之所以说是多个退出语句, 是因为代码块可以包含 goto . 但是从编译期角度来看, 一个 goto 可不能生成一个 jmp 了事情 (当然, 简单如 C 语言可以这么干)编译器遇到 goto 还得执行变量清理--- 离开作用域的变量必须正确的释放资源, 这是 QB 相比 C 语言在设计编译期上的一个难点 --- 清理变量这个操作就是代码块的退出语句. 这个由编译器自动生成 , 插入到流程跳转语句的执行之前. 这么说来, QB 和 C++ 差不多了, 有自动析构一说.
一个代码块既然有变量清理任务,自然变量是从属于代码块的---- 注意, 很多人觉得变量是属于函数的 , 其实不然. 函数只是一个 被命名的代码块. 变量本身是从属于代码块的.
那么, 代码块的 AST 必定是要包含一个符号表 , 所有在符号表中注册了的变量, 在流程跳出代码块的时候都要自动为其生成析构操作. 代码块的 AST 包含父级指针, 用户引用外部代码块的变量-- 这是一个链试符号表. 除了代码块层级的符号表, 还有个 "全局符号表" . 只有回朔到最顶层代码块依然无法找到变量声明的时候才访问全局符号表 --- QB 中, 全局符号表依然没有该变量声明, 那就 "就地声明" . 虽然这是一个非常不要的编程习惯, 但是 QB 语言标准说支持, 编译器作者自然要服从.
语法树的结构图