自己动手写编程语言（1）

Author Avatar
Wooyme 11月 09, 2019

前言

偶然看到了graal的SimpleLanguage的demo

https://github.com/graalvm/simplelanguage

然后突发奇想，干脆自己写个语言吧。
于是就有了这篇博客。

到现在我的这个玩具语言甚至加入了lambda支持，而从我下载这个demo到现在大概过了3天左右。

前期准备

准备工作可以看官网上的文档，写的非常详细

https://www.graalvm.org/docs/graalvm-as-a-platform/implement-language/

去他妈的整数

好的，拿到这个demo之后发现的第一个事情就是这货的数字类型只支持整数不支持浮点数。所以就从让它支持浮点数开始吧

浮点数的语法

浮点数得有点，那么这里就需要改动关于语法解析的文件了。可以在

language/src/main/java/com/oracle/truffle/sl/parser

里找到SimpleLanguage.g4文件，在最下方可以看到关于NUMERIC_LITERAL的定义。

1
NUMERIC_LITERAL : '0' | NON_ZERO_DIGIT DIGIT*

可以看到跟正则的语法非常像，“|”代表“或”、“*”代表“匹配0次到无数次”。那么根据这个匹配规则就可以发现，在语法解析的过程中就没有提供对小数点的支持。所以我们第一步要做的就是在语法解析中加入小数点。

这个修改非常简单

1
NUMERIC_LITERAL : '0' | NON_ZERO_DIGIT DIGIT* | '0' '.' DIGIT* | NON_ZERO_DIGIT DIGIT* '.' DIGIT*;

这就是我改动后的结果。加入了两个新的规则。分别表示”0.xxxxx”和’xxx.xxxxx’这样两种情况。总的来说唯一要注意的就是在表示数字的语法中，要阻止”0xxx”这种写法的存在。

重新生成文件

g4文件需要被antlr转换为java文件之后才能参与编译。由于我用的ide是Intellij IDEA所以就装了antlr4的插件。安装完之后就可以在底部工具栏中看到antlr preview和antlr output两栏。其中preview可以用于查看语法解析树,，output可以查看生成java文件时的错误等。

在工程中右键SimpleLanguage.g4 -> 单击generate ANTLR recognizer生成java文件-> 复制生成的文件到SimpleLanguage.g4所在目录就可以生效了。

浮点数的实现

修改了浮点数的解析之后，需要在后端完成浮点数的实现。对于数字类型，SimpleLanguage使用了BigInteger，而我们需要把它改成BigDecimal才能支持浮点数。

在runtime包下可以找到SLBigNumber这个类。类里面有一个BigInteger的属性。我们只要把这个属性的类型改成BigDecimal再把其他跟这个属性相关的部分修改一下，能编译通过就OK了。

重新编译

重新编译只要在simplelanguage目录下mvn clean package -DskipTests即可，不想要编译native的话，可以在native\make_native.sh里加入

1
SL_BUILD_NATIVE="false"

顺便一提，maven3好像有点bug。因为代码里存在大量的代码生成，这些生成的文件在target\generated-sources\annotations里。一般情况下maven是能找到这个目录的，但有时候在clean之后maven就找不到了。

我的解决方案是如果出现了找不到的情况就在simplelanguagemodule的pom.xml里加上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<plugin>
  <groupId>org.codehaus.mojo</groupId>
  <artifactId>build-helper-maven-plugin</artifactId>
  <version>3.0.0</version>
  <executions>
    <execution>
      <id>add-source</id>
      <phase>generate-sources</phase>
      <goals>
        <goal>add-source</goal>
      </goals>
      <configuration>
        <sources>
          <source>target/generated-sources/annotations</source>
        </sources>
      </configuration>
    </execution>
  </executions>
</plugin>

然后再clean，package。成功打包之后注释掉这段，就可以重归正常了。

字符串

SimpleLanguage的字符串不支持\r\n\t\"。这肯定不行，所以我们得自己加一个。
与修改数字一样，我们要先修改语法解析的东西。

原本的格式

1
2
fragment STRING_CHAR : ~( '\\' | '"' | '\r' | '\n');
STRING_LITERAL : '"' STRING_CHAR* '"';

修改后的格式

1
2
fragment STRING_CHAR :  '\\\\' | '\\"'| '\\n' | '\\t' | '\\r' | ~( '\\' | '"' | '\r' | '\n');
STRING_LITERAL : '"' STRING_CHAR* '"';

原本的字符串里是不能出现\的，现在虽然保留了最初的部分，但是我们添加了几种其他选项'\\\\' | '\\"'| '\\n' | '\\t' | '\\r' 。于是解析的时候就会优先匹配前几种。

转换

前端匹配了并没有什么卵用，如果不修改其他部分，最终得到的也只是把这些东西原封不动的输出而已。所以我们还要修改nodes/expression/SLStringLiteralNode.java。我的方案是在编译期就替换掉这些字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
@NodeInfo(shortName = "const")
public final class SLStringLiteralNode extends SLExpressionNode {
    private static HashMap<Character,Character> specialCharMap = new HashMap<>();
    // 创建特殊字符替换表
    static {
        specialCharMap.put('n','\n');
        specialCharMap.put('r','\r');
        specialCharMap.put('t','\t');
        specialCharMap.put('"','"');
    } 
    private final String value;

    public SLStringLiteralNode(String value) {
        char[] chars = value.toCharArray();
        StringBuilder sb = new StringBuilder();
        int status = 0;
        for (char aChar : chars) {
            if (aChar == '\\') {
                if (status == 0)
                    status = 1;
                else {
                    status = 0;
                    sb.append('\\'); //针对\\的情况
                }
            } else {
                if (status == 1) {
                    if (specialCharMap.containsKey(aChar)) {
                        sb.append(specialCharMap.get(aChar)); //替换字符
                        status = 0;
                    } else {
                        throw new RuntimeException("Failed to parse string"); //随便弹个异常
                    }
                } else {
                    sb.append(aChar); //普通字符
                }
            }
        }
        this.value = sb.toString();
    }

    @Override
    public String executeGeneric(VirtualFrame frame) {
        return value;
    }
}

这样在运行的时候，得到的就是已经替换特殊字符的字符串。

Boolean

语言到了这里，还有一个很重要的问题——没有Boolean值。最初我想的是，没有布朗值那就没有呗，就用0和非0来表示。但是观察了一下SimpleLanguage写好的几个内置函数(内置函数下一篇再说)是有返回bool的，而且==这样的关键字也是有对bool的比较。所以还是加一个吧

增加规则

和数字、字符串一样，我们希望可以直接使用true和false

1
2
3
a = "Hello";
b = 123.1;
c = false;

所以在g4文件里要加入对true和false的支持

1
2
3
4
LOGICAL_LITERAL : 'true' | 'false';   //添加用于匹配true和false的规则
IDENTIFIER : LETTER (LETTER | DIGIT)*;
STRING_LITERAL : '"' STRING_CHAR* '"';
NUMERIC_LITERAL : '0' | NON_ZERO_DIGIT DIGIT* | '0' '.' DIGIT* | NON_ZERO_DIGIT DIGIT* '.' DIGIT*;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
factor returns [SLExpressionNode result]
:
(
    LOGICAL_LITERAL                             { $result = factory.createLogicalLiteral($LOGICAL_LITERAL); } //添加匹配LOGICAL_LITERAL，一定要放在前面，不然就优先匹配IDENTIFIER了。
|
    IDENTIFIER                                  { SLExpressionNode assignmentName = factory.createStringLiteral($IDENTIFIER, false); }
    (
        member_expression[null, null, assignmentName] { $result = $member_expression.result; }
    |
                                                { $result = factory.createRead(assignmentName); }
    )
|
    STRING_LITERAL                              { $result = factory.createStringLiteral($STRING_LITERAL, true); }
|
    NUMERIC_LITERAL                             { $result = factory.createNumericLiteral($NUMERIC_LITERAL); }
|

    lmbd=lambda                                 { $result = $lmbd.result; }
|
    s='('
    expr=expression
    e=')'                                       { $result = factory.createParenExpression($expr.result, $s.getStartIndex(), $e.getStopIndex() - $s.getStartIndex() + 1); }
)
;

可以看到我加了个createLogicalLiteral方法给factory。这是第一次提到factory。看一下g4文件members的部分就可以发现这个factory就是SLNodeFactory。里面提供了许多封装好的创建节点的方法。

LogicalLiteral

前面我们已经看到了StringLiteral,其实还有BigIntegerLiteral(当然这个BigInteger现在已经是BigDecimal了)。这里Literal是字面的意思，这里我也不太想得到一个合适的翻译，大家自己领会了。

我们要能在代码里表示一个布朗值就需要定义一个布朗的字面量，所以我写了一个SLLogicalLiteralNode

1
2
3
4
5
6
7
8
9
10
11
12
13
@NodeInfo(shortName = "const")
public final class SLLogicalLiteralNode extends SLExpressionNode {
    private final Boolean value;
    public SLLogicalLiteralNode(boolean value){
        this.value = value;
    }

    @Override
    public Boolean executeGeneric(VirtualFrame frame) {
        return value;
    }
}

非常简单，在编译期把value放进去，然后在运行期取出来用。
然后在SLNodeFactory里添加createLogicalLiteral方法

1
2
3
4
5
6
7
public SLExpressionNode createLogicalLiteral(Token literalToken){
    SLExpressionNode result;
    result = new SLLogicalLiteralNode(Boolean.parseBoolean(literalToken.getText()));
    srcFromToken(result, literalToken);
    result.addExpressionTag();
    return result;
}

这样我们就可以直接写true和false了

Not

然后就发现问题了，SimpleLanguage连!操作符都没有。但是在nodes里我们可以找到SLLogicalNotNode,所以加一个!就只需要在语法解析上做点修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
term returns [SLExpressionNode result]
:
single_factor                                         { $result = $single_factor.result; }
(
    op=('*' | '/')
    single_factor                                     { $result = factory.createBinary($op, $result, $single_factor.result); }
)*
;

single_factor returns [SLExpressionNode result]
:
(
    (
        '!'
        factor  { $result = factory.createNot($factor.result); }
    )
|
    factor  {$result = $factor.result; }
)
;

我的方案是加了一个single_factor并把term内原本的factor改成single_factor。等于在原本的解析中插入一个对!factor的匹配。

这个匹配的写法应该是有很多的，我选了一个我第一反应想到的。

一通操作之后就可以实现这样一个基本的不能再基本的功能……..

1
2
3
4
5
fn main(){
    if(!false){
        .........
    }
}

小结

原理什么的其实我也还没完全理清楚，Truffle用了大量的注解和代码生成，导致写起来非常混乱。很多时候我也只能通过自己对于编译和虚拟机的理解去想代码运行的逻辑。下一篇是打算写一点我的理解和如何实现一个lambda。