Статьи

Создание компилятора для вашего собственного языка: от дерева разбора до абстрактного синтаксического дерева

Октябрь 20, 2018

В этом посте мы увидим, как обрабатывают и преобразуют информацию, полученную от парсера. Синтаксический анализатор ANTLR распознает элементы, присутствующие в исходном коде, и создает дерево анализа . Из дерева разбора мы получим Абстрактное синтаксическое дерево, которое мы будем использовать для проверки и создания скомпилированного кода.

Обратите внимание, что терминология может варьироваться: многие называют дерево, полученное из ANTLR, абстрактным синтаксическим деревом. Я предпочитаю отмечать разницу от этих двух шагов. Для меня дерево синтаксического анализа — это информация, значимая для синтаксического анализатора, абстрактное синтаксическое дерево — это информация, реорганизованная для лучшей поддержки следующих шагов.

Серия по созданию собственного языка

Предыдущие сообщения:

  1. Построение лексера
  2. Сборка парсера
  3. Создание редактора с подсветкой синтаксиса
  4. Создайте редактор с автозаполнением

Код доступен на GitHub под тегом 05_ ast

Приправить наш язык

В этой серии статей мы работали над очень простым языком выражений. Пришло время сделать наш язык немного более сложным, введя:

  • например, 10 : как десятичное или (1 * 2,45) как Int
  • печать заявления   например: печать (3 + 11)

Для этого нам нужно пересмотреть нашу грамматику лексера и синтаксического анализатора. Подсветка синтаксиса и автозаполнение, которые мы встроили в предыдущие посты, будут продолжать работать.

Новая грамматика лексера:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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_]* ;

И новый синтаксический анализатор:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 для содержания узлов.

Там будет несколько ключевых отличий:

  • он будет иметь более простой и приятный API, чем классы, сгенерированные ANTLR (поэтому классы, составляющие дерево разбора). В следующих разделах мы увидим, как этот API может позволить выполнять преобразования в AST
  • мы удалим элементы, которые имеют смысл только при разборе, но которые логически бесполезны: например, выражение в скобках или узел строки
  • некоторые узлы, для которых у нас есть отдельные экземпляры в дереве разбора, могут соответствовать одному экземпляру в AST. Это случай ссылок на типы Int и Decimal, которые в AST определяются с помощью одноэлементных объектов.
  • мы можем определить общие интерфейсы для связанных типов узлов, таких как BinaryExpression
  • чтобы определить, как анализировать объявление переменной, мы повторно используем правило присваивания. В AST две концепции полностью разделены
  • некоторые операции имеют одинаковый тип узла в дереве разбора, но разделены в AST. Это случай различных типов бинарных выражений

Давайте посмотрим, как мы можем определить нашу метамодель AST, используя Kotlin.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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

Начнем с определения узла . Узел представляет каждый возможный узел AST, и он является общим. Это может быть повторно использовано и для других языков. Все остальное вместо этого специфично для языка (Сэнди в нашем случае). На нашем конкретном языке нам нужны три важных интерфейса:

  • утверждение
  • выражение
  • Тип

Каждый из этих интерфейсов расширяет узел .

Затем мы объявляем два типа, которые мы используем в нашем языке. Они определены как одноэлементные объекты. Это означает, что у нас есть только один экземпляр этих классов.

Затем у нас есть интерфейс BinaryExpression , который расширяет Expression . Для классов реализует его, по одному для каждого из основных арифметических выражений.

Большинство выражений имеют в качестве дочерних узлов другие узлы. У некоторых есть вместо этого простые значения. Это VarReference (у которого есть свойство varName типа String ), а также Intlit и DecLit (оба имеют значение свойства типа String ).

Наконец, у нас есть три класса, реализующие Statement .

Обратите внимание, что мы используем классы данных, чтобы мы могли бесплатно использовать методы hashCode, equals и toString. Котлин порождает для нас также конструкторов и добытчиков. Попробуйте представить, сколько кода будет в Java.

Отображение дерева разбора на абстрактное синтаксическое дерево

Давайте посмотрим, как мы можем получить дерево разбора, созданное ANTLR, и отобразить его в наши классы AST.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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, который мы получаем для определенного фрагмента кода, именно тем, который мы ожидаем.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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, но мы не хотим, чтобы нас заставляли это делать. Таким образом, в зависимости от операций, которые нам нужно сделать, мы можем игнорировать или нет позиции. Рассмотрим тесты, которые мы написали до сих пор: не будет ли громоздким и раздражающим указание ложных позиций для всех узлов? Я так думаю.

Это новое определение узла и несколько вспомогательных классов:

1
2
3
4
5
6
7
8
9
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 :

1
data class SandyFile(val statements : List<Statement>, override val position: Position? = null) : Node

Отображение стало немного сложнее:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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)
}

На этом этапе все предыдущие тесты продолжают проходить, но мы хотим добавить тест, чтобы убедиться, что позиция определена правильно:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@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, что имеет смысл.

Ссылка: Создание компилятора для вашего собственного языка: от дерева разбора до абстрактного синтаксического дерева от нашего партнера по JCG
57
Share: