分享 用 Ruby 做编译原理大作业

mizuhashi · 发布于 2017年03月12日 · 最后由 windwiny 回复于 2017年03月15日 · 918 次阅读
23529

https://github.com/CicholGricenchos/tiny-c

做了一个微型c编译器,大概四百来行,可以编译一些简单的c代码(参见测试用例)。

语法分析自己写了一套DSL,用深度优先搜索找一个可行的解,大概算是LL(0)?这样语法定义可以写的比较简洁,但是坏处是不能给出“unexpected token xxx”这样细致的提示,因为在搜索途中不知道哪个规则才是正确的。

有了语法树(sexp)之后,就可以直接塞到interpreter递归执行了,也可以塞到compiler生成汇编,同样是在一次递归里完成。

compiler会将每个语法树节点直译成汇编代码,途中想了好久应该怎么分配寄存器,但是还是搞不定,所以汇编中有不少多余的出入栈代码,来保证每个操作都是相互隔离的,当然代码也变慢了很多。不过能正确运行就很开心了。。

共收到 7 条回复
A908ae

不明觉厉

C4522b

可以继续看一些书,关于如何分配寄存器有很多算法了。 编译原理有意思的不是在写parser,而是在构建正确的执行模型和优化上面。 可以看看这方面的内容精进一下。

27936

词法分析的时候这样一次次匹配效率不高吧,用 Hash 可能情况好一点... 另外我感觉 C 最蛋疼的地方,一个是宏(完整地按照规范搞定这玩意儿要贯穿词法分析和语法分析阶段,条件宏里面还有常量表达式),一个是在分析的时候要一边走一边带个符号表,不然不知道一个 id 是变量名还是自定义的类型...

23529
27936ecnelises 回复

嗯。。类型定义应该要先跑一遍。。宏的话我自己都还不会用= =

681

哈哈,希望可以把 ruby 编译成二进制

5017

想不想挑战一下自己? 把flex移植到ruby吧

yacc 的 ruby 版 racc 已经很成熟了, flex却没有同一级别的代替

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册