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

mizuhashi · March 12, 2017 · Last by windwiny replied at March 15, 2017 · 2435 hits

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

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

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

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

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

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

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

Reply to ecnelises

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

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

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

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

You need to Sign in before reply, if you don't have an account, please Sign up first.