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

wuyangchun 发布于2019-08-14 15:15 / 1353人阅读

摘要：一个非终结符可以被展开称为一个串，如上定义便是将这个非终结符展开称为一个又终结符和非终结符混合而成的串。特别注意我定义的方法仅仅用于修饰非终结符，而非展开式，虽然这个例子中我的方法更靠近方法，但并意味着用于修饰展开式。

各位久等了，本系列在新一年的连载中，形式会加入少许变化。首先，我会将 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 的枚举类型代表着一系列被命名了的非终结符。

之后，我们需要做以下几个工作：

定义出 tao 语言的文法。

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

写一个 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 方法，但参数留空。匿名非终结符可以让我很方便的定义某些只在展开式中出现一次的非终结符，这样我就没有必要为每一个非终结符起一个名字了。

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

服务器托管 GPU服务器从零开始的邮件服务器从零开始 linux从零开始 python从零开始

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65516.html

从零开始写个编译器吧 - LL(1)

摘要：希腊字母表示空，这个产生式表明非终结符可以产生一个空。此外，对于一个文法之中的非终结符，还有集集的概念。对于一个非终结符而言，它的集指可能展开的各种形式中，位于第一的所有终结符所组成的集合。上一章中，我说 Parser 的工作就是依据文法定义，找到一个与源代码匹配的展开方案就可以了。听起来我们只要先给出一个 tao 语言的文法定义，然后写一个找匹配方案的的程序就可以了。然而事情情况...

Tony 2019-08-14 12:03 评论0 收藏0
从零开始写个编译器吧 - tao 语言的文法定义（下）

摘要：目前为止我们创建的文件列表新上一章中我们提到了个方法它们可以用来描述非终结符和展开式的形式，那么它们又是如何工作的呢文件中定义了一些方法。特别的，注意如下代码这个方法可以纪录被掉的一组非终结符，纪录这些东西有什么用，将在随后的章节介绍。目前为止我们创建的文件列表： |- com.taozeyu.taolan.analysis |- FirstSetConstructor ...

Michael_Lin 2019-08-14 15:16 评论0 收藏0
从零开始写个编译器吧 - 程序流控制

摘要：从展开式中，可以看出，除了这个非终结符，还有其他一些非终结符。是可能展开的形式之一，在语言中，如下代码就是一行典型的从表达式来看，它是由一个级表达式和一个类型的非终结符组成。但特别注意结尾的数量词表明，整个非终结符都是可选的。目前为止我们创建的文件列表： |- com.taozeyu.taolan.analysis |- FirstSetConstructor |- ...

huangjinnan 2019-08-14 15:15 评论0 收藏0
从零开始写个编译器吧系列

摘要：是的，这个系列将呈现一个完整的编译器从无到有的过程。但在写这个编译器的过程中，我可不会偷工减料，该有的一定会写上的。该语言的虚拟机将运行于之上，同时编译器将使用实现。我早有写编译器的想法之前没写过，故希望一边写编译器一边完成这个系列。是的，这个系列将呈现一个完整的编译器从无到有的过程。当然，为了保证该系列内容的简洁（也为了降低难度），仅仅保证编译器的最低要求，即仅能用。但在写这个编译...

genedna 2019-08-14 11:58 评论0 收藏0
从零开始写个编译器吧 - 文法简介

摘要：而，称之为非终结符。而这个展开方案中对各个非终结符产生式的选择过程，即是对源代码中每一个部分的定性过程。这个过程让能够理解源代码各个部分表示的含义，并以此生成对应的语法树。我需要定义出 tao 语言的细节，在此，需要引出文法这一概念。所谓文法，即是用于描述语言的一种工具。例如，一个赋值语句可能写成如下形式： variable = 1 + 3 如何充分定义这个赋值语句的形...

stormzhang 2019-08-14 12:03 评论0 收藏0