免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: 蔡万钊

一步步实现QBASIC编译器 [复制链接]

论坛徽章:
3
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:58:11数据库技术版块每日发帖之星
日期:2015-08-30 06:20:00
发表于 2012-11-23 14:42 |显示全部楼层
回复 20# sonicling


    js 是 github 上第一流行的语言

论坛徽章:
3
摩羯座
日期:2013-11-12 20:06:19午马
日期:2013-11-27 16:35:55双鱼座
日期:2014-04-04 19:02:30
发表于 2012-11-26 00:15 |显示全部楼层
忍不住插个楼,mark一下。

支持一个先

论坛徽章:
3
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:58:11数据库技术版块每日发帖之星
日期:2015-08-30 06:20:00
发表于 2012-11-26 21:49 |显示全部楼层
第三部: 设计一个良好的类型系统

任何语言都有类型,别管是动态类型还是静态,统统都是类型。

那么类型说到底是什么东西呢?


确切的来说,对编译器而言,一个“类型”就是其内存布局和绑定在这块内存上的操作。

整数,占用一个字长,能执行加减乘除运算,还能执行  和、或、异或 运算。更是能左移右移。神码运算都支持了。更重要的是,整数这个类型居然是可以不占用内存的:放到寄存器就可以了。
浮点数:能执行的运算和整数区别很小。除了不能执行二进制运算。分单精度和双精度。我这个BASIC编译器就只打算支持双精度浮点数。

字符串: 是的,BASIC语言里字符串是内置类型。既然是内置类型就能定义运算了。字符串能做加法,和到整数的自动转换(C语言不支持,可BASIC支持)。

数组:BASIC数组是可变长度的,能执行的运算只有一种,下标访问。可变数组只能是一维的。

矩阵:矩阵是固定长度的多维数组。能执行矩阵数学里定义的四则运算。

结构体:结构体只能执行一种运算:访问结构成员。



变量的定义的时候编译器需要为其安排存储空间(不考虑寄存器优化先)。全局变量的空间是分配在 可执行文件的.data区域,而对于函数局部变量,则是安排在栈上。编译器需要知道2个信息来进行
内存分配:变量大小和对齐。变量定义的时候要求一个类型(先不讨论QBASIC支持的 any 类型)类型就隐含了这2个信息。 那么变量名就是这个分配的内存的一个别名了。
如果是在栈上分配,则这个别名指的就是到栈基址(x86 下的ebp, x86_64 下是 rbp ) 的偏移。所以你需要在函数的语法树里支持一个“符号表“ 来保存这种映射关系。


类型的实现是通过 operator* 进行的。比如 A 和 B 两个变量是 整数,表达式 A + B , 对应的汇编应该是 load A  , Load B , add A B 这样的。
那么,从语法树的考虑就是   "A" 是个 reference , 到符号表找到分配的内存,应该是使用llvm::AllocaInst 分配的栈,然后对这个栈指针执行一个 LoadInst ,就获得了一个 llvm::Value*指针
这就是 A 这个变量了,然后同理对B进行操作。获得两个 llvm::Value* 指针,这个时候调用 AddInst 生成一个加法指令。结果就行了。

所以对 AddCacluationExpressionAST  的 codegen() 函数的写法应该是类似这样的

  1. AddCacluationExpressionAST::codegen()
  2. {
  3.     llvm::Value * lhs = this->lhs->codegen();
  4.     llvm::Value * rhs = this->rhs->codegen();

  5.     return builder.CreateAdd(lhs,rhs);
  6. }

复制代码
可是同样的语法树,对应的可能是不同类型的变量,所以这样的代码只能处理整数这种 llvm 直接支持的变量。对字符串就无能为力了。为此,我们需要进行一次抽象。
创建一个  TypeOperator 抽象类。为整数实现 NumberTypeOperator

  1. NumberTypeOperator::operator_add( ExprAST * lhs, ExprAST* rhs    )
  2. {
  3.     llvm::Value * lhs = this->lhs->codegen();
  4.     llvm::Value * rhs = this->rhs->codegen();

  5. llvm::Value *     val =  builder.CreateAdd(lhs,rhs);

  6.    return NumberExprAST(val); //用这个结果重新构造一个 表达式语句节点。
  7. }
复制代码
这样表达式语句的代码生成就是这样实现的了:

  1. AddCacluationExpressionAST::codegen()
  2. {
  3. return     lhs->type->getop()->operator_add(this->lhs,this->rhs)->codegen();

  4. }

复制代码
依据其类型( lhs->type)调用其操作符表,然后调用对应的操作符。

甚至如果在 用户定义的结构体的 operator_add() 处理里生成对用户重载的 operator + () 函数的调用,就实现了 类似 C++的操作符重载了。





论坛徽章:
0
发表于 2012-12-07 15:27 |显示全部楼层
开始还能勉强看懂,都后面就看不太懂了。
lz牛人。

论坛徽章:
3
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:58:11数据库技术版块每日发帖之星
日期:2015-08-30 06:20:00
发表于 2012-12-08 10:29 |显示全部楼层
抱歉,最近有点忙,会找个时间更新的!

论坛徽章:
0
发表于 2012-12-10 23:06 |显示全部楼层
谢谢分享,看了一下,我想楼主是否有笔误?第二步,语法分析中,提到AST表示源程序的语义.其实程序的语义一直没有很好的形式化方法,只是常采用语法制导而已,抽象语法树和解析树一样表示程序语法结构,但更简炼些.

论坛徽章:
1
天蝎座
日期:2013-12-06 18:23:58
发表于 2012-12-11 15:36 |显示全部楼层
赞,给力

论坛徽章:
2
程序设计版块每日发帖之星
日期:2015-06-17 22:20:00每日论坛发贴之星
日期:2015-06-17 22:20:00
发表于 2012-12-15 10:53 |显示全部楼层
值得细看                  

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-03 17:23:07综合交流区版块每日发帖之星
日期:2015-08-19 06:20:00综合交流区版块每日发帖之星
日期:2015-09-15 06:20:00
发表于 2013-01-05 17:35 |显示全部楼层
QBASIC,我最早学习的一门语言。比英语都早。呵呵~~

论坛徽章:
5
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53
发表于 2013-01-08 01:49 |显示全部楼层
插个楼,QBasic未必就比Go好,虽然我也完全无法适应Go的语法………………

QBasic因为历史原因,其类型系统还是非常原始的。缺乏能提供足够灵活性的一些特征:比如模板,或者类型推导,而Go在这方面就很现代了。

如果要在QBasic里面做类型推导,就不是单纯词法语法分析那么简单了,需要做到语义分析,这就是现代编译器的一个大难点。即使是C++11也已经带上了一些语义特征了(最直接的也是最浅显的一个例子,C++写模板声明已经不需要在嵌套尖括号之间打空格了,这就必须涉及到对一个语句本身语义上的理解)。

所以,如果要做一个真正在现代有实际价值的编译器,那么最起码还是需要做语义分析才行。这是最最前提的条件。

而其余的东西,都是有很成熟的理论了,基本上照本宣科即可。如同你写的代码,实际上也只是将语法整个写出来,然后交给别的工具去生成而已,未必就有多少技术含量,然而理解这些东西是如何把语法的描述格式具体变成分析代码的,这才需要技术——虽然是很成熟的技术了。

举个例子。你用了lex是吧?Lua的早期版本就是用lex&yacc做分析。后来因为编译效率的原因,改用了纯手写lex&parser。为什么呢?这就是理论的先进性了。通常《编译原理》教程上都说递归向下是很原始的语法分析器,而LL(1)LR(1)甚至SLAR(1)这些才是所谓的“先进”分析器。这已经是老黄历了。事实证明yacc的LR(1)和lex的LL(1)就是比递归向下慢——虽然递归向下在理论的时空分析上比上述算法慢,但是它的常数小,没有语法栈词法栈状态机什么的。所以实际上它就是比这些东西要快速。之所以clang宣称编译比gcc快好几倍,就是因为它是手写的语法/词法分析器而gcc是用的lex&yacc。

这也就是说,虽然看起来这样可以很容易地写一个编译器了:前端有lex&yacc,后端有llvm,但是实际上,如果不懂这些东西基本的实现原理,你写出来的东西还是没办法和现代的编译器如Go或者clang比较,而只是图个热闹罢了。

这让我想起来前几年的《十分钟建站》什么的文章,看上去好像很酷,实际上却只是教你如何使用别人做好的积木而已。这样子永远不会进步,而如果因为有了这种堆积木的能力就自信自大起来,那就真无药可救了。我大学里面就听说一哥们就很狂妄,学了Python啥都不怕,啥东西都简简单单能搞出来,但是只要他用的积木出问题了, 那么就没辙了,最可怕的是他还会将这种本质上是自己的知识浅薄或者无能怪罪在其他的东西上面。这种扭曲与其说是中国特色,倒不如说是类似暴发户的无知。

就如同现在中国人的普适价值观就是挣钱养家糊口,倒不是说是错的,但是如果人就是为了这些而活着,那和猪狗有什么区别呢?虽然活着才能谈价值,但是如果是以这种心态来奋斗的话,即使最后得到的东西远远不止可以挣钱养家糊口了,最终他们依然无法创造出符合其身份的价值。中国IT行业的怪现状,乃至于所有行业的怪现状,包括所谓的体制问题,都是由此引起的。

其实TG的理论虽然错漏百出,但是放在实践上,“科学的发展观”倒的确是非常必要的。然而很多人就都没了这种发展观,身价百万千万上亿还要在目视所及的地方放慢食物才会安心,有了大笔钱还要做纯金衬衫才满意,不能不说是一种讽刺。

倒不是说你的教材不好,虽然就我看来,在现在这种阶段,与其发明语言/写编译器,不如完全吃透一种语言的内在思想。但是,你所写的东西,恰巧就是去吃透一种思想的第一步。所以我还是很支持你的。就是希望在做了这些之后,能够再进一步,去深挖,而不是很浮躁地说“哇哇看我做了一个QBasic!我明天再做个javascript!后天我做个Python玩玩!!”这样就完全没有意义了。从QBasic的实现看其的设计思路和演变,看其不足,然后结合他的演变去追逐现代的设计思想和理念,最后将之超越,这才是“科学的发展观”。

说白了,就是用深度优先搜索的思路去探究和学习,而千万别用广度优先搜索了。

@Ager,你怎么看?
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP