编译原理c语言的抽象语法树_为您自己的语言构建编译器：从分析树到抽象语法树...

阅读量：

编译原理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 的解析树到抽象语法树。

翻译自: https://www.javacodegeeks.com/2016/08/building-compiler-language-parse-tree-abstract-syntax-tree.html

编译原理c语言的抽象语法树

全部评论 (0)

还没有任何评论哟~

编译原理c语言的抽象语法树_为您自己的语言构建编译器：从分析树到抽象语法树...

编译原理c语言的抽象语法树在本文中，我们将看到如何处理和转换从解析器获得的信息。ANTLR解析器识别源代码中存在的元素，并构建一个解析树。从语法分析树中，我们将获得抽象语法树，该语法树将用于执行验证...

抽象语法树 c语言,关于c ++ 11：C ++中的抽象语法树表示

我已经有了创建令牌列表的tokenizer接口。我有解析器的工作机制。它确实是独一无二的，并且像一种魅力。我唯一想念的是AST的基本结构。树，节点和语句应如何在抽象级别上表示。我不需要任何实现，只是一...

AST抽象语法树对构建JS编译器的启发

文章目录前言一、AST是什么？二、github一个AST生成器的案例 1.主要流程 2.tokenizer的实现 3.parser的实现 4.transformer的实现（1）traverse...

java抽象语法树_抽象语法树（AST）

抽象语法树AST 最近在做一个类JAVA语言的编译器，整个开发过程，用抽象语法树AbstractSyntaxTree,AST作为程序的一种中间表示，所以首先就要学会建立相对应源代码的AST和访问AST...

python抽象语法树_Python AST –抽象语法树

python抽象语法树 AbstractSyntaxTreeisaverystrongfeaturesinPython.PythonASTmoduleallowsustointeractwithPyt...

从零写一个编译器（九）：语义分析之构造抽象语法树(AST)

项目的完整代码在C2jCompiler 前言在上一篇完成了符号表的构建，下一步就是输出抽象语法树AbstractSyntaxTree，AST 抽象语法树（abstractsyntaxtree或者缩写...

抽象语法树 c语言,一个简单的例子看懂抽象语法树的魔力

在计算机科学中，抽象语法树AbstractSyntaxTree，AST，或简称语法树Syntaxtree，是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代...

python 抽象语法树_抽象语法树(Abstract Syntax Tree)

一般来说，程序中的一段源代码在执行之前会经历下面三个步骤 1分词／词法分析这个过程会将由字符组成的字符串分解成有意义的代码快，这些代码块被称为词法单元。

java抽象语法树_抽象语法树AST的全面解析（一）

Javac编译概述将.java源文件编译成.class文件，这一步大致可以分为3个过程： 1、把所有的源文件解析成语法树，输入到编译器的符号表； 2、注解处理器的注解处理过程； 3、分析语法树并生成...

编译原理生成语法树c语言,编译原理

编译原理计算机专业课程编辑锁定讨论上传视频编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成...

是否确定退出登录?

编译原理c语言的抽象语法树_为您自己的语言构建编译器：从分析树到抽象语法树...

建立自己的语言的系列

丰富我们的语言

抽象语法树元模型

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

测试映射

考虑职位

结论

全部评论 (0)

相关文章推荐

编译原理c语言的抽象语法树_为您自己的语言构建编译器：从分析树到抽象语法树...

抽象语法树 c语言,关于c ++ 11：C ++中的抽象语法树表示

AST抽象语法树对构建JS编译器的启发

java抽象语法树_抽象语法树（AST）

python抽象语法树_Python AST –抽象语法树

从零写一个编译器（九）：语义分析之构造抽象语法树(AST)

抽象语法树 c语言,一个简单的例子看懂抽象语法树的魔力

python 抽象语法树_抽象语法树(Abstract Syntax Tree)

java抽象语法树_抽象语法树AST的全面解析（一）

编译原理生成语法树c语言,编译原理