文档结构  
翻译进度:已翻译     翻译赏金:0 元 (?)    ¥ 我要打赏

Image title

在本文中我们将会看到如何处理与转换由解析器得到的信息。 ANTLR 解析器识别源码中的元素并构建 解析树。由解析树,我们可以得到用于执行验证并生成编译代码的抽象语法树。

注意术语的变化:许多人将由 ANTLR 获得的树称抽象语法树。我更喜欢强调两步之间的区别。对我而言,解析树是对解析器有意义的信息,抽象语法树是为了更好支持下一步而重新组织的信息。

第 1 段(可获 1.4 积分)

构建你自己的语言系列

以前的文章:

  1. 构建词法器
  2. 构建解析器
  3. 创建具有语法高亮的编辑器
  4. 构建具有自动补全的编辑器

代码位于 GitHub05_ast 标签下。

设计我们的语言

在这个文章系列中,我们已经为表达式制作了一个非常简单的语言。是时候使我们的语言略微复杂一些了:

  • 转换 例如: 10 as Decimal 或者 (1 * 2.45) as Int
  • 输出语句 例如: print(3 + 11)

为此我们需要修改我们的词法分析器与解析器语法。我们在前面文章中构建的语法高亮与自动补全会继续工作。

第 2 段(可获 1.43 积分)

新的词法分析器语法:

lexer grammar SandyLexer;

// Whitespace
NEWLINE            : '\r\n' | 'r' | '\n' ;
WS                 : [\t ]+ -> skip ;

// Keywords
VAR                : 'var' ;
PRINT              : 'print';
AS                 : 'as';
INT                : 'Int';
DECIMAL            : 'Decimal';

// Literals
INTLIT             : '0'|[1-9][0-9]* ;
DECLIT             : '0'|[1-9][0-9]* '.' [0-9]+ ;

// Operators
PLUS               : '+' ;
MINUS              : '-' ;
ASTERISK           : '*' ;
DIVISION           : '/' ;
ASSIGN             : '=' ;
LPAREN             : '(' ;
RPAREN             : ')' ;

// Identifiers
ID                 : [_]*[a-z][A-Za-z0-9_]* ;

新的词法解析器语法:

parser grammar SandyParser;

options { tokenVocab=SandyLexer; }

sandyFile : lines=line+ ;

line      : statement (NEWLINE | EOF) ;

statement : varDeclaration # varDeclarationStatement
          | assignment     # assignmentStatement
          | print          # printStatement ;

print : PRINT LPAREN expression RPAREN ;

varDeclaration : VAR assignment ;

assignment : ID ASSIGN expression ;

expression : left=expression operator=(DIVISION|ASTERISK) right=expression # binaryOperation
           | left=expression operator=(PLUS|MINUS) right=expression        # binaryOperation
           | value=expression AS targetType=type                           # typeConversion
           | LPAREN expression RPAREN                                      # parenExpression
           | ID                                                            # varReference
           | MINUS expression                                              # minusExpression
           | INTLIT                                                        # intLiteral
           | DECLIT                                                        # decimalLiteral ;

type : INT     # integer
     | DECIMAL # decimal ;
第 3 段(可获 0.11 积分)

抽象语法树元模型

抽象语法树元模型是我们希望用于抽象语法树(AST)的简单数据结构。在该示例中,我们通过定义用于 AST 的类来对其进行定义。

AST 元模型看起来类似于分析树元模型,例如,由 ANTLR 生成的包含节点的类集合。

关键区别如下:

  • 相比于 ANTLR 生成的类,它有更为简单与良好的 API (从而类构成了分析树)。在接下来的内容中,我们将会看到该 API 如何允许在 AST 上执行变换。
  • 我们将会移除仅在分析时有意义而在逻辑上无用的元素:例如括号表达式与行节点。
  • 对于某些节点,在解析树中我们拥有单独实例可以对应于 AST 中的单个实例。类型引用 Int 与Decimal 则是这种情况,在 AST 中,它们是使用单体对象来定义的。
  • 我们可以为相关的节点类型,例如二值表达式,定义通用接口。
  • 为定义如何解析变量声明,我们重用赋值规则。在 AST 中,两个概念是完全不同的。
  • 解析树中的某些操作具有相同的节点类型,但是在 AST 中则完全不同。二值表达式的不同类型则是这种情况。
第 4 段(可获 3.01 积分)

让我们来看看如何在 Kotlin 中定义自己的 AST 元模型。

interface Node

//
// Sandy specific part
//

data class SandyFile(val statements : List<Statement>) : Node

interface Statement : Node { }

interface Expression : Node { }

interface Type : Node { }

//
// Types
//

object IntType : Type

object DecimalType : Type

//
// Expressions
//

interface BinaryExpression : Expression {
    val left: Expression
    val right: Expression
}

data class SumExpression(override val left: Expression, override val right: Expression) : BinaryExpression

data class SubtractionExpression(override val left: Expression, override val right: Expression) : BinaryExpression

data class MultiplicationExpression(override val left: Expression, override val right: Expression) : BinaryExpression

data class DivisionExpression(override val left: Expression, override val right: Expression) : BinaryExpression

data class UnaryMinusExpression(val value: Expression) : Expression

data class TypeConversion(val value: Expression, val targetType: Type) : Expression

data class VarReference(val varName: String) : Expression

data class IntLit(val value: String) : Expression

data class DecLit(val value: String) : Expression

//
// Statements
//

data class VarDeclaration(val varName: String, val value: Expression) : Statement

data class Assignment(val varName: String, val value: Expression) : Statement

data class Print(val value: Expression) : Statement
第 5 段(可获 0.15 积分)

我们由定义 Node 开始。Node 表示 AST 中的所有节点,且是通用的。它也可以为其他的语言所重用。其他内容则是语言特定的 (我们示例中的Sandy)。在我们的特定语言中,我们需要三个重要接口:

  • Statement
  • Expression
  • Type

每一个接口都派生自 Node

然后我们声明我们语言中所用的两种类型。他们被定义为单体对象,意味着我们仅有这些类的一个实例。

然后我们声明 BinaryExpression接口, 该接口派生自 Expression. 对于实现该接口的类,每个实现基本的算术运算。

第 6 段(可获 1.31 积分)

大部分扩展拥有其他子节点。一些仅有简单的值。它们是 VarReference (有一个 String 类型的 varName 属性), Intlit, 与 DecLit (两者都有一个 String 类型的value属性 ).

最后我们有三个实现 Statement 的类。

注意,因为我们正在使用数据类,因而我们无需考虑 hashCode, equals, 与 toString 方法。Kotlin 同时生成构造函数与 getter 方法。试着想像一下在 Java 中这将需要多少代码。

将解析树映射到抽象语法树

让我们看一下我们如何得到由 ANTLR 生成的解析树,并将其映射为我们的 AST 类。

fun SandyFileContext.toAst() : SandyFile = SandyFile(this.line().map { it.statement().toAst() })

fun StatementContext.toAst() : Statement = when (this) {
    is VarDeclarationStatementContext -> VarDeclaration(varDeclaration().assignment().ID().text, varDeclaration().assignment().expression().toAst())
    is AssignmentStatementContext -> Assignment(assignment().ID().text, assignment().expression().toAst())
    is PrintStatementContext -> Print(print().expression().toAst())
    else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
}

fun  ExpressionContext.toAst() : Expression = when (this) {
    is BinaryOperationContext -> toAst()
    is IntLiteralContext -> IntLit(text)
    is DecimalLiteralContext -> DecLit(text)
    is ParenExpressionContext -> expression().toAst()
    is VarReferenceContext -> VarReference(text)
    is TypeConversionContext -> TypeConversion(expression().toAst(), targetType.toAst())
    else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
}

fun TypeContext.toAst() : Type = when (this) {
    is IntegerContext -> IntType
    is DecimalContext -> DecimalType
    else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
}

fun  BinaryOperationContext.toAst() : Expression = when (operator.text) {
    "+" -> SumExpression(left.toAst(), right.toAst())
    "-" -> SubtractionExpression(left.toAst(), right.toAst())
    "*" -> MultiplicationExpression(left.toAst(), right.toAst())
    "/" -> DivisionExpression(left.toAst(), right.toAst())
    else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
}

 

第 7 段(可获 1.35 积分)

为实现该映射,我们可以利用 Kotlin 的三个非常有用的特性:

  • 扩展方法:我们向一些已有的类添加 toAst 方法。
  • when 构造,这是 switch 的增强版本。
  • 智能转换:在我们确定对象具有特定的类之后,编译器隐式将其转换为该类型,从而我们可以使用该类的特定方法。

我们会开发一种机制为大多数规划自动生成映射,并且仅需要自定义分析树与 AST 不同的部分。为了避免使用过多的反射黑魔法,我们并不会现在来做。如果我正在使用 Java,我会走向反射的道路以避免手动编写大量重复枯燥的代码。然而,使用 Kotlin,相应的代码会紧凑而清晰。

第 8 段(可获 1.85 积分)

测试映射

我们必须测试一下这个东西,看看我们为一段特定代码生成的 AST 是否如我们所预期。

class MappingTest {

    @test fun mapSimpleFile() {
        val code = """var a = 1 + 2
                     |a = 7 * (2 / 3)""".trimMargin("|")
        val ast = SandyParserFacade.parse(code).root!!.toAst()
        val expectedAst = SandyFile(listOf(
                VarDeclaration("a", SumExpression(IntLit("1"), IntLit("2"))),
                Assignment("a", MultiplicationExpression(
                        IntLit("7"),
                        DivisionExpression(
                                IntLit("2"),
                                IntLit("3"))))))
        assertEquals(expectedAst, ast)
    }

    @test fun mapCastInt() {
        val code = "a = 7 as Int"
        val ast = SandyParserFacade.parse(code).root!!.toAst()
        val expectedAst = SandyFile(listOf(Assignment("a", TypeConversion(IntLit("7"), IntType))))
        assertEquals(expectedAst, ast)
    }

    @test fun mapCastDecimal() {
        val code = "a = 7 as Decimal"
        val ast = SandyParserFacade.parse(code).root!!.toAst()
        val expectedAst = SandyFile(listOf(Assignment("a", TypeConversion(IntLit("7"), DecimalType))))
        assertEquals(expectedAst, ast)
    }

    @test fun mapPrint() {
        val code = "print(a)"
        val ast = SandyParserFacade.parse(code).root!!.toAst()
        val expectedAst = SandyFile(listOf(Print(VarReference("a"))))
        assertEquals(expectedAst, ast)
    }

}
第 9 段(可获 0.38 积分)

考虑位置

这很棒:我们在代码中有清晰的信息模型。元模型与映射代码看起来非常简单与清晰。然而我们需要添加一些细节:源码中节点的位置。当向用户显示错误时需要该信息。我们希望能够指定我们 AST 节点的位置,但是我们并不希望被强制如此。这样,依赖于我们需要执行的动作,我们可以忽略或不忽略位置信息。考虑我们已经编写的测试:为所有节点指定伪造的位置不是非常麻烦而恼人吗?我认为是这样。

第 10 段(可获 1.56 积分)

下面是新的 Node 定义与支持类:

interface Node {
    val position: Position?
}

data class Point(val line: Int, val column: Int)

data class Position(val start: Point, val end: Point)

fun pos(startLine:Int, startCol:Int, endLine:Int, endCol:Int) = Position(Point(startLine,startCol),Point(endLine,endCol))

我们同时需要将 position 作为可选参数添加到所有类。它会有默认值 null。例如下面是 SandyFile 现在的样子:

data class SandyFile(val statements : List<Statement>, override val position: Position? = null) : Node
第 11 段(可获 0.5 积分)

映射更为复杂:

fun SandyFileContext.toAst(considerPosition: Boolean = false) : SandyFile = SandyFile(this.line().map { it.statement().toAst(considerPosition) }, toPosition(considerPosition))

fun Token.startPoint() = Point(line, charPositionInLine)

fun Token.endPoint() = Point(line, charPositionInLine + text.length)

fun ParserRuleContext.toPosition(considerPosition: Boolean) : Position? {
    return if (considerPosition) Position(start.startPoint(), stop.endPoint()) else null
}

fun StatementContext.toAst(considerPosition: Boolean = false) : Statement = when (this) {
    is VarDeclarationStatementContext -> VarDeclaration(varDeclaration().assignment().ID().text, varDeclaration().assignment().expression().toAst(considerPosition), toPosition(considerPosition))
    is AssignmentStatementContext -> Assignment(assignment().ID().text, assignment().expression().toAst(considerPosition), toPosition(considerPosition))
    is PrintStatementContext -> Print(print().expression().toAst(considerPosition), toPosition(considerPosition))
    else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
}

fun  ExpressionContext.toAst(considerPosition: Boolean = false) : Expression = when (this) {
    is BinaryOperationContext -> toAst(considerPosition)
    is IntLiteralContext -> IntLit(text, toPosition(considerPosition))
    is DecimalLiteralContext -> DecLit(text, toPosition(considerPosition))
    is ParenExpressionContext -> expression().toAst(considerPosition)
    is VarReferenceContext -> VarReference(text, toPosition(considerPosition))
    is TypeConversionContext -> TypeConversion(expression().toAst(considerPosition), targetType.toAst(considerPosition), toPosition(considerPosition))
    else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
}

fun TypeContext.toAst(considerPosition: Boolean = false) : Type = when (this) {
    is IntegerContext -> IntType(toPosition(considerPosition))
    is DecimalContext -> DecimalType(toPosition(considerPosition))
    else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
}

fun  BinaryOperationContext.toAst(considerPosition: Boolean = false) : Expression = when (operator.text) {
    "+" -> SumExpression(left.toAst(considerPosition), right.toAst(considerPosition), toPosition(considerPosition))
    "-" -> SubtractionExpression(left.toAst(considerPosition), right.toAst(considerPosition), toPosition(considerPosition))
    "*" -> MultiplicationExpression(left.toAst(considerPosition), right.toAst(considerPosition), toPosition(considerPosition))
    "/" -> DivisionExpression(left.toAst(considerPosition), right.toAst(considerPosition), toPosition(considerPosition))
    else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
}

此时之前的测试继续成功通过测试,但是我们希望添加一个测试来验证位置被正确定义:

    @test fun mapSimpleFileWithPositions() {
        val code = """var a = 1 + 2
                     |a = 7 * (2 / 3)""".trimMargin("|")
        val ast = SandyParserFacade.parse(code).root!!.toAst(considerPosition = true)
        val expectedAst = SandyFile(listOf(
                VarDeclaration("a",
                        SumExpression(
                                IntLit("1", pos(1,8,1,9)),
                                IntLit("2", pos(1,12,1,13)),
                                pos(1,8,1,13)),
                        pos(1,0,1,13)),
                Assignment("a",
                        MultiplicationExpression(
                            IntLit("7", pos(2,4,2,5)),
                            DivisionExpression(
                                    IntLit("2", pos(2,9,2,10)),
                                    IntLit("3", pos(2,13,2,14)),
                                    pos(2,9,2,14)),
                            pos(2,4,2,15)),
                        pos(2,0,2,15))),
                pos(1,0,2,15))
        assertEquals(expectedAst, ast)
    }

 

第 12 段(可获 0.39 积分)

结论

分析树包含以最方便的方式为解析器组织的信息。对于接下为的步骤通常并不是最方便的方式。思考一下通过重用赋值规划实现的变量声明:当然,这使得语法器更为简短,且对于解析树是合理的。然而,由逻辑的视角来看,这两个元素是分离的,而在 AST 中也确实如此。

我们工具中其余的大部分将会作用于 AST,所以在 AST 上花费一些时间是有意义的。

第 13 段(可获 1.28 积分)

文章评论