Статьи

Сборка и тестирование парсера с ANTLR и Kotlin

Декабрь 24, 2018

Этот пост является частью серии о том, как создать полезный язык и все вспомогательные инструменты.

  1. Построение лексера

Код

Код доступен на GitHub . Код, описанный в этом посте, связан с тегом 02_parser

Парсер

Парсер просто определяется как грамматика ANTLR. Ранее мы построили отдельный лексер. Здесь мы повторно используем эти терминалы (NEWLINE, VAR, ID и т. Д.) Для создания таких правил, как оператор, присваивание и т. Д.

Вот наша новая грамматика ANTLR:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
parser grammar SandyParser;
  
options { tokenVocab=SandyLexer; }
  
sandyFile : lines=line+ ;
  
line      : statement (NEWLINE | EOF) ;
  
statement : varDeclaration # varDeclarationStatement
          | assignment     # assignmentStatement ;
  
varDeclaration : VAR assignment ;
  
assignment : ID ASSIGN expression ;
  
expression : left=expression operator=(DIVISION|ASTERISK) right=expression # binaryOperation
           | left=expression operator=(PLUS|MINUS) right=expression        # binaryOperation
           | LPAREN expression RPAREN # parenExpression
           | ID                #varReference
           | MINUS expression  #minusExpression
           | INTLIT # intLiteral
           | DECLIT # decimalLiteral ;
  • мы повторно используем существующий лексер ( tokenVocab = SandyLexer)
  • мы начнем с определения правила, представляющего весь файл: sandyFile. Он определяется как список из одной строки списка
  • каждая строка состоит из оператора, заканчивающегося либо новой строкой, либо концом файла
  • оператор может быть varDeclaration или присваиванием
  • Выражение может быть определено разными способами. Порядок важен, потому что он определяет приоритет оператора. Таким образом, умножение предшествует сумме

Чтобы построить его, мы просто запускаем ./gradlew generateGrammarSource . Пожалуйста, обратитесь к файлу build.gradle в репозитории или посмотрите предыдущий пост серии.

тестирование

Хорошо, мы определили наш парсер, теперь нам нужно его протестировать. В общем, я думаю, что нам нужно протестировать парсер тремя способами:

  • Убедитесь, что весь код, который нам нужен для анализа, анализируется без ошибок.
  • Убедитесь, что код, содержащий ошибки, не анализируется
  • Убедитесь, что форма результирующего AST является той, которую мы ожидаем

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

Второй и третий пункты — это уточнения, над которыми я работаю, когда я уверен, что моя грамматика может распознать все.

В этом простом случае мы напишем простые тестовые случаи, чтобы охватить первый и третий пункт: мы проверим, что некоторые примеры проанализированы, и мы проверим, что произведенный AST — тот, который мы хотим.

Немного обременительно проверить, что созданный AST — это тот, который вам нужен. Есть разные способы сделать это, но в этом случае я решил сгенерировать строковое представление AST и убедиться, что оно совпадает с ожидаемым. Это косвенный способ тестирования AST, который я хочу, но он намного проще для простых случаев, подобных этому.

Вот как мы создаем строковое представление 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package me.tomassetti.sandy
  
import org.antlr.v4.runtime.ParserRuleContext
import org.antlr.v4.runtime.tree.TerminalNode
import java.util.*
  
// Each AST element is wrapped as an element
// We can dump each element to a String
abstract class ParseTreeElement {
    abstract fun multiLineString(indentation : String = ""): String
}
  
// To dump a leaf (which corresponds to a Terminal) we just write
// T[...] and inside the square brackets we write the text corresponding
// to the terminal
class ParseTreeLeaf(val text: String) : ParseTreeElement() {
    override fun toString(): String{
        return "T[$text]"
    }
  
    override fun multiLineString(indentation : String): String = "${indentation}T[$text]\n"
}
  
// For nodes things are slightly more complex:
// we need to first print the name of the node, then in the next lines
// we print the children, recursively. While printing the children
// we increase the indentation
class ParseTreeNode(val name: String) : ParseTreeElement() {
    val children = LinkedList<ParseTreeElement>()
    fun child(c : ParseTreeElement) : ParseTreeNode {
        children.add(c)
        return this
    }
  
    override fun toString(): String {
        return "Node($name) $children"
    }
  
    override fun multiLineString(indentation : String): String {
        val sb = StringBuilder()
        sb.append("${indentation}$name\n")
        children.forEach { c -> sb.append(c.multiLineString(indentation + "  ")) }
        return sb.toString()
    }
}
  
// Given an AST node we wrap all the parts as elements:
// the terminals will be Leaf elements and the non-terminals
// will be Node elements.
// Once we have wrapped those elements we can produce a string for them
fun toParseTree(node: ParserRuleContext) : ParseTreeNode {
    val res = ParseTreeNode(node.javaClass.simpleName.removeSuffix("Context"))
    node.children.forEach { c ->
        when (c) {
            is ParserRuleContext -> res.child(toParseTree(c))
            is TerminalNode -> res.child(ParseTreeLeaf(c.text))
        }
    }
    return res
}

И вот несколько тестов:

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package me.tomassetti.sandy
  
import me.tomassetti.langsandbox.SandyLexer
import me.tomassetti.langsandbox.SandyParser
import org.antlr.v4.runtime.ANTLRInputStream
import org.antlr.v4.runtime.CommonTokenStream
import java.io.*
import java.util.*
import org.junit.Test as test
import kotlin.test.*
  
class SandyParserTest {
     
    fun lexerForResource(resourceName: String) = SandyLexer(ANTLRInputStream(this.javaClass.getResourceAsStream("/${resourceName}.sandy")))
  
    fun parseResource(resourceName: String) : SandyParser.SandyFileContext = SandyParser(CommonTokenStream(lexerForResource(resourceName))).sandyFile()
  
    @test fun parseAdditionAssignment() {
        assertEquals(
"""SandyFile
  Line
    AssignmentStatement
      Assignment
        T[a]
        T[=]
        BinaryOperation
          IntLiteral
            T[1]
          T[+]
          IntLiteral
            T[2]
    T[<EOF>]
""",
                toParseTree(parseResource("addition_assignment")).multiLineString())
    }
  
    @test fun parseSimplestVarDecl() {
        assertEquals(
"""SandyFile
  Line
    VarDeclarationStatement
      VarDeclaration
        T[var]
        Assignment
          T[a]
          T[=]
          IntLiteral
            T[1]
    T[<EOF>]
""",
                toParseTree(parseResource("simplest_var_decl")).multiLineString())
    }
  
    @test fun parsePrecedenceExpressions() {
        assertEquals(
"""SandyFile
  Line
    VarDeclarationStatement
      VarDeclaration
        T[var]
        Assignment
          T[a]
          T[=]
          BinaryOperation
            BinaryOperation
              IntLiteral
                T[1]
              T[+]
              BinaryOperation
                IntLiteral
                  T[2]
                T[*]
                IntLiteral
                  T[3]
            T[-]
            IntLiteral
              T[4]
    T[<EOF>]
""",
                toParseTree(parseResource("precedence_expression")).multiLineString())
    }
  
  
}

Просто, не правда ли?

Выводы

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

В следующем посте мы увидим, как создать редактор с подсветкой синтаксиса для нашего языка.

Ссылка: Создание и тестирование синтаксического анализатора с ANTLR и Kotlin от нашего партнера по JCG
39
Share: