Статьи

Разбор любого языка в Java за 5 минут с использованием ANTLR: например, Python

Мне нравится обрабатывать код для нескольких целей, таких как статический анализ или автоматический рефакторинг. Интересная часть для меня – рассуждать о моделях, которые вы строите из Абстрактного синтаксического дерева (AST). Чтобы добраться туда, вам нужен способ получить AST из ваших исходных файлов. Это можно легко сделать с помощью ANTLR и коллекции полных грамматик, доступных здесь: https://github.com/antlr/grammars-v4

Спасибо вам всем за грамматику!

Спасибо вам всем за грамматику!

Мы просто возьмем один для Python 3, который также должен хорошо работать и для Python 2. Если нам потребуется внести незначительную корректировку, мы можем легко сделать это, начиная с этой базы.

Получение грамматики

Перво-наперво: давайте получим грамматику.

Просто посетите https://github.com/antlr/grammars-v4 и возьмите нужную вам грамматику. Большинство грамматик имеют очень разрешительную лицензию.

Существуют десятки грамматик для таких языков, как R, Scala, Python, Swift, PHP и многих других. Существует также один для Java, но для Java вы предпочитаете использовать JavaParser, я прав?

Просто скопируйте грамматику в ваш новый проект, под src / main / antlr

Настройка проекта с использованием Gradle

Теперь мы собираемся установить скрипт сборки с Gradle.

Мы будем использовать плагин ANTLR4 от melix , потому что я считаю его более гибким из описанного в официальной документации .

Мы сгенерируем код в определенном пакете ( me.tomassetti.pythonast.parser ) и, следовательно, в каталоге, производном от этого пакета (build / generate-src / me / tomassetti / pythonast / parser).

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
buildscript {
    repositories {
        maven {
            name 'JFrog OSS snapshot repo'
            url  'https://oss.jfrog.org/oss-snapshot-local/'
        }
        jcenter()
    }
  
    dependencies {
        classpath 'me.champeau.gradle:antlr4-gradle-plugin:0.1.1-SNAPSHOT'
    }
}
  
repositories {
    mavenCentral()
    jcenter()
}
  
apply plugin: 'java'
apply plugin: 'me.champeau.gradle.antlr4'
  
antlr4 {
    source = file('src/main/antlr')
    output = file('build/generated-src/me/tomassetti/pythonast/parser')
    extraArgs = ['-package', 'me.tomassetti.pythonast.parser']
}
  
compileJava.dependsOn antlr4
  
sourceSets.main.java.srcDirs += antlr4.output
  
configurations {
    compile.extendsFrom antlr4
}
  
task fatJar(type: Jar) {
    manifest {
        attributes 'Implementation-Title': 'Python-Parser',
                   'Implementation-Version': '0.0.1'
    }
    baseName = project.name + '-all'
    from { configurations.compile.collect { it.isDirectory() ? it : zipTree(it) } }
    with jar
}

Я также добавил толстую задачу. Эти задачи создают JAR, содержащий все зависимости. Я использую его для упрощения импорта парсера в Jetbrains MPS.

Чтобы сгенерировать парсер из грамматики, вы можете просто запустить gradle antlr4.

Затем вы можете объяснить своей IDE, что она должна учитывать код в build / generate-src.

Как вызвать парсер

Теперь давайте посмотрим, как мы можем вызвать парсер.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
public class ParserFacade {
  
    private static String readFile(File file, Charset encoding) throws IOException {
        byte[] encoded = Files.readAllBytes(file.toPath());
        return new String(encoded, encoding);
    }
  
    public Python3Parser.File_inputContext parse(File file) throws IOException {
        String code = readFile(file, Charset.forName("UTF-8"));
        Python3Lexer lexer = new Python3Lexer(new ANTLRInputStream(code));
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        Python3Parser parser = new Python3Parser(tokens);
        return parser.file_input();
    }
}

Наш ParserFacade имеет только один публичный метод с именем parse . Он получает файл и возвращает AST. Это вряд ли может быть проще, чем это.

Давайте посмотрим на некоторые АСТ

Давайте возьмем простой файл:

1
2
3
4
def sum(a, b):
    return a + b
  
print("The sum of %i and %i is %i" % (5, 3, sum(5, 3)))

А теперь получите АСТ. Мы можем распечатать его, используя этот код:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
public class AstPrinter {
  
    public void print(RuleContext ctx) {
        explore(ctx, 0);
    }
  
    private void explore(RuleContext ctx, int indentation) {
        String ruleName = Python3Parser.ruleNames[ctx.getRuleIndex()];
        for (int i=0;i<indentation;i++) {
            System.out.print("  ");
        }
        System.out.println(ruleName);
        for (int i=0;i<ctx.getChildCount();i++) {
            ParseTree element = ctx.getChild(i);
            if (element instanceof RuleContext) {
                explore((RuleContext)element, indentation + 1);
            }
        }
    }
     
}

Если мы проанализируем простой пример и напечатаем его с помощью AstPrinter, мы получим супер сложный AST. Первые строки выглядят так:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
file_input
  stmt
    compound_stmt
      funcdef
        parameters
          typedargslist
            tfpdef
            tfpdef
        suite
          stmt
            simple_stmt
              small_stmt
                flow_stmt
                  return_stmt
                    testlist
                      ...

Для способа синтаксического анализа он имеет множество аннулированных правил. Это имеет смысл при разборе, но это приводит к очень загрязненному AST. Я думаю, что есть два различных ASTS: как AST для синтаксического анализа, который легко создать, и логический AST, о котором легко рассуждать. К счастью, мы можем преобразовать первый в последний без особых усилий.

Один простой способ – перечислить все правила, которые являются просто обертками, и пропустить их, взяв вместо них их единственного ребенка. Мы могли бы уточнить это, но в первом приближении давайте просто пропустим узлы, у которых есть только один дочерний элемент, что является другим правилом синтаксического анализа (без терминалов).

Таким образом, мы переходим с 164 узлов на 28. В результате получается логика 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
file_input
  funcdef
    parameters
      typedargslist
        tfpdef
        tfpdef
    suite
      simple_stmt
        return_stmt
          arith_expr
            atom
            atom
  simple_stmt
    power
      atom
      trailer
        term
          string
          atom
            testlist_comp
              integer
              integer
              power
                atom
                trailer
                  arglist
                    integer
                    integer

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

Выводы

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

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

Еще одним большим преимуществом ANTLR является наличие грамматик, готовых к использованию. Строительные грамматики требуют опыта и некоторой работы. Особенно для сложных GPL, таких как Java или Python. Это также требует очень обширного тестирования. Мы все еще находим незначительные проблемы с грамматикой Java 8 за JavaParser, даже если мы проанализировали буквально сотни тысяч файлов, используя его. Это очень хорошая причина, чтобы написать свою собственную грамматику, если вы можете избежать этого.

  • Кстати, весь код доступен на github: python-ast