АБСТРАКТНОЕ СИНТАКСИЧЕСКОЕ ДЕРЕВО ОПРЕДЕЛЕНИЕ ПРИМЕР ПОСТРОЕНИЯ

Время на прочтение

Все мы знаем о том, что JavaScript-код веб-проектов может разрастаться до прямо-таки огромных размеров. А чем больше размер кода — тем дольше браузер будет его загружать. Но проблема тут не только во времени передачи данных по сети. После того, как программа загрузится, её ещё надо распарсить, скомпилировать в байт-код, и, наконец, выполнить. Сегодня мы представляем вашему вниманию перевод 14 части серии материалов об экосистеме JavaScript. А именно, речь пойдёт о синтаксическом анализе JS-кода, о том, как строятся абстрактные синтаксические деревья, и о том, как программист может повлиять на эти процессы, добившись повышения скорости работы своих приложений.

Как устроены языки программирования

Прежде чем говорить об абстрактных синтаксических деревьях, остановимся на том, как устроены языки программирования. Вне зависимости от того, какой именно язык вы используете, вам всегда приходится применять некие программы, которые принимают исходный код и преобразуют его в нечто такое, что содержит конкретные команды для машин. В роли таких программ выступают либо интерпретаторы, либо компиляторы. Неважно, пишете ли вы на интерпретируемом языке (JavaScript, Python, Ruby), или на компилируемом (C#, Java, Rust), ваш код, представляющий собой обычный текст, всегда будет проходить этап парсинга, то есть — превращения обычного текста в структуру данных, которая называется абстрактным синтаксическим деревом (Abstract Syntax Tree, AST).

Абстрактные синтаксические деревья не только дают структурированное представление исходного кода, они, кроме того, играют важнейшую роль в семантическом анализе, в ходе которого компилятор проверяет правильность программных конструкций и корректность использования их элементов. После формирования AST и выполнения проверок эта структура используется для генерирования байт-кода или машинного кода.

Применение абстрактных синтаксических деревьев

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

Предположим, вы хотите разработать инструмент, который находит в коде часто встречающиеся структуры. Отчёты такого инструмента помогут в рефакторинге, позволят уменьшить дублирование кода. Сделать это можно, пользуясь обычным сравнением строк, но такой подход окажется весьма примитивным, возможности его будут ограниченными. На самом деле, если вы хотите создать подобный инструмент, вам не нужно писать собственный парсер для JavaScript. Существует множество опенсорсных реализаций подобных программ, которые полностью совместимы со спецификацией ECMAScript. Например — Esprima и Acorn. Существуют и инструменты, которые могут помочь в работе с тем, что генерируют парсеры, а именно, в работе с абстрактными синтаксическими деревьями.

Абстрактные синтаксические деревья, кроме того, широко используются при разработке транспиляторов. Предположим, вы решили разработать транспилятор, преобразующий код на Python в код на JavaScript. Подобный проект может быть основан на идее, в соответствии с которой используется транспилятор для создания абстрактного синтаксического дерева на основе Python-кода, которое, в свою очередь, преобразуется в код на JavaScript. Вероятно, тут вы зададитесь вопросом о том, как такое возможно. Всё дело в том, что абстрактные синтаксические деревья — это всего лишь альтернативный способ представления кода на некоем языке программирования. Прежде чем код преобразуется в AST, он выглядит как обычный текст, при написании которого следуют определённым правилам, которые формируют язык. После парсинга этот код превращается в древовидную структуру, которая содержит ту же информацию, что и исходный текст программы. В результате можно осуществить не только переход от исходного кода к AST, но и обратное преобразование, превратив абстрактное синтаксическое дерево в текстовое представление кода программы.

Поговорим о том, как строятся абстрактные синтаксические деревья. В качестве примера рассмотрим простую JavaScript-функцию:

Парсер создаст абстрактное синтаксическое дерево, которое схематично представлено на следующем рисунке.

Обратите внимание на то, что это — упрощённое представление результатов работы парсера. Настоящее абстрактное синтаксическое дерево выглядит гораздо сложнее. В данном случае наша главная цель — получить представление о том, во что, в первую очередь, превращается исходный код прежде чем он будет выполнен. Если вам интересно взглянуть на то, как выглядит реальное абстрактное синтаксическое дерево — воспользуйтесь сайтом AST Explorer. Для того, чтобы сгенерировать AST для некоего фрагмента JS-кода, его достаточно поместить в соответствующее поле на странице.

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

Присмотритесь к этому рисунку, возможно, вы увидите там кое-что интересное.

Временные затраты на выполнение JS-кода

Видите? Если нет — посмотрите ещё раз. Собственно говоря, речь идёт о том, что, в среднем, браузеры тратят 15-20% времени на парсинг JS-кода. И это — не некие условные данные. Перед вами — статистические сведения о работе реальных веб-проектов, которые так или иначе используют JavaScript. Возможно, показатель в 15% может показаться вам не таким уж и большим, но, поверьте, это много. Типичное одностраничное приложение загружает примерно 0.4 Мб JavaScript-кода, а чтобы распарсить этот код браузеру надо примерно 370 мс. Опять же, вы можете сказать, что в этом нет ничего страшного. И да, само по себе это немного. Однако не стоит забывать о том, что это — лишь время, которое нужно на то, чтобы разобрать код и превратить его в AST. Сюда не входит время, необходимое на выполнение кода, или время, которое нужно на решение других задач, сопутствующих загрузке страницы, например — задач обработки HTML и CSS и рендеринга страницы. Причём, речь тут идёт лишь о настольных браузерах. В случае с мобильными системами всё ещё хуже. В частности, время парсинга одного и того же кода на мобильных устройствах может быть в 2-5 раз больше, чем на настольных. Взгляните на следующий рисунок.

Время парсинга 1 Мб JS-кода на различных устройствах

Здесь показано время, необходимое для разбора 1 Мб JS-кода на различных мобильных и настольных устройствах.

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

Анализ сайта с помощью инструментов разработчика в браузере

К несчастью, мобильные браузеры не обладают подобными инструментами. Однако, это не означает, что мобильные версии сайтов невозможно анализировать. Тут нам на помощь придут инструменты вроде DeviceTiming. С помощью DeviceTiming можно измерить время, необходимое для парсинга и выполнения скриптов в управляемых окружениях. Работает это благодаря помещению локальных скриптов в окружение, формируемое вспомогательным кодом, что приводит к тому, что каждый раз, когда страница загружается с различных устройств, у нас появляется возможность локально измерить время парсинга и выполнения кода.

Оптимизация парсинга и JS-движки

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

Движок V8 поддерживает потоковую передачу скриптов и кэширование кода. Под потоковой передачей в данном случае понимается то, что система занимается парсингом скриптов, загружающихся асинхронно, и скриптов, выполнение которых отложено, в отдельном потоке, начиная это делать с момента начала загрузки кода. Это ведёт к тому, что парсинг завершается практически одновременно с завершением загрузки скрипта, что даёт примерно 10% уменьшение времени, необходимого на подготовку страниц к работе.

JavaScript-код обычно компилируется в байт-код при каждом посещении страницы. Этот байт-код, однако, теряется после того, как пользователь переходит на другую страницу. Происходит это из-за того, что скомпилированный код сильно зависит от состояния и контекста системы во время компиляции. Для того чтобы улучшить ситуацию в Chrome 42 появилась поддержка кэширования байт-кода. Благодаря этому новшеству скомпилированный код хранится локально, в результате, когда пользователь возвращается на уже посещённую страницу, для подготовки её к работе не нужно выполнять загрузку, парсинг и компиляцию скриптов. Это позволяет Chrome сэкономить примерно 40% времени на задачах парсинга и компиляции. Кроме того, в случае с мобильными устройствами, это ведёт к экономии заряда их аккумуляторов.

Движок Carakan, который применялся в браузере Opera и уже довольно давно заменён на V8, мог повторно использовать результаты компиляции уже обработанных скриптов. При этом не требовалось, чтобы эти скрипты были бы подключены к одной и той же странице или даже были бы загружены с одного домена. Эта техника кэширования, на самом деле, весьма эффективна и позволяет полностью отказаться от шага компиляции. Она полагается на типичные сценарии поведения пользователей, на то, как люди работают с веб-ресурсами. А именно, когда пользователь следует определённой последовательности действий, работая с веб-приложением, загружается один и тот же код.

Интерпретатор SpiderMonkey, используемый в FireFox, не занимается кэшированием всего подряд. Он поддерживает систему мониторинга, которая подсчитывает количество вызовов определённого скрипта. На основе этих показателей определяются участки кода, которые нуждаются в оптимизации, то есть — те, на которые приходится максимальная нагрузка.

Конечно, некоторые разработчики браузеров могут решить, что кэширование их продуктам и вовсе не нужно. Так, Масей Стачовяк, ведущий разработчик браузера Safari, говорит, что Safari не занимается кэшированием скомпилированного байт-кода. Возможность кэширования рассматривалась, но она до сих пор не реализована, так как генерация кода занимает менее 2% общего времени выполнения программ.

Эти оптимизации не влияют напрямую на парсинг исходного кода на JS. В ходе их применения делается всё возможное, чтобы, в определённых случаях, полностью пропустить этот шаг. Каким бы быстрым ни был парсинг, он, всё же, занимает некоторое время, а полное отсутствие парсинга — это, пожалуй, пример идеальной оптимизации.

Сокращение времени подготовки веб-приложений к работе

Как мы выяснили выше, хорошо было бы свести необходимость в парсинге скриптов к минимуму, но совсем избавиться от него нельзя, поэтому поговорим о том, как сократить время, необходимое для подготовки веб-приложений к работе. На самом деле, для этого можно сделать очень много всего. Например, можно минимизировать объём JS-кода, входящего в приложение. Код маленького объёма, готовящий страницу к работе, можно быстрее разобрать, да и его выполнение, вероятнее всего, займёт меньше времени, чем у кода более объёмного.

Для того чтобы сократить объём кода, можно организовать загрузку на страницу только того, что ей действительно необходимо, а не некоего огромного куска кода, в который входит абсолютно всё, нужное для веб-проекта в целом. Так, например, паттерн PRPL продвигает именно такой подход к загрузке кода. В качестве альтернативного варианта можно проверить зависимости и посмотреть, есть ли в них что-то избыточное, такое, что приводит лишь к неоправданному разрастанию кодовой базы. На самом деле, тут мы затронули большую тему, достойную отдельного материала. Вернёмся к парсингу.

Итак, цель данного материала заключается в обсуждении методик, позволяющих веб-разработчику помочь парсеру быстрее делать его работу. Такие методики существуют. Современные JS-парсеры используют эвристические алгоритмы для того, чтобы определить, понадобится ли выполнить некий фрагмент кода как можно скорее, или его нужно будет выполнить позже. Основываясь на этих предсказаниях, парсер либо полностью анализирует фрагмент кода, применяя алгоритм жадного синтаксического анализа (eager parsing), либо использует ленивый алгоритм синтаксического анализа (lazy parsing). При полном анализе разбираются функции, которые нужно скомпилировать как можно скорее. В ходе этого процесса выполняется решение трёх основных задач: построение AST, создание иерархии областей видимости и поиск синтаксических ошибок. Ленивый анализ, с другой стороны, используется только для функций, которые пока не нуждаются в компиляции. Здесь не создаётся AST и не выполняется поиск ошибок. При таком подходе лишь создаётся иерархия областей видимости, что позволяет сэкономить примерно половину времени в сравнении с обработкой функций, которые нужно выполнить как можно скорее.

На самом деле, концепция это не новая. Даже устаревшие браузеры вроде IE9 поддерживают подобные подходы к оптимизации, хотя, конечно, современные системы ушли далеко вперёд.

Разберём пример, иллюстрирующий работу этих механизмов. Предположим, у нас имеется следующий JS-код:

Как и в предыдущем примере, код попадает в парсер, который выполняет его синтаксический анализ и формирует AST. В результате парсер представляет код, состоящий из следующих основных частей (на функцию foo обращать внимания не будем):

Вот как это выглядит.

Результат разбора кода примера без применения оптимизации

Поговорим о том, что здесь происходит. Парсер видит объявление функции bar, объявление функции baz, вызов функции baz и вызов функции console.log. Очевидно, разбирая этот фрагмент кода, парсер столкнётся с задачей, выполнение которой никак не отразится на результатах выполнения данной программы. Речь идёт об анализе функции bar. Почему анализ этой функции не несёт практической пользы? Всё дело в том, что функция bar, как минимум, в представленном фрагменте кода, никогда не вызывается. Этот простой пример может показаться надуманным, но во множестве реальных приложений имеется большое количество функций, которые никогда не вызываются.

В подобной ситуации, вместо того, чтобы заниматься разбором функции bar, мы можем просто сделать запись о том, что она объявлена, но нигде не используется. При этом настоящий парсинг этой функции производится тогда, когда в ней возникнет необходимость, непосредственно перед её выполнением. Естественно, при выполнении ленивого синтаксического анализа нужно обнаружить тело функции и сделать запись о её объявлении, но на этом работа заканчивается. Для такой функции не надо формировать абстрактное синтаксическое дерево, так как у системы нет сведений о том, что эту функцию планируется выполнять. Кроме того, не выделяется память из кучи, что обычно требует немалых системных ресурсов. Если в двух словах, то отказ от разбора ненужных функций ведёт к значительному повышению производительности кода.

В результате, в предыдущем примере, настоящий парсер сформирует структуру, напоминающую следующую схему.

Результат разбора кода примера с оптимизацией

Обратите внимание на то, что парсер сделал запись об объявлении функции bar, но дальнейшим её разбором не занимался. Система не предприняла никаких усилий для анализа кода функции. В данном случае тело функции представляло собой команду возврата результата простых вычислений. Однако в большинстве реальных приложений код функций может быть гораздо более длинным и сложным, содержащим множество команд возврата, условия, циклы, команды объявления переменных и вложенных функций. Разбор всего этого, при условии, что такие функции никогда не вызываются, представляет собой пустую трату времени.

В вышеописанной концепции нет ничего сложного, но её практическая реализация — задача не из лёгких. Здесь мы рассмотрели очень простой пример, а, на самом деле, при принятии решения о том, будет ли некий фрагмент кода востребован в программе, нужно анализировать и функции, и циклы, и условные операторы, и объекты. В целом можно сказать, что парсеру нужно обработать и проанализировать абсолютно всё, что есть в программе.

Вот, например, весьма распространённый паттерн реализации модулей в JavaScript:

Большинство современных JS-парсеров распознают этот паттерн, он для них является сигналом того, что код, расположенный внутри модуля, нужно полностью проанализировать.

А что если бы парсеры всегда использовали ленивый синтаксический анализ? Это, к сожалению, не самая хорошая идея. Дело в том, что при таком подходе, если некий код надо выполнить как можно скорее, мы столкнёмся с замедлением работы системы. Парсер выполнит один проход ленивого синтаксического анализа, после чего тут же примется за полный анализ того, что нужно выполнить как можно скорее. Это приведёт к примерно 50% замедлению в сравнении с подходом, когда парсер сразу приступает к полному разбору самого важного кода.

Оптимизация кода с учётом особенностей его разбора

Теперь, когда мы немного разобрались с тем, что происходит в недрах парсеров, пришло время подумать о том, что можно сделать для того, чтобы им помочь. Мы можем писать код так, чтобы синтаксический анализ функций производился в нужное нам время. Тут существует один паттерн, который понимают большинство парсеров. Он выражается в том, что функции заключают в скобки. Такая конструкция практически всегда сообщает парсеру о том, что функцию надо разобрать безотлагательно. Если парсер обнаруживает открывающую скобку, сразу после которой следует объявление функции, он немедленно приступит к синтаксическому анализу функции. Мы можем помочь парсеру, применяя этот приём при описании функций, которые нужно выполнить как можно скорее.

Предположим, у нас имеется функция foo:

Так как в этом фрагменте кода нет явного указания на то, что эту функцию планируется выполнить немедленно, браузер выполнит лишь её ленивый синтаксический анализ. Однако мы уверены в том, что эта функция понадобится нам очень скоро, поэтому мы можем прибегнуть к следующему приёму.

Для начала сохраним функцию в переменной:

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

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

Подобные оптимизации может оказаться непросто выполнять вручную, так как для этого нужно знать то, в каких случаях парсер будет выполнять ленивый синтаксический анализ, а в каких — полный. Кроме того, для этого нужно потратить время на принятие решения о том, нуждается ли конкретная функция в как можно более быстрой готовности к работе или нет.

Программистам, наверняка, не захочется взваливать на себя всю эту дополнительную работу. Кроме того, что не мене важно чем всё то, о чём уже было сказано, код, обработанный таким образом, будет сложнее читать и понимать. В этой ситуации нам на помощь готовы прийти специальные программные пакеты вроде Optimize.js. Их основная цель заключается в оптимизации времени первоначальной загрузки исходного кода на JS. Они выполняют статический анализ кода и модифицируют его так, чтобы функции, которые нужно выполнить как можно скорее, были бы заключены в скобки, что приводит к тому, что браузер немедленно займётся их разбором и подготовкой к выполнению.

Итак, предположим, что мы программируем, ни о чём особо не задумываясь, и у нас имеется следующий фрагмент кода:

Выглядит это вполне нормально, работает так как ожидается, выполняется быстро, так как парсер находит открывающую скобку перед ключевым словом function. Пока всё отлично. Конечно, прежде чем всё это попадёт в продакшн, код надо минифицировать для того, чтобы уменьшить его размер:

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

Минификатор убрал скобки, в которые было заключено объявление функции, поместив в начало строки восклицательный знак. Это означает, что парсер данную строчку пропустит, то, что она будет обработана с использованием ленивого синтаксического анализа. Более того, для того, чтобы выполнить эту функцию, системе придётся выполнять полный анализ сразу после ленивого. Всё это приведёт к тому, что такой вот минифицированный код будет работать медленнее, чем его исходный вариант. Теперь пришло время вспомнить об инструментах вроде вышеупомянутого Optimize.js. Если обработать минифицированный код с помощью Optimize.js, на выходе получится следующее:

Это уже больше похоже на то, что нам нужно. Мы получаем и минификацию, и оптимизацию кода. Текст программы занимает меньше места на диске, а парсеру понятно, какие фрагменты нужно разбирать полностью и как можно скорее, а какие — используя методику ленивого синтаксического анализа.

Как видите, подготовка JS-кода к работе — дело, требующее немалых системных ресурсов. Почему бы не выполнять всё это на сервере? В конце концов, гораздо лучше один раз подготовить программу к выполнению и передавать то, что получилось, клиентам, нежели принуждать каждую клиентскую систему каждый раз обрабатывать исходный код. На самом деле, эта возможность сейчас обсуждается, в частности, вопрос заключается в том, должны ли браузерные JS-движки предлагать механизмы выполнения предварительно скомпилированных скриптов, чтобы освободить браузеры от задач по подготовке кода к выполнению. В целом, идея заключается в том, чтобы у нас был некий серверный инструмент, умеющий генерировать байт-код, который достаточно передать клиенту по сети и выполнить. Это даст значительное сокращение времени подготовки веб-страниц к работе. И хотя выглядит подобный механизм довольно соблазнительно, на самом деле, не всё так просто. Подготовка кода к работе на сервере может произвести обратный эффект, так как объём передаваемых данных, вероятно, возрастёт, может возникнуть необходимость в подписывании кода и в его проверке для целей обеспечения безопасности. Кроме того, JS-движки развиваются в уже сформировавшемся русле, в частности, команда разработчиков V8 работает над внутренними механизмами движка, направленными на то, чтобы избавиться от повторного парсинга. Подобные подходы к оптимизации на стороне клиента могут сделать предварительную компиляцию на сервере уже не столь привлекательной.

Советы по оптимизации

Вот несколько рекомендаций, которыми вы можете воспользоваться для оптимизации веб-приложений:

Автор этого материала говорит, что в его компании, которая занимается разработкой системы SessionStack, предназначенной для мониторинга и записи того, что происходит на веб-страницах, вышеописанные приёмы оптимизации начали использовать сравнительно недавно. Это позволяет им сделать так, чтобы код приложения быстрее загружался и готовился к работе. Чем быстрее это происходит — тем приятнее пользователям будет работать с системой. Пожалуй, обеспечение удобства работы пользователей — это одна из задач, которую стремятся решить разработчики любого веб-проекта, и то, о чём шла речь в этом материале, вполне способно помочь в решении этой задачи.

Уважаемые читатели! Оптимизируете ли вы ваши веб-проекты с учётом скорости загрузки и разбора их JavaScript-кода?

Определение

Начнём сразу с примера.

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

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

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

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

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

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

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

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

Мама мыла раму

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

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

AST vs parse tree

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

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

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

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

require ‘ripper’

code = «1 + (2 * 3)»
pp Ripper.sexp(code)

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

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

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

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

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

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

На AST смотри выше.

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

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

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

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

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

AST и парсинг

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

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

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

Данная грамматика соответствует строкам типа f

, 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 — буква латинского алфавита, number — число.

Данная грамматика будет соответствовать строкам типа x=5, y=21 и т. д.

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

В системах автоматической генерации парсеров подобный код даёт следующее указанию парсеру: «когда обработаешь данное правило вывода (построишь соответствующее ему parse tree), возьми первый символ (letter) и третий (number) и выполни с ними указанный код (объедини в массив из двух элементов) — это и будет AST».

Introduction

The union Constant is used to store the value of an integer or sting constant.

Associated Methods

4. Next we will form the AST for assignment statement f = 1 (in line 10).

5. Next, lets consider the statement f = n * factorial(n-1) which consists of arthimetic expressions with operands ‘-‘,’*’ and an assignment statement.

AST for f = n * factorial(n-1) is as below.

7. The AST for return statement is as folows

Абстрактное синтаксическое дерево для алгоритма Евклида, приведённого ниже:

Абстрактное синтаксическое дерево (АСД, англ. abstract syntax tree, AST) — конечное помеченное ориентированное дерево, в котором внутренние вершины сопоставлены (помечены) с операторами языка программирования, а листья — с соответствующими операндами. Таким образом, листья являются пустыми операторами и представляют только переменные и константы.

Абстрактное синтаксическое дерево отличается от дерева разбора тем, что в нём отсутствуют узлы и рёбра для тех синтаксических правил, которые не влияют на семантику программы. Классическим примером такого отсутствия являются группирующие скобки, так как в абстрактном синтаксическом дереве группировка операндов явно задаётся структурой дерева.

Для языка, который описывается контекстно-свободной грамматикой (таковыми являются почти все языки программирования) создание дерева в синтаксическом анализаторе является тривиальной задачей. Большинство правил в грамматике создают новую вершину, а символы в правиле становятся рёбрами. Правила, которые ничего не привносят в дерево (например, группирующие правила), просто заменяются в вершине одним из своих символов. Кроме того, анализатор может создать полное дерево разбора и затем пройти по нему, удаляя узлы и рёбра, которые не используются в абстрактном синтаксисе, для получения абстрактного синтаксического дерева.

Добро пожаловать в Главу 2 учебника «Создание языка программирования с LLVM». В этой главе мы увидим, как использовать лексический анализатор, созданный в Главе 1, чтобы построить полный синтаксический анализатор для нашего языка Kaleidoscope. После того, как у нас будет готов парсер, мы будем строить Abstract Syntax Tree (AST) (Абстрактное синтаксическое дерево).

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

Абстрактное синтаксическое дерево (AST)

AST отображает программу таким образом, что для более поздних стадий компилятора (например, генерации кода) она легко интерпретируется. Нам нужен один объект для каждой конструкции языка. В Kaleidoscope у нас есть выражения, прототипы и функции. Начнём с выражений:

В вышеприведённом коде показано определение базового класса ExprAST и его подкласс, который мы используем для числовых литералов.

Сейчас мы создадим только AST без различных полезных методов работы с ним. Если понадобится, то можно, например, довольно легко добавить виртуальный метод форматированного вывода кода. Вот определения узлов для других выражений AST, которые мы будем использовать в Kaleidoscope:

Всё просто: переменная содержит имя переменной, бинарный оператор содержит свой опкод (например, ‘+’) и левое и правое выражения (узлы AST), а вызовы функций содержат имя функции и список всех аргументов. Одна из замечательных вещей в AST — это то, что он охватывает языковые особенности вне зависимости от синтаксиса языка программирования. Обратите внимание, что нет никаких спорных моментов о приоритете бинарных операторов, лексической структуре и т.д.

Мы определили все узлы для выражений нашего языка. Он не является тьюринг-полным, так как не имеет условного потока управления, мы исправим это в следующей части. Следующие две вещи, которые нам необходимы — это интерфейс функций и сами функции:

В Kaleidoscope функции типизированы только количеством своих аргументов. Так как все значения — это действительные числа двойной точности, то тип каждого аргумента нет смысла нигде хранить. В реальном языке программирования класс «ExprAST», вероятно, содержал бы ещё поле с типом.

Теперь мы, наконец, можем поговорить о разборе выражений и функций в Kaleidoscope.

Основа парсера

Теперь, когда у нас есть элементы AST, нам необходимо определить синтаксический анализатор кода, чтобы его построить. Идея здесь в том, что мы хотим разобрать что-то вроде «x + y» (которое возвращается в виде трёх токенов при лексическом разборе) в AST, который может быть сгенерирован чем-то вроде этого:

ExprAST *X = new VariableExprAST(«x»);
ExprAST *Y = new VariableExprAST(«y»);
ExprAST *Result = new BinaryExprAST(‘+’, X, Y);

Прежде чем сделать это, мы определим несколько вспомогательных процедуры:

Этот код реализует простейший буфер токенов поверх лексического анализатора. Это позволяет нам смотреть вперёд на один токен, который будет возвращён лексическим анализатором. Каждая функция в нашем парсере будет считать, что CurTok является текущим токеном для разбора.

Это вспомогательные процедуры, которые наш парсер будет использовать для обработки ошибок. Исправление ошибок в нашем парсере будет далеко не лучшим и не особо удобным для пользователя, но будет достаточным в рамках этого учебника.

С этими вспомогательными функциями мы можем реализовать первую часть нашей грамматики: числовые литералы.

Парсинг выражений

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

Функция очень проста: при вызове она ожидает, что текущий токен — это tok_number. Она создает узел NumberExprAST, передавая ему значение текущего числа, перемещает лексический анализатор к следующему токену и возвращает созданный узел.

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

Эта функция иллюстрирует ряд интересных вещей о синтаксическом анализаторе:

Следующие грамматические правила — обработка ссылок на переменные и вызовов функции:

Эта функция работает так же, как и предыдущие. ( При вызове ожидает, что текущий токен — это tok_identifier). Она также использует рекурсию и обработку ошибок. Один интересный момент состоит в том, что ей приходится заглядывать вперёд, чтобы определить, является текущий идентификатор ссылкой на переменную или вызовом функции. Это проверка в зависимости от того, является ли следующий за идентификатором токен знаком ‘(‘, вызывает либо VariableExprAST, либо CallExprAST.

Теперь, когда у нас есть вся логика для разбора простейших выражений, мы можем определить вспомогательную функцию, чтобы обернуть ей в одну точку входа. Мы назовём этот класс выражения «primary» (первичным) по причинам, которые станут более ясными к концу учебника. Для разбора произвольного первичного выражения, мы должны определить, что это за выражение:

Теперь, когда мы видим определение этой функции, становится более очевидно, почему мы можем предполагать какие-либо допустимые состояния CurTok в различных функциях. При этом используется заглядывание вперёд, чтобы определить, какой вид выражения нужно проверять, а затем в соответственно вызванной функции анализируется само выражение.

Теперь, когда основные выражения могут быть обработаны, мы сможем работать с бинарными выражениями. Они гораздо сложнее.