编译原理c语言的抽象语法树
在本文中，我们将看到如何处理和转换从解析器获得的信息。 ANTLR解析器识别源代码中存在的元素，并构建一个解析树 。 从语法分析树中，我们将获得抽象语法树 ，该语法树将用于执行验证并生成已编译的代码。
请注意，术语可能会有所不同：许多人会将从ANTLR获得的树称为抽象语法树。 我更喜欢标记这两个步骤的区别。 对我而言， 解析树是对解析器有意义的信息， 抽象语法树是经过重组以更好地支持后续步骤的信息。
建立自己的语言的系列
以前的帖子：
代码在GitHub上的标签为05_ ast
丰富我们的语言
在本系列文章中，我们一直在研究一种非常简单的表达语言。 现在是时候让我们的语言稍微复杂一些了：
- 例如， 强制转换为： 10作为十进制或（1 * 2.45）作为Int
- 打印声明 例如： print（3 + 11）
为此，我们需要修改我们的词法分析器和解析器语法。 我们在之前的文章中构建的语法高亮和自动完成功能将继续起作用。
新的词法分析器语法：
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 ;抽象语法树元模型
抽象语法树元模型只是我们要用于抽象语法树（AST）的数据结构。 在这种情况下，我们通过定义将用于AST的类来定义它。
AST元模型看起来与解析树元模型相当类似，即ANTLR生成的包含节点的类集。
将有一些主要区别：
- 它会比ANTLR生成的类（因此构成解析树的类）具有更简单，更好的API。 在下一节中，我们将看到此API如何允许在AST上执行转换
- 我们将删除仅在解析时才有意义但在逻辑上是无用的元素：例如括号表达式或行节点
- 我们在解析树中具有单独实例的某些节点可以对应于AST中的单个实例。 这是类型引用Int和Decimal的情况，它们在AST中使用单例对象定义
- 我们可以为相关节点类型（例如BinaryExpression）定义通用接口
- 为了定义如何解析变量声明，我们重用分配规则。 在AST中，这两个概念是完全分开的
- 某些操作在解析树中具有相同的节点类型，但在AST中是分开的。 不同类型的二进制表达式就是这种情况
让我们看看如何使用Kotlin定义AST元模型。
interface Node
//
// Sandy specific part
//
data class SandyFile(val statements : List) : 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我们首先定义Node 。 节点代表AST的每个可能节点，它是通用的。 它也可以重用于其他语言。 其余所有语言都是特定于语言的（本例中为Sandy）。 在我们的特定语言中，我们需要三个重要的界面：
- 声明
- 表达
- 类型
这些接口均扩展Node 。
然后，我们声明我们在语言中使用的两种类型。 它们被定义为单例对象。 这意味着我们只有这些类的一个实例。
然后，我们有了BinaryExpression接口，该接口扩展了Expression 。 对于类实现它，每个基本算术表达式一个。
大多数表达式具有其他节点作为子节点。 有些具有简单的值。 他们是VarReference（其中有一个String类型的属性varName中 ），以及Intlit和DecLit（都有一个String类型的属性值 ）。
最后，我们有三个实现Statement的类。
请注意，我们正在使用数据类，因此我们可以免费使用hashCode，equals和toString方法。 Kotlin还为我们生成了构造函数和获取方法。 试想一下，用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)
}为了实现这一点，我们利用了Kotlin的三个非常有用的功能：
- 扩展方法：我们将方法toAst添加到了几个现有的类中
- when构造，它是switch的更强大的版本
- 智能转换：在检查对象是否具有某个类之后，编译器会将其隐式转换为该类型，以便我们可以使用该类的特定方法
我们可以提出一种机制，自动为大多数规则导出此映射，并仅在分析树和AST不同的地方对其进行自定义。 为了避免使用过多的反射黑魔法，我们暂时不这样做。 如果我使用Java，那么我会走上一条反思之路，以避免不得不手动编写大量多余和无聊的代码。 但是，使用Kotlin可以使这段代码紧凑而清晰。
测试映射
当然，我们需要测试这些东西。 让我们看看对于某段代码获得的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)
}
}考虑职位
那就太好了：我们有了代码中存在的信息的清晰模型。 元模型和映射代码看起来非常简单清晰。 但是，我们需要添加一些细节：节点在源代码中的位置。 向用户显示错误时将需要这样做。 我们希望有可能指定AST节点的位置，但我们不想被迫这样做。 这样，根据我们需要执行的操作，我们可以忽略或不忽略这些头寸。 考虑一下我们到目前为止编写的测试：是否必须为所有节点指定虚假位置会很麻烦又烦人？ 我认同。
这是新的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))我们还需要将位置作为可选参数添加到所有类中。 它将具有默认值null 。 例如，这是SandyFile现在的外观：
data class SandyFile(val statements : List<Statement>, override val position: Position? = null) : Node映射只是稍微复杂一点：
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)
}结论
解析树包含以最方便的方式为解析器组织的信息。 通常，这不是执行以下步骤的最方便的方法。 考虑一下通过重用赋值规则来实现的变量声明规则：当然，这会使语法更短，并且对解析树有意义。 但是，从逻辑角度看，这两个元素是分开的，并且在AST中它们确实是分开的。
我们其余的大多数工具都可以在AST上运行，因此最好花一些时间在有意义的AST上工作。
| 参考： | 为您自己的语言构建编译器：从 Federico Tomassetti博客上的JCG合作伙伴 Federico Tomassetti 的解析树到抽象语法树 。 |
编译原理c语言的抽象语法树