Этот пост является частью серии о том, как создать полезный язык и все вспомогательные инструменты.
Код
Код доступен на 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 |