VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 5689|回复: 20

[讨论] 用VB+LLVM写一个山寨编译器 第六章 自定义运算符

[复制链接]
 楼主| 发表于 2010-11-19 23:29:21 | 显示全部楼层 |阅读模式
本帖最后由 acme_pjz 于 2010-11-20 11:57 编辑

第六章、用户自定义运算符 - 这是愚蠢但是有趣的一章,讨论怎么让用户自定义任意的单目和双目运算符(可以自己设置优先级!)

英文C++版本地址:http://www.llvm.org/releases/2.8/docs/tutorial/LangImpl6.html


[我先挖个坑哈,过几天再填上(当然可能不是在一楼填了)]

本帖被以下淘专辑推荐:

发表于 2010-11-20 08:03:27 | 显示全部楼层
好多章啊,怎么不放到一个贴?以后找起来不方便了
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-24 18:04:48 | 显示全部楼层
用户自定义运算符:基本想法

在我们的山寨语言中“运算符重载”的范围比C++里面的更广泛。在C++里面,你只能重载C++里面已经定义的运算符,不能通过编程的方法来修改语法、添加新的运算符、以及修改运算符优先级。但是在这一章我们将给“万花筒”语言增加这样的功能

用户自定义运算符这个功能的实现可以使得我们看出手工构建的分析器的威力和灵活性。(泡饭快来看,如果你用LALR分析器能实现这个功能么?)其中的关键点是算符优先分析器,如果我们采用别的表达式分析器,我们将很难实现动态添加运算符类型操作

先举一些例子:
# Logical unary not.
def unary!(v)
  if v then
    0
  else
    1;

# Define > with the same precedence as <.
def binary> 10 (LHS RHS)
  RHS < LHS;

# Binary "logical or", (note that it does not "short circuit")
def binary| 5 (LHS RHS)
  if LHS then
    1
  else if RHS then
    1
  else
    0;

# Define = with slightly lower precedence than relationals.
def binary= 9 (LHS RHS)
  !(LHS < RHS | LHS > RHS);


大部分语言中,这些运算符的定义都是语言的一部分。但是在我们的山寨语言中,这些运算符变成运行库的一部分了

我们把教程分成两部分:用户定义双目运算符,还有用户定义单目运算符。

用户定义双目运算符

先给词法分析器增加支持:

  1. Public Enum enumToken
  2. '...
  3.   '// operators
  4.   tok_binary = -11
  5.   tok_unary = -12
  6. End Enum

  7. '...

  8. Public Function gettok() As Long
  9. '...
  10. Select Case IdentifierStr
  11. '...
  12. Case "binary": ret = tok_binary
  13. Case "unary": ret = tok_unary
  14. '...
复制代码
然后我们要升级一下函数原型的AST节点(PrototypeAST.cls):

Option Explicit

Private Declare Function lstrlen Lib "kernel32.dll" Alias "lstrlenA" (ByRef lpString As Any) As Long
Private Declare Sub CopyMemory Lib "kernel32.dll" Alias "RtlMoveMemory" (ByRef Destination As Any, ByRef Source As Any, ByVal Length As Long)

'/// PrototypeAST - This class represents the "prototype" for a function,
'/// which captures its name, and its argument names (thus implicitly the number
'/// of arguments the function takes).

Public sName As String
Public Args As New Collection 'std::vector<std::string> Args
Public isOperator As Boolean
Public Precedence As Long '// Precedence if a binary op.

Public Function isUnaryOp() As Boolean
If isOperator Then
  isUnaryOp = Args.Count = 1
End If
End Function

Public Function isBinaryOp() As Boolean
If isOperator Then
  isBinaryOp = Args.Count = 2
End If
End Function

Public Function getOperatorName() As Long
Dim m As Long
If isOperator Then
  m = Args.Count
  If m = 1 Or m = 2 Then
    m = Len(sName)
    If m > 0 Then getOperatorName = AscW(Mid(sName, m, 1))
  End If
End If
End Function
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-24 18:05:30 | 显示全部楼层
然后升级函数原型的语法分析器:

'/// prototype
'///   ::= id '(' id* ')'
'///   ::= binary LETTER number? (id, id)

Public Function ParsePrototype() As PrototypeAST
  Dim Kind As Long
  Dim BinaryPrecedence As Long

  Dim FnName As String
  
  BinaryPrecedence = 30
  
  Select Case CurTok
  Case tok_identifier
    FnName = IdentifierStr
    Kind = 0
    getNextToken
  Case tok_binary
    getNextToken
    If Not isascii(CurTok) Then
      pError "Expected binary operator"
      Exit Function
    End If
    FnName = "binary" + ChrW(CurTok)
    Kind = 2
    getNextToken
   
    '// Read the precedence if present.
    If CurTok = tok_number Then
      If NumVal < 1 Or NumVal > 100 Then
        pError "Invalid precedecnce: must be 1..100"
        Exit Function
      End If
      BinaryPrecedence = NumVal
      getNextToken
    End If

  Case Else
    pError "Expected function name in prototype"
    Exit Function
  End Select
  
'...
  
  '// Verify right number of names for operator.
  If Kind > 0 Then
    If obj.Args.Count <> Kind Then
      pError "Invalid number of operands for operator"
      Exit Function
    End If
  End If

  
  obj.sName = FnName
  obj.isOperator = Kind <> 0
  obj.Precedence = BinaryPrecedence

  Set ParsePrototype = obj
End Function


我们保存该函数的类型,0=普通函数,1=单目运算符,2=双目运算符。还有优先级,默认值为30。有趣的一点是我们直接把运算符的名字设置为函数名称,因为LLVM里面允许函数名称为任意字符串。(官方文档说vbNullChar也可以,但是可能只有C++版本支持此功能 ---译者注)

接下来修改双目运算符表达式节点的中间代码生成函数(BinaryExprAST.cls):

  1. Private Function ExprAST_CodeGen() As Long
  2. '...
  3.   Case Else
  4.     '// If it wasn't a builtin binary operator, it must be a user defined one. Emit
  5.     '// a call to it.
  6.     Dim F As Long
  7.     F = LLVMGetNamedFunction(hModule, "binary" + ChrW(Op))
  8.     If F = 0 Then
  9.       pError "binary operator not found!"
  10.       Exit Function
  11.     End If
  12.   
  13.     Dim Ops(1) As Long
  14.     Ops(0) = L
  15.     Ops(1) = R
  16.    
  17.     ExprAST_CodeGen = LLVMBuildCall(hBuilder, F, Ops(0), 2, "binop")
  18.   End Select
  19. End Function
复制代码
最后修改函数节点的代码生成函数(FunctionAST.cls),使得生成函数的时候把表达式优先级填进表里面去:

Public Function CodeGen() As Long
  Set NamedValues = New Collection
  
  Dim TheFunction As Long
  TheFunction = Proto.CodeGen
  If TheFunction = 0 Then Exit Function
  
  '// If this is an operator, install it.
  If Proto.isBinaryOp Then
    BinopPrecedence(Proto.getOperatorName) = Proto.Precedence
  End If


  '// Create a new basic block to start insertion into.
  Dim BB As Long
  BB = LLVMAppendBasicBlock(TheFunction, "entry")
  LLVMPositionBuilderAtEnd hBuilder, BB

'...


现在双目运算符自定义的部分完成了。下面是单目运算符。不过到目前为止,我们的山寨语言根本没有任何单目运算符的支持。所以我们还得继续写代码……

[未完待续……]
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-24 18:06:20 | 显示全部楼层
单目运算符的支持

我们要新建一个单目运算符表达式节点类,UnaryExprAST.cls:

  1. Option Explicit

  2. '/// UnaryExprAST - Expression class for a unary operator.

  3. Implements ExprAST

  4. Public Op As Long
  5. Public Operand As ExprAST

  6. Private Function ExprAST_CodeGen() As Long
  7.   Dim OperandV As Long
  8.   OperandV = Operand.CodeGen
  9.   If OperandV = 0 Then Exit Function
  10.   
  11.   Dim F As Long
  12.   F = LLVMGetNamedFunction(hModule, "unary" + ChrW(Op))
  13.   If F = 0 Then
  14.     pError "Unknown unary operator"
  15.     Exit Function
  16.   End If
  17.   
  18.   ExprAST_CodeGen = LLVMBuildCall(hBuilder, F, OperandV, 1, "unop")
  19. End Function
复制代码
顺便连代码生成函数也写了原理很简单,查一下是否定义了这个运算符的处理函数,如果定义了,直接调用函数就完了,否则报错……

然后写语法分析函数:

  1. '/// unary
  2. '///   ::= primary
  3. '///   ::= '!' unary
  4. Public Function ParseUnary() As ExprAST
  5.   '// If the current token is not an operator, it must be a primary expr.
  6.   If CurTok = ["("] Or CurTok = [","] Or Not isascii(CurTok) Then
  7.     Set ParseUnary = ParsePrimary
  8.     Exit Function
  9.   End If
  10.   
  11.   '// If this is a unary operator, read it.
  12.   Dim Opc As Long
  13.   Dim Operand As ExprAST
  14.   Opc = CurTok
  15.   getNextToken
  16.   Set Operand = ParseUnary()
  17.   If Not Operand Is Nothing Then
  18.     Dim obj As New UnaryExprAST
  19.     obj.Op = Opc
  20.     Set obj.Operand = Operand
  21.     Set ParseUnary = obj
  22.   End If
  23. End Function
复制代码
这个函数用了递归调用,为了使得我们可以识别“!!x”这样的代码。然后我们把ParseBinOpRHS和ParseExpression里面的ParsePrimary替换成ParseUnary。代码就不在此列出了

然后我们还要继续升级函数原型处理函数:

'/// prototype
'///   ::= id '(' id* ')'
'///   ::= binary LETTER number? (id, id)
'///   ::= unary LETTER (id)

Public Function ParsePrototype() As PrototypeAST
  Dim Kind As Long
  Dim BinaryPrecedence As Long
  Dim FnName As String
  
  BinaryPrecedence = 30
  
  Select Case CurTok
  Case tok_identifier
    FnName = IdentifierStr
    Kind = 0
    getNextToken
  Case tok_unary
    getNextToken
    If Not isascii(CurTok) Then
      pError "Expected unary operator"
      Exit Function
    End If
    FnName = "unary" + ChrW(CurTok)
    Kind = 1
    getNextToken

'...


到此为止,单目运算符的处理也写好了。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-24 18:06:45 | 显示全部楼层
第六章补充材料

我总算实验出VB直接导出函数给LLVM JIT的办法了……原来要JIT的才能导出,解释器模式不能导出……函数如下:

  1. Public Sub ExportTest(ByVal sName As String, ByVal nArgCount As Long, ByVal lpAddress As Long)

  2. Dim nType As Long
  3. Dim Doubles() As Long, i As Long
  4. Dim nFuncType As Long
  5. Dim nFuncPtrType As Long
  6. Dim F As Long

  7. Dim V2 As Long

  8. nType = LLVMDoubleType
  9. ReDim Doubles(nArgCount)
  10. For i = 0 To nArgCount - 1
  11.   Doubles(i) = nType
  12. Next i
  13. nFuncType = LLVMFunctionType(nType, Doubles(0), nArgCount, 0)
  14. nFuncPtrType = LLVMPointerType(nFuncType, 0)

  15. F = LLVMAddFunction(hModule, sName, nFuncType)
  16. LLVMSetLinkage F, LLVMExternalLinkage

  17. For i = 0 To nArgCount - 1
  18.   Doubles(i) = LLVMGetParam(F, i)
  19.   LLVMSetValueName Doubles(i), "a" + CStr(i)
  20. Next i

  21. Dim BB As Long
  22. BB = LLVMAppendBasicBlock(F, "entry")
  23. LLVMPositionBuilderAtEnd hBuilder, BB

  24. V2 = LLVMConstInt(LLVMInt32Type, CCur(lpAddress) * 0.0001@, 0)
  25. V2 = LLVMConstIntToPtr(V2, nFuncPtrType)
  26. V2 = LLVMBuildCall(hBuilder, V2, Doubles(0), nArgCount, "calltmp")
  27. LLVMSetInstructionCallConv V2, LLVMX86StdcallCallConv
  28. LLVMBuildRet hBuilder, V2

  29. LLVMVerifyFunction F, LLVMPrintMessageAction

  30. LLVMRunFunctionPassManager hFPManager, F

  31. End Sub
复制代码
稍微解释一下,我们的山寨语言所有数据类型全都是Double,所以你想导出的函数所有参数必须是ByVal As Double,返回值是Double,可别乱写了,否则出错别怪我……

由于LLVMConstInt函数传进去的整数是64位的,VB不直接支持64位整数,所以我API声明里面写了个Currency类型……而Currency的0.0001@在内存里面就是1,所以传进来的函数指针要乘一个0.0001@再传过去……

VB的函数全都是stdcall的,不同于C/C++的cdecl,这个我想地球人都知道……所以调用函数的时候要把调用类型设置成stdcall(好在LLVM有这个功能)……

然后我们要导出几个函数,这些函数在之后的教程要用到:

  1. Public Function printd(ByVal i As Double) As Double
  2. printf CStr(i) + vbCrLf
  3. End Function

  4. Public Function putchard(ByVal i As Double) As Double
  5. Dim n As Long
  6. n = CLng(i) And &HFFFF&
  7. If n = 13 Or n = 10 Then
  8. printf vbCrLf
  9. Else
  10. printf ChrW(n)
  11. End If
  12. End Function
复制代码
在Main函数里面调用ExportTest导出这些函数:

  1. Public Sub Main()
  2. '...
  3. ExportTest "printd", 1, AddressOf printd
  4. ExportTest "putchard", 1, AddressOf putchard

  5.   '// Prime the first token.
  6.   printf "ready> "
  7.   getNextToken

  8.   '// Run the main "interpreter loop" now.
  9.   MainLoop

  10. '...
复制代码
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-24 18:07:31 | 显示全部楼层
然后我们开始干一些疯狂的事情:用我们的山寨语言画Mandelbrot集。先测试一下自定义运算符的效果。山寨一下VB的冒号功能:
ready> def binary : 1 (x y) 0;  # Low-precedence operator that ignores operands.
..
ready> printd(123) : printd(456) : printd(789);
123.000000
456.000000
789.000000
Evaluated to 0.000000


然后定义一箩筐的运算符:

# Logical unary not.
def unary!(v)
  if v then
    0
  else
    1;
   
# Unary negate.
def unary-(v)
  0-v;

# Define > with the same precedence as <.
def binary> 10 (LHS RHS)
  RHS < LHS;

# Binary logical or, which does not short circuit.
def binary| 5 (LHS RHS)
  if LHS then
    1
  else if RHS then
    1
  else
    0;

# Binary logical and, which does not short circuit.
def binary& 6 (LHS RHS)
  if !LHS then
    0
  else
    !!RHS;

# Define = with slightly lower precedence than relationals.
def binary = 9 (LHS RHS)
  !(LHS < RHS | LHS > RHS);


然后定义一个函数,按照迭代次数显示出字符:
extern putchard(char)
def printdensity(d)
  if d > 8 then
    putchard(32)  # ' '
  else if d > 4 then
    putchard(46)  # '.'
  else if d > 2 then
    putchard(43)  # '+'
  else
    putchard(42); # '*'

测试一下效果:
printdensity(1): printdensity(2): printdensity(3) :
          printdensity(4): printdensity(5): printdensity(9): putchard(10);


最后测试一下Mandelbrot集。Mandelbrot集的详细内容百度+Google+维基百科都有……

# determine whether the specific location diverges.
# Solve for z = z^2 + c in the complex plane.
def mandleconverger(real imag iters creal cimag)
  if iters > 255 | (real*real + imag*imag > 4) then
    iters
  else
    mandleconverger(real*real - imag*imag + creal,
                    2*real*imag + cimag,
                    iters+1, creal, cimag);

# return the number of iterations required for the iteration to escape
def mandleconverge(real imag)
  mandleconverger(real, imag, 0, real, imag);

# compute and plot the mandlebrot set with the specified 2 dimensional range
# info.
def mandelhelp(xmin xmax xstep   ymin ymax ystep)
  for y = ymin, y < ymax, ystep in (
    (for x = xmin, x < xmax, xstep in
       printdensity(mandleconverge(x,y)))
    : putchard(10)
  )

# mandel - This is a convenient helper function for ploting the mandelbrot set
# from the specified position with the specified Magnification.
def mandel(realstart imagstart realmag imagmag)
  mandelhelp(realstart, realstart+realmag*78, realmag,
             imagstart, imagstart+imagmag*40, imagmag);
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-24 18:09:28 | 显示全部楼层
输入下面的函数,测试一下效果。警告:运行得有点慢,你最好在printf的VB实现里面加一个DoEvents……

ready> mandel(-2.3, -1.3, 0.05, 0.07);
*******************************+++++++++++*************************************
*************************+++++++++++++++++++++++*******************************
**********************+++++++++++++++++++++++++++++****************************
*******************+++++++++++++++++++++.. ...++++++++*************************
*****************++++++++++++++++++++++.... ...+++++++++***********************
***************+++++++++++++++++++++++.....   ...+++++++++*********************
**************+++++++++++++++++++++++....     ....+++++++++********************
*************++++++++++++++++++++++......      .....++++++++*******************
************+++++++++++++++++++++.......       .......+++++++******************
***********+++++++++++++++++++....                ... .+++++++*****************
**********+++++++++++++++++.......                     .+++++++****************
*********++++++++++++++...........                    ...+++++++***************
********++++++++++++............                      ...++++++++**************
********++++++++++... ..........                        .++++++++**************
*******+++++++++.....                                   .+++++++++*************
*******++++++++......                                  ..+++++++++*************
*******++++++.......                                   ..+++++++++*************
*******+++++......                                     ..+++++++++*************
*******.... ....                                      ...+++++++++*************
*******.... .                                         ...+++++++++*************
*******+++++......                                    ...+++++++++*************
*******++++++.......                                   ..+++++++++*************
*******++++++++......                                   .+++++++++*************
*******+++++++++.....                                  ..+++++++++*************
********++++++++++... ..........                        .++++++++**************
********++++++++++++............                      ...++++++++**************
*********++++++++++++++..........                     ...+++++++***************
**********++++++++++++++++........                     .+++++++****************
**********++++++++++++++++++++....                ... ..+++++++****************
***********++++++++++++++++++++++.......       .......++++++++*****************
************+++++++++++++++++++++++......      ......++++++++******************
**************+++++++++++++++++++++++....      ....++++++++********************
***************+++++++++++++++++++++++.....   ...+++++++++*********************
*****************++++++++++++++++++++++....  ...++++++++***********************
*******************+++++++++++++++++++++......++++++++*************************
*********************++++++++++++++++++++++.++++++++***************************
*************************+++++++++++++++++++++++*******************************
******************************+++++++++++++************************************
*******************************************************************************
*******************************************************************************
*******************************************************************************
Evaluated to 0.000000
ready> mandel(-2, -1, 0.02, 0.04);
**************************+++++++++++++++++++++++++++++++++++++++++++++++++++++
***********************++++++++++++++++++++++++++++++++++++++++++++++++++++++++
*********************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
*******************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
*****************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.....
***************++++++++++++++++++++++++++++++++++++++++++++++++++++++++........
**************++++++++++++++++++++++++++++++++++++++++++++++++++++++...........
************+++++++++++++++++++++++++++++++++++++++++++++++++++++..............
***********++++++++++++++++++++++++++++++++++++++++++++++++++........        .
**********++++++++++++++++++++++++++++++++++++++++++++++.............         
********+++++++++++++++++++++++++++++++++++++++++++..................         
*******+++++++++++++++++++++++++++++++++++++++.......................         
******+++++++++++++++++++++++++++++++++++...........................           
*****++++++++++++++++++++++++++++++++............................              
*****++++++++++++++++++++++++++++...............................               
****++++++++++++++++++++++++++......   .........................               
***++++++++++++++++++++++++.........     ......    ...........                 
***++++++++++++++++++++++............                                          
**+++++++++++++++++++++..............                                          
**+++++++++++++++++++................                                          
*++++++++++++++++++.................                                          
*++++++++++++++++............ ...                                             
*++++++++++++++..............                                                  
*+++....++++................                                                   
*..........  ...........                                                      
*                                                                              
*..........  ...........                                                      
*+++....++++................                                                   
*++++++++++++++..............                                                  
*++++++++++++++++............ ...                                             
*++++++++++++++++++.................                                          
**+++++++++++++++++++................                                          
**+++++++++++++++++++++..............                                          
***++++++++++++++++++++++............                                          
***++++++++++++++++++++++++.........     ......    ...........                 
****++++++++++++++++++++++++++......   .........................               
*****++++++++++++++++++++++++++++...............................               
*****++++++++++++++++++++++++++++++++............................              
******+++++++++++++++++++++++++++++++++++...........................           
*******+++++++++++++++++++++++++++++++++++++++.......................         
********+++++++++++++++++++++++++++++++++++++++++++..................         
Evaluated to 0.000000
ready> mandel(-0.9, -1.4, 0.02, 0.03);
*******************************************************************************
*******************************************************************************
*******************************************************************************
**********+++++++++++++++++++++************************************************
*+++++++++++++++++++++++++++++++++++++++***************************************
+++++++++++++++++++++++++++++++++++++++++++++**********************************
++++++++++++++++++++++++++++++++++++++++++++++++++*****************************
++++++++++++++++++++++++++++++++++++++++++++++++++++++*************************
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++**********************
+++++++++++++++++++++++++++++++++.........++++++++++++++++++*******************
+++++++++++++++++++++++++++++++....   ......+++++++++++++++++++****************
+++++++++++++++++++++++++++++.......  ........+++++++++++++++++++**************
++++++++++++++++++++++++++++........   ........++++++++++++++++++++************
+++++++++++++++++++++++++++.........     ..  ...+++++++++++++++++++++**********
++++++++++++++++++++++++++...........        ....++++++++++++++++++++++********
++++++++++++++++++++++++.............       .......++++++++++++++++++++++******
+++++++++++++++++++++++.............        ........+++++++++++++++++++++++****
++++++++++++++++++++++...........           ..........++++++++++++++++++++++***
++++++++++++++++++++...........                .........++++++++++++++++++++++*
++++++++++++++++++............                  ...........++++++++++++++++++++
++++++++++++++++...............                 .............++++++++++++++++++
++++++++++++++.................                 ...............++++++++++++++++
++++++++++++..................                  .................++++++++++++++
+++++++++..................                      .................+++++++++++++
++++++........        .                               .........  ..++++++++++++
++............                                         ......    ....++++++++++
..............                                                    ...++++++++++
..............                                                    ....+++++++++
..............                                                    .....++++++++
.............                                                    ......++++++++
...........                                                     .......++++++++
.........                                                       ........+++++++
.........                                                       ........+++++++
.........                                                           ....+++++++
........                                                             ...+++++++
.......                                                              ...+++++++
                                                                    ....+++++++
                                                                   .....+++++++
                                                                    ....+++++++
                                                                    ....+++++++
                                                                    ....+++++++
Evaluated to 0.000000


到此为止,第六章结束。下一张我们将加入局部变量功能……

工程文件:

llvm-vb-test-ch6.rar

10.47 KB, 下载次数: 333

评分

参与人数 1威望 +10 人气 +3 收起 理由
shanhan + 10 + 3 神马都是浮云

查看全部评分

回复 支持 反对

使用道具 举报

发表于 2010-11-24 18:15:24 | 显示全部楼层
咦?本章无下载?
回复 支持 反对

使用道具 举报

发表于 2010-11-24 18:17:42 | 显示全部楼层
看到了.
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2019-8-18 10:33

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表