Построение абстрактного синтаксического дерева

3. Синтаксический анализ

Реализовать синтаксический анализ выбранного языка программирования и построение абстрактного синтаксического дерева (Abstract Syntax Tree, AST). Парсер должен распознавать все предусмотренные вашим вариантом синтаксические конструкции:

1. Вызов функций.
2. Арифметические и логические выражения с учетом приоритетов операций.
3. Условные и циклические конструкции.
4. Определение функций.
5. Дополнительно: все, что необходимо для компиляции минимального примера на целевом языке программирования: директивы препроцессора, подключение модулей, определение класса и т. д.

Документация

• Language Implementation Patterns, Terence Parr
  • Chapter 4: Building Intermediate Form Trees
  • Chapter 5: Walking and Rewriting Trees

  Порядок выполнения работы

  Выполнение работы следует разбить на две части:

  Разработка минимальной грамматики. На этом этапе вам нужно написать грамматику, достаточную для парсинга приложения «Hello, World». Этап будет достаточно объемным:

  1. Нужно будет принять множество решений: каким спроектировать AST, как тестировать парсер.
  2. Разобраться с API antlr и паттерном Visitor. Вам предстоит как реализовывать интерфейсы Visitor’а, сгенерированного antlr, так и разрабатывать свои Visitor для обхода AST.
  3. Реализовать преобразование дерева в машино- или человеко- читаемый формат (json, xml, s-expr).

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

  Пример

  Пусть на входе у компилятора приложение на языке С:

  int main()  printf("Hello World\n"); return 0; > 

  Тогда AST в различных форматах может выглядеть так.

  (program (function (int main) (call printf "Hello World\n") (return 0))) 

    name="main" return-type="int">  name="printf"> "Hello, World\n"  0   

  Ваш формат может отличаться.

  Часть 1

  Реализуйте Hello, World на целевом языке программирования и напишите грамматику, описывающую его структуру.

  Определите множество типов узлов AST. Для приведенного выше примера на языке С это могут быть:

  • Program
  • FunctionDefinition
  • Statement
    • ReturnStatement
    • FunctionCall
    • StringLiteral
    • IntegerLiteral

    Сгенерированный парсер возвращает дерево разбора. Дерево разбора (Parse Tree) представляет полную синтаксическую структуру входной программы, включая всю пунктуацию (скобки, запятые и т. д.). Для последующей обработки программы детали конкретного синтаксиса не важны, и ваша следующая задача — абстрагироваться от синтаксиса, преобразовать дерево разбора в абстрактное синтаксическое дерево.

    1. Укажите генератору ANTLR создать Visitor для обхода дерева разбора. Будут сгенерированы классы: абстрактный *Visitor и *BaseVisitor с заглушками.
    2. Реализуйте интерфейс *Visitor и для каждого метода напишите создание соответствующего узла AST. Для наших задач оптимальным выбором будет нормализованное гетерогенное или гомогенное дерево.
    3. Для реализации проходов по вашему AST создайте интерфейс AstVisitor.
    4. Реализуйте конкретный visitor-преобразователь AST в выбранный формат.
    5. По умолчанию парсер выводит ошибки в stderr . Создайте свой обработчик ошибок для сохранения их в контейнер. Для этого можно унаследоваться от BaseErrorListener.
    6. Покройте тестами как построение AST, так и негативные сценарии с возникновением синтаксических ошибок.

    Отправьте работу на проверку.

    Часть 2

    Реализуйте оставшиеся классы AST.

    Варианты проектирования AST

    От выбора структуры дерева зависит удобство реализации его обходов и способ добавления новых типов узлов.

    Более подробное описание вы найдете в книге Language Implementation Patterns.

    Гомогенное дерево (Homogeneous AST)

    Все узлы представлены единственным классом:

    public class AST  Token token; ListAST> children; public AST(Token token)  this.token = token; > public int getNodeType()  return token.type; > public void addChild(AST t)  . > > 

    1. Крайне простая реализация.
    2. Список потомков одного типа существенно облегчает реализацию обхода дерева по сравнению с денормализованной структурой.

    Недостаток: нет возможности хранить данные, специфичные для узлов. Например, если возникнет потребность хранить тип выражения, то его придется хранить для всех узлов, а не только для Expression.

    Нормализованное гетерогенное дерево (Normalized Heterogeneous AST)

    Для каждого узла создается отдельный тип, но список детей хранится единым списком:

    public abstract class ExprNode extends AST  int evalType; public int getEvalType()  return evalType; > . > 

    1. Возможность хранить специфичные для узла данные.
    2. Сохраняется простота обхода дерева за счет нормализованного списка потомков.

    Недостаток: увеличивается объем кода.

    Денормализованное гетерогенное дерево (Irregular Heterogeneous AST)

    Для каждого узла создается отдельный тип. Каждый потомок хранится в отдельном поле.

    class FunctionCall extends AST  Body body; ListExprNode> argument_list; . > 

    Преимущество: упрощается доступ к отдельным потомкам дерева. Так, вместо обращений вида children[0] и children[1] в дереве появляются именованные поля, например, body и argument_list .

    Недостаток: в каждом обходе дерева приходится реализовывать функцию для каждого типа узла.

    © Copyright 2021, Evgeny Pimenov. Ревизия 15191b02 .

    Источник

    Построение абстрактного синтаксического дерева

    Возьмём арифметическое выражение 1 + (2 * 3) .

    Абстрактным синтаксическим деревом (abstract syntax tree, AST) для него будет следующее:

    

    Абстрактное синтаксическое дерево выражения 1 + (2 * 3) .

    Объясним словосочетание «абстрактное синтаксическое дерево» по частям.

    «Синтаксическое» — значит, отражает структуру (синтаксис) исходного выражения. А именно, узлы дерева соответствуют операциям (сложению и умножению), а листья соответствуют операндам (числам). Каждый узел дерева отражает конкретную операцию исходного выражения (и наоборот).

    «Абстрактное» — дерево «очищено» от вспомогательных символов, использующихся в исходной строке (для данного примера — отсутствуют скобки).

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

    AST и естественный язык

    Несколько упрощая, абстрактным синтаксическим деревом предложения

    

    «Абстрактное синтаксическое дерево» предложения на русском языке

    Предикат (то есть глагол) стоит в узле. Его референты (в математике мы их называли «операнды», а в лингвистике «актанты»: объект и субъект) отходят от предиката листьями.

    AST vs parse tree

    Важно не путать «абстрактное синтаксическое дерево» и «дерево парсинга» (parse tree).

    Собственно, у них одно отличие: дерево парсинга «конкретно», то есть содержит все вспомогательные языковые средства.

    А абстрактное (= очищенное) синтаксическое дерево содержит то и только то, что существенно для понимания предложения (в языках программирования под «пониманием» имеется в виду вычисление/выполнение).

    Например, в языке Ruby можно получить «parse tree» с помощью следующей команды:

    require 'ripper' code = "1 + (2 * 3)" pp Ripper.sexp(code) 

    На выходе мы получим вот такой массив, являющийся префиксным выражением (S-expression):

    [:program, [[:binary, [:@int, "1", [1, 0]], :+, [:paren, [[:binary, [:@int, "2", [1, 5]], :*, [:@int, "3", [1, 9]]]]]]]] 

    В виде дерева вот как выглядит:

    

    Ruby-специфичный parse tree выражения 1 + (2 * 3) .

    Нас здесь интересует следующее: в parse tree нашёл отражение тот факт, что (2 * 3) была взята в скобки (получился узел :paren ).

    Нужна ли эта информация для вычисления выражения? Нет, не нужна, так как в дереве и так видно, что первым выполняется умножение (оно стоит на более низком уровне дерева), а следом сложение (которое использует в правой ветке результат умножения).

    Логика такая: детали языковых средств записи попали в дерево. Значит, это не «абстрактное» дерево. Значит, это не AST, а parse tree.

    Как изобразить AST

    Предложение «мама мыла раму» можно написать мелом на доске, можно печатным текстом в книге, можно ручкой в тетради. Это будет всё то же предложение.

    Точно также и AST можно изобразить в виде рисунка (как здесь), можно записать на бумаге (или в тексте) линейно как префиксное выражение, а можно сохранить на жёсткий диск в виде последовательности байтов.

    А можно в виде структуры на каком-нибудь языке программирования, например:

    Концептуальной разницы это не создаёт. Без ограничения общности мы все такие варианты будем назвывать «абстрактными синтаксическими деревьями», хотя это может быть не буквальный рисунок дерева, а массив (структура данных внутри языка разработки парсера), линейный текст, либо последовательность зарядов электронов на SSD-диске.

    AST и парсинг

    На этапе парсинга наша задача — получить из выражения (из программы) именно AST (для дальнейшей обработки и/или вычисления).

    При этом алгоритмы парсинга и средства автогенерации парсеров создают, изначально, parse tree. Получается, возникает дополнительная задача специально отметить те узлы parse tree, которые должны попасть в AST.

    Рассмотрим на примере. Пусть дана следующая грамматика:

     ::= '(' ')' ::= | ε ::= number ',' | number ::= string 

    Где string это строка, соответствующая регулярному выражению [a-z] .

    Данная грамматика соответствует строкам типа f(1) , multiply(2,5) , now() и т. п.

    Рассмотрим строку multiply(2,5) . Parse tree, соответствующее этой строке, следующее:

    

    Дерево парсинга для строки “multiply(2,5)” в заданной грамматике

    Итак, дерево парсинга (parse tree) однозначно отображает, какие правила вывода и в каком порядки были применены и каким терминалам исходной строки сопоставлены.

    В методе рекурсивного нисходящего парсинга синие узлы соответствуют вызову функции, обрабатывающей указанный нетерминал, а белые узлы — «снятию» ( shift ) символа с входной ленты. Обход дерева сверху вниз и слева направо соответствует порядку операций при данном методе парсинге.

    Возникает вопрос: нафига козе боян а зачем нам такое избыточное количество информации, все «потроха» синтаксического разбора, если мы хотим просто «понять», что видим перед собой «вызов функции со списком таких-то аргументов»?

    Мы хотим получить AST. Например, что-то вроде такого:

    

    Абстрактное синтаксическое дерево для строки “multiply(2,5)” выбранной структуры

    Отметим, что структуру AST разработчик языка выбирает исходя из соображений облегчения дальнейшего выполнения кода, «зафиксированного» в виде AST.

    Трансформация parse tree в AST

    Для преобразования parse tree в некий заранее спроектированный вариант AST требуется сделать ряд типовых операций:

    • переименовать некоторые узлы;
    • удалить «служебные» узлы;
    • свернуть порождённое рекурсией поддерево в линейный список/массив.

    Рассмотрим, для примера, следующую грамматику (упрощённый оператор присвоения):

    ::= letter » x», 5] , [«y», 21] и т. д. (В данном случае мы, говоря AST, имеем в виду в первую очередь внутреннюю структуру данных языка разработки, а не её графическое изображение.)

    Тогда мы можем добавить код (в фигурных скобках) к данному правилу в следующей манере:

    ::= letter » /programming/creating-language/p-03-racc.html»>автоматической генерации парсеров подобный код даёт следующее указанию парсеру: «когда обработаешь данное правило вывода (построишь соответствующее ему parse tree), возьми первый символ ( letter ) и третий ( number ) и выполни с ними указанный код (объедини в массив из двух элементов) — это и будет AST».

    Источник

    Читайте также:  Сейф конструктор из дерева ugears