65.9K
CodeProject 正在变化。 阅读更多。
Home

Bird 编程语言：第三部分

Dávid Kocsis
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.88/5 (5投票s)

2012 年 11 月 10 日

GPL3

5分钟阅读

viewsIcon

32474

downloadIcon

318

一种新的通用编程语言，目标是快速、高级且易于使用。

关于 Bird 的文章 

目录 

Bird 结构概述

  • 表达式由不同的识别器进行解析，节点传递给插件。
  • 插件可以修改识别出的表达式，包括类型管理、常量计算
  • 架构用于为特定平台生成代码。目前只有 x86。

代码解析基础

该语言由识别器组成，通过替换识别器即可支持新语言。函数、类型、变量将在 Bird 和新语言之间共享。我没有使用解析器生成器，因为我认为使用其他软件可能会阻止我实现某些功能，或者我不得不以不同的方式做事。

CompilerState 类包含一个 Language 对象，其中包含所有识别器。这是 Language 类

public abstract class Language : LanguageNode
{
    public IList<IExprRecognizer> ExprRecognizers;
    public IList<IIdRecognizer> IdRecognizers;
    public IList<ICommRecognizer> CommRecognizers;
    public IList<IModRecognizer> ModRecognizers;
    public IList<INameGenerator> NameGenerators;
    public IList<IResultSkippingHandler> GlobalHandlers;

    public IArgRecognizer ArgRecognizer;
    public IGenericRecognizer GenericRecognizer;
    public IGroupRecognizer GroupRecognizer;

    public IRetValLessRecognizer RetValLessRecognizer;
    public IInnerScopeRecognizer InnerScopeRecognizer;
    public IVarDeclRecognizer VarDeclRecognizer;
    public ITypeDeclRecognizer TypeDeclRecognizer;
    public IConstDeclRecognizer ConstDeclRecognizer;
    public INamespaceDeclRecognizer NamespaceDeclRecognizer;
    public IDeclarationRecognizer DeclarationRecognizer;

    public IGlobalScopeProcessor GlobalScopeProcessor;
    public ICodeFileProcessor CodeFileProcessor;
    public ICodeProcessor CodeProcessor;
    ...
}

字符串处理

Bird 使用 StringSlice 来存储 string，以避免在调用 string.Substring 时进行新的 string 分配。此结构还包含括号处理和其他操作的函数。CodeString 结构由一个 StringSlice 和对 CodeFile 类的引用组成，该类还可以管理它们的行和缩进。CodeString 有一个 Line 字段，当需要其子字符串时，它会更新 Line 成员。CodeString 的大多数方法只是 StringSlice 函数的包装器。

ISkippingHandler 接口用于跳过 string 常量或括号中的结果。识别器可以在 ResultSkippingManager.Datas 中存储数据，如果需要的话。在某些情况下，必须确保括号不被跳过。如果 ResultSkippingManager.DoNotSkipBrackets 为 true，则括号识别器不应跳过括号。

public class BracketRecognizer : LanguageNode, IExprRecognizer,
                IIdRecognizer, IResultSkippingHandler
{
    ...

    public int SkipResult(ref ResultSkippingManager RSM)
    {
        if (!RSM.DoNotSkipBrackets && Helper.GetBracket(RSM.CurrentChar, RSM.Back))
        {
            var Handlers = RSM.SkippingHandlers;
            if (RSM.Back)
            {
                var NewString = RSM.String.Substring(0, RSM.Current + 1);
                var Pos = NewString.GetBracketPos(true, Handlers);
                if (Pos != -1) return Pos;
            }
            else
            {
                var NewString = RSM.String.Substring(RSM.Current);
                var Pos = NewString.GetBracketPos(false, Handlers);
                if (Pos != -1) return Pos + RSM.Current;
            }
        }

        return -1;
    }
}

这是 BracketRecognizer 类。它必须返回一个字符串搜索应继续的索引，或者返回 -1。GetBracketPos 方法返回字符串以其结尾或开头匹配的括号的位置。如果第一个参数为 false，则字符串必须以朝向右方的括号开头。

LanguageNode 类和识别器

LanguageNode 类包含一个名为 Operators 的字符串数组，它会识别这些字符串，以及一个名为 LanguageNode.Skip 的字符串数组，它应该跳过这些字符串，因为要识别的运算符是它们的一部分。例如，一个加法识别器有 +、- 运算符，那么跳过数组应该包含 ++、--。NewLine 字符串包含哪些运算符需要前一行或后一行。例如，如果一行以 + 结尾，则会继续到下一行

public abstract class LanguageNode
{
    public DataList Data = new DataList();
    public Language Root;
    public LanguageNode Parent;
    public IList<LanguageNode> Children;
    public IList<IResultSkippingHandler> SkippingHandlers;

    public string[] Operators;
    public string[] SkipFind;
    public string[] Skip;

    public string[] NewLineLeft;
    public string[] NewLineRight;
    public string[] OnlyLeft;
    public string[] OnlyRight;

    ...
}

识别以递归方式完成。我认为这是一种简单但可能不是解析代码文件的最快方式。为了减少在 string 操作上花费的时间，我使用了自己优化的函数，它们速度快得多，尽管代码生成花费的时间要多得多。目前我的编译器可以在大约 1 秒内处理 10,000 行代码。

表达式识别器应继承自此类和 IExprRecognizer 接口。识别器可以使用 Find2 函数来确定哪些运算符不是一元运算符。如果结果的左侧以运算符结尾或为空，则会忽略该结果。当仅使用 LanguageNode.Operators 不够时，例如转换识别器需要实现 IFind2Handler 接口。以下代码是加法识别器

public class AdditiveRecognizer : LanguageNode, IExprRecognizer
{
    public AdditiveRecognizer()
    {
        Operators = new string[] { "+", "-" };
        NewLineLeft = NewLineRight = Operators;
    }

    public ExprRecognizerRes Recognize
        (CodeString Code, ExprPlugin Plugin, ref ExpressionNode Ret)
    {
        var Result = ExprRecognizerHelper.Find2(this, Plugin.Container, Code.String);
        if (Result.Position != -1)
        {
            var Ch = ExprRecognizerHelper.TwoParamOpNode(Code, Result, Plugin);
            if (Ch == null) return ExprRecognizerRes.Failed;

            Operator Op;
            if (Result.Index == 0) Op = Operator.Add;
            else if (Result.Index == 1) Op = Operator.Subract;
            else throw new ApplicationException();

            Ret = new OpExpressionNode(Op, Ch, Code);
            return ExprRecognizerRes.Succeeded;
        }

        return ExprRecognizerRes.Unknown;
    }
}

这仍然与 NumberRecognizer 不兼容，因为浮点数可以带有 e 表示法（2e+2 = 2 * 102）。为了解决这个问题，NumberRecognizer 向 LanguageNode.SkippingHandlers 添加了一个结果跳过器。ExprRecognizerHelper.Find2 首先接受一个 LanguageNode 参数，该参数用于从中获取跳过处理器。

代码生成器

这是 Bird 中最复杂的部分。它占整个项目的约三分之一。以下是它编译函数的主要步骤

  1. 处理表达式
  2. 计算表达式结果的存储位置
  3. 计算局部变量的位置
  4. 检查是否需要临时寄存器（在 x86 汇编中，大多数指令只能有一个内存操作数，有些必须是内存位置或通用寄存器，等等）
  5. 如果需要临时寄存器，则重新开始数据位置分配，分配临时寄存器，并继续到第 2 点。
  6. 生成汇编（不含跳转）
  7. 跳转优化
  8. 跳转替换

跳转优化与替换

int Fib(int x)
    if x < 2: return 1
    else return Fib(x - 1) + Fib(x - 2)

在没有跳转优化的此函数将具有以下汇编

_Fib:
    push ebx
    push ebp
    mov ebp, eax
    cmp ebp, 2
    jge _26
    mov eax, 1
    jmp _2
    jmp _24
_26:
    mov eax, ebp
    dec eax
    call _Fib
    mov ebx, eax
    mov eax, ebp
    sub eax, 2
    call _Fib
    add eax, ebx
    jmp _2
_24:
_2:
    pop ebp
    pop ebx
    ret

标签 _26 和 _24 用于条件，标签 _2 用于函数返回。有一些不必要的跳转和标签应该被删除

_Fib:
    push ebx
    push ebp
    mov ebp, eax
    cmp ebp, 2
    jge _26
    mov eax, 1
    jmp _2
_26:
    mov eax, ebp
    dec eax
    call _Fib
    mov ebx, eax
    mov eax, ebp
    sub eax, 2
    call _Fib
    add eax, ebx
_2:
    pop ebp
    pop ebx
    ret

如果跳转目标与其执行的操作相同，则可以节省一次跳转。除非目标太长，否则会替换该跳转

_Fib:
    push ebx
    push ebp
    mov ebp, eax
    cmp ebp, 2
    jge _26
    mov eax, 1
    pop ebp
    pop ebx
    ret
_26:
    mov eax, ebp
    dec eax
    call _Fib
    mov ebx, eax
    mov eax, ebp
    sub eax, 2
    call _Fib
    add eax, ebx
    pop ebp
    pop ebx
    ret

临时寄存器处理

IsEqual 函数需要 3 个临时寄存器来实现 mov 指令只能有一个内存操作数，并且内存位置不能有内存地址

long* g_Pointers
int g_Index
long g_Value

bool IsEqual()
    return g_Value == g_Pointers[g_Index]


_IsEqual:
    mov eax, dword[_g_Pointers]
    mov edx, dword[_g_Index]
    mov ecx, dword[eax + edx * 8]
    cmp dword[_g_Value], ecx
    jne _27
    mov ecx, dword[eax + edx * 8 + 4]
    cmp dword[_g_Value + 4], ecx
    jne _27
    mov al, 1
    ret
_27:
    xor al, al
    ret

条件汇编生成

这是条件汇编生成的主要函数（Bird.CodeGenerator.GetConditionCode)

void GetConditionCode(ExpressionNode Node, int Then, int Else, bool ElseAfterCondition)

Then 和 Else 是标签的索引。如果 ElseAfterCondition 为

  • True，则条件后跟着 else 块，跳转的条件与操作符相同，并跳转到 Then 标签
  • False，则条件后跟着 then 块，跳转的条件被否定，并跳转到 Else 标签

这是一个例子。

void WhileTest(bool Loop)
    var a = 0
    while Loop
        a++

void DoWhileTest(bool Loop)
    var a = 0

    do
        a++
    while Loop
    
    
; This is the assembly without jump replacements
_WhileTest:
    xor edx, edx
_90:
    test eax, eax
    jnz _18
    inc edx
    jmp _90
_18:
    ret

_DoWhileTest:
    xor edx, edx
_93:
    inc edx
    test eax, eax
    jz _93
    ret
	
	
; After jump replacements
_WhileTest:
    xor edx, edx
    test eax, eax
    jnz _18
_89:
    inc edx
    test al, al
    jnz _89
_18:
    ret

_DoWhileTest:
    xor edx, edx
_93:
    inc edx
    test eax, eax
    jz _93
    ret

在 WhileTest 函数中，条件后跟着 then 块，ElseAfterCondition 为 false。在 DoWhileTest 中，它后面跟着 return 命令（当条件为 false 时发生），ElseAfterCondition 为 true。

这是 and 和 or 运算符的工作方式

void While_OrTest(bool x, y, z)
    var a = 0
    while x or y or z
        a++

void DoWhile_OrTest(bool x, y, z)
    var a = 0

    do
        a++
    while x or y or z

void While_AndTest(bool x, y, z)
    var a = 0
    while x and y and z
        a++

void DoWhile_AndTest(bool x, y, z)
    var a = 0

    do
        a++
    while x and y and z
    
    
_While_OrTest:
    xor ecx, ecx
_45:
    test al, al
    jnz _44
    test ah, ah
    jnz _44
    test dl, dl
    jz _7
_44:
    inc ecx
    jmp _45
_7:
    ret

_DoWhile_OrTest:
    xor ecx, ecx
_50:
    inc ecx
    test al, al
    jnz _50
    test ah, ah
    jnz _50
    test dl, dl
    jnz _50
    ret

_While_AndTest:
    xor ecx, ecx
_57:
    test al, al
    jz _9
    test ah, ah
    jz _9
    test dl, dl
    jz _9
    inc ecx
    jmp _57
_9:
    ret

_DoWhile_AndTest:
    xor ecx, ecx
_62:
    inc ecx
    test al, al
    jz _10
    test ah, ah
    jz _10
    test dl, dl
    jnz _62
_10:
    ret

在所有 while 和 do-while 测试中，最后一个条件保持不变，ElseAfterCondition 仅在前两个条件中更改。对于 and 条件，ElseAfterCondition 为 false，对于 or 条件，它为 true。

这是一个包含这两个运算符的示例

void While_AndOrTest(bool x, y, z, w)
    var a = 0
    while (x or y) and (z or w)
        a++

void DoWhile_AndOrTest(bool x, y, z, w)
    var a = 0

    do
        a++
    while (x or y) and (z or w)
    
    
_While_AndOrTest:
    xor ecx, ecx
_71:
    test al, al
    jnz _72
    test ah, ah
    jz _11
_72:
    test dl, dl
    jnz _70
    test dh, dh
    jz _11
_70:
    inc ecx
    jmp _71
_11:
    ret

_DoWhile_AndOrTest:
    xor ecx, ecx
_77:
    inc ecx
    test al, al
    jnz _79
    test ah, ah
    jz _12
_79:
    test dl, dl
    jnz _77
    test dh, dh
    jnz _77
_12:
    ret
© . All rights reserved.