编译原理:
lexical analyze -> syntax analyze -> build Abstruct Syntax Tree -> convert AST to Concreat Syntax Tree -> Generating "register reallocate" intermediate language -> Generating NATIVE assembly -> native machine code -> executable object .
为了学习编译原理, 找了个简单的语言编写编译器. 我选择了 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 支持数组, 数组的下标可以在定义的时候设定起始点. 第二, 数组自动扩展 实现办法: [1] 数组实现为一个 STL 容器. 对下标的访问由编译器自动转化为对 operator [] 的调用. operator 函数由编译器自动生成. [2] 内置类型的operator则由运行时实现. 以便进行快速实现更好 的算法 [2] 变量离开作用域后要自动调用构析函数释放资源. 这样数组才不会导致内存泄漏.
2) 字符串. QBASIC 的字符串是内置类型. 字符串可以进行很多操作. 内存自动管理. 字符串可以做 + 法和比较运算. 实现办法: 字符串实际上为一个结构体, 由运行时库实现. 编译器自动插入对运行时的调用来完成 字符串操作. 字符串离开作用域要自动调用释放函数释放内存
3) PRINT/INPUT 语句. 和C不一样, BASIC 把 IO 操作内置为语言的一部分. 到目前为止我的编译器已经实现了部分的 PRINT 指令. 对打印到屏幕的PRINT语句直接转化为对 printf的操作. 这样一个不使用字符串,不输出到文件的QBASIC程序, 编译后将只依赖 C 运行时. PRINT 有个可选的参数 #(数字) , 表示打印到数字指示的文件中. 这个必须由运行时来完成了.
4) 所有的运行时我都放到了 libbrt - the qBasic RunTime library -里了. 目前为止没有任何实现. 运 行时默认将采取静态链接的方式. 对于生成脱离运行时的程序非常有用.
恩, 好了,大概就那么多. 困死啦 ~~ 睡觉.
在 2012年11月16日 星期五 13:27:45,Ma Xiaojun 写道:
不錯的嘛? 不過你確定FreeBASIC是解釋器而不是編譯器?
去年尝试的时候还不支持 64位. 不知道现在怎么样了.
这个是解释+编译的. 大致看了一下代码历史,好像有个分支采用 llvm 后端了.
http://www.freebasic.net/
Fedora中文郵件列表:https://admin.fedoraproject.org/mailman/listinfo/chinese
2012/11/16 微蔡 microcai@fedoraproject.org:
这个是解释+编译的. 大致看了一下代码历史,好像有个分支采用 llvm 后端了.
什麼叫解釋+編譯? 不如你也參與這個?我初學編程的時候用FreeBASIC寫過一些簡單的遊戲,感覺很方便,至今沒有發現更方便的2D圖形環境。雖然我應該已經受不了BASIC的語法了……
在 2012年11月16日 星期五 19:03:48,Ma Xiaojun 写道:
2012/11/16 微蔡 microcai@fedoraproject.org:
这个是解释+编译的. 大致看了一下代码历史,好像有个分支采用 llvm 后端了.
我打算扩展BASIC语言, 参加别人的项目会无法自由的进行我的扩展
现在决定的扩展(已经实现了)就是自由的调用C库函数.
什麼叫解釋+編譯? 不如你也參與這個?我初學編程的時候用FreeBASIC寫過一些簡單的遊戲,感覺很方便,至今沒有
發現更方便的2D圖形環境。雖然我應該已經受不了BASIC的
語法了…… -- Fedora中文郵件列表:https://admin.fedoraproject.org/mailman/listinfo/chinese
你沒回答我的問題……
On 11/17/2012 02:53 AM, 微蔡 wrote:
现在决定的扩展(已经实现了)就是自由的调用C库函数.
其實FreeBASIC我覺得已經有點過於C化了,BASIC就是要壓根不需要理解什麼是指 針才帶感。我最早學C的時候,最驚訝的就是C的字符串處理居然這麼原始這麼麻煩。 當然我現在理解了,Unix上有Shell/AWK/Tcl/Perl/Python,C這樣的底層工具不需 要提供太高的抽象。 只不過你把BASIC也帶入C指針那萬劫不復的深淵做什麼呢?還是說你另有高明的辦法? BASIC語法確實簡單,不想現在除C、Shell之外的語言的語法基本都複製到不行, 一個string literal都要幾種引號幾種花樣,更別說其他語法糖了。 但是BASIC的語法並不甜,就算是以前大概也是不寫分號,然後有些明明應該是函 數的語句所以就感覺比較簡單好用。雖然Python以前也是把print當做語句的……
在 2012年11月17日 星期六 03:22:08,Xiaojun Ma 写道:
你沒回答我的問題……
On 11/17/2012 02:53 AM, 微蔡 wrote:
现在决定的扩展(已经实现了)就是自由的调用C库函数.
其實FreeBASIC我覺得已經有點過於C化了,BASIC就是要壓根不需要理解什麼是指 針才帶感。我最早學C的時候,最驚訝的就是C的字符串處理居然這麼原始這麼麻煩。 當然我現在理解了,Unix上有Shell/AWK/Tcl/Perl/Python,C這樣的底層工具不需 要提供太高的抽象。
和C有什么关系. 能自由的调用 C 接口是为了可以在BASIC 里使用现有的大量的库函数. 和C语言本身 又没有关系.
只不過你把BASIC也帶入C指針那萬劫不復的深淵做什麼呢?還是說你另有高明的辦法? BASIC語法確實簡單,不想現在除C、Shell之外的語言的語法基本都複製到不行, 一個string literal都要幾種引號幾種花樣,更別說其他語法糖了。 但是BASIC的語法並不甜,就算是以前大概也是不寫分號,然後有些明明應該是函 數的語句所以就感覺比較簡單好用。雖然Python以前也是把print當做語句的……
本来就是纯正的 QBASIC. 另外加可以调用 C 函数. 因为是编译的, 所以只要调用约定和C保持一致就 可以相互调用, 这个不需要付出太大的努力, 只能说是 "编译" 的副产品.
于 2012-11-17 19:20, 微蔡 写道:
在 2012年11月17日 星期六 03:22:08,Xiaojun Ma 写道:
你沒回答我的問題……
On 11/17/2012 02:53 AM, 微蔡 wrote:
现在决定的扩展(已经实现了)就是自由的调用C库函数.
其實FreeBASIC我覺得已經有點過於C化了,BASIC就是要壓根不需要理解什麼是指 針才帶感。我最早學C的時候,最驚訝的就是C的字符串處理居然這麼原始這麼麻煩。 當然我現在理解了,Unix上有Shell/AWK/Tcl/Perl/Python,C這樣的底層工具不需 要提供太高的抽象。
和C有什么关系. 能自由的调用 C 接口是为了可以在BASIC 里使用现有的大量的库函数. 和C语言本身 又没有关系.
但是,FreeBASIC 不是就可以调用 C 么。。。我以前还调用过 GTK 写 GUI 呢。。
只不過你把BASIC也帶入C指針那萬劫不復的深淵做什麼呢?還是說你另有高明的辦法? BASIC語法確實簡單,不想現在除C、Shell之外的語言的語法基本都複製到不行, 一個string literal都要幾種引號幾種花樣,更別說其他語法糖了。 但是BASIC的語法並不甜,就算是以前大概也是不寫分號,然後有些明明應該是函 數的語句所以就感覺比較簡單好用。雖然Python以前也是把print當做語句的……
本来就是纯正的 QBASIC. 另外加可以调用 C 函数. 因为是编译的, 所以只要调用约定和C保持一致就 可以相互调用, 这个不需要付出太大的努力, 只能说是 "编译" 的副产品.
調用約定一樣就行? 那你函數名分不分大小寫?BASIC是不分的哦! 還有你怎麼整合C和BASIC的字符串?(其實這是N年前大家用VB6調用Win32 API的主要問題之一) 比如說fgets(str, num, stdin),你這個str得傳一個buffer進去吧,是靜態區,堆區,還是棧區? 當然真正噁心的地方是,C函數可能返回一個malloc的buffer,可能返回它自己的一個靜態buffer,也可能返回修改后的參數,你封裝到BASIC的string還是把細節暴露給用戶? 看了一下BASIC的字符串操作,似乎是immutable的語義(抱歉是VB的): http://en.wikibooks.org/wiki/Visual_Basic/Built_In_String_Functions immutable去和mutable整合,只能說看你能有什麼新發明了,如果把內存的細節完全暴露到BASIC層面,只能說這壓根就不是BASIC。
在 2012年11月17日 星期六 16:00:46,Ma Xiaojun 写道:
調用約定一樣就行? 那你函數名分不分大小寫?BASIC是不分的哦! 還有你怎麼整合C和BASIC的字符串?(其實這是N年前大家用VB6調用Win32 API的主要問題之
一)
比如說fgets(str, num, stdin),你這個str得傳一個buffer進去吧,是靜態區,堆區,還是棧區? 當然真正噁心的地方是,C函數可能返回一個malloc的buffer,可能返回它自己的一個靜態
buffer,也可能返回修改后的參數,你封裝到BASIC的s
BASIC 有自己的 INPUT 这个问题就别纠结了吧?
tring還是把細節暴露給用戶? 看了一下BASIC的字符串操作,似乎是immutable的語義(抱歉是
VB的):
别把 VB 套上来 . VB 是解释执行的 .
http://en.wikibooks.org/wiki/Visual_Basic/Built_In_String_Functions immutable去和mutable整合,只能說看你能有什麼新發明了,如果把內存的細節完全暴露到
BASIC層面,只能說這壓根就不是BASIC。
-- Fedora中文郵件列表:https://admin.fedoraproject.org/mailman/listinfo/chinese
2012/11/18 微蔡 microcai@fedoraproject.org:
BASIC 有自己的 INPUT 这个问题就别纠结了吧?
你覺得需要傳buffer的C函數很少麼……scanf只是一個例子,在libc裏面可能可以方便你測試而已……
别把 VB 套上来 . VB 是解释执行的 .
我只是引用VB字符串函數接口而已,這和VB怎麼實現有關嗎?和前面那個回答一樣,你根本就沒有回答我真正的問題。
字符串部分实现. print "hello world" 实现 a = "hello world" print a 也实现了
a = "hello world" 将会导致一个 strdup 调用. 离开作用域后a会被自动调用free()撤销字符串占用的 空间.
AGAIN : 只依赖 libc
NEXT: 实现字符串相加以及其他操作 & 字符串格式化操作.
NEXT: 数组
NEXT: 结构体
所有这些 BASIC 功能的实现,运行时除了libc都不需要依赖其他.
在 2012年11月17日 星期六 03:21:27,微蔡 写道:
编译原理:
lexical analyze -> syntax analyze -> build Abstruct Syntax Tree -> convert AST to Concreat Syntax Tree -> Generating "register reallocate" intermediate language -> Generating NATIVE assembly -> native machine code -> executable object .
为了学习编译原理, 找了个简单的语言编写编译器. 我选择了 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
实现方面的细节考虑:
- QBASIC 支持数组, 数组的下标可以在定义的时候设定起始点. 第二, 数组自动扩展 实现办法: [1] 数组实现为一个 STL 容器. 对下标的访问由编译器自动转化为对 operator [] 的调用.
operator 函数由编译器自动生成. [2] 内置类型的operator则由运行时实现. 以便进行快速实现更好 的算法 [2] 变量离开作用域后要自动调用构析函数释放资源. 这样数组才不会导致内存泄漏.
- 字符串. QBASIC 的字符串是内置类型. 字符串可以进行很多操作. 内存自动管理. 字符串可以做 +
法和比较运算. 实现办法: 字符串实际上为一个结构体, 由运行时库实现. 编译器自动插入对运行时的调用来完成 字符串操作. 字符串离开作用域要自动调用释放函数释放内存
- PRINT/INPUT 语句. 和C不一样, BASIC 把 IO 操作内置为语言的一部分. 到目前为止我的编译器已经实现了部分的 PRINT 指令. 对打印到屏幕的PRINT语句直接转化为对
printf的操作. 这样一个不使用字符串,不输出到文件的QBASIC程序, 编译后将只依赖 C 运行时. PRINT 有个可选的参数 #(数字) , 表示打印到数字指示的文件中. 这个必须由运行时来完成了.
- 所有的运行时我都放到了 libbrt - the qBasic RunTime library -里了. 目前为止没有任何实现.
运
行时默认将采取静态链接的方式. 对于生成脱离运行时的程序非常有用.
恩, 好了,大概就那么多. 困死啦 ~~ 睡觉.
我认为最好的string实现是STL中的rope
在 2012年11月19日 上午2:30,微蔡 microcai@fedoraproject.org写道:
字符串部分实现. print "hello world" 实现 a = "hello world" print a 也实现了
a = "hello world" 将会导致一个 strdup 调用. 离开作用域后a会被自动调用free()撤销字符串占用的 空间.
AGAIN : 只依赖 libc
NEXT: 实现字符串相加以及其他操作 & 字符串格式化操作.
NEXT: 数组
NEXT: 结构体
所有这些 BASIC 功能的实现,运行时除了libc都不需要依赖其他.
chinese@lists.fedoraproject.org