Архив Тега для: token

Это первая статья из цикла “Разра­ба­тываем свой язык програм­ми­ро­вания на Java”, который на примере разра­ботки простого языка, покажет полный путь создания языка, а также написания и поддержки инстру­ментов для него. К концу данной статьи реализуем интер­пре­татор, с помощью которого можно будет выполнять программы на нашем языке.

Любой язык програм­ми­ро­вания имеет синтаксис, который необходимо преоб­ра­зовать в удобную для валидации, преоб­ра­зо­вания и испол­нения структуру данных. Как правило, такой струк­турой данных выступает абстрактное синтак­си­ческое дерево (abstract syntax tree, AST). Каждый узел дерева обозначает конструкцию, встре­ча­ю­щуюся в исходном коде. Исходный код разби­рается парсером и на выходе получается AST.

Языки разра­ба­ты­ваются давно, и поэтому на текущий момент мы имеем довольно много зрелых инстру­ментов, в том числе генераторы парсеров. Генераторы парсеров на вход принимают описание грамматики конкретного языка, а на выходе получаем парсеры, интер­пре­таторы и компиляторы.

В данной статье рассмотрим инструмент ANTLR. ANTLR – утилита, на вход которой подается грамматика в виде РБНФ, а на выходе получаем интерфейсы/классы (в нашем случае это java-код) для разбора программ. Список языков, на которых генери­руются парсеры, можно найти здесь.

Пример грамматики

Перед тем как перейти к реальной грамматике, попробуем на словах описать некоторые правила типичного языка программирования:

• ПЕРЕМЕННАЯ – это ИДЕНТИФИКАТОР
• ЦИФРА – это один из символов 0 1 2 3 4 5 6 7 8 9
• ЧИСЛО – это один или более элементов типа ЦИФРА
• ВЫРАЖЕНИЕ – это ЧИСЛО
• ВЫРАЖЕНИЕ – это ПЕРЕМЕННАЯ
• ВЫРАЖЕНИЕ – это ВЫРАЖЕНИЕ ‘+’ ВЫРАЖЕНИЕ
• ВЫРАЖЕНИЕ – это ‘(‘ ВЫРАЖЕНИЕ ’)’

Как видно из данного списка, языковая грамматика – это набор правил, которые могут иметь рекур­сивные связи. Каждое правило может ссылаться на себя или на любое другое правило. ANTLR в своем арсенале имеет множество опера­торов для описания таких правил.

: метка начала правила
; метка конца правила
| оператор альтернативы
.. оператор диапазона
~ отрицание
. любой символ
= присваивание
(...) подправило
(...)* повторение подправила 0 или более раз
(...)+ Повторение подправила 1 или более раз
(...)? подправило, может отсутствовать
{...} семантические действия (на языке, использующемся в качестве выходного – например, Java)
[...] параметры правила

Примеры правил на ANTLR

Следующий пример описывает правила для целых чисел и чисел с плавающей точкой:

NUMBER : [0-9]+ ;
FLOAT  : NUMBER '.' NUMBER ;

Очень важно понимать, что грамматика описывает только синтаксис языка, на основе которого будет генери­ро­ваться парсер. Парсер будет генери­ровать AST, используя который, можно будет реали­зовать семантику языка. В преды­дущем примере, мы задали правило для разбора целого числа, но не описали какой объем памяти занимает число (8 бит, 16, …), является ли число со знаком или без. Например, в некоторых языках програм­ми­ро­вания переменную можно начать исполь­зовать, не объявив ее. Также можно не объявлять тип переменной, в этом случае тип будет определен автома­ти­чески в рантайме. Все эти правила семантики языка не описы­ваются в грамматике, а реали­зуются в другой части языка.

Лексемы и выражения ANTLR

Грамматика ANTLR состоит из двух типов правил: лексем и выражений, которые исполь­зуются для опреде­ления структуры грамматики и разбора входных данных.

Лексемы (или токены) – это правила, которые определяют отдельные лекси­ческие элементы входного языка, такие как числа, иденти­фи­каторы, знаки операций и т.д. Каждой лексеме соответ­ствует опреде­ленный тип токена, который исполь­зуется для дальнейшей обработки синтак­си­ческим анали­за­тором. Лекси­ческий анали­затор сканирует входной текст, разбивает его на лексемы и создает после­до­ва­тель­ность токенов, которые затем передаются синтак­си­че­скому анали­затору. Записы­ваются в верхнем регистре (Например: NUMBER, IDENTIFIER).

Выражения – это правила, которые определяют структуру грамматики входного языка. Они описывают, каким образом лексемы связаны между собой и как они могут быть объединены в более сложные конструкции. Выражения могут содержать ссылки на лексемы, а также на другие выражения. Записы­ваются в нотации сamelCase (Например: expression, functionDefinition).

Таким образом, разница между лексемами и выраже­ниями в ANTLR заклю­чается в том, что лексемы определяют отдельные лекси­ческие элементы входного языка и преоб­разуют их в токены, а выражения определяют структуру грамматики и описывают, каким образом лексемы связаны между собой в более сложные конструкции.

Требо­вания к языку

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

• Переменные (типов String, Long, Double);
• Оператор присва­и­вания (=);
• Арифме­ти­ческие операции (+, -, *, /);
• Операторы сравнения (>, <, >=, <=, ==, !=);
• Условные операторы (if, else);
• Функции;
• Печать в консоль (встро­енный оператор println).

Грамматика

Ну и наконец, полное описание грамматики для языка:

grammar Jimple;

// корневое правило грамматики
program: (statement)* EOF;

// список возможных утверждений
statement: variableDeclaration
         | assignment
         | functionDefinition
         | functionCall
         | println
         | return
         | ifStatement
         | blockStatement
         ;

// список возможных выражений
expression: '(' expression ')'                                      #parenthesisExpr
          | left=expression op=(ASTERISK | SLASH) right=expression  #mulDivExpr
          | left=expression op=(PLUS | MINUS) right=expression      #plusMinusExpr
          | left=expression compOperator right=expression           #compExpr
          | IDENTIFIER                                              #idExp
          | NUMBER                                                  #numExpr
          | DOUBLE_NUMBER                                           #doubleExpr
          | STRING_LITERAL                                          #stringExpr
          | functionCall                                            #funcCallExpr
          ;

// описания отдельных выражений и утверждений
variableDeclaration: 'var' IDENTIFIER '=' expression ;

assignment: IDENTIFIER '=' expression ;

compOperator: op=(LESS | LESS_OR_EQUAL | EQUAL | NOT_EQUAL | GREATER | GREATER_OR_EQUAL) ;

println: 'println' expression ;

return: 'return' expression ;

blockStatement: '{' (statement)* '}' ;

functionCall: IDENTIFIER '(' (expression (',' expression)*)? ')' ;

functionDefinition: 'fun' name=IDENTIFIER '(' (IDENTIFIER (',' IDENTIFIER)*)? ')' '{' (statement)* '}' ;

ifStatement: 'if' '(' expression ')' statement  elseStatement? ;

elseStatement: 'else' statement ;

// список токенов
IDENTIFIER          : [a-zA-Z_] [a-zA-Z_0-9]* ;
NUMBER              : [0-9]+ ;
DOUBLE_NUMBER       : NUMBER '.' NUMBER ;
STRING_LITERAL      : '"' (~["])* '"' ;

ASTERISK            : '*' ;
SLASH               : '/' ;
PLUS                : '+' ;
MINUS               : '-' ;

ASSIGN              : '=' ;
EQUAL               : '==' ;
NOT_EQUAL           : '!=' ;
LESS                : '<' ;
LESS_OR_EQUAL       : '<=' ;
GREATER             : '>' ;
GREATER_OR_EQUAL    : '>=' ;

SPACE               : [ \r\n\t]+ -> skip;
LINE_COMMENT        : '//' ~[\n\r]* -> skip;

Как вы уже, наверное, догадались, наш язык называется Jimple (проис­ходит от Jvm Simple). Пожалуй, стоит объяснить некоторые моменты, которые могут быть неоче­видными при первом знакомстве с ANTLR.

Метки

При описании правил некоторых операций была исполь­зована метка op. Это позволяет нам в дальнейшем исполь­зовать эту метку в качестве имени переменной, которая будет содержать значение оператора. В принципе, можно было бы обойтись без указания меток, но в таком случае придется писать допол­ни­тельный код, чтобы достать значение оператора из дерева разбора.

compOperator: op=(LESS | LESS_OR_EQUAL | EQUAL | NOT_EQUAL | GREATER | GREATER_OR_EQUAL) ;

Имено­ванные альтер­нативы правил

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

expression: '(' expression ')'  #parenthesisExpr
          | IDENTIFIER          #idExp
          | NUMBER              #numExpr

ANTLR сгене­рирует следующий код:

public interface JimpleVisitor<T> {
    T visitParenthesisExpr(ParenthesisExprContext ctx);

    T visitIdExp(IdExpContext ctx);

    T visitNumExpr(NumExprContext ctx);
}

Каналы

В ANTLR существует такая конструкция как канал (channel). Обычно каналы исполь­зуются для работы с коммен­та­риями, но так как в большинстве случаев нам не нужно проверять наличие коммен­тариев их необходимо отбросить с помощью -> skip, чем мы и восполь­зо­вались. Однако, бывают случаи, когда нам нужно интер­пре­ти­ровать значение коммен­тариев или других конструкций, тогда вы исполь­зуете каналы. В ANTLR уже есть встро­енный канал под названием HIDDEN, который вы можете исполь­зовать, или объявить свои каналы для опреде­ленных целей. Далее при разборе кода можно будет получить доступ к этим каналам.

Пример объяв­ления и исполь­зо­вания канала

channels { MYLINECOMMENT }

LINE_COMMENT : '//' ~[rn]+ -> channel(MYLINECOMMENT) ;

Фрагменты

На ряду с токенами (лексемами) в ANTLR присут­ствует такое понятие как фрагменты (fragment). Правила с префиксом фрагмента могут быть вызваны только из других правил лексера. Они не являются токенами сами по себе. В следующем примере мы вынесли во фрагменты опреде­ления чисел для разных систем счисления.

NUMBER: DIGITS | OCTAL_DIGITS | HEX_DIGITS;
fragment DIGITS: '1'..'9' '0'..'9'*;
fragment OCTAL_DIGITS: '0' '0'..'7'+;
fragment HEX_DIGITS: '0x' ('0'..'9' | 'a'..'f' | 'A'..'F')+;

Таким образом, число в любой системе счисления (например: «123», «0762» или «0xac1») будет рассмат­ри­ваться как токен NUMBER, а не DIGITS, OCTAL_DIGITS или HEX_DIGITS. В Jimple фрагменты не используются.

Инстру­менты

Перед тем как приступить к генерации парсера, нам нужно настроить инстру­менты для работы с ANTLR. Как известно, хороший и удобный инструмент — это половина успеха. Для этого нам понадо­бится скачать ANTLR библиотеку и написать скрипты для его запуска. Существуют также maven/gradle/IntelliJ IDEA плагины, которые мы не будем исполь­зовать в этой статье, но для продук­тивной разра­ботки они могут быть полезны.

Нам понадо­бятся следующие скрипты:

Скрипт antlr4.sh

java -Xmx500M -cp ".:/usr/lib/antlr-4.12.0-complete.jar" org.antlr.v4.Tool $@

Скрипт grun.sh

java -Xmx500M -cp ".:/usr/lib/antlr-4.12.0-complete.jar" org.antlr.v4.gui.TestRig $@

Генерация парсера

Сохраните грамматику в файле Jimple.g4. Далее запустите скрипт следующим образом:

antlr4.sh Jimple.g4 -package org.jimple.lang -visitor

Параметр -package позволяет указать java package, в котором будет сгене­ри­рован код. Параметр -visitor позволяет сгене­ри­ровать интерфейс JimpleVisitor, который реализует паттерн Visitor.

После успешного выпол­нения скрипта в текущей дирек­тории появятся несколько файлов: JimpleParser.java, JimpleLexer.java, JimpleListener.java, JimpleVisitor.java. Первые два файла содержат сгене­ри­ро­ванный код парсера и лексера соответ­ственно. Остальные два файла содержат интер­фейсы для работы с деревом разбора. В этой статье мы будем исполь­зовать интерфейс JimpleVisitor, а точнее JimpleBaseVisitor — это также сгене­ри­ро­ванный класс, который реализует интерфейс JimpleVisitor и содержит реали­зации всех методов. Это позволяет переопре­делить только те методы, которые нам нужны.

Реали­зация интерпретатора

Наконец-то мы добрались до самого интересного — реали­зации интер­пре­татора. Хотя в данной статье не будем затра­гивать вопрос проверки кода на ошибки, но ошибки интер­пре­тации все-таки будут реали­зованы. Для начала, создадим класс JimpleInterpreter с методом eval, на вход которого будет подаваться строка с кодом на Jimple. Далее нам нужно разобрать исходный код на токены с помощью JimpleLexer, затем создать дерево AST, используя JimpleParser.

public class JimpleInterpreter {
    public Object eval(final String input) {
        // разбираем исходный код на токены
        final JimpleLexer lexer = new JimpleLexer(CharStreams.fromString(input));
        // создаем дерево AST
        final JimpleParser parser = new JimpleParser(new CommonTokenStream(lexer));
        // создаем объект класса JimpleInterpreterVisitor
        final JimpleInterpreterVisitor interpreterVisitor = new JimpleInterpreterVisitor(new JimpleContextImpl(stdout));
        // запускаем интерпретатор
        return interpreterVisitor.visitProgram(parser.program());
    }
}

У нас есть синтак­си­ческое дерево. Давайте добавим семантики с помощью написанного нами класса JimpleInterpreterVisitor, который будет обходить AST, вызывая соответ­ствующие методы. Так как корневым правилом нашей грамматики является правило program (см. выше program: (statement)* EOF), то обход дерева начинается именно с него. Для этого вызываем реали­зо­ванный по умолчанию метод visitProgram у объекта JimpleInterpreterVisitor, на вход которого даем объект класса ProgramContext. Реали­зация ANTLR состоит из вызова метода visitChildren(RuleNode node), который обходит все дочерние элементы заданного узла дерева, вызывая для каждого из них метод visit.

// код сгенерирован ANTLR
public class JimpleBaseVisitor<T> extends AbstractParseTreeVisitor<T> implements JimpleVisitor<T> {
    @Override public T visitProgram(JimpleParser.ProgramContext ctx) {
        return visitChildren(ctx);
    }

    // другие методы опущены для краткости
}

Как можно заметить, JimpleBaseVisitor — это generic-класс, для которого нужно определить тип обработки каждого узла. В нашем случае это класс Object, так как выражения могут возвращать значения разного типа. Обычно выражение (expression) должно вернуть какое-либо значение, а утвер­ждение (statement) ничего не возвращает. В этом и заклю­чается их различие. В случае утвер­ждения можем возвращать null. Однако, чтобы случайно не столк­нуться с NullPointerException, вместо null будем возвращать объект типа Object, который глобально определен в классе JimpleInterpreter:

public static final Object VOID = new Object();

Класс JimpleInterpreterVisitor расширяет класс JimpleBaseVisitor, переопре­деляя только интере­сующие нас методы. Рассмотрим реали­зацию встро­енного оператора println, который в грамматике описан как println: 'println' expression ;. Первое, что нужно сделать — это вычислить выражение expression, для этого нам нужно вызвать метод visit и передать в него объект expression из текущего контекста PrintlnContext. В методе visitPrintln нас совер­шенно не интересует, как вычис­ляется выражение, за вычис­ление каждого правила (контекста) отвечает соответ­ствующий метод. Например, для вычис­ления строкового литерала исполь­зуется метод visitStringExpr.

public class JimpleInterpreterVisitor extends JimpleBaseVisitor<Object> {
    @Override
    public Object visitPrintln(final JimpleParser.PrintlnContext ctx) {
        final Object result = visit(ctx.expression());
        System.out.println(result);
        return null;
    }

    @Override
    public Object visitStringExpr(final JimpleParser.StringExprContext ctx) {
        // возвращаем строковый литерал
        return cleanStringLiteral(ctx.STRING_LITERAL().getText());
    }

    private String cleanStringLiteral(final String literal) {
        // очистить строку от кавычек
        return literal.length() > 1 ? literal.substring(1, literal.length() - 1) : literal;
    }

    // другие методы опущены для краткости
}

Реали­зовав только лишь эти методы, интер­пре­татор уже поддер­живает println и строковые литералы, что позволяет нам выполнить код println "Hello, Jimple!".

Запуск интер­пре­татора

Для запуска интер­пре­татора нужно создать стандартный метод main, который после небольших проверок, используя класс JimpleInterpreter, будет запускать наш код:

public class MainApp {
    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("usage: jimple input.jimple");
            System.exit(1);
        }

        Path path = Paths.get(args[0]);
        if (!Files.exists(path)) {
            System.err.println("File not found: " + path);
            System.exit(1);
        }

        new JimpleInterpreter().eval(path);
    }
}

Детали реали­зации

Приводить весь код реали­зации интер­пре­татора нет необхо­ди­мости, ссылку на исходники можно будет найти в конце статьи. Однако хочу остано­виться на некоторых интересных деталях.

Как уже было упомянуто, интер­пре­татор построен на основе паттерна Visitor, который посещает узлы дерева AST и выполняет соответ­ствующие инструкции. В процессе выпол­нения кода в текущем контексте появляются новые иденти­фи­каторы (имена переменных и/или функций), которые нужно где-то хранить. Для этого напишем класс JimpleContext, который будет хранить не только эти иденти­фи­каторы, но и текущий контекст выпол­нения вложенных блоков кода и функций, так как локальная переменная и/или параметр функции должны быть удалены после выхода из области их видимости.

@Override
public Object handleFunc(FunctionSignature func, List<String> parameters, List<Object> arguments, FunctionDefinitionContext ctx) {
    Map<String, Object> variables = new HashMap<>(parameters.size());
    for (int i = 0; i < parameters.size(); i++) {
    variables.put(parameters.get(i), arguments.get(i));
    }
    // создаем новую область видимости параметров функции и помещаем ее в стек
    context.pushCallScope(variables);

    // выполнение выражений функций опущены для краткости

    // удаляем область видимости параметров функции из стека
    context.popCallScope();

    return functionResult;
}

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

Зачем нужно два прохода?

Перво­на­чальная версия интер­пре­татора заклю­чалась в реали­зации метода для каждого правила. Например, если метод обработки объяв­ления функции находит функцию с таким именем (и количе­ством параметров) в текущем контексте, то выбра­сы­вается исклю­чение, иначе функция добав­ляется в текущий контекст. Таким же образом работает метод вызова функции. Если функция не найдена, то выбра­сы­вается исклю­чение, иначе функция вызывается. Такой подход работает, но он не позволяет вызывать функцию до её опреде­ления. Например, следующий код не будет работать:

var result = 9 + 10

println "Result is " + add(result, 34)

fun add(a, b) {
return a + b
}

В данном случае, у нас есть два подхода. Первый — это требовать определять функции до её исполь­зо­вания (не очень удобно для пользо­ва­телей языка). Второй — выполнять два прохода. Первый проход нужен для того, чтобы найти все функции, которые были определены в коде. А второй — непосред­ственно для выпол­нения кода. В своей реали­зации выбрал второй подход. Следует перенести реали­зацию метода visitFunctionDefinition в отдельный класс, который расширяет уже известный нам сгене­ри­ро­ванный класс JimpleBaseVisitor<T>.

// класс находит все функции в коде и регистрирует их в контексте
public class FunctionDefinitionVisitor extends JimpleBaseVisitor<Object> {
    private final JimpleContext context;
    private final FunctionCallHandler handler;

    public FunctionDefinitionVisitor(final JimpleContext context, final FunctionCallHandler handler) {
        this.context = context;
        this.handler = handler;
    }

    @Override
    public Object visitFunctionDefinition(final JimpleParser.FunctionDefinitionContext ctx) {
        final String name = ctx.name.getText();
        final List<String> parameters = ctx.IDENTIFIER().stream().skip(1).map(ParseTree::getText).toList();
        final var funcSig = new FunctionSignature(name, parameters.size());
        context.registerFunction(funcSig, (func, args) -> handler.handleFunc(func, parameters, args, ctx));
        return VOID;
    }
}

Теперь у нас есть класс, который можем исполь­зовать перед непосред­ственным запуском класса интер­пре­татора. Он будет наполнять наш контекст опреде­ле­ниями всех функций, которые будем вызывать в классе интерпретатора.

Как выглядит AST?

Для того, чтобы визуа­ли­зи­ровать AST, нужно восполь­зо­ваться утилитой grun (см. выше). Для этого следует запустить grun с параметрами Jimple program -gui (первый параметр – имя грамматики, второй – имя правила). В результате откроется окно с деревом AST. Перед выпол­нением этой утилиты важно скомпи­ли­ровать сгене­ри­ро­ванный ANTLR-ом код.

# сгенерировать парсер
antlr4.sh Jimple.g4
# скомпилировать сгенерированный код
javac -cp ".:/usr/lib/jvm/antlr-4.12.0-complete.jar" Jimple*.java
# запустить grun
grun.sh Jimple program -gui
# ввести код: "println "Hello, Jimple!"
# нажать Ctrl+D (Linux) или Ctrl+Z (Windows)

Для Jimple-кода println "Hello, Jimple!" сгене­ри­руется следующее AST:

 

Резюме

В данной статье, вы позна­ко­мились с таким понятиями как лекси­ческий и синтак­си­ческий анали­заторы. Исполь­зовали инструмент ANTLR для генерации таких анали­за­торов. Узнали, как писать грамматику ANTLR. В итоге смогли создать простой язык, а именно разра­ботали интер­пре­татор для него. В качестве бонуса смогли визуа­ли­зи­ровать AST.

Весь исходный код интер­пре­татора можно посмотреть по ссылке.

Ссылки

• • https://www.antlr.org/
  • https://en.wikipedia.org/wiki/Abstract_syntax_tree
  • https://en.wikipedia.org/wiki/Compiler-compiler