从零开始写个编译器吧 - tao 语言的文法定义(上)

java 40 2016-02-29 13:03

各位久等了,本系列在新一年的连载中,形式会加入少许变化。首先,我会将 tao 语言编译器(以及运行环境)的全部内容贴在 GitHub 上,在阅读本系列的时候,需要对照 GitHub 上的内容。以取代之前一段一段贴代码的这种形式。此外,本系列也不会像之前那样贴出每一行代码,并对其进行讲解,取而待之,仅仅对核心代码和有代表性的代码进行讲解。如有疑问,欢迎评论。

GitHub 中的 tao 语言编译器项目

目前为止,我们已经写好了如下几个文件:

- com.taozeyu.taolan.analysis
|- FirstSetConstructor
|- LexicalAnalysis
|- LexicalAnalysisException
|- NonTerminalSymbol
|- SignParser
|- TerminalSymbol
|- Token

上一章中 NonTerminalSymbol.java 文件中留着一个 TODO,现在我把它填上:

static enum Exp {
    //空白
    SplitSpaceSign, SpaceOrEnter, Space,
    //基本单元
    Enter, This, Null, Boolean,
    Number, Variable, String, RegEx,
    Element,
    //表达式相关
    L0Expression, L0ParamExpression, L0Sign,
    L1Expression, L1ParamExpression,
    L2Expression, L2ParamExpression, L2Sign,
    L3Expression, L3ParamExpression, L3Sign,
    L4Expression, L4ParamExpression, L4Sign,
    L5Expression, L5ParamExpression, L5Sign,
    L6Expression, L6ParamExpression, L6Sign,
    L7Expression, L7ParamExpression, L7Sign,
    L8Expression, L8ParamExpression, L8Sign,
    L9Expression, L9ParamExpression, L9Sign,
    L10Expression, L10ParamExpression, L10Tail, L10TailOperation,
    L11Expression,
    //控制流语法
    Chunk, StartChunk, Line,
    Command, Operate, When,
    DefineVariable, DefineVariableElement,
    DefineFunction, ParamsList,
    IfElseChunk, TryCatch,
    WhileChunk, DoUntilChunk,
    ForEachChunk, ForEachCommand, ForEachCondition,
    //语法糖
    Lambda,
    List, Map, MapEntry,
    Invoker, InvokerBraceless, InvokerBanLambda, InvokerBracelessBanLambda,
    ParamList, ParamListBanTokens ,
    Array, Container,
}

这个 Exp 的枚举类型代表着一系列被命名了的非终结符。

之后,我们需要做以下几个工作:

  1. 定义出 tao 语言的文法。

  2. 写一个 Complier-complier,并用它分析之前定义的 tao 语言文法,得出一部分必要的信息,并将这些信息保存在 NonTerminalSymbol 节点中。

  3. 写一个 Parser,结合文法定义,以及 Complier-complier 分析出的信息,将一段 tao 语言的源代码分析成语法树。

OK,上面列出的清单就是一个写出一个可用的 Parser 的一个大致计划了。我们一步一步来吧。

首先,我们先写出一个 SyntacticDefine.java 文件。

源代码我就不贴了,请大家自行打开连接观看。(PS:之后的源代码文件会越来越长,我不一定会贴全部,请大家适应通过打开 GitHub 页面查看源代码的方式。)

可以看出,SyntacticDefine.java 中这个巨大的 static 块中定义了 tao 语言的全部内容。

在此,我稍微解释一下我是如何定义 tao 语言的文法的。例如:

node(Exp.Line).or(Exp.Command)
                .or(Exp.Operate)
                .or(Exp.DefineVariable)
                .or(Exp.DefineFunction)
                .or(Exp.IfElseChunk)
                .or(Exp.WhileChunk)
                .or(Exp.DoUntilChunk)
                .or(Exp.ForEachChunk)
                .or(Exp.TryCatch)

每一个 Exp 枚举类型都代表一个被命名的非终结符,如上这个定义代表如下一组展开式:

Line -> Command | Operate | DefineVariable ...

注意到,Line 这个非终结符存在很多中展开式,即它可能被展开为多种形式,因此在 static 块中,使用 or() 方法将其并列。

node(Exp.Array).or(token(Type.Sign, "["), Exp.SpaceOrEnter, Exp.List, Exp.SpaceOrEnter, token(Type.Sign, "]"))

一个非终结符可以被展开称为一个串,如上定义便是将 Array 这个非终结符展开称为一个又终结符和非终结符混合而成的串。

我使用 token() 这个方法来定义终结符,例如 token(Type.Sign, "[") 则定义了一个左方括号的终结符。由于 Array 只有一种展开形式,因此只调用了一次 or 方法。

node(Exp.SplitSpaceSign).or(token(Type.Space)).sign('+')

对非终结符可以使用量词进行修饰,我使用 sign() 方法来代表量词。如上这行定义,代表 SplitSpaceSign 这个非终结符可以展开为 1~N 个 space 类型的终结符。(特别注意:我定义的 sign() 方法仅仅用于修饰非终结符,而非展开式,虽然这个例子中我的 sign 方法更靠近 or 方法,但并意味着 sign 用于修饰展开式。)

node(Exp.L2ParamExpression).or(Exp.L3ParamExpression, node().or(Exp.L2Sign, Exp.L3ParamExpression).sign('*'))

在展开式中可以加入匿名非终结符,即调用 node 方法,但参数留空。匿名非终结符可以让我很方便的定义某些只在展开式中出现一次的非终结符,这样我就没有必要为每一个非终结符起一个名字了。

被命名的非终结符和匿名非终结符没有任何区别,它们仅仅就是形式上的不同罢了,请勿把它们当成有实质不同的东西。

文章评论