|
用VB+LLVM写一个山寨编译器 第一章 介绍+词法分析器 摘要: 首先声明，这个不是我原创的，主要是翻译这个 http://www./releases/2.8/docs/tutorial/LangImpl1.html 成VB的而已…… ===介绍=== 欢迎来到“用LLVM写一个山寨编译器”教程。整个教程演示了怎么实现一 ... 首先声明，这个不是我原创的，主要是翻译这个 http://www./releases/2.8/docs/tutorial/LangImpl1.html 成VB的而已…… ===介绍=== 欢迎来到“用LLVM写一个山寨编译器”教程。整个教程演示了怎么实现一个简单的语言，而且我们将看到这是多么地容易和有趣。（@#%^$^&@#$……剩下的基本上是废话(主要是我懒得译了)，大家有兴趣的自己看一下原文吧 ---译者注） 简单介绍一下每章的内容： 第一章、山寨语言的介绍和词法分析器的实现 - 介绍一下我们想让山寨语言能实现的基本功能。为了使代码简单而且便于修改，所有词法分析和语法分析的代码都用C++（被我黑成VB的了 ---译者注）实现，而不用自动词法分析和语法分析生成器…… 第二章、语法分析器和抽象语法树(AST)的生成 - 当词法分析器编好之后我们可以讨论语法分析技术和简单的AST生成。我们采用递归下降分析器和算符优先分析器。前两章都没有用到LLVM哟:)，就是编译原理的基本内容…… 第三章、LLVM IR 中间代码的生成 - 当AST生成之后我们将会看到，生成中间代码是多么的容易 第四章、即时编译器(JIT)和优化器 - 由于很多人对LLVM作为JIT感兴趣，所以我们在这里演示加上几行代码就可以实现JIT功能（VB不能简单地加几行代码就搞定，因为不支持函数指针 ---译者注） 第五章、给语言加上判断和循环语句功能 - 如题，这给我们讨论静态单赋值形式(SSA)和控制流优化的机会 第六章、用户自定义运算符 - 这是愚蠢但是有趣的一章，讨论怎么让用户自定义任意的单目和双目运算符（可以自己设置优先级!）这使得我们语言的很大一部分变成函数…… 第七章、变量的支持 - 讨论怎么让用户自定义局部变量，还有赋值运算符……还演示了怎么用LLVM创建SSA形式，事实上你的程序根本不需要手工创建SSA形式！ 第八章、结论 - 讨论了怎么继续扩展我们的山寨语言，例如数据类型、全局变量等，还包括垃圾收集器、错误处理、调试、spaghetti stacks（不懂是什么意思 ---译者注）等…… 最后我们写了不到700行（这是C++那个，VB的还不懂要写多少行 ---译者注）代码来实现一个语言的编译器，其中包括词法分析器、语法分析器、抽象语法树生成器、代码生成器和JIT编译器，功能还不少吧（就是缺了exe生成器，下次我再研究一下 ---译者注） 关于教程的注记：我们希望你能自己扩展源代码，并且在自己修改代码中找到乐趣。尽情地修改代码吧，编译器不是什么很可怕的东西，写编译器可以是一件很有趣的事情！ 补充内容 (2011-11-8 22:02): 后来我真的用VB写了个山寨Basic编译器，看这里http://code.google.com/p/yet-another-fake-basic/ 还有http://www./thread-107320-1-1.html 山寨语言的简单描述 我们这个山寨语言名字叫做“万花筒”（Kaleidoscope，这个名字怎么这么恶心啊 ---译者注）“万花筒”是一个基于过程的语言，允许你定义函数，使用判断语句，数学运算，等等。随着教程的推进，我们会逐渐加入if/then/else支持，循环支持，自定义运算符支持，JIT编译，等等…… 因为我们想使得事情保持简单，“万花筒”语言的唯一数据类型是64位浮点数，就是C里面的double（VB里面的Double）。所以“万花筒”里面的每个值都是双精度的，而且不需要声明数据类型。这使得“万花筒”语言的语法很简单举个例子，下面的代码是算斐波那契数的： # Compute the x'th fibonacci number. def fib(x) if x < 3 then 1 else fib(x-1)+fib(x-2) # This will compute the 40th number. fib(40) 我们还让“万花筒”语言能直接调用C的库函数（LLVM JIT使得这件事变成平凡的）。这意味着在使用一个函数之前，你能用“extern”关键字来声明这个函数（这在递归中也是要用到的）。举个例子： extern sin(arg); extern cos(arg); extern atan2(arg1 arg2); atan2(sin(.4), cos(42)) 第六章中有一个更有趣的例子，是用来显示曼德勃罗集的…… 接下来就是词法分析器的实现了…… 引用 download 2010-11-19 20:55 太好了,我也正在研究这个... 比较喜欢第四章...JIT 引用 acme_pjz 2010-11-19 21:00 先在VB里面实现一些C/C++的内部函数 新建一个窗体，放入Text1,Text2，全部设置为多行文本框，Text1.Locked=True；新建一个Command1，Default=True，标题设置成“输入”或者别的什么新建一个模块，定义全局变量m_bEOF As Boolean，m_sInputBuffer As String，m_nInputPos As Long…… 在窗体里面设置Command1_Click成m_sInputBuffer = m_sInputBuffer + Text2.Text + vbCrLf：Text2.Text = ""，相当于把Text2的内容加到输入缓冲区里面，然后清空Text2的内容……把Form_QueryUnload或者Form_Unload设置成OnDestroy，这个函数我们稍后定义…… 在模块里面定义全局函数OnDestroy，只有一句话，m_bEOF = True，表示程序退出了，标准输入完蛋了…… 定义常量Public Const EOF As Long = -1，把VB内置的EOF给覆盖掉反正我们用不到…… 写如下的脏代码，让VB也能用char类型（这是我上星期想出来的馊主意） 1. 2.Public Enum enumVBChar 3. ["\0"] = 0 4. ["\t"] = 9 5. ["\n"] = 10 6. ["\r"] = 13 7. [" "] = 32 8. ["!"] = 33 9. ["""] = 34 10. ["#"] = 35 11. ["$"] = 36 12. ["%"] = 37 13. ["&"] = 38 14. ["'"] = 39 15. ["("] = 40 16. [")"] = 41 17. ["*"] = 42 18. ["+"] = 43 19. [","] = 44 20. ["-"] = 45 21. ["."] = 46 22. ["/"] = 47 23. ["0"] = 48 24. ["1"] = 49 25. ["2"] = 50 26. ["3"] = 51 27. ["4"] = 52 28. ["5"] = 53 29. ["6"] = 54 30. ["7"] = 55 31. ["8"] = 56 32. ["9"] = 57 33. [":"] = 58 34. [";"] = 59 35. ["<"] = 60 36. ["="] = 61 37. [">"] = 62 38. ["?"] = 63 39. ["@"] = 64 40. ["a"] = 65 41. ["b"] = 66 42. ["c"] = 67 43. ["d"] = 68 44. ["e"] = 69 45. ["f"] = 70 46. ["g"] = 71 47. ["h"] = 72 48. ["i"] = 73 49. ["j"] = 74 50. ["k"] = 75 51. ["l"] = 76 52. ["m"] = 77 53. ["n"] = 78 54. ["o"] = 79 55. ["p"] = 80 56. ["q"] = 81 57. ["r"] = 82 58. ["s"] = 83 59. ["t"] = 84 60. ["u"] = 85 61. ["v"] = 86 62. ["w"] = 87 63. ["x"] = 88 64. ["y"] = 89 65. ["z"] = 90 66. ["lll"] = 91 67. ["\"] = 92 68. ["rrr"] = 93 69. ["^"] = 94 70. ["_"] = 95 71. ["`"] = 96 72. ["aa"] = 97 73. ["bb"] = 98 74. ["cc"] = 99 75. ["dd"] = 100 76. ["ee"] = 101 77. ["ff"] = 102 78. ["gg"] = 103 79. ["hh"] = 104 80. ["ii"] = 105 81. ["jj"] = 106 82. ["kk"] = 107 83. ["ll"] = 108 84. ["mm"] = 109 85. ["nn"] = 110 86. ["oo"] = 111 87. ["pp"] = 112 88. ["qq"] = 113 89. ["rr"] = 114 90. ["ss"] = 115 91. ["tt"] = 116 92. ["uu"] = 117 93. ["vv"] = 118 94. ["ww"] = 119 95. ["xx"] = 120 96. ["yy"] = 121 97. ["zz"] = 122 98. ["{"] = 123 99. ["|"] = 124 100. ["}"] = 125 101. ["~"] = 126 102.End Enum 103. 先实现一下getchar函数： 1. 2. Public Function getchar() As Long 3. Do 4. If m_bEOF Then 5. getchar = EOF 6. Exit Do 7. Else 8. If m_nInputPos < Len(m_sInputBuffer) Then 9. m_nInputPos = m_nInputPos + 1 10. getchar = AscW(Mid(m_sInputBuffer, m_nInputPos, 1)) And &HFFFF& 11. Exit Do 12. Else 13. If m_nInputPos > 0 Then 14. m_nInputPos = 0 15. m_sInputBuffer = "" 16. End If 17. Sleep 10 18. DoEvents 19. End If 20. End If 21. Loop 22. End Function 23. API Sleep的声明自己补上哈……getchar的主要工作原理就是个死循环，先看看m_bEOF（完蛋了没有？），如果完蛋了直接返回-1……否则看看输入缓冲区读完了没有，如果没有读完就读一个字符，返回（注意AscW主要是为了Unicode支持，不过用Asc，甚至AscB也无所谓）……如果读完了就死循环吧，Sleep 10+DoEvents直到输入东西或者退出为止……If m_nInputPos > 0没什么用，删掉也无所谓，主要就是省得疯狂清空字符串而已…… 接下来是几个判断函数，用过C的人都知道： 1.Public Function isspace(ByVal c As Long) As Boolean 2.isspace = c = [" "] Or c = ["\t"] Or c = ["\r"] Or c = ["\n"] 3.End Function 4. 5.Public Function isdigit(ByVal c As Long) As Boolean 6.isdigit = c >= ["0"] And c <= ["9"] 7.End Function 8. 9.Public Function isalpha(ByVal c As Long) As Boolean 10.isalpha = (c >= ["a"] And c <= ["z"]) Or (c >= ["aa"] And c <= ["zz"]) 11.End Function 12. 13.Public Function isalnum(ByVal c As Long) As Boolean 14.isalnum = (c >= ["0"] And c <= ["9"]) Or (c >= ["a"] And c <= ["z"]) Or (c >= ["aa"] And c <= ["zz"]) 15.End Function 16. 17.Public Function isascii(ByVal c As Long) As Boolean 18.isascii = c >= [" "] And c <= ["~"] 19.End Function 接下来正式开始 ===词法分析器=== 当实现一种语言的时候，第一件需要做的事就是处理一个文本文件，然后识别出里面说什么。经典的办法是使用“词法分析器”来把输入拆分成一些“标记”(Tokens)。每个Token包含一个代码表明这是什么类型的（数值，字符串，关键字……），还有一些可选的数据，例如一个数字的数值等。首先我们定义几种最简单的可能性： 1. 2.'// The lexer returns tokens [0-255] if it is an unknown character, otherwise one 3.'// of these for known things. 4.Public Enum enumToken 5. tok_eof = -1 6. tok_def = -2 7. tok_extern = -3 8. tok_identifier = -4 9. tok_number = -5 10.End Enum 11. 12.Public IdentifierStr As String ' // Filled in if tok_identifier 13.Public NumVal As Double ' // Filled in if tok_number 14. 每个Token或者是枚举enumToken里面的类型，或者是其他的“未知”字符，通过字符的ASCII返回。如果是关键字，IdentifierStr变量将会保存关键字的名字，如果是数值，则NumVal会保存当前值。说明：为了简单起见，我们用全局变量来保存这些信息，但是在真正的编译器程序中这样做可绝对不是好主意 词法分析器的实现就一个函数gettok。每调用一次，就会返回从标准输入进来的下一个Token。代码： 1. 2.'/// gettok - Return the next token from standard input. 3.Public Function gettok() As Long 4.Static LastChar As Long 5.Dim ret As Long 6.'/// 7.gettok_start: 8.'/// 9.If LastChar = 0 Then LastChar = [" "] 10.'// Skip any whitespace. 11.Do While isspace(LastChar) 12. LastChar = getchar 13.Loop 14. gettok函数会调用getchar，一次读取一个字符，并保存读取的字符到LastChar，但是并没有对这个字符进行处理。第一件事情是忽略掉相邻两个Token之间的空格。 下一件事情是看看输入的是不是关键字： 1. 2.If isalpha(LastChar) Then '// identifier: [a-zA-Z][a-zA-Z0-9]* 3. IdentifierStr = ChrW(LastChar) 4. Do 5. LastChar = getchar 6. If Not isalnum(LastChar) Then Exit Do 7. IdentifierStr = IdentifierStr + ChrW(LastChar) 8. Loop 9. Select Case IdentifierStr 10. Case "def": ret = tok_def 11. Case "extern": ret = tok_extern 12. Case Else: ret = tok_identifier 13. End Select 14. gettok = ret 15. Exit Function 16.End If 17. 注意，关键字的内容保存在全局变量IdentifierStr中。数值的处理也类似： 1. 2.If isdigit(LastChar) Or LastChar = ["."] Then '// Number: [0-9.]+ 3. Dim NumStr As String 4. Do 5. NumStr = NumStr + ChrW(LastChar) 6. LastChar = getchar 7. Loop While isdigit(LastChar) Or LastChar = ["."] 8. NumVal = Val(NumStr) 9. gettok = tok_number 10. Exit Function 11.End If 12. 这个代码很简单吧……就是有严重的Bug：当输入的不是数字的时候也会错误识别，例如“1.23.45.67”，识别成1.23（更严重的是这个代码不支持科学计数法 ---译者注）请自行修正这些错误下面是注释的处理： 1. 2.If LastChar = ["#"] Then 3. '// Comment until end of line. 4. Do 5. LastChar = getchar 6. Loop While LastChar <> EOF And LastChar <> ["\r"] And LastChar <> ["\n"] 7. If LastChar <> EOF Then GoTo gettok_start 8.End If 9. 处理方法是跳过输入的字符，直到换行符为止，然后读取下一个Token（原来这里是用递归的，我觉得递归占资源太多就改成GoTo了 ---译者注）最后是处理不属于上面的所有情况：如果输入不符合上面的情况，则或者是+,-这样的运算符，或者是文件尾(EOF)（还有中文 ---译者注）。代码是： 1. 2.'// Check for end of file. Don't eat the EOF. 3.If LastChar = EOF Then 4. gettok = tok_eof 5. Exit Function 6.End If 7.'// Otherwise, just return the character as its ascii value. 8.gettok = LastChar 9.LastChar = getchar 10.End Function 11. 到此为止，我们已经完成了“万花筒”语言的最简单的词法分析器。接下来我们要写一个语法分析器和抽象语法树(AST)构建器（见下一章）。 为了测试一下这段代码，我们写一个简单的测试程序： 1. 2.Public Sub Main() 3.Dim c As Long 4.Form1.Show 5.Do 6. c = gettok 7. If c = EOF Then Exit Do 8. Debug.Print c; 9.Loop 10.End Sub 11. 把启动项目设置成Sub Main，然后运行程序…… 输入测试代码：（注意，由于Command1.Default=True，所以不能直接输入，只能Ctrl+C Ctrl+V） 1. 2.# Compute the x'th fibonacci number. 3.def fib(x) 4. if x < 3 then 5. 1 6. else 7. fib(x-1)+fib(x-2) 8. 9.# This will compute the 40th number. 10.fib(40) 输出： -2 -4 40 -4 41 -4 -4 60 -5 -4 -5 -4 -4 40 -4 45 -5 41 43 -4 40 -4 45 -5 41 -4 40 -5 41 对照一下，看看输出是什么意思？ 挖一个坟……搞了半天忘记介绍LLVM是干什么的了，下面是百度百科的山寨介绍： 先来说说LLVM的历史。2000年LLVM开始开发，2005年Apple雇了Chris Lattner，LLVM也相当于成了Apple的官方支持的编译器。Apple已经将它用在OpenCL的流水线优化，Xcode已经能使用llvm-gcc编译代码。可以说05年之前LLVM一直都是学术界的东西，05年之后用于工业界.而这篇文章写在04年.本博最近听过一个关于LLVM的讨论会，会中有资深人士提到LLVM现在越来越像一个普通的编译器。说这番话的意思是，我们可以从这篇文章里找到LLVM的架构设计和早期的一些实现思想，但请不要迷信LLVM现在有多么神奇，每个架构都会有它的优缺点。 LLVM 是 Illinois 大学发起的一个开源项目，它到底是什么呢？从字面上看，它是一个虚机系统，然而这又和之前为大家所熟知的 JVM 以及 .net Runtime 这样的虚机不同，它提供了一套中立的中间代码和编译基础设施，并围绕这些设施提供了一套全新的编译策略（使得优化能够在编译、连接、运行环境执行过程中，以及安装之后以有效的方式进行）和其他一些非常有意思的功能。 为什么这个项目很重要呢？对于普通的开发人员来说，LLVM计划提供了越来越多的可以使用、编译器以外的其他工具。例如代码静态检查工具 LLVM/Clang Static Analyzer，是一个 Clang 的子项目，能够使用同样的 Makefile 生成 HTML 格式的分析报告；而对关注编译技术的开发人员来说，LLVM提供了很多优点： 现代化的设计：LLVM的设计是高度模块化的，使得其代码更为清晰和便于排查问题所在。 语言无关的中间代码：这使得透过LLVM能够将不同的语言相互连结起来；另一方面，这也使得LLVM能够紧密地与IDE交互和集成。另一方面，发布中间代码而非目标代码能够在目标系统上更好地发挥其潜能而又不伤害可调试性（i.e. 在目标系统上针对本机的硬件环境产生目标代码，但又能够直接通过中间代码来进行行级调试） 作为工具和函数库：使用LLVM提供的工具可以比较容易地实现新的编程语言的优化编译器或VM，或为现有的编程语言引入一些更好的优化／调试特性。 另外前两天LLVM出新版本2.9了，我下载回来又编译了一次，而且这次附带clang，也就是说可以直接用VB调用clang编译C/C++/ObjectiveC源代码……不过现在我还没有搞出DLL版本呢，只有一个命令行的clang.exe…… 补充内容 (2012-5-11 23:05): LLVM 2.9数个月前已经搞定了，在山寨编译器Yet Another Fake Basic里面下载，倒是LLVM 3.0 (还有3.1) DLL没搞定 |
|
|
