Абстрактное синтаксическое дерево ast

Абстрактное синтаксическое дерево ast

Возьмём арифметическое выражение 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».

Источник

Abstract Syntax Tree (AST) — Explained in Plain English

As a developer, the source code that you write is all so concise and elegant. And other developers can read and understand your code with ease. However, a compiler has to do much more to make sense of your code. In this post, you’ll learn how compilers try to understand what your code does with a focus on what an Abstract Syntax Tree (AST) is, and its relevance to static analysis.

How Does the Compiler Make Sense of Your Code?

The steps involved in the compiler’s processing of source code are illustrated below: Let’s expand on this a bit.

The source code is first split into smaller chunks called tokens through the process of lexical analysis. Lexical analysis is also called tokenization.

An Abstract Syntax Tree (AST) abstracts away certain details and retains just enough information to help the compiler understand the structure of the code.

Therefore, an AST is a tree data structure that best represents the syntactic structure of the source code.

Don’t worry if things aren’t clear just yet!

Over the next few minutes, you’ll draw a relatable analogy. And understand how the compiler works very similarly to how you’d try to understand a sentence.

Lexical Analysis

In this section, you’ll learn about lexical analysis.

Suppose you’re learning a new language—not a programming language though😄. And you’re given the task of inferring the meaning of a sentence in that language.

As a first step, you’ll try identifying the nouns, verbs, or more generally, words that matter. Lexical analysis is very similar to this step.

• Given the source code, the compiler tries to first identify the different types of tokens that your code is composed of.
• A token could be any valid entity in the programming language—a literal that takes a fixed value, a variable, an operator, or a function call.

As lexical analysis breaks down the source code into tokens, it is also called tokenization.

Syntactic Analysis

So far, you’ve learned that tokenization leaves you with tokens or entities—just the way you’d identify entities in a sentence.

Let’s go back to the analogy again.

After you’ve identified the nouns and verbs in the sentence, how’ll you go about inferring its meaning?

Well, you’ll now try to parse the relationship between the nouns, verbs and the like—to see how they fit together—how they conform to the language’s grammar.

This leads to the step of syntax analysis or parsing.

And to perform syntactic analysis, there’s a parser that processes these tokens and parses them into a tree called the Abstract Syntax Tree (AST).

More on AST Representation

The different entities and their relationships are often language-specific. For example, the syntactic structure of a sentence in German may be very different from its syntactic structure in Hindi.

Similarly, there’s no one common AST representation and the actual AST structure may depend on the specific language.

In general, the AST models the relationship between tokens in the source code as a tree comprising of nodes and the nodes containing children. And each node contains information about the type of token, and related data.

For example, if your node represents a function call , the arguments and the return values will be the associated data.

Let’s draw the AST corresponding to the following equation:

In the above AST representation, the nodes + and — are operators, z is a variable, and 1 and 2 are just literals. Notice how the parentheses are discarded in the AST; they’re subsumed in the representation of (z — 1) : z and 1 are both children of the — operator node. Want to explore more on ASTs? The AST Explorer helps in visualizing ASTs in several popular languages such as Go, Python, Java, and JavaScript. Here’s a simple example in Python:

Here, the type of node is VariableDeclaration as we declare the variable my_str .

Relevance of AST in Development

So where do AST show up in the development process? In most languages, parsers that give you the AST will also give you the methods to traverse an AST. This would enable you to visit different nodes of the AST to understand the functionality of each node, and additionally perform analysis.

• define rules,
• traverse the parse tree by visiting each node, and
• check for violation of rules.

And this is where ASTs are relevant in static code analysis.

Static code analysis involves parsing of the source code into an intermediary representation—on which you can run analysis—without actually running the code. The intermediary representation is often the AST.

This analysis then returns potential security issues, bugs, and performance issues in your code, which you can fix almost immediately. For more information on static analysis, consider reading the following post.

Static Code Analysis — A Beginner’s Guide

Bala Priya C ・ Dec 6 ’21

Conclusion

In this tutorial, you’ve learned:

• how lexical and syntactic analyses work,
  • lexical analysis: identifies the tokens in the source code, and
  • syntactic analysis: parses the relationship between these tokens to see how they fit together.

  Thank you for reading. Hope you found this post helpful!

  Источник