从零开始写个编译器吧 - 程序流控制

java 4 2016-02-29 13:03
女装

目前为止我们创建的文件列表:

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

我们来看看 SyntacticDefine.java 文件(142~159 行):

    node(Exp.StartChunk).or(Exp.Chunk),
    node(Exp.Chunk).or(
            Exp.SpaceOrEnter,
            node().or(Exp.Line, Exp.Space,
                      node().or(token(Type.NewLine), Exp.SpaceOrEnter)
                            .or(token(Type.EndSymbol))).sign('?')
    ).sign('*'),
    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)

我们定义了三个命名了的非终结符:StartChunk、Chunk、Line。

其中 StartChunk 是我们展开式的所有起点,每一个 tao 语言的源代码文件都从 StartChunk 开始展开。这里我简单的将其展开为 Chunk。

而 Chunk 表示一个语法块,它由许多行(Line)构成。但是在文法定义中,我必须为其每行的首位定义许多必要的杂项。从展开式中,可以看出,除了 Line 这个非终结符,还有其他一些非终结符:SpaceOrEnter、Space、NewLine、EndSymbol。

这些非终结符的含义,可以在 SyntacticDefine.java 文件的对应位置找到(可以使用 ctrl+F 搜索),只要找到它们对应的展开式,相信不难理机它们的含义。特别的 EndSymbol,即是 Tokenizer 代表源代码解析结束的终止符。

Chunk 是语言文法定义中最重要的非终结符。

再看看 Line,这个非终结符可以简单的理解为“一行代码”。自然,Chunk 就是由很多行代码组成的。特定的一行代码可以写很多东西,可能用于定义一个变量,也可能是一行赋值语句,也可能是在调用一个方法。总之,它可以是很多很多种东西。从之前这段代码中,可以看到,它有很多种展开式。

大家可以通过 GitHub 自行查看 Line 展开后对应的非终结符具体还能再如何展开,但受限于篇幅,我只会对其中一部分进行讲解。

node(Exp.Operate).or(Exp.L0Expression, Exp.When)

Operate 是 Line 可能展开的形式之一,在 tao 语言中,如下代码就是一行典型的 Operate:

count = size * 2 + 1

从表达式来看,它是由一个 0 级表达式(L0Expression)和一个 When 类型的非终结符组成。

其中 L0Expression 代表一个表达式,它可能是一行赋值语句,也可能是一个函数调用,它是我们文法定义中一个比较复杂,但却到处都会出现的东西,我会在之后的章节进行简单介绍。

随后,紧接而来的是 When 非终结符。我们来看看 When 的定义是怎么样的:

node(Exp.When).or(node().or(Exp.SplitSpaceSign).sign('?'),
              node().or(token(Type.Keyword, "when"), Exp.SplitSpaceSign, Exp.L0Expression).sign('?'))

它主要由一个 when 关键字紧接令一个 0 级表达式组成。但特别注意结尾的 .sign('?') 数量词表明,整个非终结符 When 都是可选的。也就是说,Operate 后面不写 when 也没有关系。

一行写了 when 的 tao 语言代码可能是如下形式:

count = size * 2 + 1 when size > 1

这是一种简写形式,在 tao 语言中等价于如下写法:

if size > 1
    count = size * 2 + 1
end

接下来,我们来看看 DefineVariable 非终结符:

node(Exp.DefineVariable).or(token(Type.Keyword, "var"), Exp.Space, Exp.DefineVariableElement,
                            node().or(Exp.Space, token(Type.Sign, ","),
                            Exp.SpaceOrEnter, Exp.DefineVariableElement).sign('*'))

注意到 DefineVariableElement 似乎还可以继续展开:

node(Exp.DefineVariableElement).or(token(Type.Identifier), Exp.Space,
                                   node().or(token(Type.Sign, "="), Exp.Space, Exp.L0Expression).sign('?'))

这表明 tao 语言中定义局部变量的形式如下:

var cat = take_cat(), dog = Dog.alloc().init()

当然,从 DefineVariableElement 的展开式中的 .sign('?') 量词可以知道,去掉等号以及等号后面的表达式,也是合法的局部变量定义:

var cat, dog

甚至,一次只定义一个变量,当然也是可以的:

var cat

在接下来,就是 IfElseChunk 了:

node(Exp.IfElseChunk).or(
                    token(Type.Keyword, "if"), Exp.Space,
                    Exp.L0Expression, Exp.SpaceOrEnter,
                    Exp.Chunk,
                    node().or(token(Type.Keyword, "elsif"), Exp.Space,
                              Exp.L0Expression, Exp.SpaceOrEnter,
                              Exp.Chunk).sign('*'),
                    node().or(token(Type.Keyword, "else"), Exp.SpaceOrEnter,
                              Exp.Chunk).sign('?'),
                    Exp.SpaceOrEnter,
                    token(Type.Keyword, "end"))

注意到,这里展开出现了四种关键字:if、elsif、else、end。

tao 语言中,一个典型的 if-else-chunk 是如下这样子的:

if check_condition(100)
    a = 1 + 1
elsif a > 2
    a += 3
else
    a = 0
end

当然,elsif 可以重复出现0~N 次:

if check_condition(100)
    a = 1 + 1
elsif a > 2
    a += 3
elsif a > 3
    a += 4
elsif a > 4
    a += 7
else
    a = 0
end

而 else 是可选的,可以没有:

if check_condition(100)
    a = 1 + 1
elsif a > 2
    a += 3
end

也可以只剩下 if 和 end:

if check_condition(100)
    a = 1 + 1
end

从文法定义的角度来看,if-else-chunk 这种形式的变化,我通过数量词 sign('*') 和 sign('?') 来控制。

女装
文章评论