Лекция Г2. Абстрактное синтаксическое дерево (AST)

Лекция Г2. Абстрактное синтаксическое дерево (AST) сад и огород
ast деревья

Ast деревья

Начните с примера.

Получим 1 + арифметическое выражение (2 * 3).

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

AST

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

‘Объясните фразу’. абстрактное синтаксическое дерево » по частям.

‘Дерево’ — см. форму.

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

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

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

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

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

'Мама вымыла рамы'. 

AST Natural

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

Обвинение (т. е. глагол) находится в узле. Вышеупомянутые (в математике называемые «операторами», в «активной» лингвистике: объекты и субъекты) удаляются из листьев.

AST vs parse tree

Важно не путать « абстрактное синтаксическое дерево » и « дерево Дерево анализа («дерево разбора»).

На самом деле, разница есть. дерево Анализ является «конкретным». Это означает, что в него включены все вспомогательные лингвистические средства.

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

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

'ripper' code = "1 + (2 * 3)" pp ripper. sexp (code) is required 

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

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

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

Дерево анализа Ripper

1 + специальное для Ruby выражение (2 * 3) в дереве анализа.

Нас интересует вот что. В дереве анализа отражен тот факт, что (2 * 3) было в скобках (узел: Paren).

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

Логика выглядит следующим образом. Введены детали лингвистических средств записи в дерево . Значит, это не « абстрактное » дерево . Следовательно, это не АСТ, а дерево анализа.

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

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

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

Или в виде структуры языка программирования, например

["Мыло", ["Мама", "Раму"]]. 

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

AST и парсинг

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

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

Давайте рассмотрим пример. Выполните следующий синтаксис.

:: = '(' ')' :: = |Q :: = число ',' |Number: = строка 

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

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

Рассмотрим множественную строку (2. 5). Дерево анализа, соответствующее этой буквенно-цифровой строке, выглядит следующим образом

Вызовите функцию дерева анализа

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

Итак, дерево Дерево анализа наглядно показывает, какие правила выхода применяются, а также порядок и терминалы, в которых были определены порядок и терминалы исходной строки.

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

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

Я хочу получить AST. Например:

Вызовите функцию AST < pan>. Например, рассмотрим следующую грамматику (упрощенный оператор присваивания).

Абстрактное синтаксическое дерево ‘Умножить (2. 5)’ из буквенно-цифровых символов выбранной структуры.

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

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

Чтобы преобразовать дерево анализа в заранее запланированный вариант AST, необходимо выполнить ряд стандартных функций.

  • Переименовать некоторые узлы,
  • Удалить узел ‘service’,
  • Свернуть сторонников, сгенерированных линейным списком/массивом ретроспектив.

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

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

Затем вы можете добавить код (в скобках) к этому правилу следующим образом

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

Оцените статью