Статьи

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

Февраль 19, 2019

Итак, вы проанализировали свой код и создали для него чистый AST. Теперь пришло время проверить, имеет ли смысл то, что выразил пользователь. Мы должны выполнить валидацию, выявив семантические ошибки, чтобы общаться вместе с лексическими и синтаксическими ошибками (предоставленными анализатором).

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

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

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

Код доступен на GitHub под тегом 07_validation

Реализуйте семантические проверки

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

1
2
3
fun <T: Node> Node.specificProcess(klass: Class<T>, operation: (T) -> Unit) {
    process { if (klass.isInstance(it)) { operation(it as T) } }
}

Давайте посмотрим, как использовать конкретный процесс для:

  • найдите все VariableDeclarations и убедитесь, что они не объявляют уже объявленную переменную
  • найти все VarReferences и убедиться, что они не ссылаются на переменную, которая не была объявлена ​​или была объявлена ​​после VarReference
  • выполнить ту же проверку, выполненную на VarReferences и для назначений
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
data class Error(val message: String, val position: Point)
 
fun SandyFile.validate() : List<Error> {
    val errors = LinkedList<Error>()
 
    // check a variable is not duplicated
    val varsByName = HashMap<String, VarDeclaration>()
    this.specificProcess(VarDeclaration::class.java) {
        if (varsByName.containsKey(it.varName)) {
            errors.add(Error("A variable named '${it.varName}' has been already declared at ${varsByName[it.varName]!!.position!!.start}",
                    it.position!!.start))
        } else {
            varsByName[it.varName] = it
        }
    }
 
    // check a variable is not referred before being declared
    this.specificProcess(VarReference::class.java) {
        if (!varsByName.containsKey(it.varName)) {
            errors.add(Error("There is no variable named '${it.varName}'", it.position!!.start))
        } else if (it.isBefore(varsByName[it.varName]!!)) {
            errors.add(Error("You cannot refer to variable '${it.varName}' before its declaration", it.position!!.start))
        }
    }
    this.specificProcess(Assignment::class.java) {
        if (!varsByName.containsKey(it.varName)) {
            errors.add(Error("There is no variable named '${it.varName}'", it.position!!.start))
        } else if (it.isBefore(varsByName[it.varName]!!)) {
            errors.add(Error("You cannot refer to variable '${it.varName}' before its declaration", it.position!!.start))
        }
    }
 
    return errors
}

Итак, вызов validate для корня AST вернет все возможные семантические ошибки.

Получение всех ошибок: лексических, синтаксических и семантических

Сначала нам нужно вызвать анализатор ANTLR и получить:

  • дерево разбора
  • список лексических и синтаксических ошибок
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
data class AntlrParsingResult(val root : SandyFileContext?, val errors: List<Error>) {
    fun isCorrect() = errors.isEmpty() && root != null
}
 
fun String.toStream(charset: Charset = Charsets.UTF_8) = ByteArrayInputStream(toByteArray(charset))
 
object SandyAntlrParserFacade {
 
    fun parse(code: String) : AntlrParsingResult = parse(code.toStream())
 
    fun parse(file: File) : AntlrParsingResult = parse(FileInputStream(file))
 
    fun parse(inputStream: InputStream) : AntlrParsingResult {
        val lexicalAndSyntaticErrors = LinkedList<Error>()
        val errorListener = object : ANTLRErrorListener {
            override fun reportAmbiguity(p0: Parser?, p1: DFA?, p2: Int, p3: Int, p4: Boolean, p5: BitSet?, p6: ATNConfigSet?) {
                // Ignored for now
            }
 
            override fun reportAttemptingFullContext(p0: Parser?, p1: DFA?, p2: Int, p3: Int, p4: BitSet?, p5: ATNConfigSet?) {
                // Ignored for now
            }
 
            override fun syntaxError(recognizer: Recognizer<*, *>?, offendingSymbol: Any?, line: Int, charPositionInline: Int, msg: String, ex: RecognitionException?) {
                lexicalAndSyntaticErrors.add(Error(msg, Point(line, charPositionInline)))
            }
 
            override fun reportContextSensitivity(p0: Parser?, p1: DFA?, p2: Int, p3: Int, p4: Int, p5: ATNConfigSet?) {
                // Ignored for now
            }
        }
 
        val lexer = SandyLexer(ANTLRInputStream(inputStream))
        lexer.removeErrorListeners()
        lexer.addErrorListener(errorListener)
        val parser = SandyParser(CommonTokenStream(lexer))
        parser.removeErrorListeners()
        parser.addErrorListener(errorListener)
        val antlrRoot = parser.sandyFile()
        return AntlrParsingResult(antlrRoot, lexicalAndSyntaticErrors)
    }
 
}

Затем мы сопоставляем дерево разбора с AST и выполняем семантическую проверку. Наконец мы возвращаем AST и все ошибки вместе.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
data class ParsingResult(val root : SandyFile?, val errors: List<Error>) {
    fun isCorrect() = errors.isEmpty() && root != null
}
 
object SandyParserFacade {
 
    fun parse(code: String) : ParsingResult = parse(code.toStream())
 
    fun parse(file: File) : ParsingResult = parse(FileInputStream(file))
 
    fun parse(inputStream: InputStream) : ParsingResult {
        val antlrParsingResult = SandyAntlrParserFacade.parse(inputStream)
        val lexicalAnsSyntaticErrors = antlrParsingResult.errors
        val antlrRoot = antlrParsingResult.root
        val astRoot = antlrRoot?.toAst(considerPosition = true)
        val semanticErrors = astRoot?.validate() ?: emptyList()
        return ParsingResult(astRoot, lexicalAnsSyntaticErrors + semanticErrors)
    }
 
}

В остальной части системы мы просто вызовем SandyParserFacade без необходимости прямого вызова синтаксического анализатора ANTLR.

Проверка теста

Будет ли это летать? Давайте проверим это.

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
class ValidationTest {
 
    @test fun duplicateVar() {
        val errors = SandyParserFacade.parse("""var a = 1
                                               |var a =2""".trimMargin("|")).errors
        assertEquals(listOf(Error("A variable named 'a' has been already declared at Line 1, Column 0", Point(2,0))), errors)
    }
 
    @test fun unexistingVarReference() {
        val errors = SandyParserFacade.parse("var a = b + 2").errors
        assertEquals(listOf(Error("There is no variable named 'b'", Point(1,8))), errors)
    }
 
    @test fun varReferenceBeforeDeclaration() {
        val errors = SandyParserFacade.parse("""var a = b + 2
                                               |var b = 2""".trimMargin("|")).errors
        assertEquals(listOf(Error("You cannot refer to variable 'b' before its declaration", Point(1,8))), errors)
    }
 
    @test fun unexistingVarAssignment() {
        val errors = SandyParserFacade.parse("a = 3").errors
        assertEquals(listOf(Error("There is no variable named 'a'", Point(1,0))), errors)
    }
 
    @test fun varAssignmentBeforeDeclaration() {
        val errors = SandyParserFacade.parse("""a = 1
                                               |var a =2""".trimMargin("|")).errors
        assertEquals(listOf(Error("You cannot refer to variable 'a' before its declaration", Point(1,0))), errors)
 
    }

Выводы

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

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